Izpitno vprašanje RAČ2PRA 18500

Iz MaFiRaWiki

Vprašanje

Na praktičnem primeru razloži, kako poteka reševanje problema trgovskega potnika z metodo razveji in omeji.

Odgovor

Pri dani matriki ocenimo koliko bo vsaj stalo to stanje. Pri izpeljavi si pomagamo z redukcijo osnovne matrike. Da zapustimo vozlišče 1, nas bo stalo vsaj toliko kot je minimalna cena. To vrednost tudi odštejemo po celi vrstici. Enako je tudi za vsa ostala vozlišča. Z redukcijo dobimo spodnjo mejo, kar je najnižja cena povezave ali več.

Praktični primer:

http://wiki.fmf.uni-lj.si/wiki/Slika:RIO.JPG

Osebna orodja