algorithm - グラフとツリーを使用して、どのような問題を解決またはより簡単に取り組むことができますか?

Question

これらのデータ構造の両方で解決できる最も一般的な問題は何ですか?

次のような本についての推奨事項もあるとよいでしょう。

構造を実装する
それらを使用するアルゴリズムの推論を実装して説明する

score 17 · Accepted Answer

この質問を読んで最初に考えるのは、どのような種類のものでグラフ/ツリーが使用されているかということです。そして、それらをどのように使用できるかを逆に考えます。

たとえば、ツリーの一般的な用途を 2 つ取り上げます。

DOM
ファイルシステム

DOM と XML は、ツリー構造に似ています。
代替テキスト

それも理にかなっています。このデータをどのように配置する必要があるかを考えると、これは理にかなっています。ファイルシステムも。UNIX システムにはルートノードがあり、その下に分岐しています。新しいデバイスをマウントすると、ツリーにアタッチされます。

また、データがこのタイプの構造に該当するかどうかを自問する必要があります。問題に意味のあるデータ構造を作成すれば、あとは続きます。

簡単である限り、それは相対的だと思います。ツリー/グラフをトラバースするための再帰関数は得意ですか? 木のバランスをとる必要がある場合はどうしますか？

単語検索パズルを解くプログラムについて考えてみてください。単語検索のすべての文字をグラフにマップし、周囲のノードをチェックして、その文字列がいずれかの単語と一致するかどうかを確認できます。しかし、単一の配列で同じことを行うことはできませんか? 文字を確認するにはインデックスを左右に動かし、上下の文字を確認するには幅だけ移動するだけです。グラフでこの問題を解決することは難しくありませんが、グラフの使用に慣れていない場合は、多くの余分な作業と困難が生じる可能性があります。彼ら。

これらの構造について考えるのに役立つことを願っています。本の推薦については、Introduction to Algorithmsを使用する必要があります。

score 4 · Accepted Answer

回路図。

コンパイル（有向非巡回グラフ）

マップ。グラフとして非常にコンパクト。

ネットワークフローの問題。

エキスパートシステムの決定木（原文のまま）

故障発見、プロセス改善、安全性分析のためのフィッシュボーン図。ボーナスポイントについては、エラー回復コードをフィッシュボーン図であるオブジェクトとして実装します。

score 3 · Accepted Answer

ほぼすべての問題は、グラフ理論の観点から書き直すことができます。冗談ではありません。NP完全問題に関する本を見てください。グラフを操作するための優れたツールがあるため、グラフ理論に変わるかなり奇抜な問題がいくつかあります...

score 2 · Accepted Answer

Algorithm Design Manualには、グラフをクリエイティブに使用した興味深いケーススタディが含まれています。その名前にもかかわらず、この本は非常に読みやすく、時には面白いものです。

score 1 · Accepted Answer

@DavidJoiner /すべて：

FWIW：アルゴリズム設計マニュアルの新しいバージョンがいつでもリリースされる予定です。

スキーナ教授がこの本を開発したコース全体は、Webでも入手できます。

http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html

score 1 · Accepted Answer

私の大学にはそのようなことのためのコースがあります: CSE 326 . この本はあまり役に立たなかったと思いますが、プロジェクトは楽しく、単純な構造のいくつかを実装する方法をかなり教えてくれます。

たとえば、ツリーを使用して解決できる最も一般的な問題 (ツリーを使用している人の数による) の 1 つは、携帯電話のテキスト入力の問題です。ツリー (必ずしもバイナリではない) を使用して、ユーザーが非常に迅速にパンチインする特定の数字のリストから出てくる可能性のある単語のスペースを表すことができます。

score 1 · Accepted Answer

ツリーは、再帰的な性質があるため、関数型プログラミング言語でより多く使用されます。

また、グラフとツリーは、多くの AI の問題をモデル化するための優れた方法です。

score 1 · Accepted Answer

ゲームでは、多くの場合、グラフを使用して、ゲームの世界全体でパスを見つけるのを容易にします。世界のグラフ表現には、幅優先探索や A* などのアルゴリズムを使用して、世界を横断するルートを見つけることができます。

また、ツリーを使用して世界内のエンティティを表すこともよくあります。何千ものエンティティがあり、特定の位置にあるエンティティを見つける必要がある場合、特に頻繁に行う必要がある場合は、リストを直線的に反復するのは非効率的です。したがって、領域をツリーに分割して、より迅速に検索できるようにすることができます。線形空間を二分探索で効率的に検索できる (したがって、二分木に分割できる) ように、2D 空間を四分木に分割し、 3D 空間を八分木に分割できます。

score 1 · Accepted Answer

ゲームやマルチメディアアプリケーションでグラフィックスを描画するためのシーングラフは、ツリーとグラフを多用します。ノードは、レンダリングされるオブジェクト、変換、コントロール、グループなどを表します。

通常、シーングラフには複数のレイヤーと属性があります。これは、指定された順序 (レイヤー) でグラフの一部のノード (属性) のみを描画できることを意味します。シーングラフの種類に応じて、宣言とインスタンス化という 2 つの並列構造を持つことができます。目

score 1 · Accepted Answer

Algorithms for Java: Robert Sedgewick によるパート 5 は、グラフアルゴリズムとデータ構造に関するものです。いくつかのグラフアルゴリズムを実装したい場合は、この本を最初に読むとよいでしょう。

algorithm - グラフとツリーを使用して、どのような問題を解決またはより簡単に取り組むことができますか?

10 に答える 10

Related

Reference