Projekt Schiebepuzzle mit dem A*-Algorithmus lösen - Versionsgeschichte

Administrator: 6 Versionen importiert: Import

2020-10-24T10:56:55Z

6 Versionen importiert: Import

← Nächstältere Version

Version vom 24. Oktober 2020, 10:56 Uhr

itawiki>Marco Bakera: /* Auftrag */ +Bild

2015-11-30T11:53:11Z

Auftrag: +Bild

← Nächstältere Version		Version vom 30. November 2015, 11:53 Uhr
Zeile 4:		Zeile 4:

	== Auftrag ==		== Auftrag ==
			[[Datei:15-puzzle-02.jpg\|miniatur]]

	Beim Spiel „8-Puzzle“ geht es darum, von einer beliebig durcheinander gebrachten Position der		Beim Spiel „8-Puzzle“ geht es darum, von einer beliebig durcheinander gebrachten Position der
	Zahlen durch Verschieben einzelner Zahlen in das jeweils leere Feld die folgende Zielposition zu		Zahlen durch Verschieben einzelner Zahlen in das jeweils leere Feld die folgende Zielposition zu

itawiki>Marco Bakera: Abschnitt aus Links in Beschreibung verschoben.

2015-11-30T11:51:28Z

Abschnitt aus Links in Beschreibung verschoben.

← Nächstältere Version		Version vom 30. November 2015, 11:51 Uhr
Zeile 1:		Zeile 1:
	{{Projektinfo\| Aufwand=12 \| Teamgröße=1-2 \| Schwierigkeit=schwierig \| Kontakt=[[Benutzer:Bakera\|Herr Bakera]]}}		{{Projektinfo\| Aufwand=12 \| Teamgröße=1-2 \| Schwierigkeit=schwierig \| Kontakt=[[Benutzer:Bakera\|Herr Bakera]]}}

			Bei der Bearbeitung der Aufgaben helfen dir die verlinkten Unterlagen (Skript, Präsentationsfolien und Informationen) zum Thema [http://www.swisseduc.ch/informatik/theoretische_informatik/kuenstliche_intelligenz/ Künstliche Intelligenz].

	== Auftrag ==		== Auftrag ==
Zeile 46:		Zeile 48:
	# Der Quelltext ist in einer Dokumentation erläutert.		# Der Quelltext ist in einer Dokumentation erläutert.
	# Die Dokumentation enthält eine beispielhafte Ausführung eines Programms.		# Die Dokumentation enthält eine beispielhafte Ausführung eines Programms.

	== Links ==

	* [http://www.swisseduc.ch/informatik/theoretische_informatik/kuenstliche_intelligenz/ Künstliche Intelligenz] - Unterlagen als Skript, Folien und Erläuterungen.

itawiki>Marco Bakera: /* Links */

2015-11-29T19:36:46Z

Links

← Nächstältere Version		Version vom 29. November 2015, 19:36 Uhr
Zeile 49:		Zeile 49:
	== Links ==		== Links ==

	* [http://www.swisseduc.ch/informatik/theoretische_informatik/kuenstliche_intelligenz/\|Künstliche Intelligenz] - Unterlagen als Skript, Folien und Erläuterungen.		* [http://www.swisseduc.ch/informatik/theoretische_informatik/kuenstliche_intelligenz/ Künstliche Intelligenz] - Unterlagen als Skript, Folien und Erläuterungen.

itawiki>Marco Bakera: /* Meilensteine */ +Unterlagen

2015-11-29T19:36:38Z

Meilensteine: +Unterlagen

← Nächstältere Version		Version vom 29. November 2015, 19:36 Uhr
Zeile 46:		Zeile 46:
	# Der Quelltext ist in einer Dokumentation erläutert.		# Der Quelltext ist in einer Dokumentation erläutert.
	# Die Dokumentation enthält eine beispielhafte Ausführung eines Programms.		# Die Dokumentation enthält eine beispielhafte Ausführung eines Programms.

			== Links ==

			* [http://www.swisseduc.ch/informatik/theoretische_informatik/kuenstliche_intelligenz/\|Künstliche Intelligenz] - Unterlagen als Skript, Folien und Erläuterungen.

itawiki>Marco Bakera: /* Meilensteine */

2014-12-09T15:40:38Z

Meilensteine

← Nächstältere Version		Version vom 9. Dezember 2014, 15:40 Uhr
Zeile 46:		Zeile 46:
	# Der Quelltext ist in einer Dokumentation erläutert.		# Der Quelltext ist in einer Dokumentation erläutert.
	# Die Dokumentation enthält eine beispielhafte Ausführung eines Programms.		# Die Dokumentation enthält eine beispielhafte Ausführung eines Programms.
	# (optional) ???

itawiki>Marco Bakera: angelegt

2014-09-15T12:30:53Z

angelegt

Neue Seite

{{Projektinfo| Aufwand=12 | Teamgröße=1-2 | Schwierigkeit=schwierig | Kontakt=[[Benutzer:Bakera|Herr Bakera]]}}

== Auftrag ==

Beim Spiel „8-Puzzle“ geht es darum, von einer beliebig durcheinander gebrachten Position der
Zahlen durch Verschieben einzelner Zahlen in das jeweils leere Feld die folgende Zielposition zu
erreichen:
1 2 3
8 4
7 6 5

Der A*-Algorithmus kann verwendet werden, um diese Aufgabe für beliebige Ausgangsstellungen zu lösen. Im Folgenden geht es darum, diesen algorithmischen Lösungsweg nachzuvollziehen und mit Suchverfahren ohne Heuristik zu vergleichen.

===Aufgabe 1 ===

Finde mittels einer Tiefensuche den Lösungsweg zur oben beschriebenen Zielposition aus folgender Ausgangsstellung:

2 8 3
1 6 4
7 5

Vervollständige dazu den Suchbaum auf dem nächsten Blatt von links nach rechts bis der Zielknoten erreicht ist. Schreibe neben jeden Knoten die Reihenfolge, in welcher diese besucht werden (z.B. mit roter Farbe)

===Aufgabe 2 ===

Denke dir eine Heuristik aus (d.h. definiere die Funktion h(N)), um dieses Problem mit dem A*-Algorithmus zu lösen. Diese Heuristik soll ein Maß dafür sein, wie nahe am Ziel der jeweilige Knoten ist.

===Aufgabe 3===

Zeichne in den Suchbaum aus Aufgabe 1) ein, wie der A*-Algorithmus mit deiner Funktion h(N) von Aufgabe 2) den Baum absuchen würde. Beginne beim Startknoten und berechne für alle Nachfolgeknoten f(n) = g(n) + h(n). Dabei ist g(n) die Anzahl bereits zurückgelegten Kanten. Verfolge immer denjenigen Nachfolgeknoten weiter, der den kleinsten Wert von f(n) hat. Schreibe neben jeden betrachteten Knoten den Wert der Funktion f(N) (z.B. so: (1) mit grün) und die
Reihenfolge in welcher die Knoten besucht werden (z.B. <4> mit blau).

* Ist der Algorithmus schneller als ohne Heuristik?
* Wie viele Knoten müssen besucht werden?
* Vergleiche diese Zahl mit denjenigen der Breiten- bzw. Tiefensuche.

== Projektgruppen ==

Bitte tragt euch für das Projekt auf der Seite [[Projekte von Herrn Bakera]] ein.

== Meilensteine ==

# Ich habe ein Klassendiagramm erstellt, das Klassen meiner Problemlösung enthält.
# Ich habe eine Anwendung geschrieben, das einen Lösungsweg für eine Ausgangsstellung für das 8-Puzzle ausgibt.
# Ich habe mein Programm mit einem ausführlichen Test getestet.
# Der Quelltext ist in einer Dokumentation erläutert.
# Die Dokumentation enthält eine beispielhafte Ausführung eines Programms.
# (optional) ???