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 x₁X₂..... X_Nwo kosten c_ijbezeichnet die Reisekosten von der Stadt x_ichzu x_J. Das Problem des Handlungsreisenden besteht darin, eine Route zu finden, die bei x beginnt und endet₁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₁und wählen Sie dann den Bereich mit den minimalen Kosten aus, der von H aus erreichbar ist₁.

Bereich H markieren₆weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist₁und wählen Sie dann den von H aus erreichbaren Mindestkostenbereich aus₆.

Bereich H markieren₇weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist₆und wählen Sie dann den von H aus erreichbaren Mindestkostenbereich aus₇.

Dharmendra-Alter

Bereich H markieren₈weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist₈.

Bereich H markieren₅weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist₅.

Bereich H markieren₂weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist₂.

Bereich H markieren₃weil es der Bereich mit den minimalen Kosten ist, der von H aus erreichbar ist₃.

Staaten in den USA

Bereich H markieren₄und wählen Sie dann den Bereich mit den minimalen Kosten aus, der von H aus erreichbar ist₄es ist H₁.Mit der Greedy-Strategie erhalten wir also Folgendes.

 4 3 2 4 3 2 1 6 H<sub>1</sub> &#x2192; H<sub>6</sub> &#x2192; H<sub>7</sub> &#x2192; H<sub>8</sub> &#x2192; H<sub>5</sub> &#x2192; H<sub>2</sub> &#x2192; H<sub>3</sub> &#x2192; H<sub>4</sub> &#x2192; <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:

1. S ist eine endliche Menge.
2. 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.
3. 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) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

für jedes A ∈ S.