U kom rasponu su M i N?

Pa M i N su priozvoljin ali recimo do 20.

Za table vece od 5x5 ce biti puteva kojima se obilazi cela tabla stajuci na svako polje tacno po jedanput. Za tablu velicine 8x8 broj puteva je tako veliki da se jako tesko (ili za danas nikako) ne moze ni izracunati. Mozes koristiti neki bektreking.

Možda ti ova tema da ideju:
http://www.elitesecurity.org/tema/46908

Za tablu 8x8 slucajno znam da postoji bar jedan kompletan put (sva polja iskoriscena). Znam, jer sam pravio slican zadatak za prijem kandidata u moju firmu. Sef ga ipak nije uvrstio u konkurs, pitam se zasto ;) . Elem, trebalo je minut ili dva da komp pronadje taj put (Delphi + Athlon na 1.1 MHz); i da, koristio sam rekurziju umesto backtracking-a; i, takodje je moguce promeniti velicinu table. Ali kako prebrojati sve takve puteve ZA ZIVOTA PROGRAMERA, stvarno ne znam.

Rajko

jel možeš da kažeš u kojoj to firmi radiš, želim da konkurišem.. ;)

to je problem "Knight's tour" i o njemu ima na netu texta koliko hoces... :) a postavljeno pitanje je sasvim drugi problem... ne treba uopste stati na sva polja tacno jednom... vec naci najkraci put...

a da bi znao koji je put najkraći prvo moraš naći sve moguće puteve...

Treba obratiti paznju da tabla nemora biti kvadratna, sta je sa pravougaonim tablama?

Ko kaze? Mozes da probas A* pathfinding alg. Ono sto je bitno je pravljenje funkcije koja dodaje heuristiku algoritmu. Koristi se u gotovo svim video-igrama.

A* star je malo zaguljen za problem konja u sahu. Naime on koristi heuristiku kao svoj znacajni element (koji ga u principu i ubrzava). Heuristika pri odabiru sledeceg najboljeg polja je najcesce fizicka razdaljina do ciljne tacke (najcesce se koriste dve vrste razdaljina euklidova i manhatan razdaljina) , sto je u problemu konja veoma nezahvalno jer neko polje 'A' moze fizicki biti blize ciljnom 'G', ali od 'A' do 'G' mozda treba vise poteza da se oigra nego od nekog polja 'B' do 'G' a 'B' je fizicki dalje od 'G'. To znaci da bi morao da razvijes poprilicno zaguljenu heuristiku da bi dobio bas najkraci put, e ta heuristika moze da oduzme vise procesorskog vremena nego sam algoritam trazenja puta. Ukoliko je potrebno naci tacno jedan od najkracih puteva (jer mogu postojati vise puteva do ciljne tacke sa istim brojem poteza) preporucujem Dijkstra algoritam koji se isto svodi na prolaz kroz graf. Ali ukoliko nije potrebno da put uvek bude sto posto najkraci onda zbog brzine preporucujem A*. E sad zasto se u igrama koristi A*? Odgovor: Iskljucivo zato sto su mu performanse brzina/tacnost_nadjenog_puta najbolje tj. u igrama nije potrebno da put bude uvek bas onaj najkraci nego da to dovoljno lici na najkraci put (pod najkracim putem se smatra onaj najbolji a ne bas fizicki najkraci put). Potpuno je druga stvar u nekim istrazivackim , vojnim , svemirskim programima gde je tacnost na prvom a brzina na drugom mestu (ono u fazonu kupicemo do jaja nadrndan hardver jer nam nije skup, koji ce da resi problem brzine)

A bili se to moglo rješiti BFS-om tako da pamtiš u kojem si polju bio i s kojim brojem koraka( kako
se BFS ne bi okretao u beskonačnost) i na kraju uzeš najveći broj. Mislim da za ovo ne treba baš puno vremena.

Naravno moze se resiti bilo kojim algoritmom za prolazak kroz graf (BFS , DFS , ...), ali kao sto sam rekao Dijkstra je ispala najoptimalnija. Inace postoje dva BFS algoritma Breadth Firts(100% tacan) i Best First (koji uopste ne daje najbolje puteve jer se zasniva iskljucivo na heuristici)

Ako sam dobro skontao, pitanje je bilo kako pronaci ne najkraci vec najduzi put, i to samo njegova duzina.

E vidi stvarno he he.