Ask Proggit: Is Graph Theory really as important as some say? Have any good war stories about using Graph Theory to solve a tricky problem?

グラフ理論って本当に人が言ってるように大切なものなの？

グラフ理論を使って難しい問題を解く興味深い話何かないの？

 war stories:戦記:解くのに苦労したということで奮闘記？の意味でしょうか

good:いい、ではあんまりなので興味深い、としました

tricky:狡猾な、手際の良い、油断ならない 

 

△One really interesting use of graph theory is AI planning and strategy.

実に興味深い例の一つとして人工知能の行動決定のときにグラフ理論が利用されている。

planning and strategy:計画と行動戦略


Picture a graph where the current state of the world is your start node. Pick a goal node, where you want the world state to be. The each node branches out to a different world state for every possible move from that node's world state. From there, you can run Dijkstra to generate a plan for the AI to take itself from the current state of the world to the goal state.

今現在の周りの状況を始点としてグラフを描くんだ。そして(グラフの中から)目的地点をえらんでみよう、それが君が望んでいる状況だね。グラフのそれぞれの枝が分岐して現在の枝からいける違う状態につながっている。そこから、人工知能はダイクストラ法*のアルゴリズムを用いて現在の状況から目的の状況へ向かうにはどうすればいいのかプランを立てることができる。

branch:分岐する、広がる 

二行目について、訳が違ってるおそれあります。
 

I'm actually personally playing around with this right now, having the goal nodes be found using an emergent behavior trick. It's pretty damn cool.

今自分でちょうどこれをして遊んでるところだよ。 Emergent behavior trickを使って(緊急時の行動をうまく考えることで?)目的地点へのたどり着き方を発見できるんだ、 いや、まったくすごいもんだ。

 emergent:形:出現する、新興の 、緊急の

 emergent behavior trick:  emergent behavior を検索すれば多くの論文が出てくると思います。興味ある方はそちらを参照してくださし。



■グラフ理論を使って難しい問題を解く興味深い話何かないの？


△

自分は複雑なデータベースにおいて外部キー参照グラフ*に対してトポロジカルソート**を適用している。

**無閉路有向グラフに対するソート方法の一種

  sequence:名:連続、続発 


△

どういうわけか、自分はいつもこう思ってるんだよね、トポロジカルソート問題の初期状態って有限有向非巡回グラフではなく有限半順序グラフ*だって。トポロジカルソートはアルゴリズムを使って半順序関係を全順序関係に拡張する問題だよ。

for some reason :何らかの理由で

natural setting:初期状態(?)

*無閉路有向グラフについてはこれは正しい(と管理人は思います)

algorithmically:アルゴリズム的に



もちろんこの二つのオブジェクトは実は同じものなんだ。同じ概念に対する色々な定義の取り方をできるだけ理解してしっかり認識することはとても大切なことだよ。グラフ理論の分野の問題を考えることによって新しい見方と問題の解決方法が示されることがよくあるんだ。たとえその問題が既成のアルゴリズムを適用できない問題だったとしてもね。

appreciate:vt:進化を認める、高く評価する、認識する

insights:洞察

off-the-shelf:在庫品の[既成の、と訳しました]


△

グラフ理論はコンピューターサイエンスの基礎となる部分のひとつだ。真の意味でグラフ理論とコンピュータサイエンスを二分することはできない。もしもコンピューターサイエンスを理解しようとするならば、組み合わせ理論とグラフ理論を学ぶ必要がある。そうしないのならば、難しい問題に直面したときに何もできなくなるよ。

 combinatorics:組み合わせ理論 

otherwise:さもなくば、そうしないのならば、別な方法で

amateur hour:慣用句らしいです


出典:http://www.reddit.com/r/programming/comments/929cs/ask_proggit_is_graph_theory_really_as_important/

グラフ理論は管理人的にかなり楽しい分野。待ち行列理論などもそのうち掲載してみようと思います。