問題タブ [np-hard]

問題を形式化して、次の ILP を完成させました。

NP困難であることを証明するために複数のナップザック問題に還元しようとしましたが、制約(4)のために立ち往生しました。誰かが私にいくつかの提案をしてもらえますか? ありがとう

$A$ の場所から $B$ の場所まで歩きたいとしますが、その間にいくつかの川があります。$A$ の場所から $B$ の場所まで歩くには、川ごとに橋を架ける必要があります。

数種類の板をご用意しております。厚板の種類が異なればコストと長さも異なりますが、同じ種類の厚板は同じコストと長さです。厚板を使って橋を架けることができます。ただし、利用できる板の数は限られています。私たちの目的は、厚板の総コストを最小限に抑えながら、各川に橋を架けることです。

問題をよりよく説明するために、問題を説明する図を描きます。

必要な橋の長さがそれぞれ $d_1$、$d_2$、$d_3$ の 3 つの川があります。

$4$ 種類の厚板があります。$l_i$ と $c_i$ は、$i$ 番目のタイプの厚板の長さとコストを示します。$\delta_i$ が利用可能な $i$ 番目の種類の厚板の数を表すとします。$n_{ij}$ が橋 $j$ を構築するために使用される厚板の数を表すとします。

次に、問題は次のように定式化できます。

$\sum_{j=1}^3 \sum_{i=1}^4 n_{ij}c_i$ を最小化

st

$\sum_{i=1}^4 n_{ij}l_i \geq d_j$

$\sum_{j=1}^3 n_{ij} \leq \delta_i$

$n_{ij}\geq 0$ & $n_{ij} \in Z$

この問題は整数計画問題であるため、NP-Hard である必要があると思います。これは本当ですか？この問題を解決する方法を知っている人はいますか？最適ではないソリューションでさえ。

ナップザックの崩壊問題は、通常のナップザック問題の一般化であり、ナップザックの容量は含まれるアイテムの数の非増加関数です。

アイテムの数ではなく、選択したアイテムに応じてナップザックの容量が変化するバリアント (つまり、ドメインはアイテムのパワーセット) について何か (名前、文献、アルゴリズムなど) を知っている人はいますか?

ウィキによると、（N-1）かかります！N都市のツアーを計算します。それを行うためのより良い方法を見つけましたが、それをどれだけ改善したかを計算するための計算を行うことはできません. 私の自宅の PC では、20 都市の地図を 1 時間以内に解くことができました。20！= 2.43290200e+18. これが私がしたことです：

N 個の都市 (名前を付けましょう: City(1)、City(2)、City(3)... City(N)) のルートを braut アルゴリズムで検索する場合、最初に次のテストを実行します: City( 1)、City(2)、City(3)、City(4)... City(N)、そしてしばらくしてから、City(1)、City(3)、City(2)、City(4) )...都市(N). 2番目の計算は不要だと主張しています。City(4) ... City(N) の最短ルートを 1 回だけ計算した場合、それを 2 回目の計算に使用して、どのルートがより適切かを判断できます。

このトリックを使用して、K 都市に対して行っている計算の数を次のように減らすことができます: (N - k) これは、誰が最初の都市になるかを示すことができるオプションの数であり、(N - K - 1) を掛けます。 ! これは、残りの都市を選択するために必要なオプションの数であり、完全な計算を実行するために必要な最初の時間を差し引いたものです。なので(N-K)!となります。そして、k = 3 から k = N - 2 までのすべての K について合計する必要があります。

これは私が行った限りです（それほど遠くありません）...これを計算するのを手伝ってくれることを願っています.

編集: このアルゴリズムの改善が見つかりました。ぜひご覧ください。

この質問は私の古い質問の改善です。ここで、 Java コード サンプルを示し、私のアルゴリズムを詳しく説明したいと思います。

巡回セールスマン問題の正確な解を得るための多項式アルゴリズムを見つけたと思います。私の実装は5つのステップから構築されています:

• 1) クイックセットアップ
• 2)解決策を探す
• 3)停止条件 1
• 4) 停止条件 2
• 5) 停止条件 3

ステップ 2 と 3 から始めたいと思います。ここで間違っていなければ、残りをお見せします。

これからお見せするのは、多項式アルゴリズムではなく、時間 O(n^2 2^n) で問題を解決するHeld–Karp アルゴリズムの改良です。

braut アルゴリズムを使用して 6 都市のルートを解決したいとしましょう。(6-1) あります！=そのための120のオプションがあるため、それらすべてをテストして、確立された最短ルートを返す必要があります。そのため、次のようになります (都市名は次のとおりです: A、B、C、D、E、F):

• オプション 1 : A -> B -> C -> D -> E -> F -> A
• オプション 2 : A -> B -> C -> D -> F -> E -> A
• オプション 3 : A -> C -> B -> D -> E -> F -> A
• オプション 4 : A -> C -> B -> D -> F -> E -> A
• .
• .
• オプション120

ここで、オプション 1 と 2 を計算した後、オプション 3 と 4 をスキップできると言っています。それは簡単です: オプション 1 を計算するとき、都市 D から始まり、都市 A で終わり、都市 E、F を通過する最短ルートを計算する必要があります。実際には、オプション 1 と 2 を計算します。最初と最後の都市を強制する 4 つの都市のマップを作成します。この例では、オプション 1 を計算するときに、そこからの最短経路のデータを保持する D、E、F、A のマップを作成します。 D から A から E、F まで。したがって、オプション 3 と 4 の計算を開始すると、都市 D に到達した時点で停止できます。これは、都市 D で開始し、都市 A で終了し、都市 E、F を通過する最短ルートが既にわかっているためです。

これは、私がアルゴリズムで使用した原則です。ブルートアルゴリズムを実行し、すべてのサブ結果をマッピングしました。これらの結果はサブルートではありません。混乱しないでください。これらは、最短ルートを見つけるために実行する必要がある計算の一部にすぎません。そのため、同じ計算を行っていることに気付くたびに、マップからの解を使用しました。

これは、19 の都市で実行された私のアルゴリズムの出力です。これはほんの一例ですが、それ以上の意味があります。実際、これは 19 都市のすべての結果を表しています。19 都市の入力が何であれ、アルゴリズムは常に同じ量のマップを作成し、同じ量のアクションを実行し、同じ時間で解決します。

Source(19)は入力都市です。私のPCでは321550 mills計算に時間がかかりました（約5分）。Created: 20801457作成された検索インスタンスの数を表します (マップを使用した、またはマップを作成したすべての時間。この数をよりよく理解するには、コードを確認する必要があります)。Map(3)作成された 3 つの都市のマップの数について話します。2448 の 3 都市マップを作成し、34272 回使用しました。

私のアルゴリズムがN都市のルートで K 都市のサイズで生成するマップの数は次のようになります: マップの最初の都市を選択できる回数:残りの都市: (n-1)! / ((n - k - 1)! * (k-1)!)。それはnに来ます！/ ((n - k - 1)! * (k-1)!) . サイズ 3 のマップの作成がアトミック アクションであると仮定すると、私のアルゴリズムの効率は、これらすべてのマップの合計になります。

したがって、私のアルゴリズムには次の効率があります。

N * (N - 1) * (N - 2) / 2! + N * (N - 1) * (N - 2) * (N - 3) / 3! + N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4! + ... ん！/ (N - 1)! = N * (N - 1) * (N - 2) / 2! + N * (N - 1) * (N - 2) * (N - 3) / 3! + N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4! + ... N

では、これはどのような効率でしょうか。

O(N^C*2^N)の指数関数のように見えます。ここで、C は 1 より少し小さいです。これは、N を 7 から 100 までの効率アルゴリズムを解いて見つけ、以前の結果 (N = 9 で N = 8 の結果、N = 24 で N = 23 の結果) と比較すると、 N の数が多いと、比較結果は 2 になります。それから、従来の動的計画法アルゴリズムの効率についても同じことを行いました。これが私が得たもののリストです：

列 1 は N、列 2 は私のアルゴリズム効率の比較、列 3 は動的計画法アルゴリズムの比較、列 4 は私のアルゴリズム効率乗算 N 比較です。

列 3 と 4 がほぼ同じであることがわかります。これが私が見つけた方法です。

私の仕事を確認し、コードを見て、私に同意するかどうか教えてください. そうでない場合は、アルゴリズムまたは数学が正確なサンプルで機能していない場所を教えてください。私に同意する場合は、アルゴリズムのこの部分が Held-Karp アルゴリズムよりも優れていることを示すことで、wiki ページを変更するのを手伝ってください。