reference

Question

正規の CS 問題の良いリファレンスを知っている人はいますか?

「仕分け問題」、「ビン詰め問題」、「しつこいセールスマン問題」などを考えています。

編集：ウェブサイトを優先

score 4 · Accepted Answer

おそらく、 Introduction to Algorithmsなどのアルゴリズムの教科書で最適なものを見つけることができます。私はその特定の本を読んだことはありませんが、徹底していることで非常に有名であり、おそらく遭遇する可能性のある問題のほとんどが含まれているでしょう.

score 4 · Accepted Answer

Garey と Johnson による"Computers and Intractability: A guide to the theory of NP-Completeness"は、この種の事柄に関する優れたリファレンスですが、(P での) "解決された" 問題は、本では明らかにあまり注目されていません。

私は適切なオンラインリソースを知りませんが、削減と複雑さに関する Karp の影響力のある論文Reducibility between Combinatorial Problems (1972)は、おそらく Hard Problems の「正規の」リファレンスです。

score 3 · Accepted Answer

ウィキペディアのカテゴリ:計算問題とカテゴリ:NP 完全問題のページを見たことがありますか? おそらく完全ではありませんが、良い出発点のように見えます。ウィキペディアは、CS のトピックでかなりうまくいっているようです。

score 3 · Accepted Answer

1冊の本だけでこれらすべての問題の答えが見つかるとは思いません。アルゴリズムに関するきちんとした包括的な Web サイトを見たことがないので、本に固執することをお勧めします。とはいえ、正規アルゴリズムのテキストに関する入門資料をいつでも入手できます (私が通常お勧めするのは常に次の 3 つです: CLRS、Manber、Aho、 Hopcroft 、および Ullman(これはいくつかの重要なトピックで少し古くなっていますが、非常に形式的でよく書かれているので必読です)。それらのすべてには、ある意味でコンピューターサイエンスの標準的な問題である重要な組み合わせ問題が含まれています。グラフ理論の基礎を学んだ後、ネットワークフローと線形計画法に移行できるようになります。これらは、遭遇するほとんどの問題を最終的に解決する一連の手法で構成されています (整数値に制限された変数を使用した線形計画法は NP 困難です)。ネットワークフローは、グラフ理論とはまったく関係がないように見える分野での非常に興味深いアプリケーションを使用して、グラフ (加重/容量化されたエッジ) で定義された問題を扱います。これに関する教科書は、Ahuja、Magnant、Orlin のものです。. 線形計画法は、ある種のネットワークフローのスーパーセットであり、線形方程式系の形式で制約を受ける変数に対する線形関数の最適化を扱います。ネットワークフローとの関係を強調した本はBazaraa の. 次に、ビンパッキング、タスクスケジューリング、ナップザック問題などの問題をモデル化するための多くの自然な手法を提供する非常に価値のあるツールである整数計画法に進むことができます。L. Wolsey の本が参考になります。

score 2 · Accepted Answer

NIST のDictionary of Algorithms and Data Structures を必ず確認してください。巡回セールスマン問題、ビザンチンの将軍問題、哲学者の食事の問題、ナップザックの問題(= あなたの「ビン詰めの問題」だと思います)、切り株問題、8 人の女王の問題、騎士の巡回問題、ビジービーバー問題、停止問題、などなど。

銃殺隊の同期の問題(その省略には驚いた) も、ジープの問題(コンピューターサイエンスよりもロジスティクスの問題)もありません。

興味深いことに、codinghorror.comにブログがあり、これらのいくつかについてパズル形式で説明しています。(ブログで引用されている Smullyan の本を読んだかどうか思い出せませんが、彼はパズルと哲学的な思索の優れた編纂者です。Martin Gardner と Douglas Hofstadter とHE Dudeneyは他にもいます。)

また、 Stony Brook Algorithm Repositoryもチェックしてください。

(または、Google で「組み合わせ問題」を検索するか、Wolfram Mathworldで「問題」を検索するか、ヒルベルトの問題を調べてください。ただし、これらすべてのリンクでは、それらの多くはコンピューターサイエンスよりも純粋な数学です。)

score 0 · Accepted Answer

@rcreswickそれらは良い参考文献のように聞こえますが、私が考えていることに少し恥ずかしがり屋です。（しかし、私が知っている限り、それは最高です）

人々がより良い参照を見つけることができることを期待して、私は何も受け入れられたものとしてマークしないつもりです。

その間、私はここにいくつかの問題をリストするつもりです、もっと自由に追加することができました

ソートの問題与えられた方法で単調であるセットの順序を見つけます

ビンパッキング問題は、各サブセットが特定の制限よりも「小さい」最小数のセットにセットを分割します

巡回セールスマン問題最小の総重みを持つ重み付きグラフでハミルトン閉路を見つける

reference - 正規の問題リスト

6 に答える 6

Related