Resande säljare problem
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 x 1 x 2 ..... x n där kostnad c I j anger kostnaden för att resa från stad x i till x j . Problemet med den resande säljaren är att hitta en rutt som börjar och slutar vid x 1 som 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:
kosta I j =
Turen startar från område H 1 och välj sedan det lägsta kostnadsområde som kan nås från H 1 .
Markera område H 6 eftersom det är det lägsta kostnadsområdet som kan nås från H 1 och välj sedan lägsta kostnadsområde som kan nås från H 6 .
Markera område H 7 eftersom det är det lägsta kostnadsområdet som kan nås från H 6 och välj sedan lägsta kostnadsområde som kan nås från H 7 .
Markera område H 8 eftersom det är det lägsta kostnadsområdet som kan nås från H 8 .
Markera område H 5 eftersom det är det lägsta kostnadsområdet som kan nås från H 5 .
Markera område H 2 eftersom det är det lägsta kostnadsområdet som kan nås från H 2 .
Markera område H 3 eftersom det är det lägsta kostnadsområdet som kan nås från H 3 .
Markera område H 4 och välj sedan det lägsta kostnadsområde som kan nås från H 4 det är H 1 .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.
