利用者:Albeit-Kun/最短路検索 - 版の履歴

Albeit-Kun: /* 階層メッシュ疎化法 */

2009-11-17T12:35:36Z

階層メッシュ疎化法

Albeit-Kun: /* 階層メッシュ疎化法 */

2009-11-17T12:34:25Z

階層メッシュ疎化法

Albeit-Kun: /* 階層メッシュ疎化法 */

2009-11-17T12:33:28Z

階層メッシュ疎化法

Albeit-Kun: /* 階層メッシュ疎化法 */

2009-11-17T12:29:33Z

階層メッシュ疎化法

2009年11月17日 (火) 10:42にAlbeit-Kunによる

2009-11-17T10:42:41Z

2009年11月17日 (火) 10:18にAlbeit-Kunによる

2009-11-17T10:18:33Z

差分を表示

2009年11月17日 (火) 08:53にAlbeit-Kunによる

2009-11-17T08:53:08Z

2009年11月17日 (火) 08:52にAlbeit-Kunによる

2009-11-17T08:52:17Z

差分を表示

2009年11月17日 (火) 07:56にAlbeit-Kunによる

2009-11-17T07:56:35Z

2009年11月7日 (土) 06:33にAlbeit-Kunによる

2009-11-07T06:33:32Z

@@ 191行目: / 191行目: @@
 図2は残った枝を正方形の大きさごとに示した例である．
-<gallery caption="図2: 抽出された枝の例" widths="300px" heights="300px" perrow="2">
+<gallery caption="図2: 抽出された枝の例" widths="200px" heights="200px" perrow="2">
 画像:3-g.png
 画像:4-g.png

@@ 191行目: / 191行目: @@
 図2は残った枝を正方形の大きさごとに示した例である．
-<gallery caption="図2: 抽出された枝の例" widths="150px" heights="150px" perrow="4">
+<gallery caption="図2: 抽出された枝の例" widths="300px" heights="300px" perrow="2">
 画像:3-g.png
 画像:4-g.png

@@ 194行目: / 194行目: @@
 画像:3-g.png
 画像:4-g.png
-画像ル:5-g.png
+画像:5-g.png
 画像:6-g.png
 </gallery>

@@ 192行目: / 192行目: @@
 <gallery caption="図2: 抽出された枝の例" widths="150px" heights="150px" perrow="4">
-ファイル:3-g.png
+画像:3-g.png
-ファイル:4-g.png
+画像:4-g.png
-ファイル:5-g.png
+画像ル:5-g.png
-ファイル:6-g.png
+画像:6-g.png
 </gallery>

@@ 36行目: / 36行目: @@
 入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．
-{| border="1" style="text-align:center"
+{| border="1" style="text-align:center; margin:0 auto"
 |+ 表1: 各最短路検索手法の比較
 ! 手法 !! 検索 !! 付加データ !! 前処理
@@ 70行目: / 70行目: @@
 枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
 始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．
 : <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
@@ 102行目: / 100行目: @@
 一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
 三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
-\footnote{これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ}．
+(これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ)．
 ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
 図1にダイクストラ法およびA*法で探索される範囲の例を示す．
@@ 170行目: / 168行目: @@
 付加データの大きさはトランジットノードの数に依存し，おおむね
-<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)\text{の平均})\, </math>程度である．
+<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)</math>の平均<math>)\, </math>程度である．
 トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
 このとき付加データの大きさは入力データの数倍程度になる．
@@ 193行目: / 191行目: @@
 図2は残った枝を正方形の大きさごとに示した例である．
-<gallery caption="図2: 抽出された枝の例" widths="200px" heights="200px" perrow="4">
+<gallery caption="図2: 抽出された枝の例" widths="150px" heights="150px" perrow="4">
 ファイル:3-g.png
 ファイル:4-g.png

@@ 1行目: / 1行目: @@
 '''【さいたんろけんさく（shotest path query）】'''
@@ 23行目: / 10行目: @@
 === 最短路検索とは ===
-枝重み付きネットワーク上で始点<math>s<math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
+枝重み付きネットワーク上で始点<math>s</math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
 （本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
 最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．

@@ 1行目: / 1行目: @@
 '''【さいたんろけんさく（shotest path query）】'''
-== 概要 ==
+==概要==
 与えられたネットワーク上での2 地点間最短路検索を最短路検索とよぶ．ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

← 古い版		2009年11月7日 (土) 06:33時点における版
6行目:		6行目:

	== 詳説 ==		== 詳説 ==
		+
		+
		+	=== 最短路検索とは ===


	== 参考文献 ==		== 参考文献 ==