Razveji in omeji

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Razveji in omeji je metoda za iskanje rešitve problema, pri kateri hranimo možne rešitve in ocenjujemo njihovo obetavnost. Pri iskanju rešitve sproti zavržemo kandidate, ki ne morejo pripeljati do boljših rešitev kot jih že hranimo.

Metodo uporabljamo, ko:

  • imamo N stanj in vsa moramo obiskati,
  • poznamo "vrednost, ceno" prehoda iz enega stanja v drugega,
  • želimo čim ugodnjeje obiskati vsa stanja in priti na začetek.
  • Začetek ni pomemben!

Razveji in omeji je izboljšana metoda sestopanje, ki pri iskanju najboljše rešitve preveri vse možnosti. Prednost metode razveji in omeji je v tem, da ne išče po vejah možnosti, kjer ni boljših rešitev od že pridobljene.

Metodo je smiselno uporabljati takrat, ko imamo veliko število stanj. Ocena vrednosti je namreč lahko preveč potratna za majhno število stanj.

Postopek

  • Sestavimo matriko omrežja v kateri so vse možne povezave in njihove vrednosti.
  • Izvedemo postopek redukcija matrike omrežja, ki pove, koliko nas bo minimalno stala določena pot.
  • Po najbolj obetavni poti pridemo do možne rešitve (krožne poti), ki ima določeno končno vrednost.
  • Oklestimo vse poti, ki imajo kvečjemu enako vrednost ali pa slabšo.
  • Nadaljujemo na poteh, kjer je mogoče dobiti boljšo vrednost.

Primeri

Osebna orodja