グラフやツリーを使用すると、どのような問題を解決したり、より簡単に取り組むことができるでしょうか?[閉まっている]

Question

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

次のような本に関するお勧めも教えていただければ幸いです。

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

Answer 1

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

たとえば、ツリーの 2 つの一般的な用途を考えてみましょう。

• DOM
• ファイルシステム

DOM、さらに言えば XML はツリー構造に似ています。

それも当然です。 このデータをどのように整理する必要があるかを考えれば、これは理にかなっています。. 。ファイルシステムも。UNIX システムにはルート ノードがあり、その下に分岐します。新しいデバイスを取り付けるときは、それを木に取り付けることになります。

また、次のように自問する必要があります。データはこのタイプの構造に分類されますか?問題を理解するデータ構造を作成すれば、残りは後から続きます。

簡単かというと、それは相対的なものだと思います。ツリーやグラフを走査するための再帰関数は得意ですか?木のバランスをとる必要がある場合はどうすればよいでしょうか?

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

これらの構造について考えるのに役立つことを願っています。お勧めの本については、これを選ぶ必要があります アルゴリズムの概要.

Answer 2

回路図。

コンパイル (有向非巡回グラフ)

地図。グラフとしては非常にコンパクトです。

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

決断 木 エキスパート システム用 (原文どおり)

故障発見、プロセス改善、安全分析のための特性要因図。ボーナスポイントを獲得するには、エラー回復コードをオブジェクトとして実装します。 は 特性要因図。

Answer 3

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

Answer 4

アルゴリズム設計マニュアル グラフを創造的に使用した興味深いケーススタディがいくつか含まれています。その名前にもかかわらず、この本は非常に読みやすく、時には面白くさえあります。

Answer 5

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

例として、ツリーを使用して解決される最も一般的な問題 (使用する人の数による) の 1 つは、携帯電話のテキスト入力の問題です。ツリー (必ずしもバイナリである必要はありません) を使用して、ユーザーが非常に素早く入力する特定の数値リストから出現する可能性のある単語の空間を表すことができます。

Answer 6

Java のアルゴリズム:パート5 Robert Sedgewick による本書は、グラフ アルゴリズムとデータ構造に関するものです。これは、グラフ アルゴリズムを実装したい場合に最初に取り組むのに適した本です。

Answer 7

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

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

Answer 8

@DavidJoiner / すべて:

FW:新しいバージョンの アルゴリズム設計マニュアル もうすぐ発売される予定です。

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

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

Answer 9

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

また、グラフやツリーは、AI の問題の多くをモデル化するのに適した方法です。

Answer 10

ゲームでは、ゲーム世界全体にわたるパスを見つけやすくするためにグラフがよく使用されます。世界のグラフ表現には、それを横切るルートを見つけるための幅優先検索や A* などのアルゴリズムを含めることができます。

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