programiranje heuristika

[nemo]

potaknut ovom temom, tj. problemom kojim se taj diplomski bavi sjetio sam se jedne stvari koja me neko vrijeme muči.

znam što su heuristici i znam što su algoritmi, ali mi nekako nije baš jasno kako računala natjerati da rade sa heuristicima, tj. programirati ih heuristicima ili bolje rečeno kako napraviti algoritam za heuristik (sama stvar mi zvuči oksimoronski ).

pa ako bi netko tko je bolje upoznat sa tematikom bio toliko dobar i pojasnio mi to

_________________
Umjesto da postavlja pitanje o tome što je prije nastalo - kokoš ili jaje, čovjeku se najednom učinilo da je kokoš zamisao jajeta o stvaranju novih jaja.

[krcko]

Ne smislja racunalo heuristike, nego se algoritam zasniva na nekoj heuristici koju su izmislili ljudi (vjerojatno te to zbunilo). Heuristika je recimo 'kad se izgubis u planini, uvijek izaberi najstrmiji put'. Nije dokazano da funkcionira, al zbog Murphyjevog zakona ugodniji putevi obicno vode u krivom smjeru. Nije tesko implementirati u programu pravila poput ovih (jedan od algoritama o kojima je pricala Anamari zove se 'steepest ascent' ).

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[nemo]

[krcko]

"Izaberi najstrmiji put" nije odokativna uputa. Imas problem diskretne optimizacije s nekom funkcijom susjedstva na skupu dopustivih rjesenja. To znaci da biras ono rjesenje iz okoline trenutnog koje ce najvise povecati/smanjiti funkciju cilja.

Tek da vidis geneticke algoritme.. ideja je glumljenje evolucije. Evolucija podrazumijeva razmnozavanje, tj. seks. Zamisli kako izgleda seks medju Hamiltonovim ciklusima grafa

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[vsego]

Ja sam radio evolucijske algoritme za problem trgovackog putnika; jedno poglavlje se zove "Sprecavanje incesta" ili tako nesto.

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.

[anamari]

Za diplomski sam morala isprogramirati evolucijski/geneticki program za trgovackog putnika i napravila sam bug: natjerala sam permutacije da se incestuozno ponasaju. Dobila sam puno bolje rezultate od standardnog genetickog algoritma.

Jest da se kosi s mojim moralnim nacelima, ali...


Kao sto je Krcko i rekao, heuristiku odreduje covjek. Algoritam su smislili ljudi. Racunala kao i uvijek samo rade tocno ono sto smo im mi odredili (cak i za generiranje random broja postoji formula). Heuristicki algoritmi pokusavaju rijesiti neki problem, ali nema garancije da ce ga i rijesiti. Uvijek ce ponuditi neko rjesenje, samo to rjesenje ne mora biti najbolje moguce. A i moze biti. Mi ne znamo matematicki utemeljeno ustvrditi kakvo ce to rjesenje biti (citaj: nema teorema koji ce reci: "rjesenje ce uvijek biti blizu optimalnom" ili nesto slicno). Heuristicki algoritmi se koriste kada su algoritmi koji egzaktno rjesavaju problem prespori.

Kod problema trgovackog putnika, egzaktni algoritam bi rjesenje za problem od 100 gradova trazio milijardama godina. A heuristicki algoritam vec za koju minutu moze dati neko solidno rjesenje. Naravno je bi mi najradije najbolje rjesenje, al kako ne mozemo cekati milijarde godina, onda je nam se i neko problizno rjesenje cini ok.


Inace, za sve koji planiraju uploviti u heuristicke vode: heuristicki algoritmi su zakon! Prilikom testiranja sam se toliko puta ugodno iznenedila odlicnim rjesenjima koja su davali.

_________________

STOP nasilju medu zivotinjama!