A* Algorithmus < Künstl. Intelligenz < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:34 Mo 25.10.2010 | | Autor: | Anja470 |
| Aufgabe | Implementieren Sie eine Variante des Suchverfahrens "A*- Suche" als eine Klasse A_Star,
die Unterklasse der Klasse TreeSearch (s. Praktikum) ist. Für die Pfadkosten zwischen zwei
Knoten ist dabei die Anzahl der sie verbindenden Kanten zu wählen. Als Heuristik soll die
Anzahl der falsch platzierten Puzzleteile (vgl. Vorlesung zum Thema "Heur. Suchverfahren")
zum Einsatz kommen. Die Prozedur zum update der Menge open von noch zu testenden
Knoten ist dabei wie folgt zu modifizieren:
Es werden stets nur solche Nachfolger eines Knotens K zur Knotenmenge open
hinzufügt, deren Zustand state
• in keinem Knoten in open vorkommt
• bei keinem der bis zu diesem Zeitpunkt schon getesteten Knoten auftrat. |
Hallo,
ich habe ein Problem, ich weis nicht so genau wie ich den A* Algorithmus in der Klasse umsetzen kann. Ich hab schonmal angefangen die Klasse in c++ zu schreiben, aber ich weis nicht weiter.
A_Star::A_Star(char * start2, char * ziel2): baumsuche(start2, ziel2)
{
liste = new knotenwarteschlange();
suchtiefe = 30;
}
void A_Star::update(void)
{
knoten * aktivknoten = liste->aktiverknoten();
int pfadtiefe = aktivknoten->pfadtiefe + 1;
if(pfadtiefe <= suchtiefe)
{
knoten * neuerknoten;
folgezustaende zustaende = problem.succ(aktivknoten->zustand);
if (zustaende.zulaessig[0].....)
neuerknoten = new knoten;
neuerknoten->eltern = aktivknoten;
neuerknoten->aktion = 0;
for(int i = 0; i < 9; i++)neuerknoten->zustand[i] = zustaende.zustaende[0][i];
neuerknoten->pfadtiefe = pfadtiefe;
liste->neuerknoten(neuerknoten);
}
if (zustaende.zulaessig[1].....)
{
neuerknoten = new knoten;
neuerknoten->eltern = aktivknoten;
neuerknoten->aktion = 1;
for(int i = 0; i < 9; i++)neuerknoten->zustand[i] = zustaende.zustaende[1][i];
neuerknoten->pfadtiefe = pfadtiefe;
liste->neuerknoten(neuerknoten);
}
if (zustaende.zulaessig[2].....)
{
neuerknoten = new knoten;
neuerknoten->eltern = aktivknoten;
neuerknoten->aktion = 2;
for(int i = 0; i < 9; i++)neuerknoten->zustand[i] = zustaende.zustaende[2][i];
neuerknoten->pfadtiefe = pfadtiefe;
liste->neuerknoten(neuerknoten);
}
if(zustaende.zulaessig[3].....)
{
neuerknoten = new knoten;
neuerknoten->eltern = aktivknoten;
neuerknoten->aktion = 3;
for(int i = 0; i < 9; i++)neuerknoten->zustand[i] = zustaende.zustaende[3][i];
neuerknoten->pfadtiefe = pfadtiefe;
liste->neuerknoten(neuerknoten);
}
}
else
{
while(pfadtiefe > aktivknoten->pfadtiefe)
{
liste->knotenloeschen();
.....
}
}
Ich weis nur, dass bei ..... die Heuristik (der Algorithmus) verwendet werden sollte, aber wie schreibe ich das in dem Programm?
Für jede Idee wäre ich dankbar!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Do 28.10.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
