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 x₁x₂..... x_nhvor omkostningerne c_ijangiver omkostningerne ved at rejse fra by x_jegtil x_j. Problemet med den rejsende sælger er at finde en rute, der starter og slutter ved x₁der 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

koste_ij=

Turen starter fra område H₁og vælg derefter det minimumsomkostningsområde, der kan nås fra H₁.

Marker område H₆fordi det er det mindste omkostningsområde, der kan nås fra H₁og vælg derefter minimumsomkostningsområde, der kan nås fra H₆.

Marker område H₇fordi det er det mindste omkostningsområde, der kan nås fra H₆og vælg derefter minimumsomkostningsområde, der kan nås fra H₇.

Marker område H₈fordi det er det mindste omkostningsområde, der kan nås fra H₈.

Marker område H₅fordi det er det mindste omkostningsområde, der kan nås fra H₅.

Marker område H₂fordi det er det mindste omkostningsområde, der kan nås fra H₂.

Marker område H₃fordi det er det mindste omkostningsområde, der kan nås fra H₃.

Marker område H₄og vælg derefter det minimumsomkostningsområde, der kan nås fra H₄det er H₁.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> &#x2192; H<sub>6</sub> &#x2192; H<sub>7</sub> &#x2192; H<sub>8</sub> &#x2192; H<sub>5</sub> &#x2192; H<sub>2</sub> &#x2192; H<sub>3</sub> &#x2192; H<sub>4</sub> &#x2192; <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:

1. S er en endelig mængde.
2. 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.
3. 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) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

for enhver A ∈ S.