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.
proljeće sv
Pretpostavimo da su gradovi x1x2..... xngdje trošak ci Joznačava trošak putovanja iz grada xido xj. Problem putujućeg prodavača je pronaći rutu koja počinje i završava na x1koji ć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šaki J=
Tura kreće iz područja H1a zatim odaberite područje minimalne cijene dostupno iz H1.
Označite područje H6jer je to područje s minimalnom cijenom dostupno iz H1a zatim odaberite područje minimalne cijene dostupno iz H6.
Označite područje H7jer je to područje s minimalnom cijenom dostupno iz H6a zatim odaberite područje minimalne cijene dostupno iz H7.
Označite područje H8jer je to područje s minimalnom cijenom dostupno iz H8.
Označite područje H5jer je to područje s minimalnom cijenom dostupno iz H5.
Označite područje H2jer je to područje s minimalnom cijenom dostupno iz H2.
Označite područje H3jer je to područje s minimalnom cijenom dostupno iz H3.
Označite područje H4a zatim odaberite područje minimalne cijene dostupno iz H4to je H1.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.
mojflixr