Problem med reisende selger
De reisende selgerproblemene følger en selger og et sett med byer. Selgeren må besøke hver og en av byene fra en bestemt by (f.eks. hjembyen) og returnere til samme by. Utfordringen med problemet er at den reisende selgeren må minimere den totale lengden på reisen.
Anta at byene er x 1 x 2 ..... x n hvor kostnad c ij angir kostnadene ved å reise fra by x Jeg til x j . Problemet med reisende selger er å finne en rute som starter og slutter på x 1 som vil ta inn alle byer med minimumskostnad.
Eksempel: En avisagent sender daglig avisen til det tildelte området på en slik måte at han må dekke alle husene i det respektive området med minimum reisekostnad. Beregn minimum reisekostnad.
Området som er tildelt agenten der han må slippe avisen, er vist på fig.
Løsning: Kostnads-tilstøtende matrisen til graf G er som følger:
koste ij =
Turen starter fra område H 1 og velg deretter minimumskostnadsområdet tilgjengelig fra H 1 .
Merk område H 6 fordi det er det minste kostnadsområdet som kan nås fra H 1 og velg deretter minimumskostnadsområde tilgjengelig fra H 6 .
Merk område H 7 fordi det er det minste kostnadsområdet som kan nås fra H 6 og velg deretter minimumskostnadsområde tilgjengelig fra H 7 .
Merk område H 8 fordi det er det minste kostnadsområdet som kan nås fra H 8 .
Merk område H 5 fordi det er det minste kostnadsområdet som kan nås fra H 5 .
Merk område H 2 fordi det er det minste kostnadsområdet som er tilgjengelig fra H 2 .
Merk område H 3 fordi det er det minste kostnadsområdet som kan nås fra H 3 .
Merk område H 4 og velg deretter minimumskostnadsområdet tilgjengelig fra H 4 det er H 1 .Så, ved å bruke den grådige strategien får vi følgende.
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>.
Minimum reisekostnad = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroider:
En matroid er et ordnet par M(S, I) som tilfredsstiller følgende betingelser:
- S er et begrenset sett.
- I er en ikke-tom familie av delmengder av S, kalt de uavhengige delmengder av S, slik at hvis B ∈ I og A ∈ I. Vi sier at I er arvelig hvis den tilfredsstiller denne egenskapen. Merk at det tomme settet ∅ nødvendigvis er et medlem av I.
- Hvis A ∈ I, B ∈ I og |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Vi sier at en matroide M (S, I) vektes hvis det er en assosiert vektfunksjon w som tildeler en strengt positiv vekt w (x) til hvert element x ∈ S. Vektfunksjonen w strekker seg til en delmengde av S ved summering :
w (A) = ∑<sub>x∈A</sub> w(x)
for enhver A ∈ S.
