すべての質問
4 件の質問
0
票
2
回答
534
閲覧数
ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される
ダイクストラ法のコード(python)を参考に以下のプログラムを実行しました。
出力として最短ルートは'A->C->B->D'と求められましたが、コストは「5+(-4)+1=2」になるところ、'A->B->D'の「3+1=4」が出力されました。原因がわからないです。
グラフ部分はコードのrouteにあたります。
出力
$ python dijkstra.py
visited to A.
...
1
票
1
回答
453
閲覧数
レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して
レーベンシュタイン距離(編集距離)を計算して、2単語間の最小編集コストを求めようとしています。
以下のように、python-Levenshteinというライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。
「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、レーベンシュタイン距離(...
5
票
0
回答
158
閲覧数
グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?
グラフ構造、たとえばツリー構造を探索することを考えます。
ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。
この時、
幅優先探索はしばしばキューを用いて
深さ優先探索はしばしばスタックを用いて
それぞれ実装されます。
これはちょうど、
各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う
次のノードを pop() ...
4
票
1
回答
804
閲覧数
グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい
グラフ理論に関する質問です。
頂点(ノード)間の位置関係をinvariantに保持する方法・表現を考えたいです。
具体的な例として、ある化合物の分子を考えます。
ここで、その分子内の原子(グラフにおける頂点)たちと、
各原子の三次元座標(3次元ベクトル)が与えられています。
この三次元座標を用いて、頂点間の距離(グラフにおける辺の長さ)などが計算できます。
ここで、化合物内のある原子(...