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 x1x2..... xnhvor kostnad cijangir kostnadene ved å reise fra by xJegtil xj. Problemet med reisende selger er å finne en rute som starter og slutter på x1som 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:
hvordan lese fra en csv-fil i java
kosteij=
Turen starter fra område H1og velg deretter minimumskostnadsområdet tilgjengelig fra H1.
Merk område H6fordi det er det minste kostnadsområdet som kan nås fra H1og velg deretter minimumskostnadsområde tilgjengelig fra H6.
Merk område H7fordi det er det minste kostnadsområdet som kan nås fra H6og velg deretter minimumskostnadsområde tilgjengelig fra H7.
Merk område H8fordi det er det minste kostnadsområdet som kan nås fra H8.
Merk område H5fordi det er det minste kostnadsområdet som kan nås fra H5.
Merk område H2fordi det er det minste kostnadsområdet som er tilgjengelig fra H2.
Merk område H3fordi det er det minste kostnadsområdet som kan nås fra H3.
Merk område H4og velg deretter minimumskostnadsområdet tilgjengelig fra H4det er H1.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.