グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。 2頂点対最短経路問題 特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。 単一始点最短経路問題 (SSSP：Single Source Shortest Path) 特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。 全点対最短経路問題 (APSP : All Pair Shortest Path) グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。 このよう
「ビードソート（Bead Sort）」や「ネットワークソート」のように、特定の道具が必要なものから、「ボゴソート」や「ストゥージソート（Stooge Sort）」（「Three Stooges」というコメディ番組から命名）のように、実用的でなく、実証のためだけに存在するものまで、まだまだたくさんのソートアルゴリズムや手法が存在します。バブルソート バブルソートは最も古くから使われているソートアルゴリズムです。この記事で用意した基本のコードでは、2つのループを準備して、単純にリストの要素を一度に1つずつ調べ、その要素とその要素の後に続く要素とを比較し、小さい（または大きい）方の要素をリストの前方に配置します。 このアルゴリズムを使用するには2つの方法があります。どちらも正確であり、実行時間と処理の回数はほぼ同じ結果となります。1つは「後方バブルソート」です。これは、外側のループはリストの後方
PukiWiki/1.4 ※しろくろのへや:do_diffから移動してきました。 -- ぱんだ 差分表示の改造† 文書比較アルゴリズムより... 文書比較を行う問題は、２つの文書Ａ，Ｂの最長共通部分（ＬＣＳ Longuest Common Subsequence）、または最小エディット距離（ＳＥＤ Shotest Edit Distance）を求める問題と等価である。 …だそうです。なんとなく速そうだったので、PukiWikiの差分表示ルーチンをO(NP)アルゴリズムで作ってみようと思った次第で。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) difference algorithm and its variations", Algorithmixa, 1 (1986), pp.251-266 [2] S.W.
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
