• Razvijamo drevo stanj – kot pri sestopanju
• Drevo stanj: vozlišča drevesa opisujejo v katerih stanjih smo že bili (denimo da smo opravili zaporedje obiskov 1 – 3 – 5 )
• Dodatno: ocenjujemo “obetavnost” stanja
• Gremo v smeri najbolj obetavne veje
• Ko pridemo do rešitve, oklestimo “slabe” veje
• Pomembnost ocenjevanja, kdaj zavreči vejo

• Vse ocene morajo biti SMISELNE (dopustne) – torej ne smejo oceniti vozlišča previsoko (preko dejanske vrednosti)
• Ocena:
  a) Vzemimo kar oceno 0
  
• Je dopustna, saj je minimum krožnih poti 0 ali več
  b) Vrednost povezav v segmentu, ki ga opisuje vozlišče
  
• Je dopustna, saj vse krožne poti s tem segmentom stanejo vsaj toliko kot ta segment, torej tudi minimalna med njimi
  c) Naj bo ocena kar minimum
  
• Zagotovo je dopustna, saj je vsako število <= samega sebe
• Problem je v tem, ker je IZRAČUN take ocene drag (saj gre kar za rešitev problema)

• Dobra ocena

  • Vsekakor mora biti dopustna
  • Čim bližje pravim vrednostim (rešitvam)
  • Enostavno izračunljiva

• Delamo kompromis med kvaliteto ocene in tem, da jo izračunamo hitro

  • Oceno a) izračunamo zelo hitro, a je zanič
  • Oceno b) izračunamo zelo hitro, a tudi ni zelo dobra
  • Ocena c) je zelo dobra ocena (najboljša možna), a je izračun predrag

• Različni načini ocenjevanja
• V praksi se dobro obnese način, pri katerem si pomagamo s t.i. redukcijo matrike omrežja
• Redukcija nam da tudi neko smiselno oceno, koliko nas bo krožna pot vsaj stala
• Pogosto je za reševanje problemov v realnem času dovolj že ta informacija

• Vozlišče 1 moramo zapustiti - to nas bo stalo vsaj toliko, kot je minimalna cena iz 1 ven - to vrednost lahko v vsej 1 vrstici odštejemo
• Enako za vsa ostala vozlišča

• V vozlišče 1 moramo priti - to nas bo stalo vsaj toliko, kot je minimalna cena vhoda v 1 - to vrednost lahko v 1 stolpcu odštejemo
• Enako za vsa ostala vozlišča

• Ne dobimo nujno enak rezultat – enake ocene

• Katera boljša?

  • Nobena
  • Odvisno od primera
• Obe reducirani matriki opisujeta ISTO omrežje
• V obeh vrednosti pomenijo dodatna sredstva, če krožna pot vsebuje točno TO povezavo

Po vrsticah: 68

Po stolpcih: 69

• Kaj sedaj početi s temi "redukcijami" in izračunanimi vrednostmi
• različna drevesa stanj
• različno ocenjevanje - spodnja meja

• Drevo stanj - drevo vozlišč, ki jih obiskujemo
• V vsakem vozlišču razvijemo vse možne sosede - če nismo pri koncu, ne smemo narediti cikla
• Začnemo v vozlišču 1

• Kaj pomeni, da gremo iz vozlišča 1 v vozlišče 2

  • pot nas bo stala C12 - povečamo spodnjo mejo
  • iz 1 ne smemo v nobeno drugo vozlišče Vse ostale vrednost v 1. vrstici postavimo na .
  • v 2 ne smemo priti iz nobenega drugega vozlišča. Vse ostale vrednosti v 2. stolpcu postavimo na .
• Nova redukcija - povečanje sm

redukcija

• Imamo kandidata za rešitev, ki je krožna pot s ceno 28

• Poznamo pa tudi oceno obetavnosti vozlišč

  • Koliko nas VSAJ (verjetno več!) stanejo TISTE krožne poti
• Vsa ne dovolj obetavna vozlišča lahko zavržemo!

• Običajno nimamo take “sreče”, da takoj pridemo do optimalne rešitve
• Še kak zgled

• Konstruirajmo omrežje, ki ustreza prvotnemu omrežju, le da gremo obvezno po povezavi 1 – 2.
• V matriki vrstico 1 postavimo na ∞ (iz 1 ne smemo več nikamor drugam).
• Enako 2 stolpec (v 2 ne smemo več priti!).
• Prav tako postavimo 2 – 1 na ∞, saj se iz 2 še ne smemo vrniti v 1

Krožne poti s povezavo 1 – 2
matrika omrežja: m12

• Poleg 68 (kot je vrednost vseh poti)
• Dodatno zato, da uporabimo 1 – 2: 10
• Enak razmislek kot na začetku nam omogoča, da matriko še enkrat reduciramo (če gre!)
• Tudi tu namreč velja, da iz 2, 3, 4, 5 bomo morali iti. In zato, da zapustimo 2 (v vseh tistih omrežjih, kjer gremo obvezno po povezavi 1 – 2), nas stane vsaj še 0 dodatnih sredstev. Zato, da zapustimo 5 pa vsaj še dodatni 2 enoti (ker ne moremo več iz 5 v 2!)

10 (zapustimo 3 ) + 1 (zapustimo 5)

• Osnovna sredstva: 68
• Dodatno zato, da uporabimo 1 – 2: 10
• Redukcija po vrsticah: 11
• Redukcija po stolpcih: 0
• Skupaj: 89
• Vsaka krožna pot v našem problemu, ki vsebuje povezavo 1 -2, stane torej 89 ali več!

• 1 – 3:
• 68 + 19 + redukcija (0 + 3): 90

• 1 – 4:
• 68 + 0 + redukcija (0): 68

• 1 – 5: 1
• 68 + 1+ redukcija (4 + 3): 76

• Najbolj obetavno za nadaljni razvoj je vozlišče 14
• Razvijemo
• m143: matrika, ki ustreza prvotnemo omrežju, a kjer moramo obvezno uporabiti povezavi 1 – 4 in 4 - 3

• 4 - 2: 13
• 68 + 12 + redukcija (15 + 2 / + 5): 102

• 4 - 3: 4
• 68 + 4 + redukcija (0 + 5): 77

• 4 - 5: 0
• 68 + 0 + redukcija (0): 68

• Kandidati so vsa nerazvita vozlišča: 12, 13, 15, 142, 143, 145
• Najbolj obetavno za nadaljni razvoj je vozlišče 145
• Razvijemo
• m1452: matrika, ki ustreza prvotnemo omrežju, a kjer moramo obvezno uporabiti povezave 1 – 4, 5 - 2 in 4 - 3

• 5 - 2: 0
• 68 + 0 + redukcija (15): 83

• 5 - 3: 12
• 68 + 12 + redukcija (0): 80

• 5 - 2: 0
• 76 + 0 + redukcija (7 + 2): 85

• 5 - 3: 12
• 76 + 12 + redukcija (2 + 7): 97

• 5 - 4: 0
• 76 + 0 + redukcija (0): 76

• Kandidati so vsa nerazvita vozlišča: 12, 13,142, 143, 1452, 1453, 152, 153 in 154
• Najbolj obetavno za nadaljni razvoj je vozlišče 154

• 4 - 2: 9
• 76 + 9 + redukcija (15): 100

• 4 - 3: 0
• 76 + 0 + redukcija (0): 76

• Kandidati so vsa nerazvita vozlišča: 12, 13,142, 143, 1452, 1453, 152, 153, 154, 1542 in 1543
• Najbolj obetavno za nadaljnji razvoj je vozlišče 1543

• Kandidati so vsa nerazvita vozlišča: 12, 13,142, 143, 1452, 1453, 152, 153, 154, 1542 in 1543
• Najbolj obetavno za nadaljni razvoj je vozlišče 1543

• 3 - 2: 0
• 2 – 1: 0
• Končna vrednost krožne poti: 76

• Kandidat za končno rešitev: krožna pot dolžine 76 – pomečemo proč vsa nerazvita vozlišča z oceno za krožno pot dolžine 76 ali več
• Proč smo pometali prav vsa nerazvita vozlišča
• Imamo končno rešitev!