algorithm - まともな初心者向けグラフパズルとは？

Question

私は、グラフを解決する必要がある問題 (グラフによって解決するのが最適です) について、よりよく知ろうとしています。

誰かがグラフを利用した古い ACM プログラミングコンペティションの問題を抱えている場合、または解決したときに特に啓発的であると感じた別の問題を抱えている場合は、感謝します。グラフに慣れ、グラフタイプの問題を簡単に特定し、基本的なグラフトラバーサルアルゴリズムを利用できるようになりたいです。

誰でも私に送ることができる甘い問題を抱えていますか?

score 2 · Accepted Answer

グラフの操作をよりよく理解するには、いくつかの既知のグラフアルゴリズムを実装することをお勧めします。

ぬりかべソルバーやジェネレーターを実装してみてください。かなりの古典的なグラフ操作が必要になります。

score 1 · Accepted Answer

グラフは文字通り、ほとんどすべての問題をモデル化するために使用できます。Topcoder.comのマラソンマッチは、多くの場合、グラフベースのソリューションに適しています。

これらの問題のいくつかをチェックアウトするかもしれません - そしてそれらがどこから来たのかもっとあります。

score 1 · Accepted Answer

この本は非常に役に立ちました (Amazon リンク): Programming Challenges

グラフ、ツリー、基本的なデータ構造のかなり詳細な説明を提供するだけでなく、各タイプに関連するいくつかのプログラミングの課題を提供します! この文書は私の教科書よりも役に立ちます!

その中のグラフの問題のいくつかを次に示します。

グラフトラバーサルに関する問題:

グラフアルゴリズム(ダイクストラ、最小スパニングツリーなど)に関する問題:

score 1 · Accepted Answer

ケーニヒスベルク橋問題に精通している必要があります。また、グラフ理論の問題でよく出てくるデータ構造のタイプにも精通している必要があります。

score 0 · Accepted Answer

どの言語を使用しているかは言いません (使用を考えています)。可能であれば、Lisp または Python をお勧めします。どちらも簡単なグラフ操作に適しています。本当に凝ったものにしたい場合は、PyGame を使用してきれいな出力を作成することをお勧めします。

問題は、簡単なプログラムを見て、グラフに変換してください。ヒント、各トークンはノードです。いくつかのループと方程式があると仮定すると、グラフをトラバースして、ループの外に移動できるものを特定できます。方程式は、より「効率的」になるように再配置できます。

この問題に対する私の論理的根拠は、コンパイラの最適化フェーズ内で進行している可能性のあるプロセスの種類を確認することで、プログラマーとして役立つということです。

ところで、上記を試してみて、Plexを見てください。パーサーで多くの時間を節約できます。

score 0 · Accepted Answer

ヒント: DAWG は非常に優れた方法です。

6 に答える 6