Quote:
Originally Posted by Redback
Adott egy 100mx100m-es térkép. Minden egyes ponthoz meg van adva a magassága. Tekintsük úgy, hogy egy négyzet 1mx1m, és egy négyzet minden pontja ugyan olyan tengerszint feletti magasságon van. Írjunk programot, amely megmondja kialakítható-e rajta egy legalább 50M^2-es tó, bal felső és jobb alsó koordinátáját adja meg a tónak. HAsználnátok-e hozzá valamilyen féle mesterséges intelligenciás algoritmust? Ha igen, melyiket? Nekem megvan a program ,viszonylag gyors is, de mesterséges intelligenciát nem hiszem hogy tartalmaz.
|
Nah így reggel józanabb fejjel megnézve, erre egyértelmüen egy backtrack-hez hasonló keresési algoritmust kell használni
brute force-al ez picit több mint 6milla összehasonlítás, ha az összes lehetőséget megnézed, egy jól megírt backtrack-el nagyságrendekkel kisebb
plusz még tovább tudod finomitani, ha a hibás eredményt kielemzi a program, és így kihagyhat pár lépést.
Lehet elkezdek holnap irogatni rá egy keresési algoritmust, nem árt majd a jövöheti vizsgámhoz
Ha esetleg nem ismered még a backtrack-et amúgy, a legjobb a 8királynő problémáján keresztül szemlélteni, hogy hogy is müködik.
->feltesszük az első királynőt az első sorba.
->feltesszük a következőt az első sorba. üti? tovább toljuk eggyel, megint üti?még1-el,ez így megy amig nem.
->feltesszük a harmadikat azzal is eljátszuk ezt. ha eljutunk addig hogy minden pontban ütés van, visszalépünk az elözö királynőhöz és tolunk rajta egyet, ha azzal is eljutunk a végéhez, még 1-et.
Az algoritmus futhat az első helyes eredményig, de megkeresheti az összes helyes eredményt. Bizonyitható, hogy minden helyes variáción végig fog menni (ezt most nem teszem meg). ahogy az is belátható,hogy ha az első királynő eléri a táblavégét és nincs helyes eredmény, akkor a feladatnak nincs megoldása. ugye az algoritmus lényege, hogy hibás eredménynél csak 1-et lép vissza és ott módosít.