[mips-nastava:2003] - Re: jun - domaci, pitanje za Gvozdena by "Damjan S. Vujnovic" <damjan@galeb.etf.bg.ac.yu>

> 2. Sta tacno znaci heuristika u ovom zadatku; neka kvazi
> inteligencija ili se misli na cisto sporo matematicko nalazenje putanje,
> (oni algoritmi iz struktura podataka).

Misli se na neki algoritam polinomijalne vremenske slozenosti koji daje
sub-optimalno resenje. Na primer, putanju pravis tako sto krenes iz tacke
najblize koordinatnom pocetku, i odaberes najblizu tacku kao sledecu
destinaciju, pa ponovo najblizu (naravno, najblizu od onih koje nisi vec
obisao), i tako dok ne iscrpis sve tacke. Slozenost ove heuristike je
O(n^2), gde je n broj tacaka. Ako imas knjigu "Diskretna matematika", D.
Cvetkovic, mozes pogledati i jednu heuristiku vece slozenosti...

Takodje, treba obratiti paznju i na metriku koja zbog prirode problema nije
euklidska, vec je za proizvoljne tacke T1(x1, y1) i T2(x2, y2) rastojanje
definisano sa:

d(T1, T2) = max(abs(x1-x2), abs(y1-y2))

Pozdrav,
Damjan S. Vujnovic