Algoritmus
Nyers erő avagy visszalépéses keresés
Lépkedünk a gráfon, az eddigi lépéseket egy tömbben tároljuk. Figyeljük, hogy az eddigi lépések száma nem haladta-e meg a megengedettet, továbbá azt, hogy kívánt számú lépés után nem vagyunk-e pont a célban. Bármelyik feltétel sérülésekor visszalépünk, és ha a legelső pozícióról kell visszalépni, akkor jelezzük, hogy nincs megoldás.
Egy gonosz bemenet, amin a visszalépéses keresés elvérzik
A visszalépéses kereséssel előfordulhat, hogy exponenciális sok lépés után ér csak célba.
Egy tipikus rossz "gráf": az elején kettéágazik, az első ágon van egy nagy teljes részgráf, amiben nem érhető el a cél, és a második ágon van a cél. Ekkor a "BT" (back-track, visszalépéses keresés) "az idők végezetéig" a teljes részgráfban lépked, nem kapunk kivárható időn belül eredményt.
Okos algoritmus
Fehér Gábor megoldása:
- vegyünk egy 100 hosszú boolean-tömböt, minden csúgy egy boolean
- az algoritmus álljon lépésekből, az i. lépésben a tömb tartalma
legyen a következő: azok a csúcsok legyen true-k, amikbe van i hosszú
séta (sétahossz = csomópontok száma)
- első lépésben ez csak a bejárat csúcsa
- i-ből i+1. lépés könnyen generálható az élek mentén
- ha a k. lépésben a kijárat true, akkor van séta
- kicsit több adminisztrációval megkapható maga a a séta is, egy NxN-es tömb kell visszamutató pointerekkel
Kódok
Nyers erő
Okosabban
