Problem mit reisenden Verkäufern
Die Probleme des Handlungsreisenden bestehen aus einem Handlungsreisenden und einer Reihe von Städten. Der Verkäufer muss jede einzelne Stadt besuchen, beginnend mit einer bestimmten Stadt (z. B. der Heimatstadt) und in dieselbe Stadt zurückkehren. Die Herausforderung des Problems besteht darin, dass der Handlungsreisende die Gesamtdauer der Reise minimieren muss.
Angenommen, die Städte sind x 1 X 2 ..... X N wo kosten c ij bezeichnet die Reisekosten von der Stadt x ich zu x J . Das Problem des Handlungsreisenden besteht darin, eine Route zu finden, die bei x beginnt und endet 1 das alle Städte mit minimalen Kosten abdeckt.
Beispiel: Ein Zeitungsagent wirft die Zeitung täglich in dem zugewiesenen Gebiet ab, sodass er alle Häuser in dem betreffenden Gebiet mit minimalen Reisekosten abdecken muss. Berechnen Sie die Mindestreisekosten.
Der dem Agenten zugewiesene Bereich, in dem er die Zeitung ablegen muss, ist in Abb. dargestellt:
Lösung: Die Kosten-Adjazenzmatrix von Graph G lautet wie folgt:
kosten ij =
Die Tour beginnt im Bereich H 1 und wählen Sie dann den Bereich mit den minimalen Kosten aus, der von H aus erreichbar ist 1 .
Bereich H markieren 6 weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist 1 und wählen Sie dann den von H aus erreichbaren Mindestkostenbereich aus 6 .
Bereich H markieren 7 weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist 6 und wählen Sie dann den von H aus erreichbaren Mindestkostenbereich aus 7 .
Bereich H markieren 8 weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist 8 .
Bereich H markieren 5 weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist 5 .
Bereich H markieren 2 weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist 2 .
Bereich H markieren 3 weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist 3 .
Bereich H markieren 4 und wählen Sie dann den Bereich mit den minimalen Kosten aus, der von H aus erreichbar ist 4 es ist H 1 .Mit der Greedy-Strategie erhalten wir also Folgendes.
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>.
Somit sind die minimalen Reisekosten = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroiden:
Ein Matroid ist ein geordnetes Paar M(S, I), das die folgenden Bedingungen erfüllt:
- S ist eine endliche Menge.
- I ist eine nichtleere Familie von Teilmengen von S, die als unabhängige Teilmengen von S bezeichnet werden, so dass gilt, wenn B ∈ I und A ∈ I. Wir sagen, dass I erblich ist, wenn es diese Eigenschaft erfüllt. Beachten Sie, dass die leere Menge ∅ notwendigerweise ein Mitglied von I ist.
- Wenn A ∈ I, B ∈ I und |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Wir sagen, dass ein Matroid M (S, I) gewichtet ist, wenn es eine zugehörige Gewichtsfunktion w gibt, die jedem Element x ∈ S ein streng positives Gewicht w (x) zuweist. Die Gewichtsfunktion w erstreckt sich durch Summation auf eine Teilmenge von S :
w (A) = ∑<sub>x∈A</sub> w(x)
für jedes A ∈ S.
