Problem putujuće trgovačke osobe
Problemi trgovačkog putnika ovise o trgovačkom putniku i skupu gradova. Prodavač mora posjetiti svaki od gradova počevši od određenog (npr. rodnog grada) i vratiti se u isti grad. Izazov problema je u tome što trgovački putnik treba minimizirati ukupnu duljinu putovanja.
Pretpostavimo da su gradovi x 1 x 2 ..... x n gdje trošak c i J označava trošak putovanja iz grada x i do x j . Problem putujućeg prodavača je pronaći rutu koja počinje i završava na x 1 koji će obuhvatiti sve gradove uz minimalne troškove.
Primjer: Novinski agent dnevno baca novine na dodijeljeno područje na takav način da mora pokriti sve kuće u dotičnom području uz minimalne troškove putovanja. Izračunajte minimalne troškove putovanja.
Područje dodijeljeno agentu gdje mora ispustiti novine prikazano je na sl.
Rješenje: Matrica troškovne susjednosti grafa G je sljedeća:
trošak i J =
Tura kreće iz područja H 1 a zatim odaberite područje minimalne cijene dostupno iz H 1 .
Označite područje H 6 jer je to područje s minimalnom cijenom dostupno iz H 1 a zatim odaberite područje minimalne cijene dostupno iz H 6 .
Označite područje H 7 jer je to područje s minimalnom cijenom dostupno iz H 6 a zatim odaberite područje minimalne cijene dostupno iz H 7 .
Označite područje H 8 jer je to područje s minimalnom cijenom dostupno iz H 8 .
Označite područje H 5 jer je to područje s minimalnom cijenom dostupno iz H 5 .
Označite područje H 2 jer je to područje s minimalnom cijenom dostupno iz H 2 .
Označite područje H 3 jer je to područje s minimalnom cijenom dostupno iz H 3 .
Označite područje H 4 a zatim odaberite područje minimalne cijene dostupno iz H 4 to je H 1 .Dakle, korištenjem pohlepne strategije dobivamo sljedeće.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
Stoga je minimalni trošak putovanja = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroidi:
Matroid je uređeni par M(S, I) koji zadovoljava sljedeće uvjete:
- S je konačan skup.
- I je neprazna familija podskupova od S, koja se naziva nezavisnim podskupovima od S, takva da ako je B ∈ I i A ∈ I. Kažemo da je I nasljedan ako zadovoljava ovo svojstvo. Primijetimo da je prazan skup ∅ nužno član I.
- Ako je A ∈ I, B ∈ I i |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Kažemo da je matroid M (S, I) ponderiran ako postoji pridružena težinska funkcija w koja dodjeljuje striktno pozitivnu težinu w (x) svakom elementu x ∈ S. Težinska funkcija w proteže se na podskup od S zbrajanjem :
w (A) = ∑<sub>x∈A</sub> w(x)
za bilo koji A ∈ S.
