állapottér átmérője

Kapcsolódó fogalmak: 
mélységi keresés
Kapcsolódó fogalmak: 
mélységkorlátozott
Rövid szöveges bemutatás: 
Az állapottér átmérőjének meghatározása a keresési feladatokban nagyon hasznos lehet, mert ezzel kiszűrhetjük az olyan kereséseket, amelyek indokolatlanul hosszú megoldást eredményeznek. Tegyük fel például, hogy van egy térképünk rajta 20 db várossal. A feladat az, hogy egy adott városból eljussunk egy másikba minél rövidebb úton. Könnyű végig gondolni, hogy ebben a feladatban az állapottér átmérője 19. Hiszen legrosszabb esetben az utolsó város amire lépni tudunk és még nem jártunk ott, az lesz a keresett város. De ha felfedezzük, hogy minden városból bármely másik város legfeljebb 12 lépésben elérhető, akkor ez a szám, ez az átmérő egy jobb mélységkorlátot ad, ami hatékonyabb keresést eredményez, mivel azokat a kereséseket amelyek már a 13. lépést kezdenék, azokat ki tudjuk szűrni.