問題タブ [np-complete]

荷物があるとします。A 地点から B 地点、B 地点から C 地点、そして最後に C 地点から D 地点に移動する必要があります。5 日以内に到達する必要があり、できるだけ少ない金額で済みます。各レグには 3 つの可能な荷送人があり、各レグにはそれぞれ異なる時間とコストがあります。

プログラムで最適な組み合わせを見つけるにはどうすればよいでしょうか?

これまでの私の最善の試み（3番目または4番目のアルゴリズム）は次のとおりです。

1. 各区間で最長の荷送人を見つける
2. 最も「高価な」ものを排除する
3. 各区間で最も安い荷送人を見つける
4. 総費用と日数を計算する
5. 日数が許容できる場合は終了、そうでない場合は 1 に移動

PHP ですばやくモックアップします (以下のテスト配列は問題なく動作しますが、上記のテスト配列で試してみると、正しい組み合わせが見つからないことに注意してください)。

文字通り、各組み合わせを 1 つずつ (一連のループを使用して) 作成し、それぞれの合計「スコア」を合計して、最高のものを見つけるという、ある種のことを実際に行う必要があると思います....

編集：明確にするために、これは「宿題」の課題ではありません（私は学校にいません）。それは私の現在のプロジェクトの一部です。

要件は (いつものように) 常に変化しています。この問題に取り組み始めた時点で現在の制約が与えられていたとしたら、A* アルゴリズムの変形 (またはダイクストラまたは最短経路またはシンプレックスなど) を使用していたでしょう。しかし、すべてが変形し、変化しており、それが私を今いる場所に導きます.

つまり、これまでに行ったすべてのがらくたを忘れて、パス検索アルゴリズムである、使用すべきだとわかっているものを使用する必要があることを意味していると思います。

私は 10 進数 (それを goalと呼びましょう) と他の 10 進数の配列 (配列elementsと呼びましょう) を持っており、合計がゴールになる要素から数値のすべての組み合わせを見つける必要があります。

私は C# (.Net 2.0) でのソリューションを好みますが、最高のアルゴリズムが勝つ可能性があります。

メソッドの署名は次のようになります。

グラフでハミルトニアンウォークを見つけるための多項式時間アルゴリズムはありますか?

私のアルゴリズムは N 階乗であり、非常に遅いです。

P=NP かどうかという問題は、おそらくすべてのコンピューター サイエンスで最も有名です。どういう意味ですか？そして、なぜそれはとても興味深いのですか？

ああ、そして追加の信用のために、声明の真実または虚偽の証拠を投稿してください. :)

固定サイズのブロックの束で構成された大きなファイルがあるとします。これらの各ブロックには、いくつかの可変サイズのレコードが含まれています。各レコードは 1 つのブロック内に完全に収まる必要があり、定義上、そのようなレコードは完全なブロックより大きくなることはありません。時間の経過とともに、レコードがこの「データベース」に出入りするにつれて、これらのブロックにレコードが追加されたり、ブロックから削除されたりします。

ある時点で、特に多くのレコードがデータベースに追加され、いくつかが削除された後、ブロックの多くが部分的にしか埋められない場合があります。

このデータベース内のレコードをシャッフルして、部分的に満たされたブロックをより適切に埋めることにより、ファイルの末尾にある不要なブロックを圧縮するための適切なアルゴリズムは何ですか?

アルゴリズムの要件:

• 圧縮は、元のファイルの代わりに発生する必要があり、その開始サイズからせいぜい数ブロック分以上ファイルを一時的に拡張する必要はありません。
• アルゴリズムは、すでにほとんどがいっぱいになっているブロックを不必要に妨害してはなりません
• ブロック全体を一度にファイルから読み書きする必要があり、書き込み操作は比較的高価であると想定する必要があります
• レコードをあるブロックから別のブロックに移動する場合、操作が中断された場合に「失敗した」圧縮の結果としてレコードが失われないように、開始位置から削除する前に新しい場所に追加する必要があります。(このようなレコードの一時的な重複は、回復時に検出できると仮定します)。
• この操作に使用できるメモリは、全体のファイル サイズの非常に小さな割合である、おそらく数ブロック程度です。
• レコードが 10 バイトから 1K バイトのオーダーで、平均サイズがおそらく 100 バイトであると想定します。固定サイズのブロックは 4K または 8K のオーダーであり、ファイルは 1000 のブロックのオーダーです。

問題/問題のコミック: http://xkcd.com/287/

これが最善の方法かどうかはわかりませんが、これまでのところ私が思いついた方法は次のとおりです。私は CFML を使用していますが、誰でも読めるはずです。

上記のコードは、$15.05 になる唯一の組み合わせはミックス フルーツの 7 注文であり、完了するまでに testCombo 関数を 232 回実行する必要があることを示しています。

正しい解決策に到達するためのより良いアルゴリズムはありますか? 私は正しい解決策にたどり着きましたか？

NP完全問題とは？なぜそれがコンピュータ サイエンスの重要なトピックなのですか?

NP-Complete のウィキペディアのエントリから:

「いくつかの新しい問題が NP 完全であることを証明する最も簡単な方法は、最初にそれが NP であることを証明し、次に既知の NP 完全問題をそれに還元することです。」

私はこれを理解していると確信しています: 問題がある場合、次の場合にそれが NP-Complete であることを示すことができます:

1. NP であることを示します (問題の解は、非決定論的チューリング マシンで多項式時間で検証できます)。

2. すでに NP 完全であることがわかっている問題を新しい問題に「還元」できることを示す

では、私の質問は、最初の NP 完全問題がどのようにして NP 完全であることが「証明」されたのかということです。かつて、既知の NP 完全問題のセットはゼロであったに違いありません。これにより、上記のプロセスのステップ 2 に頼ることができなくなります。

これは、私が気付いていない証明のための別の方法があると私に思わせます。それか、既知の多項式時間解がないために、NP完全なプロパティ全体が特定の問題に対して「想定」されている可能性があります。（実際、これを書いたので、そうであっても驚かないでしょうが、いずれにせよ、グルのフィードバックが欲しいです）。

部分和の問題に関連する問題があり、その違いによって問題が解決しやすくなるかどうか、つまり妥当な時間で解決できるかどうか疑問に思っています。

値 V、集合サイズ L、数列 [1,N] S が与えられたとき、S のサイズ L のサブセットの合計が V 未満になるのはいくつですか?

これは、次の 3 つの点でサブセット和問題とは異なります。

1. 等しいサブセットの数ではなく、与えられた値よりも小さいサブセットの数を気にします。
2. サブセットのサイズは固定されています。
3. 存在するかどうかだけでなく、合計が V 未満になるセットの数を気にします。

これを解決する合理的に効率的なアルゴリズムはありますか?

編集: 明らかに、これは組み合わせ生成アルゴリズムを使用して O(N choose L) で実行できます。私が本当に興味を持っているのは、それを大幅に高速化する巧妙なハックです。

各ノードが最大で 3 つの子と 3 つの親を持つ *n サイズの多頭非巡回グラフが与えられた場合、2 つのノードが同じ値を共有しない n 長のパスが存在するかどうかを識別する非指数アルゴリズムはありますか?セットの値は説明されますか?

基本的に、各スペースにランダムな値 (1..n) を持つ n*n 迷路があります。すべての値を含む n ノードの (上から下への) パスを見つける必要があります。

現在、深さ優先検索を使用していますがT(n) = 3T(n-1) + O(1)、それはO(3^n)理想的ではない解決策です。

私の恐れを確認するか、正しい方向に向けていただければ幸いです。

編集：これをもう少し具体的にするために、ここに解決策のある迷路があります（深さ優先の解決策を使用して解決されます）。