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

Унапријед пуно хвала, када је Гвозден још у хибернацији :)) око ове листе
(изгледа да га је екипа од прошлог домаћег гадно исцрпјела, па сада из
тактички разлога се не јавља ;))   ) онда се морамо међусобно сналазити :))
Па ја ни не видим зашто је то што си рекао нека хеуристика, колико се сјећам
то су алгоритми који користе неке претпоставке и неке можда и емпиријске
чињенице, налазећи квази најоптималније рјешење без егзактног математичког
доказа: сјећам се неке хеуристике баш за налажење најкраћег пута, и оа је
радила нешто као налажење глобално двије најближе тачке, па онда ваљда
дијаметрално (што ми се чини болесно за израчунавање) од њих двије најближе
тачке, итд. док се све не исцрпе. Ово што си ми ти рекао ми се само чини као
неправилни покушај егзактног алгоритма који је заборавио "преко преће
наоколо краће". Шалим се. Наиме не "размишља" о томе да иако му је тај пут
наизглед краћи он мора да се ипак "дуго" враћа до слиједеће тачке. Ово није
"подје'авање" већ је такав мој став. Али ако ти сматраш да је то хеуристика
и то прихвати Гвозден онда је све ОК.

П.С. Ако имаш ту књигу да ли је могуће да ми је позајмиш (није фрка ако имаш
неки оправдани разлог :)))   ) ?

Саша

>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
>
>-----------------------------------------------------------------
>Informacije vezane za predmet Mikroprocesorski sistemi:
>   http://titan.etf.bg.ac.yu/~gvozden/mips
>-----------------------------------------------------------------
>unsubscribe:
>   minimalist@titan.etf.bg.ac.yu?subject=unsubscribe%20mips-nastava
>-----------------------------------------------------------------
>