巡回セールスマンの問題は、セールスマンと一連の都市に依存します。営業マンは、ある都市（例えば故郷）から出発してすべての都市を訪問し、同じ都市に戻る必要がある。この問題の課題は、巡回セールスマンが総出張時間を最小限に抑える必要があることです。
都市が x であるとします。1バツ2..... バツnここでコストcij都市xからの移動コストを示します私×にj。巡回販売員の問題は、x で始まり x で終わるルートを見つけることです。1これにより、最小限のコストですべての都市を利用できるようになります。
例： 新聞社は、最小限の旅費で各地域のすべての家をカバーできるように、割り当てられた地域に毎日新聞を配達します。最低出張費を計算します。
エージェントに割り当てられ、新聞を投函する必要があるエリアを図に示します。
解決策: グラフ G のコスト隣接行列は次のとおりです。
料金ij=
ツアーはエリアHからスタート1次に、H から到達可能な最小コスト領域を選択します。1。
エリアHにマークを付ける6それは H から到達可能な最小コスト領域であるためです。1次に、H から到達可能な最小コスト領域を選択します。6。
エリアHにマークを付ける7それは H から到達可能な最小コスト領域であるためです。6次に、H から到達可能な最小コスト領域を選択します。7。
エリアHにマークを付ける8それは H から到達可能な最小コスト領域だからです8。
エリアHにマークを付ける5それは H から到達可能な最小コスト領域だからです5。
エリアHにマークを付ける2それは H から到達可能な最小コスト領域だからです2。
エリアHにマークを付ける3それは H から到達可能な最小コスト領域だからです3。
エリアHにマークを付ける4次に、H から到達可能な最小コスト領域を選択します。4それはHです1したがって、貪欲戦略を使用すると、次の結果が得られます。
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>.
したがって、最小旅行コスト = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
マトロイド:
マトロイドは、次の条件を満たす順序ペア M(S, I) です。
- S は有限集合です。
- I は、B ∈ I および A ∈ I の場合に、S の独立部分集合と呼ばれる、S の部分集合の空ではない族です。この性質を満たす場合、I は遺伝的であると言います。空集合 ∅ は必ず I のメンバーであることに注意してください。
- 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) = ∑<sub>x∈A</sub> w(x)
任意の A ∈ S に対して。