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.
Switch-Methode Java
Angenommen, die Städte sind x1X2..... XNwo kosten cijbezeichnet die Reisekosten von der Stadt xichzu xJ. Das Problem des Handlungsreisenden besteht darin, eine Route zu finden, die bei x beginnt und endet1das 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:
kostenij=
Die Tour beginnt im Bereich H1und wählen Sie dann den Bereich mit den minimalen Kosten aus, der von H aus erreichbar ist1.
Bereich H markieren6weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist1und wählen Sie dann den von H aus erreichbaren Mindestkostenbereich aus6.
Bereich H markieren7weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist6und wählen Sie dann den von H aus erreichbaren Mindestkostenbereich aus7.
Dharmendra-Alter
Bereich H markieren8weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist8.
Bereich H markieren5weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist5.
Bereich H markieren2weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist2.
Bereich H markieren3weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist3.
Staaten in den USA
Bereich H markieren4und wählen Sie dann den Bereich mit den minimalen Kosten aus, der von H aus erreichbar ist4es ist H1.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.