Den resande försäljarens problem följer en säljare och en uppsättning städer. Säljaren måste besöka var och en av städerna med början från en viss (t.ex. hemstaden) och återvända till samma stad. Utmaningen med problemet är att den resande säljaren måste minimera resans totala längd.
Antag att städerna är x1x2..... xndär kostnad cI janger kostnaden för att resa från stad xitill xj. Problemet med den resande säljaren är att hitta en rutt som börjar och slutar vid x1som tar in alla städer med lägsta kostnad.
Exempel: En tidningsförmedlare lämnar dagligen tidningen till det anvisade området på ett sådant sätt att han måste täcka alla hus i respektive område med minsta resekostnad. Beräkna den lägsta resekostnaden.
Området som tilldelats agenten där han måste lämna tidningen visas i fig.
Lösning: Kostnads-angränsningsmatrisen för graf G är som följer:
kostaI j=
Turen startar från område H1och välj sedan det lägsta kostnadsområde som kan nås från H1.
Markera område H6eftersom det är det lägsta kostnadsområdet som kan nås från H1och välj sedan lägsta kostnadsområde som kan nås från H6.
Markera område H7eftersom det är det lägsta kostnadsområdet som kan nås från H6och välj sedan lägsta kostnadsområde som kan nås från H7.
Markera område H8eftersom det är det lägsta kostnadsområdet som kan nås från H8.
Markera område H5eftersom det är det lägsta kostnadsområdet som kan nås från H5.
Markera område H2eftersom det är det lägsta kostnadsområdet som kan nås från H2.
Markera område H3eftersom det är det lägsta kostnadsområdet som kan nås från H3.
Markera område H4och välj sedan det lägsta kostnadsområde som kan nås från H4det är H1.Så, med den giriga strategin får vi följande.
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>.
Minsta resekostnad = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroider:
En matroid är ett ordnat par M(S, I) som uppfyller följande villkor:
- S är en ändlig mängd.
- I är en icke-tom familj av delmängder av S, kallade oberoende delmängder av S, så att om B ∈ I och A ∈ I. Vi säger att I är ärftligt om den uppfyller denna egenskap. Observera att den tomma uppsättningen ∅ nödvändigtvis är en medlem av I.
- Om A ∈ I, B ∈ I och |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>
Vi säger att en matroid M (S, I) viktas om det finns en associerad viktfunktion w som tilldelar en strikt positiv vikt w (x) till varje element x ∈ S. Viktfunktionen w sträcker sig till en delmängd av S genom summering :
w (A) = ∑<sub>x∈A</sub> w(x)
för alla A ∈ S.