Den rejsende sælger problemer overholder en sælger og en række byer. Sælgeren skal besøge hver eneste af byerne fra en bestemt by (f.eks. hjembyen) og vende tilbage til den samme by. Udfordringen ved problemet er, at den rejsende sælger skal minimere rejsens samlede længde.
Antag, at byerne er x1x2..... xnhvor omkostningerne cijangiver omkostningerne ved at rejse fra by xjegtil xj. Problemet med den rejsende sælger er at finde en rute, der starter og slutter ved x1der vil tage imod alle byer med minimumsomkostninger.
Eksempel: En avisagent afleverer dagligt avisen til det anviste område på en sådan måde, at han skal dække alle huse i det respektive område med minimum rejseomkostninger. Beregn minimum rejseomkostninger.
Det område, der er tildelt agenten, hvor han skal aflevere avisen, er vist i fig.
Løsning: Omkostnings-tilstødende matrix af graf G er som følger:
tegn til streng i java
kosteij=
Turen starter fra område H1og vælg derefter det minimumsomkostningsområde, der kan nås fra H1.
Marker område H6fordi det er det mindste omkostningsområde, der kan nås fra H1og vælg derefter minimumsomkostningsområde, der kan nås fra H6.
Marker område H7fordi det er det mindste omkostningsområde, der kan nås fra H6og vælg derefter minimumsomkostningsområde, der kan nås fra H7.
Marker område H8fordi det er det mindste omkostningsområde, der kan nås fra H8.
Marker område H5fordi det er det mindste omkostningsområde, der kan nås fra H5.
Marker område H2fordi det er det mindste omkostningsområde, der kan nås fra H2.
Marker område H3fordi det er det mindste omkostningsområde, der kan nås fra H3.
Marker område H4og vælg derefter det minimumsomkostningsområde, der kan nås fra H4det er H1.Så ved at bruge den grådige strategi 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 rejseomkostninger = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroider:
En matroid er et ordnet par M(S, I), der opfylder følgende betingelser:
- S er en endelig mængde.
- I er en ikke-tom familie af delmængder af S, kaldet de uafhængige delmængder af S, sådan at hvis B ∈ I og A ∈ I. Vi siger, at I er arvelig, hvis den opfylder denne egenskab. Bemærk, at det tomme sæt ∅ nødvendigvis er et medlem af 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 siger, at en matroide M (S, I) vægtes, hvis der er en tilknyttet vægtfunktion w, der tildeler en strengt positiv vægt w (x) til hvert element x ∈ S. Vægtfunktionen w strækker sig til en delmængde af S ved summering :
w (A) = ∑<sub>x∈A</sub> w(x)
for enhver A ∈ S.