Skip to main content

すべての質問

でタグ付けされた
絞り込み
並べ替え
タグ付けされた
1
1 回答
453 閲覧数

レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して

レーベンシュタイン距離(編集距離)を計算して、2単語間の最小編集コストを求めようとしています。 以下のように、python-Levenshteinというライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。 「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、レーベンシュタイン距離(...
user avatar
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. ...
user avatar