np-hard

0熱

1答えて

私は、旅行者がある距離をグラフで移動でき、すべての双方向エッジがある長さ（距離）を持つ問題を発見しました。特定のエッジ（いずれかの方向）を走行すると、あなたはあなたが旅行することができます与えられた距離のために収集することができる最大のお金を見つける必要があるので、いくつかのお金/ギフト（それはすべてのエッジのために問題になっている）を得ると仮定する。基本的な問題は、与えられた距離（グラフ内にルー

3熱

1答えて

潜在的なNPハードの最大エッジ加重マルチサイクルグラフへの入力が必要

申し訳ありませんが、複雑な名前は申し分ありません。問題を提示しましょう。コンテキスト：私はいくつかの分割をしたい場所ネットワークのタイプを持っています。問題の定義：私は、Eは、エッジ、頂点Vのセットと{W、V、E}無向重み付きグラフG =を有し、エッジ重みWのエッジがVにすべての頂点の間に存在今、サイクルC = {C1 ... CN}のサイズ| C1 | ... | CN | s.t. |

0熱

1答えて

車両を1台だけ使用してVRPTWの走行距離を最適化できますか？

1台の車両でVRPTWを最適化することは可能ですか？1台の車両は顧客の予約時間順に顧客に行く必要があるためです。

1熱

1答えて

NP-complete対NP-hard（なぜそれらは等しくないのですか）

なぜNP-hardはNP-completeと等しくないのですか？使用されている定義の私の非公式の理解： NP - 多項式時間で検証することができるすべての問題 NP完全 - NPとNP-ハードあるすべての問題NP-hard - NPの最も難しい問題と同じくらい難しいです。 Decision Problem - 入力に関して質問をしてブール値を出力する問題混乱： NP対Pの未知の解決策の問題は

1熱

1答えて

NP完全なpr0blemもNPハードですか？

NP完結問題とは、NPとNP困難な問題ですが、問題がNP完全であるという理由だけでNP困難であると主張できます。例：NP完全問題aを問題bに縮小します。したがって、問題bはNP完全であることが証明されています。実際にそれがNP困難であると言うことはできますか？

1熱

1答えて

NP完了またはNP困難？

n個の正の整数のリスト（n偶数）を指定すると、2つのサブリストの整数の和の差が最小になるようにリストを2つのサブリストに分割します。これはNP完全な問題かNP困難な問題か？

0熱

1答えて

均一性の制限がないハイパーグラフの頂点の色付けはNP-hardですか？

均一性の制約がないハイパーグラフの頂点の色付けはNP困難ですか？私は、k-unoformハイパーグラフの頂点の色付けがNP困難であることを示す論文を見てきました。しかし、私は、一般的なケース（k-ユニフォームではない）ハイパーグラフの頂点カラーリングがNPハードであるかどうかを明示的に示しているソースは見つかりませんでした。

-1熱

1答えて

証明方法E_tm = {M | Mは何も受け入れないチューリングマシンです}はNP-Hardですか？

私は始める方法もわかりません。私の考えは、いくつかのNP完全な問題から多時間短縮を提供することです。 E_tm 私が理解できないことは、E_tmは決定できないが、NP-Hardクラスは決定可能であることを知っていることです。

0熱

1答えて

クロマの高速完全ソルバ

グラフの色数を見つけることはNP困難な問題であるため、理論的には高速なソルバはありません。グラフの正確な色数をすばやく計算できる一般に公開されているソフトウェアはありますか？私は、多くのグラフの色数を計算するPythonスクリプトを書いていますが、それは小さなグラフでさえ長すぎます。グラフ私は疎または密であるが通常10,000ノード以下の幅広いグラフを扱っている。私は問題を整数計画として定式化し