Rejsende sælger problem
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 1 x 2 ..... x n hvor omkostningerne c ij angiver omkostningerne ved at rejse fra by x jeg til x j . Problemet med den rejsende sælger er at finde en rute, der starter og slutter ved x 1 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:
koste ij =
Turen starter fra område H 1 og vælg derefter det minimumsomkostningsområde, der kan nås fra H 1 .
Marker område H 6 fordi det er det mindste omkostningsområde, der kan nås fra H 1 og vælg derefter minimumsomkostningsområde, der kan nås fra H 6 .
Marker område H 7 fordi det er det mindste omkostningsområde, der kan nås fra H 6 og vælg derefter minimumsomkostningsområde, der kan nås fra H 7 .
Marker område H 8 fordi det er det mindste omkostningsområde, der kan nås fra H 8 .
Marker område H 5 fordi det er det mindste omkostningsområde, der kan nås fra H 5 .
Marker område H 2 fordi det er det mindste omkostningsområde, der kan nås fra H 2 .
Marker område H 3 fordi det er det mindste omkostningsområde, der kan nås fra H 3 .
Marker område H 4 og vælg derefter det minimumsomkostningsområde, der kan nås fra H 4 det er H 1 .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.
