問題タブ [np-hard]

コンセプトの明確化が必要でした。問題が NP 完全であることを証明するために、リダクションを使用します。

ここで、L<=L' があるとします。L から L' への削減がありますか、それとも逆の方法で行うことはできますか? つまり、L が L' を使用して解決できる場合、L' は NP 完全であることを示すことができますか??

私はこれに関してかなり混乱しています。

例えば。ハム サイクルからハム パスへの削減については、逆方向にします。

また、「少なくとも k 個のエッジを持つグラフに s から t へのパスがあるかどうか」を示す必要があるという問題を、ハム サイクルからのリダクションで解決できません。

上記の問題について説明し、私を導いてください。ありがとう

私は、NP-Hard/Complete の問題を実装およびテストするプロジェクトに取り組んでいます。私はスケジューリングで何かをするという一般的なアイデアを持っていて、ジョブショップの問題についてたくさん読んだことがあります。OR ライブラリから使用する有名なテスト ケース/ベンチマークがあることは知っています。テストインスタンスを読み取り、そのデータを保存するためのコード (Java) があります。今、私は、スケジュールを作成するアルゴリズム/方法を見つけて、最適なスケジュールを提示しようとしてループに詰まっているように感じます. 私は多くの学術論文を読んでいますが、特に複雑な集合表記については、それらの中で少し迷ってしまいます。疑似コードの例をもっと見つけたいと思います。私はこれが古典的な問題であることを知っており、ジョブショップに対する単純な古典的な解決策、特に疑似コードの例もある提案を誰かが持っているかどうか疑問に思っています。このプロジェクトのために独自の調査を行う必要はありません。NP 困難な問題を解決するための既知の手法を適用し、コードを記述し、テストを実行し、実験結果を提示し、それらにコメントする方法を学ぶ必要があるだけです。アドバイスや助けをいただければ幸いです。

「多くの仕事を行う必要があり、すべての仕事は一定の時間、多くのマシンを使用することから成り立っています。問題は、すべてのジョブをすべての異なるマシンで最短時間で実行するための最適な計画を見つけることです。 ."

問題の例:

データライン セクションの各行は、10 組の連続した数字でジョブを指定します。数値の各ペアは、ジョブの 1 つのタスクを定義します。これは、マシン上でのジョブの処理を表します。各ペアについて、最初の数字はそれが実行されるマシンを識別し、2 番目の数字は期間です。10 個のペアの順序によって、ジョブのタスクの順序が定義されます。

「ローレンス 10x10 インスタンス」(表 6、インスタンス 4); (seta4) または (A4) とも呼ばれます (Applegate および Cook、1991 年) -10 台のマシン、0 ～ 9 の番号が付けられている -10 行 = 10 ジョブ --最適: 842

2 44 3 5 5 58 4 97 0 9 7 84 8 77 9 96 1 58 6 89

4 15 7 31 1 87 8 57 0 77 3 85 2 81 5 39 9 73 6 21

9 82 6 22 4 10 3 70 1 49 0 40 8 34 2 48 7 80 5 71

1 91 2 17 7 62 5 75 8 47 4 11 3 7 6 72 9 35 0 55

6 71 1 90 3 75 0 64 2 94 8 15 4 12 7 67 9 20 5 50

7 70 5 93 8 77 2 29 4 58 6 93 3 68 1 57 9 7 0 52

6 87 1 63 4 26 5 6 2 82 3 27 7 56 8 48 9 36 0 95

0 36 5 15 8 41 9 78 3 76 6 84 4 30 7 76 2 36 1 8

5 88 2 81 3 13 6 82 4 54 7 13 8 29 9 40 1 78 0 75

9 88 4 54 6 64 7 32 0 52 2 6 8 54 5 82 3 6 1 26

一般的に、NPC に問題があると仮定します。それに制約を追加する（より困難にする）と、問題がNPHになる可能性はありますか？NPC と NPH の違いはわかっていますが、既存の NPC 問題に新しい制約を追加すると NPH になるか、NPC のままになるかを示す方法がわかりません。

問題がNP困難であるというスケジューリング問題をいくつか見ました。私の質問は、1）問題がNP困難であると言うとき、それはNPにないことを意味しますか？それがNPである場合、問題はNP完全であると言うからです。a）NPにある場合b）NP困難である場合、問題はNPCにあることを私は知っています。

私は、利益(i、j)が利益(j、i)と等しくない可能性があるように、頂点の各ペア間で定義された利益を持つ一連の頂点を持っています。さらに、プラスのウェイト サイクルが存在し、利益がマイナスになる場合もあります。

これは、最大の利益を見つけるための NP 困難な問題であるため、問題は、各都市を訪問する利益を最大化することです (すべての都市を訪問する必要はありません)。これを見つけるために、次のアルゴリズムを試しました。

• 頂点の完全なセットに対する貪欲なアルゴリズム。
• 力ずくで貪欲: まず頂点の貪欲なシーケンスを見つけます。これにより、ほぼクラスターを形成する頂点の近似セットが得られます。次に、たとえば 8 つの都市の連続したセットを取り、それらを並べ替えて、力ずくで最大の利益を見つけます。

しかし、これらを 100 個の頂点で試した場合、あまり良い結果は得られません。

コストを最大化するための他の確率的または近似的な方法はありますか?

整数線形計画法 (ILP) を使用して問題の解決策を実装しようとしています。問題は NP 困難であるため、Simplex Method によって提供されるソリューションが最適かどうか疑問に思っていますか? シンプレックス法を使用したILPの最適性についてコメントしたり、ソースを指摘したりできますか。ILP 問題に最適なソリューションを提供できる他のアルゴリズムはありますか?

編集:ILPのアルゴリズム(シンプレックス法、分岐および境界および切断面)のいずれかによって得られたソリューションの最適性に対するyes/noの答えを探しています。

巡回セールスマン問題を解決するためのヒューリスティックス/近似値を見つけようとしています。そのために、いくつかの「難しい」TSP インスタンスを (最もよく知られている解決策と共に) 探しています。それらを見て、私がどれだけうまくやれるか見てください。

理想的には、それらは単に隣接行列または隣接リストのテキストベースのリストです (私は解析を扱いたくありません。アルゴリズムだけを扱いたいのです)。
「難しい」とは、ブルートフォースを使用して解決または近似することが事実上不可能であることを意味します。
(これは、最もよく知られている答えに近い答えを見つけた場合、単に幸運になるだけでなく、実際に何か正しいことをしていると合理的に確信できるようにするためです。)

この目的のために機能するリストはありますか? 私は少し周りを検索しましたが、何も見つかりませんでした。

NP Hard 問題はマッピングによって他の NP Hard 問題に還元されるため、私の質問は一歩前進です。たとえば、そのアルゴのすべてのステップ: 他の NP ハードにもマッピングできますか?

前もって感謝します