Izpitno vprašanje RAČ2PRA 17800

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka KlaraRozina.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Drevo stanj za problem trgovskega potnika potnika - pomen vozlišč pomen ocen ...

Odgovor

Vozlišča ocenjujemo s pomočjo drevesa stanj. Vedno nadaljujemo s tistim vozliščem, kateri ima najmanjšo vrednost in seveda enako ali večjo od spodnje meje. Če na primer po eni strani razvijemo že do četrte točke in opazimo, da ima začetna povezava v neko točko manjšo vrednost, nadaljujemo tukaj.

Drevo stanj nam pomaga, da je vse skupaj veliko bolj pregledno in da takoj opazimo, katera vrednost je najmanjša, kako pridemo do nje in če ima katera povezava slučajno enako vrednost. Na koncu pa nas vedno zanima samo vrednost najcenejše krožne poti in pripadajoče drevo. Tako da vse ostale povezave odstranimo iz drevesa.

Glej tudi

Problem trgovskega potnika

Osebna orodja