@filmil (uz pozdrav):
Pa nisam bas siguran da ne postoji neko "posebno bolje resenje" za sahovsku tablu... Zamisli da imas bas veliku tablu (na primer 1000x1000; za malu tablu ce ionako sve osim backtrackinga biti brzo) i da gledas kako najkrace da stignes iz donjeg levog u gornji desni ugao (na primer). Ono sto meni pada na pamet je da prvo ides "greedy" - sto brze ka cilju ("pravolinijski", ta se pogresno izrazim), a onda kad dodjes "dovoljno blizu" pocnes pametnije da biras korake.
Sve je ovo posledica postojanja simetrije - ako malo (mnogo) odemo u krajnost i skakaca zamenimo pionom (dobro, dobro, ovde je stepen simetrije mnogo veci, ali i kod konja definitivno postoji), postaje ocigledno da moze brze od Dijkstre, 99% je sigurno da slicno moze i ovde.
Ono sto meni pada na pamet je da se "prekalkulisu" najkrace putanje na, npr tabli 10x10 i da se onda do okoline 10x10 ide greedy i da se gleda kako je najbolje uci u tu 10x10 oblast... Ovo u ovom obliku lici na heuristiku, ali zbog (opet) simetrije mi se cini da se moze napraviti i algoritam koji daje optimalno resenje...
Hef fan,
Damjan
P.S. Ono sa ant-om je proslo, 10x...
I love the smell of copyright violations in the morning. Smells like... freedom!