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

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

Problem trgovackog putnika je NP-kompletan problem i (za sada, a verovatno i
doveka) ne postoji polinomijalni algoritam za njegovo resavanje, te u tom
kontekstu, heuristika je brz (citaj polinomijalni) algoritam koji daje
resenje koje nije optimalno, ali je na neki nacin prihvatljivo.

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

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

Knjigu nemam :(, ali to udzbenik iz M4, sigurno mozes da nadjes na
fakultetu.

Poz,
DSV