A csillag kereses pelda

1.
Vizsgaljuk a kovetkezo feladatot az A csillag keresesre.
Az abran egy 11 mezobol allo sakktabla-reszlet lathato, melynek bal felso sarkaban, az (1,1) mezon egy huszar heleyezkedik el. A feladat a huszart a (4,1) celallapotba juttatni. Minden mezo bal felso sarkaban az adott mezo heurisztikaja van feltuntetve. A "h" heurisztikus fuggveny azt mutatja, hogy az adott mezo hany lougrasnyira van a celmezotol, illetve mennyi lepesben lehet elerni a celallapotot. 

2.
Peldaul, a (2,2) mezo heurisztikaja 1, mert a (4,1) celallapotot 1 lepesbol lehet elerni. Ugyanigy, az (1,3) mezo heurisztikaja 3, mivel a celallapotot 3 lepesbol lehet elerni.
Az A csillag algoritmus segitsegevel fejtsuk ki a keresofat es talaljuk meg a megoldast. Amennyiben több csomópontnak ugyanaz a heurisztikája, eloször a legmélyebben fekvo csomópontot kell kifejteni. 

3.
Ebben a peldaban az egyes lépések költsége a lépés fajtájától függ. Ha a huszár kettot lép balra vagy jobbra és egyet fel vagy le, a lépésköltség 1. Ha a huszár kettot lép fel vagy le és egyet jobbra vagy balra, a lépésköltség 2.

4.
A kifejtest az (1,1) gyokercsomoponttol kezdjuk, es nyilvantartunk ket listat: az eddig kifejtett csomopontokat es a kifejtesre varakozo csomopontokat, illetve a peremet. A gyokercsomopont becsult koltsege 5, amit ugy kaptunk hogy osszeadtuk az eddig megtett lepesek szamat ami 0, es a gyokertol szamitott becsult koltseget, ami 5. 

5.
A perem kifejtesevel nyerjuk a (2,3) es (3,2) csomopontokat. Ekkor az (1,1) kikerul a perembol es a kifejtett csomopontok listajara helyezzuk, a peremhez pedig hozzaadjuk a (2,3) es a (3,2) csomopontokat. Az agak mellett az adott lepes koltsege van jelolve, a perem csomopontja mellett pedig az adott csomopont becsult koltsege. 
A kifejtesre varo csomopontok kozul a (2,3)-nak kisebb a becsult koltsege, ezert ezt fejtjuk ki eloszor. 

6.
A (2,3) kovetoi az (1,1), (3,1) es a (4,2) csomopontok, ezert ezeket vesszuk fel a perembe, a (2,3) csomopont pedig atkerul a kifejtett csomopontok listajara.

7.
Most a (3,1) csomopontnak van a legkisebb becsult koltsege, ezert kovetkezonek ezt fejtjuk ki. A (3,1) a peremrol atkerul a kifejtett csomopontok listajara, a perembe pedig az (1,2) es a (2,3) csomopontokat vesszuk fel.

8.
Most tortenik meg eloszor hogy a legkisebb becsult koltseg, a 6-os tobb helyen is megjelenik. A feladat feltetele szerint a legmelyebben fekvo 6-osnak van prioritasa, ezert az (1,2)-t kell kovetkezonek kifejteni. Ezutan a perembe a (3,1) es a (3,3) csomopontokat kell felvenni. Kovetkezik a (4,2).

9.
Ezutan mar csak a (3,2)-tes csomopont maradt 6-os koltseggel, ezert ez kovetkezik.

10.
Most minden olyan csomopont melynek becsult koltsege 6 volt ki lett fejtve, a 7-es csomopontok kozul a legmelyebben a (3,3) fekszik, ezert ezt fejtjuk ki.

11.
A peremen szereplo csomopontok legkisebb becsult koltsege 7, a legmelyebben fekvo csomopont pedig eppen a (4,1) celcsomopont, ezert azt mondhatjuk hogy megtalaltuk a megoldast.

12.
A megoldasig vezeto utvonal az (1,1) gyokercsomoponttol indul, es a (2,3), (3,1), (1,2), (3,3) utan jut el a (4,1) celcsomopontba.
A hallgato feladata kivizsgalni, hogy letezik-e meg olyan ut amelyiknek ugyanekkora, tehat 7 volna a koltsege.