巡回セールスマンの問題は、セールスマンと一連の都市に依存します。営業マンは、ある都市（例えば故郷）から出発してすべての都市を訪問し、同じ都市に戻る必要がある。この問題の課題は、巡回セールスマンが総出張時間を最小限に抑える必要があることです。

都市が x であるとします。 ₁ バツ ₂ ..... バツ _n ここでコストc _ij 都市xからの移動コストを示します _私 ×に _j 。巡回販売員の問題は、x で始まり x で終わるルートを見つけることです。 ₁ これにより、最小限のコストですべての都市を利用できるようになります。

例： 新聞社は、最小限の旅費で各地域のすべての家をカバーできるように、割り当てられた地域に毎日新聞を配達します。最低出張費を計算します。

エージェントに割り当てられ、新聞を投函する必要があるエリアを図に示します。

解決策: グラフ G のコスト隣接行列は次のとおりです。

料金 _ij =

ツアーはエリアHからスタート ₁ 次に、H から到達可能な最小コスト領域を選択します。 ₁ 。

エリアHにマークを付ける ₆ それは H から到達可能な最小コスト領域であるためです。 ₁ 次に、H から到達可能な最小コスト領域を選択します。 ₆ 。

エリアHにマークを付ける ₇ それは H から到達可能な最小コスト領域であるためです。 ₆ 次に、H から到達可能な最小コスト領域を選択します。 ₇ 。

エリアHにマークを付ける ₈ それは H から到達可能な最小コスト領域だからです ₈ 。

エリアHにマークを付ける ₅ それは H から到達可能な最小コスト領域だからです ₅ 。

エリアHにマークを付ける ₂ それは H から到達可能な最小コスト領域だからです ₂ 。

エリアHにマークを付ける ₃ それは H から到達可能な最小コスト領域だからです ₃ 。

エリアHにマークを付ける ₄ 次に、H から到達可能な最小コスト領域を選択します。 ₄ それはHです ₁ したがって、貪欲戦略を使用すると、次の結果が得られます。

 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>.  

したがって、最小旅行コスト = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25

マトロイド:

マトロイドは、次の条件を満たす順序ペア M(S, I) です。

1. S は有限集合です。
2. I は、B ∈ I および A ∈ I の場合に、S の独立部分集合と呼ばれる、S の部分集合の空ではない族です。この性質を満たす場合、I は遺伝的であると言います。空集合 ∅ は必ず I のメンバーであることに注意してください。
3. A ∈ I、B ∈ I および |A| の場合 <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>

各要素 x ∈ S に厳密に正の重み w (x) を割り当てる関連する重み関数 w が存在する場合、マトロイド M (S, I) は重み付けされていると言います。重み関数 w は合計によって S のサブセットに拡張されます。 :

 w (A) = &#x2211;<sub>x&#x2208;A</sub> w(x)  

任意の A ∈ S に対して。