ORWiki - 利用者の投稿記録 [ja]

メインページ

2012-09-14T11:37:30Z

Fujimoto: 数式表示が機能するようになったのでお知らせ削除

メインページ

2012-09-14T10:44:20Z

Fujimoto: お知らせ追記

= '''OR事典Wiki''' =

OR事典Wiki [[ORWiki:ORWikiについて|ORWiki]] にようこそ！

このページは，
[https://orsj.org 公益社団法人日本オペレーションズ・リサーチ学会]
[[OR事典編集委員会]]
によって作成されております．

== 目次 ==

[[基礎編：大項目一覧|基礎編]]

[[用語編]]

[[事例編]]

[https://orsj.org/wp-content/wiki/shiryou 資料編]

== お知らせ ==
現在、ソフトウェアの更新作業に伴い、数式表示が適切に機能しない現象が発生しております。
お見苦しいところがありますが、あらかじめご了承ください。--2012年9月14日 (金) 19:44 (JST)

----
[[ORWiki:著作権|著作権]]について

----

メインページ

2012-09-10T11:39:45Z

Fujimoto:

= '''OR事典Wiki''' =

OR事典Wiki [[ORWiki:ORWikiについて|ORWiki]] にようこそ！

このページは，
[https://orsj.org 公益社団法人日本オペレーションズ・リサーチ学会]
[[OR事典編集委員会]]
によって作成されております．

== '''目　　次''' ==

[[基礎編：大項目一覧|基礎編]]

[[用語編]]

[[事例編]]

[https://orsj.org/wp-content/wiki/shiryou 資料編]

----
[[ORWiki:著作権|著作権]]について

----

待ち行列モデル M/M/c

2012-04-02T05:53:49Z

Fujimoto: /* 詳説 */ typo mu_k -> mu_i

'''【まちぎょうれつもでるえむえむしー (queueing model M/M/<math>c</math>)】'''
=== 概要 ===

ポアソン到着, 指数サービス, 窓口が <math>c\,</math> 個の待ち行列モデル. 最も基本的な待ち行列モデルの1つ. 待ち行列モデルを指して "マルコフモデル" というときは, このモデルを指していることが多い.
=== 詳説 ===
　[[待ち行列モデル M/M/c]] (queueing model M/M/<math>c\, </math>)は, 客の到着がパラメータ <math>\lambda\, </math> のポアソン過程に従い, サービス時間が平均 <math>1/\mu\, </math> の指数分布に従う, 窓口 <math>c\, </math> 個の最も基本的な待ち行列モデルである. 待ち行列理論が[[アーラン, アグナー・K|A. K. Erlang]]によって20世紀初頭に誕生したときに, 真っ先に研究の対象となったのがこのタイプのモデルであった. それ以来, モデルの簡潔さ, 公式のわかりやすさから, 代表的な待ち行列モデルとして, 常に待ち行列理論のよりどころとなり, また多方面で実際問題の解決に応用されてきている. 近年研究が進められている[[待ち行列ネットワーク]]でも, その中心となっているのはこの M/M/<math>c\, </math> モデルをネットワーク状につないだ[[ジャクソンネットワーク|ジャクソン型ネットワーク]]とそれを拡張した[[BCMPネットワーク|BCMP型ネットワーク]]であることからも, その重要性が理解できよう.

'''ポアソン到着と指数サービス'''　M/M/<math>c\, </math> モデルに関連して, いくつかの用語が慣用的に用いられている. 客の到着が[[ポアソン過程]]にしたがうとき, つまり客の到着間隔が独立で同一の指数分布に従うとき, その到着の仕方を[[ポアソン到着]] (Poisson arrival) という. この場合, 到着過程のパラメータを <math>\lambda\, </math> とすると, 長さ <math>t\, </math> の時間に到着する人数は平均 <math>\lambda t\, </math> のポアソン分布に従う. この <math>\lambda\, </math> のことを[[到着率]] (arrival rate) と呼ぶ. また, サービス時間の分布が指数分布に従うとき, サービスの仕方は[[指数サービス]] (exponential service) であるという. このとき平均サービス時間の逆数 <math>\mu\, </math> のことを[[サービス率]] (service rate) と呼ぶ.

'''マルコフ性'''　M/M/<math>c\, </math> モデルが容易に解析できるのは, 指数分布がつぎの"無記憶性"をもつことによる. 確率変数 <math>X\, </math> がパラメータ <math>\lambda\, </math> の指数分布に従っているものとしよう. すると, 任意の <math>s, t>0\, </math> に対して

<center>
<math>
\mbox{P}\{ X>s+t\mid X>s \} = \mathrm{e}^{-\lambda t} = \mbox{P}\{ X>t \}\,
\, </math>
</center>

が成り立つ. これは, 現在の状況 (<math>X>s\, </math> ということ) がわかると, 今後の確率的挙動は過去の履歴とは無関係, ということであり, この性質を[[無記憶性 (指数分布の)|無記憶性]] (memoryless property) または[[マルコフ性]] (Markov property) と呼ぶ. M/M/<math>c\, </math> などの[[ケンドールの記号]]において, ポアソン到着と指数サービスを M で表現するのは, このマルコフ性に由来する.

　M/M/<math>c\, </math> モデルでは, ポアソン到着と指数サービスの仮定から, 系内人数を状態とする[[マルコフ連鎖]]を導くことができる. このマルコフ連鎖は[[出生死滅過程]]と呼ばれる特殊な型をしており, その解析は容易である. マルコフ連鎖の一般論から, 適当な条件の下でこの出生死滅過程は時間の経過とともに[[平衡状態]]に近づく. そのため M/M/<math>c\, </math> モデルでは, 平衡状態における状態確率 (これを[[定常状態確率]] (stationary state probability) とか極限状態確率と呼ぶ) を解析的に求め, それらから[[待ち確率]], [[平均待ち時間]], [[待ち時間分布]]}, 平均[[系内人数]], 系内人数分布などの混雑の尺度を計算して, 実際のシステムの性能評価に役立てている.

'''M/M/1 モデル'''　[[待ち行列モデル M/M/1]] (queueing model M/M/1) は, <math>c=1\, </math> の場合で, ポアソン到着, 指数サービス, 単一窓口をもつ待ち行列として定義される. 定常状態確率が存在するための必要十分条件は, <math>\rho = \lambda/\mu<1\, </math> を満たすことである. そのときシステム内に<math>k\, </math>人の客がいる定常状態確率は

<center>
<math>
p_k=(1-\rho)\rho^k, \qquad k=0, 1, 2, \cdots \,
\, </math>　　　　　<math>(1)\, </math>
</center>

で与えられ, 幾何分布に従う. 窓口がサービス中である確率は <math>1-p_0=\rho\, </math> であるので, <math>\rho\, </math> を[[利用率]]と呼ぶ. これは到着した客が待たされる確率, すなわち[[待ち確率]], でもある ([[PASTA]]参照). (1) 式より, 平均系内人数は <math>L=\rho/(1-\rho)\, </math> であり, 平均待ち行列長は <math>L_q=\rho^2/(1-\rho)\, </math> である.

　待ち時間分布は <math>t=0\, </math> に <math>1-\rho\, </math> のマスをもち, <math>t>0\, </math> では指数分布型の密度をもつ

<center>
<math>
F(t)=\mbox{P}\{ \boldsymbol{W_q} \leq t \}
=\left\{ \begin{array}{ll} 0, & t<0 \\
1-\rho \mathrm{e}^{-(\mu-\lambda)t}, \qquad & t \geq 0
\end{array} \right.
\, </math>　　　　　<math>(2)\, </math>
</center>

で与えられる. この分布関数から, または[[リトルの公式]]から, 平均待ち時間は <math>W_q=L_q/\lambda=\rho/\mu(1-\rho)\, </math>, 平均系内滞在時間は <math>W=L/\lambda=1/\mu (1-\rho)\, </math> であることがわかる.

'''M/M/<math>\boldsymbol {c}\, </math> モデル'''　[[待ち行列モデル M/M/c]] は, ポアソン到着で <math>c\, </math>個 (通常は複数) の指数サービス窓口をもつモデルである. これも[[出生死滅過程]]を用いて解析できる. 客の到着率を <math>\lambda\, </math>, 平均サービス時間を <math>1/\mu\, </math> とすると, 平衡状態が存在するための条件は <math>\rho=\lambda/c \mu < 1\, </math> である. 系内に <math>c\, </math> 人以上の客がいるときはすべての窓口がサービス中なので, 短い時間 <math>dt\, </math> の間にいずれかのサービスが終了する確率は <math>c \mu \, dt\, </math> であり, 系内にいる客の数が <math>k\, </math> 人 (<math>k<c\, </math>) のときは, <math>k\, </math> 個の窓口でサービスを行っているだけなので, この確率は <math>k\mu \, dt\, </math> である. そこで

<center>
<math>
\mu_k=\left\{
\begin{array}{ll}
k\mu, & \qquad k=0, 1, \cdots, c-1 \\
c\mu, & \qquad k=c, c+1, \cdots
\end{array} \right.
\, </math>　　　　　<math>(3)\, </math>
</center>

とおけば, <math>dt\, </math> の間に一人の客が到着する確率が <math>\lambda \, dt\, </math> であることから, 平衡状態において <math>k\, </math> 人の客がいる確率は

<center>
<math>
p_k=p_0 \prod_{i=1}^k \frac{\lambda}{\mu_i}, \qquad k=1, 2, \cdots
\, </math>　　　　　<math>(4)\, </math>
</center>

で与えられる. ここで <math>p_0\, </math> は, (4) の <math>p_k\, </math> の和が 1 となるよう

<center>
<math>
p_0 = \left[\sum_{k=0}^{c-1} \frac{c^k \rho^k}{k!}
+\frac{c^c \rho^c}{c! \, (1-\rho)}\right]^{-1}
\, </math>　　　　　<math>(5)\, </math>
</center>

で与えられる. 安定性の条件 <math>\rho<1\, </math> は, (4) の <math>p_k\, </math> の和が有限の値に収束するための条件となっていることに注意しよう. この <math>\rho\, </math> は各窓口がサービス中の時間の割合になっており, やはり利用率と呼ばれる. すべての窓口がふさがっている確率は,

<center>
<math>
\Pi=\sum_{k=c}^\infty p_k = \frac{c^c \rho^c}{c! \, (1-\rho)} p_0
\, </math>　　　　　<math>(6)\, </math>
</center>

であり, PASTA よりこれが待ち確率でもある. 待ち時間分布は

<center>
<math>
\mbox{P}\{ \boldsymbol{W_q} \leq t\} = \left\{ \begin{array}{ll}
0 , & t <0 \\
1 - \Pi \, \mathrm{e}^{-c \mu(1-\rho)t}, \quad & t \geq 0
\end{array} \right.
\, </math>　　　　　<math>(7)\, </math>
</center>

で与えられ, 平均待ち時間は <math>W_q= \Pi / c \mu (1 - \rho)\, </math> である.

'''M/M/<math>\boldsymbol {c/c}\, </math>モデル'''　[[待ち行列モデル M/M/c/c]] (queueing model M/M/<math>c\, </math>/<math>c\, </math>) は, ポアソン到着で, <math>c\, </math>個の指数サービス窓口があるが, 待合室が無く, 客が待つことができない待ち行列である. 客が到着したときに, 空いた窓口がある場合には直ちにサービスを受けるが, すべての窓口が塞がっている場合にはサービスを受けることなく立ち去る. このようにサービスを受けずに立ち去る客がある待ち行列モデルは損失系と呼ばれ, 電話回線などのトラフィック理論でしばしば利用される. このときサービスを受けずに立ち去る客の割合を[[呼損率]] (loss probability) という.

　到着率を <math>\lambda\, </math>, 平均サービス時間を <math>1/\mu\, </math> とすると, 定常状態確率は (3) を用いて (4) で与えられる. ただし, 今度の場合, とりうる状態は <math>k=0, 1, 2, \ldots , c\, </math> だけであるので, <math>p_0\, </math> は

<center>
<math>
p_0 = \left[\, \sum_{k=0}^{c}
\frac{1}{k!}\left(\frac{\lambda}{\mu}\right)^k \right]^{-1}
\, </math>　　　　　<math>(8)\, </math>
</center>

で与えられ, たとえ <math>\rho=\lambda/c \mu<1\, </math> でなくてもシステムは安定的である. PASTA の性質により, 呼損率は系内にちょうど <math>c\, </math> 人の客がいる確率

<center>
<math>
p_c=\frac{1}{c!} \left(\frac{\lambda}{\mu}\right)^c p_0
\, </math>　　　　　<math>(9)\, </math>
</center>

と等しい. この式は[[アーランの損失式]] (Erlang's loss formula) と呼ばれ, 損失系の性能評価で最も重要な特性量のひとつである. なお, この式は M/G/<math>c\, </math>/<math>c\, </math> モデル, すなわち一般サービスのときでも成り立つことが知られている.

----
'''参考文献'''

[1] L. Kleinrock, ''Queueing Systems Vol. 1 Theory,'' Wiley, New York, 1975.

[2] 森村英典, 大前義次, 『応用待ち行列理論』, 日科技連, 1975.

[3] 尾崎俊治, 『確率モデル入門』, 朝倉書店, 1996.

[4] S. M. Ross, ''Stocastic Processes,'' Wiley, New York, 1980.

[[category:確率と確率過程|まちぎょうれつもでるえむえむしー]]

[[category:待ち行列|まちぎょうれつもでるえむえむしー]]

利用者:Fujimoto/最短路問題

2009-11-05T07:51:07Z

Fujimoto: 数式修正（すべて画像に置換されるよう）

'''【さいたんろもんだい (shortest path problem)】'''

== 概要 ==


最短路問題は経路探索などの多くの応用を持ち, また他の[[最適化問題]]の子問題として用いられることも多く, 適用範囲の広い組合せ最適化問題である. そのため, 最短路問題を高速に解くことは重要な意味を持つ. 最短路問題に対する解法には, 安定的かつ効率的な高速な[[アルゴリズム]]が存在するが, 実問題は大規模(全米の道路ネットワークでは, 2400万点, 5800万枝にも及ぶ)になるため高速化が不可欠である.本解説では最短路問題の定義・種類を述べた後, 著名なアルゴリズムである[[ダイクストラ法]]に対する高速実装と実験結果<ref>安井雄一郎, 藤澤克樹, 笹島啓史, 後藤和茂, 宮本裕一郎, "大規模最短路問題に対するダイクストラ法の高速化," 2008 年度日本 OR 学会秋季研究発表会. 314-315, 2008.</ref>等について説明を行う.

== 詳説 ==

=== 最短路問題の定義と種類 ===
最短路問題は次のような問題である.


<blockquote>
ある有向グラフ<math>G = (V, E)\, </math> と各枝 <math>(v,w) \in E\, </math> に重み <math>l(v,w)\, </math> が付与されているネットワーク <math>N = (G,l)\, </math> が与えられているとする. このとき有向グラフ <math>G\, </math> の任意の 2 点 <math>s, t \in V\, </math> に対し, 点 <math>s\, </math> を始点とし, 点 <math>t\, </math> を終点とする有向パス <math>p\, </math> の中で, その長さ(パスに含まれる枝の重みの合計)が最小のパスを点 <math>s\, </math> から点 <math>t\, </math> への最短路 (shortest path) といい, 最短路を求める問題を最短路問題 (shortest path problem) という.
</blockquote>

最短路問題は次のように 3 種類に分けることができる.

;1対全(single-source)最短路問題: 1点から全点に対する最短路と最短距離(最短路の長さ)を求める問題. 非負の枝の重みを持つグラフ上ではダイクストラ(Dijkstra)法が, 負の重みを持つ枝がある場合にはベルマン・フォード(Bellman-Ford)法が有名である.
;全対全(all-pairs)最短路問題: 全点間の最短路と最短距離を求める問題. ワーシャル・フロイド(Warshall-Folyd)法が有名であるが, 1対全最短路問題アルゴリズムを各点に対して適用することでも求めることができる.
;1対1(point-to-point)最短路問題: 2点間の最短路と最短距離を求める問題.

=== 探索アルゴリズムと実装方法 ===

最短路問題に関する探索アルゴリズムの中でも, 最も頻繁に利用されるダイクストラ法を取り上げ, アルゴリズムの説明から, 高速化のための優先キューの適用方法・実装方法について示していく.

==== ダイクストラ法 ====

1959年, E. W. Dijkstra<ref name="dijkstra">E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, 1:269-271, 1959.</ref>によって提案された1対全最短路問題に対するアルゴリズムである. 探索するグラフ上の全ての枝の重みが非負でなければならないが, ベルマン・フォード法<ref>R. E. Bellman, "On a Routing Problem," Quarterly of Applied Mathematics, 16:87-90, 1958.</ref>に比べ効率的かつ高速である.ダイクストラ法は, ベルマン・フォード法と同じように動的計画法の一種とみなすことができるが, 点の探索の順序に特徴をもつ. 探索の途中で得られた始点 <math>s\, </math> からの距離の最小値をポテンシャルもしくは距離ラベルとよび, その値の小さい順に点の探索を行い,最短路および最短距離を確定していく. つまり, 各点に対し, <math>d(s) = 0, d(v) = +\infty (v \in V)\, </math> とするポテンシャル <math>d\, </math> を用意し, 探索点 <math>v\, </math> に接続する枝 <math>(v,w)\, </math> に対して, <math>d(v) + l(v,w) < d(w)\, </math> ならば <math>d(w) := l(v,w) + d(v)\, </math> とする操作を繰り返し行う. 終点 <math>t\, </math> が探索点になった時点で終了させることで, 1対1最短路問題も効率的に求解可能である.

===== ダイクストラ法のアルゴリズム =====

1: ポテンシャル <math>d\, </math>の初期設定
2: <math>S := V\, </math>
3: '''while''' <math>S \neq \emptyset</math> '''do'''
4: <math>d(v)\, </math> が最小の点 <math>v \in S\, </math> を選択
5: <math>S := S \backslash \left\{ v \right\}\, </math>
6: '''for all''' <math>(v, w)\, </math> '''do'''
7: '''if''' <math>d(v) +l(v,w) < d(w)\, </math> '''then'''
8: <math>d(w) := d(v) +l(v,w)\, </math>
9: '''end if'''
10: '''end for'''
11: '''end while'''

==== 高速化のための優先キューの利用 ====
ダイクストラ法は, 効率的かつ高速なアルゴリズムだが, 探索点を決定する操作([[#ダイクストラ法のアルゴリズム|アルゴリズム]]中の4行目,5行目)が, ボトルネックであることが知られている<ref name="dijkstra" />. 探索候補点集合(アルゴリズム中の<math>S\, </math>)に対して優先キューを適用することで, 改善できる.

==== 優先キューの実装方法 ====
優先キューとは, データを優先度によって操作するデータ構造のことである. ダイクストラ法に適用する優先キューは,<code>insert</code>, <code>decrease-key</code>, <code>extract-min</code>と呼ばれる操作に対応している必要がある.
;<code>insert</code>: ポテンシャル<math>d(v)\, </math>を優先度として, 点<math>v \in V\, </math>を優先キュー<math>Q\, </math>へ挿入する.
;<code>decrease-key</code>: 優先キュー内に格納されている点 <math>v \in Q\, </math>の優先度<math>d(v)\, </math>を, <math>d'(v)\, </math>に更新する.
;<code>extract-min</code>: 優先度<math>d(v)\, </math>が最小である点<math>v \in Q\, </math>を取り出し, 点<math>v\, </math>を次探索点とする.
ダイクストラ法では, 繰り返しこれらの操作を行うことになるため, より効率的なものを適用することで, 高速化が可能になる.

==== データ構造の選択 ====
優先キューは, 木構造による安定した実行が可能なヒープ系データ構造と, データをルールに従いバケットに格納するバケット系データ構造とに分類が可能である. ここでは, それぞれの最も基本的なデータ構造であるバイナリ・ヒープと1レベル・バケットに加え, 実験的に最も高速であるといわれているマルチレベル・バケットを取り上げ, 比較を行う.

===== 2-heap(バイナリ・ヒープ) =====
2-heap<ref name="heap">J. Williams, "Heapsort," Communications of the ACM, 7:347-348, 1964.</ref>は, 図1のように, 親は高々2つの子を持つ木構造で構成される. 常に親の優先度は子より高い. 点数 <math>n\, </math>, 枝数 <math>m\, </math>に対して, 1対全最短路問題の計算量は <math>O((m+n)\log{n})\, </math> である.

{| border="1" style="text-align:center; margin:0 auto"
|-
! Index
| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14
|-
! Data
| 1 || 2 || 4 || 3 || 2 || 5 || 6 || 6 || 4 || 3 || 5 || 8 || 6 || 7 || 9
|}

[[画像:heap-2.png|thumb|center|300px|図1: バイナリ・ヒープの例]]

2-heapは以下の特徴をもつ.
#木構造により実行性能が安定している.
#メモリ要求量が大変少なく, データの局所性を高めやすい.
#木構造のためデータの読み書きが多発するので,データ交換操作がボトルネックとなりやすい.

===== Buckets(1 レベル・バケット)=====
Buckets<ref name="dial">R. B. Dial, "Algorithm 360: Shortest Path Forest with Topological Ordering, " Comm. ACM, 12:632-633, 1969.</ref>は, 最大枝長 <math>U\, </math>に対し, <math>U+1\, </math>個のバケットの循環リストとして構成される (図2). 点 <math>v\, </math>のポテンシャル<math>d(v)\, </math>に対し, <math>d(v)\mod(U+1)\, </math>により操作するバケットを決定する. 各バケット内のデータは双方向リストで結ばれており, 同一バケット内に格納されている点の優先度は常に等しい. 1対全最短路問題の計算量は, 点数<math>n\,</math>, 枝数<math>m\, </math>, 最大枝長<math>U\, </math>に対し, <math>O(m+nU)\, </math>である.

#実行時間・メモリ要求量が, 最大枝長に依存する(重み小:高速, 重み大:低速).
#道路ネットワークグラフと相性が良い.

[[画像:buckets-2.png|thumb|center|250px|図2: 1レベル・バケットの例]]

===== MLB(マルチレベル・バケット) =====
MLB(Multi-Level Buckets)<ref name="mlb">A. V. Goldberg, "A Simple Shortest Path Algorithm with Linear Average Time," Technical Report STAR-TR-01-03, STAR Lab., InterTrust Tech., Inc., Santa Clara, CA, USA. 2001.</ref>は, ヒープ系優先キュー, バケット系優先キューの双方の有効な特性を融合させた優先キューである. グラフ特性の影響は小さく安定かつ高速であるが, 非常にメモリ要求量が大きい. 1レベル・バケットとは異なり,MLBではバケットは <math>\lceil \log{U} \rceil + 1\, </math>だけ用意すればよい. 点数 <math>n\, </math>, 枝数 <math>m\, </math>, 最大枝長 <math>U\, </math>に対し, 1対全最短路問題の計算量は<math>O(m + n\log{U})\, </math>となる.

#グラフ特性の影響は小さく, 安定かつ高速
#バケットを決定には高速なビット演算で行う
#メモリ要求量が非常に大きい

=====優先キューの比較=====
点数 <math>n\, </math>, 枝数<math>m\, </math>, 最大枝数 <math>U\, </math>であるグラフに対して, 計算量をまとめると表1のようになる.1対全最短路問題では, 枝数分の<code>insert</code>と<code>decrease-key</code>, 点数分の<code>extract-min</code>を行うことになる.また, その特性は図3となる. これは, 比較的小さいグラフに対し, 各枝長を<math>2^{t} (t=[-10,-9,..,9,10])\, </math>倍し, 計算機実験を行った結果である. Buckets の特性がよく表れている.

{| border="1" style="text-align:center"
|+ 表1: 優先キューの計算量
! !! <code>insert</code> !! <code>decrease-key</code> !! <code>extract-min</code> !! 1対全最短路問題の計算量
|-
! 2-heap
| <math>O(\log{n})\, </math> || <math>O(\log{n})\, </math> || <math>O(\log{n}) \, </math> || <math>O((n+m)\log{n})\, </math>
|-
! Buckets
| <math>O(1)\, </math> || <math>O(1)\, </math> || <math>O(U)\, </math> || <math>O(m+nU)\, </math>
|-
! MLB
| <math>O(1)\, </math> || <math>O(1)\, </math> || <math>O(\log{U})\, </math> || <math>O(m+n\log{U})\, </math>
|}

[[画像:length-scaling2.png|thumb|center|500px|図3: 優先キューの特性]]

====優先キューの性能====
2-heap, Buckets, MLB それぞれの全米道路ネットワークに対しての計算機実験を行い, 実行時間とメモリ要求量をまとめると,表2, 表3のようになる. 用いたグラフデータは, 約 2400 万点, 約 5800 万枝にも及ぶ道路ネットワークを変換させた大規模な実データである(TIGER/Line<ref>http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html</ref>で公開されている). 実行時間は, ランダムに選択した1対1最短路問題を 256 回解いた際の平均である.

最短路問題では計算量に対してデータ量が大規模であるため, データ型によるメモリ使用量や実行時間に対する影響が大きい. 各変数が 32ビット整数型と 64ビット変数型の 2 種類の計算機実験の結果を記載する. グラフデータは大規模であるが, 32ビット整数型の範囲で収まるため, どちらの場合でもアルゴリズムは正しく終了するが, 距離ラベルはいずれも 64ビット整数である.

{| border="1" style="text-align:center"
|+ 表2: 全米グラフの実行時間(単位は秒)
! !! 32ビット整数型 !! 64ビット整数型
|-
! 2-heap
| 2.47 || 3.14
|-
! Buckets
| 1.68 || 2.28
|-
! MLB
| 2.63 || 2.65
|}

{| border="1" style="text-align:center"
|+ 表3: 全米グラフのメモリ要求量(単位はGB)
! !! 32ビット整数型 !! 64ビット整数型
|-
! 2-heap
| 1.27 || 1.99
|-
! Buckets
| 1.09 || 1.62
|-
! MLB
| 2.17 || 2.17
|}

===大規模最短路問題に対する高速処理システム===
現在では Web 上で最短経路を求めるサービスが複数行われている(Google Maps<ref>http://maps.google.com/</ref>や最短路問題オンラインソルバー<ref>http://opt.indsys.chuo-u.ac.jp/portal/</ref>など).

これらのシステムでは, 多くのユーザからの要求に対応する必要があるので, 単にダイクストラ法実行1回の処理を高速化するだけでなく, それらを並列に高速処理する技術が必要である.

ユーザからの要求量は時間帯や突発的な事象によって大きく変動するため, 最大需要を見越した計算資源を保有しておくのは無駄が多くコストも増大してしまう. そこでクラウド・コンピューティング技術を用いて, 高負荷時には自動的に計算機資源の増大を行うシステムなどが必要になってくる.

最近ではカーナビゲーション・システムの拡張として渋滞・事故情報をリアルタイムに把握しながら集約された大規模サーバで最短路を探索してユーザに結果を送信するシステムも構築されている. 動的な情報を考慮した最短路探索を行うことにより, これまでの経路探索に比べてより精度を向上させることができる. 特定の道路への集中を防ぐように交通量の分散を行うことで, 渋滞の緩和, 事故発生率の低下, 排出ガスの削減などを目指した交通管制を行うことも可能になると予想されている.

== 参考文献 ==
<references />

利用者:Fujimoto/最短路問題

2009-10-21T11:49:05Z

Fujimoto: URL誤りを訂正

'''【さいたんろもんだい (shortest path problem)】'''

== 概要 ==


最短路問題は経路探索などの多くの応用を持ち, また他の[[最適化問題]]の子問題として用いられることも多く, 適用範囲の広い組合せ最適化問題である. そのため, 最短路問題を高速に解くことは重要な意味を持つ. 最短路問題に対する解法には, 安定的かつ効率的な高速な[[アルゴリズム]]が存在するが, 実問題は大規模(全米の道路ネットワークでは, 2400万点, 5800万枝にも及ぶ)になるため高速化が不可欠である.本解説では最短路問題の定義・種類を述べた後, 著名なアルゴリズムである[[ダイクストラ法]]に対する高速実装と実験結果<ref>安井雄一郎, 藤澤克樹, 笹島啓史, 後藤和茂, 宮本裕一郎, "大規模最短路問題に対するダイクストラ法の高速化," 2008 年度日本 OR 学会秋季研究発表会. 314-315, 2008.</ref>等について説明を行う.

== 詳説 ==

=== 最短路問題の定義と種類 ===
最短路問題は次のような問題である.


<blockquote>
ある有向グラフ<math>G = (V, E)</math> と各枝 <math>(v,w) \in E</math> に重み <math>l(v,w)</math> が付与されているネットワーク <math>N = (G,l)</math> が与えられているとする. このとき有向グラフ <math>G</math> の任意の 2 点 <math>s, t \in V</math> に対し, 点 <math>s</math> を始点とし, 点 <math>t</math> を終点とする有向パス <math>p</math> の中で, その長さ(パスに含まれる枝の重みの合計)が最小のパスを点 <math>s</math> から点 <math>t</math> への最短路 (shortest path) といい, 最短路を求める問題を最短路問題 (shortest path problem) という.
</blockquote>

最短路問題は次のように 3 種類に分けることができる.

;1対全(single-source)最短路問題: 1点から全点に対する最短路と最短距離(最短路の長さ)を求める問題. 非負の枝の重みを持つグラフ上ではダイクストラ(Dijkstra)法が, 負の重みを持つ枝がある場合にはベルマン・フォード(Bellman-Ford)法が有名である.
;全対全(all-pairs)最短路問題: 全点間の最短路と最短距離を求める問題. ワーシャル・フロイド(Warshall-Folyd)法が有名であるが, 1対全最短路問題アルゴリズムを各点に対して適用することでも求めることができる.
;1対1(point-to-point)最短路問題: 2点間の最短路と最短距離を求める問題.

=== 探索アルゴリズムと実装方法 ===

最短路問題に関する探索アルゴリズムの中でも, 最も頻繁に利用されるダイクストラ法を取り上げ, アルゴリズムの説明から, 高速化のための優先キューの適用方法・実装方法について示していく.

==== ダイクストラ法 ====

1959年, E. W. Dijkstra<ref name="dijkstra">E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, 1:269-271, 1959.</ref>によって提案された1対全最短路問題に対するアルゴリズムである. 探索するグラフ上の全ての枝の重みが非負でなければならないが, ベルマン・フォード法<ref>R. E. Bellman, "On a Routing Problem," Quarterly of Applied Mathematics, 16:87-90, 1958.</ref>に比べ効率的かつ高速である.ダイクストラ法は, ベルマン・フォード法と同じように動的計画法の一種とみなすことができるが, 点の探索の順序に特徴をもつ. 探索の途中で得られた始点 <math>s</math> からの距離の最小値をポテンシャルもしくは距離ラベルとよび, その値の小さい順に点の探索を行い,最短路および最短距離を確定していく. つまり, 各点に対し, <math>d(s) = 0, d(v) = +\infty (v \in V)</math> とするポテンシャル <math>d</math> を用意し, 探索点 <math>v</math> に接続する枝 <math>(v,w)</math> に対して, <math>d(v) + l(v,w) < d(w)</math> ならば <math>d(w) := l(v,w) + d(v)</math> とする操作を繰り返し行う. 終点 <math>t</math> が探索点になった時点で終了させることで, 1対1最短路問題も効率的に求解可能である.

===== ダイクストラ法のアルゴリズム =====

1: ポテンシャル ''d'' の初期設定
2: ''S'' := ''V''
3: '''while''' <math>S \neq \emptyset</math> '''do'''
4: <math>d(v)</math> が最小の点 <math>v \in S</math> を選択
5: ''S'' := <math>S \backslash \left\{ v \right\}</math>
6: '''for all''' (''v'', ''w'') '''do'''
7: '''if''' <math>d(v) +l(v,w) < d(w)</math> '''then'''
8: <math>d(w) := d(v) +l(v,w)</math>
9: '''end if'''
10: '''end for'''
11: '''end while'''

==== 高速化のための優先キューの利用 ====
ダイクストラ法は, 効率的かつ高速なアルゴリズムだが, 探索点を決定する操作([[#ダイクストラ法のアルゴリズム|アルゴリズム]]中の4行目,5行目)が, ボトルネックであることが知られている<ref name="dijkstra" />. 探索候補点集合(アルゴリズム中の''S'')に対して優先キューを適用することで, 改善できる.

==== 優先キューの実装方法 ====
優先キューとは, データを優先度によって操作するデータ構造のことである. ダイクストラ法に適用する優先キューは,<code>insert</code>, <code>decrease-key</code>, <code>extract-min</code>と呼ばれる操作に対応している必要がある.
;<code>insert</code>: ポテンシャル<math>d(v)</math>を優先度として, 点<math>v \in V</math>を優先キュー''Q''へ挿入する.
;<code>decrease-key</code>: 優先キュー内に格納されている点 <math>v \in Q</math>の優先度<math>d(v)</math>を, <math>d'(v)</math>に更新する.
;<code>extract-min</code>: 優先度<math>d(v)</math>が最小である点<math>v \in Q</math>を取り出し, 点''v''を次探索点とする.
ダイクストラ法では, 繰り返しこれらの操作を行うことになるため, より効率的なものを適用することで, 高速化が可能になる.

==== データ構造の選択 ====
優先キューは, 木構造による安定した実行が可能なヒープ系データ構造と, データをルールに従いバケットに格納するバケット系データ構造とに分類が可能である. ここでは, それぞれの最も基本的なデータ構造であるバイナリ・ヒープと1レベル・バケットに加え, 実験的に最も高速であるといわれているマルチレベル・バケットを取り上げ, 比較を行う.

===== 2-heap(バイナリ・ヒープ) =====
2-heap<ref name="heap">J. Williams, "Heapsort," Communications of the ACM, 7:347-348, 1964.</ref>は, 図1のように, 親は高々2つの子を持つ木構造で構成される. 常に親の優先度は子より高い. 点数 ''n'', 枝数 ''m'' に対して, 1対全最短路問題の計算量は <math>O((m+n)\log{n})</math> である.

{| border="1" style="text-align:center; margin:0 auto"
|-
! Index
| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14
|-
! Data
| 1 || 2 || 4 || 3 || 2 || 5 || 6 || 6 || 4 || 3 || 5 || 8 || 6 || 7 || 9
|}

[[画像:heap-2.png|thumb|center|300px|図1: バイナリ・ヒープの例]]

2-heapは以下の特徴をもつ.
#木構造により実行性能が安定している.
#メモリ要求量が大変少なく, データの局所性を高めやすい.
#木構造のためデータの読み書きが多発するので,データ交換操作がボトルネックとなりやすい.

===== Buckets(1 レベル・バケット)=====
Buckets<ref name="dial">R. B. Dial, "Algorithm 360: Shortest Path Forest with Topological Ordering, " Comm. ACM, 12:632-633, 1969.</ref>は, 最大枝長''U''に対し, <math>U+1</math>個のバケットの循環リストとして構成される (図2). 点''v''のポテンシャル<math>d(v)</math>に対し, <math>d(v)\mod(U+1)</math>により操作するバケットを決定する. 各バケット内のデータは双方向リストで結ばれており, 同一バケット内に格納されている点の優先度は常に等しい. 1対全最短路問題の計算量は, 点数''n'', 枝数''m'', 最大枝長''U''に対し, <math>O(m+nU)</math>である.

#実行時間・メモリ要求量が, 最大枝長に依存する(重み小:高速, 重み大:低速).
#道路ネットワークグラフと相性が良い.

[[画像:buckets-2.png|thumb|center|250px|図2: 1レベル・バケットの例]]

===== MLB(マルチレベル・バケット) =====
MLB(Multi-Level Buckets)<ref name="mlb">A. V. Goldberg, "A Simple Shortest Path Algorithm with Linear Average Time," Technical Report STAR-TR-01-03, STAR Lab., InterTrust Tech., Inc., Santa Clara, CA, USA. 2001.</ref>は, ヒープ系優先キュー, バケット系優先キューの双方の有効な特性を融合させた優先キューである. グラフ特性の影響は小さく安定かつ高速であるが, 非常にメモリ要求量が大きい. 1レベル・バケットとは異なり,MLBではバケットは <math>\lceil \log{U} \rceil + 1</math>だけ用意すればよい. 点数''n'', 枝数''m'', 最大枝長''U''に対し, 1対全最短路問題の計算量は<math>O(m + n\log{U})</math>となる.

#グラフ特性の影響は小さく, 安定かつ高速
#バケットを決定には高速なビット演算で行う
#メモリ要求量が非常に大きい

=====優先キューの比較=====
点数''n'', 枝数''m'', 最大枝数''U''であるグラフに対して, 計算量をまとめると表1のようになる.1対全最短路問題では, 枝数分の<code>insert</code>と<code>decrease-key</code>, 点数分の<code>extract-min</code>を行うことになる.また, その特性は図3となる. これは, 比較的小さいグラフに対し, 各枝長を<math>2^{t} (t=[-10,-9,..,9,10])</math>倍し, 計算機実験を行った結果である. Buckets の特性がよく表れている.

{| border="1" style="text-align:center"
|+ 表1: 優先キューの計算量
! !! <code>insert</code> !! <code>decrease-key</code> !! <code>extract-min</code> !! 1対全最短路問題の計算量
|-
! 2-heap
| <math>O(\log{n})</math> || <math>O(\log{n})</math> || <math>O(\log{n}) </math> || <math>O((n+m)\log{n})</math>
|-
! Buckets
| <math>O(1)</math> || <math>O(1)</math> || <math>O(U)</math> || <math>O(m+nU)</math>
|-
! MLB
| <math>O(1)</math> || <math>O(1)</math> || <math>O(\log{U})</math> || <math>O(m+n\log{U})</math>
|}

[[画像:length-scaling2.png|thumb|center|500px|図3: 優先キューの特性]]

====優先キューの性能====
2-heap, Buckets, MLB それぞれの全米道路ネットワークに対しての計算機実験を行い, 実行時間とメモリ要求量をまとめると,表2, 表3のようになる. 用いたグラフデータは, 約 2400 万点, 約 5800 万枝にも及ぶ道路ネットワークを変換させた大規模な実データである(TIGER/Line<ref>http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html</ref>で公開されている). 実行時間は, ランダムに選択した1対1最短路問題を 256 回解いた際の平均である.

最短路問題では計算量に対してデータ量が大規模であるため, データ型によるメモリ使用量や実行時間に対する影響が大きい. 各変数が 32ビット整数型と 64ビット変数型の 2 種類の計算機実験の結果を記載する. グラフデータは大規模であるが, 32ビット整数型の範囲で収まるため, どちらの場合でもアルゴリズムは正しく終了するが, 距離ラベルはいずれも 64ビット整数である.

{| border="1" style="text-align:center"
|+ 表2: 全米グラフの実行時間(単位は秒)
! !! 32ビット整数型 !! 64ビット整数型
|-
! 2-heap
| 2.47 || 3.14
|-
! Buckets
| 1.68 || 2.28
|-
! MLB
| 2.63 || 2.65
|}

{| border="1" style="text-align:center"
|+ 表3: 全米グラフのメモリ要求量(単位はGB)
! !! 32ビット整数型 !! 64ビット整数型
|-
! 2-heap
| 1.27 || 1.99
|-
! Buckets
| 1.09 || 1.62
|-
! MLB
| 2.17 || 2.17
|}

===大規模最短路問題に対する高速処理システム===
現在では Web 上で最短経路を求めるサービスが複数行われている(Google Maps<ref>http://maps.google.com/</ref>や最短路問題オンラインソルバー<ref>http://opt.indsys.chuo-u.ac.jp/portal/</ref>など).

これらのシステムでは, 多くのユーザからの要求に対応する必要があるので, 単にダイクストラ法実行1回の処理を高速化するだけでなく, それらを並列に高速処理する技術が必要である.

ユーザからの要求量は時間帯や突発的な事象によって大きく変動するため, 最大需要を見越した計算資源を保有しておくのは無駄が多くコストも増大してしまう. そこでクラウド・コンピューティング技術を用いて, 高負荷時には自動的に計算機資源の増大を行うシステムなどが必要になってくる.

最近ではカーナビゲーション・システムの拡張として渋滞・事故情報をリアルタイムに把握しながら集約された大規模サーバで最短路を探索してユーザに結果を送信するシステムも構築されている. 動的な情報を考慮した最短路探索を行うことにより, これまでの経路探索に比べてより精度を向上させることができる. 特定の道路への集中を防ぐように交通量の分散を行うことで, 渋滞の緩和, 事故発生率の低下, 排出ガスの削減などを目指した交通管制を行うことも可能になると予想されている.

== 参考文献 ==
<references />

利用者:Fujimoto/最短路問題

2009-10-16T12:05:43Z

Fujimoto: 画像追加、ひとまず完成

'''【さいたんろもんだい (shortest path problem)】'''

== 概要 ==


最短路問題は経路探索などの多くの応用を持ち, また他の[[最適化問題]]の子問題として用いられることも多く, 適用範囲の広い組合せ最適化問題である. そのため, 最短路問題を高速に解くことは重要な意味を持つ. 最短路問題に対する解法には, 安定的かつ効率的な高速な[[アルゴリズム]]が存在するが, 実問題は大規模(全米の道路ネットワークでは, 2400万点, 5800万枝にも及ぶ)になるため高速化が不可欠である.本解説では最短路問題の定義・種類を述べた後, 著名なアルゴリズムである[[ダイクストラ法]]に対する高速実装と実験結果等について説明を行う.

== 詳説 ==

=== 最短路問題の定義と種類 ===
最短路問題は次のような問題である.


<blockquote>
ある有向グラフ<math>G = (V, E)</math> と各枝 <math>(v,w) \in E</math> に重み <math>l(v,w)</math> が付与されているネットワーク <math>N = (G,l)</math> が与えられているとする. このとき有向グラフ <math>G</math> の任意の 2 点 <math>s, t \in V</math> に対し, 点 <math>s</math> を始点とし, 点 <math>t</math> を終点とする有向パス <math>p</math> の中で, その長さ(パスに含まれる枝の重みの合計)が最小のパスを点 <math>s</math> から点 <math>t</math> への最短路 (shortest path) といい, 最短路を求める問題を最短路問題 (shortest path problem) という.
</blockquote>

最短路問題は次のように 3 種類に分けることができる.

;1対全(single-source)最短路問題: 1点から全点に対する最短路と最短距離(最短路の長さ)を求める問題. 非負の枝の重みを持つグラフ上ではダイクストラ(Dijkstra)法が, 負の重みを持つ枝がある場合にはベルマン・フォード(Bellman-Ford)法が有名である.
;全対全(all-pairs)最短路問題: 全点間の最短路と最短距離を求める問題. ワーシャル・フロイド(Warshall-Folyd)法が有名であるが, 1対全最短路問題アルゴリズムを各点に対して適用することでも求めることができる.
;1対1(point-to-point)最短路問題: 2点間の最短路と最短距離を求める問題.

=== 探索アルゴリズムと実装方法 ===

最短路問題に関する探索アルゴリズムの中でも, 最も頻繁に利用されるダイクストラ法を取り上げ, アルゴリズムの説明から, 高速化のための優先キューの適用方法・実装方法について示していく.

==== ダイクストラ法 ====

1959年, E. W. Dijkstra<ref name="dijkstra">E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, 1:269-271, 1959.</ref>によって提案された1対全最短路問題に対するアルゴリズムである. 探索するグラフ上の全ての枝の重みが非負でなければならないが, ベルマン・フォード法<ref>R. E. Bellman, "On a Routing Problem," Quarterly of Applied Mathematics, 16:87-90, 1958.</ref>に比べ効率的かつ高速である.ダイクストラ法は, ベルマン・フォード法と同じように動的計画法の一種とみなすことができるが, 点の探索の順序に特徴をもつ. 探索の途中で得られた始点 <math>s</math> からの距離の最小値をポテンシャルもしくは距離ラベルとよび, その値の小さい順に点の探索を行い,最短路および最短距離を確定していく. つまり, 各点に対し, <math>d(s) = 0, d(v) = +\infty (v \in V)</math> とするポテンシャル <math>d</math> を用意し, 探索点 <math>v</math> に接続する枝 <math>(v,w)</math> に対して, <math>d(v) + l(v,w) < d(w)</math> ならば <math>d(w) := l(v,w) + d(v)</math> とする操作を繰り返し行う. 終点 <math>t</math> が探索点になった時点で終了させることで, 1対1最短路問題も効率的に求解可能である.

===== ダイクストラ法のアルゴリズム =====

1: ポテンシャル ''d'' の初期設定
2: ''S'' := ''V''
3: '''while''' <math>S \neq \emptyset</math> '''do'''
4: <math>d(v)</math> が最小の点 <math>v \in S</math> を選択
5: ''S'' := <math>S \backslash \left\{ v \right\}</math>
6: '''for all''' (''v'', ''w'') '''do'''
7: '''if''' <math>d(v) +l(v,w) < d(w)</math> '''then'''
8: <math>d(w) := d(v) +l(v,w)</math>
9: '''end if'''
10: '''end for'''
11: '''end while'''

==== 高速化のための優先キューの利用 ====
ダイクストラ法は, 効率的かつ高速なアルゴリズムだが, 探索点を決定する操作([[#ダイクストラ法のアルゴリズム|アルゴリズム]]中の4行目,5行目)が, ボトルネックであることが知られている<ref name="dijkstra" />. 探索候補点集合(アルゴリズム中の''S'')に対して優先キューを適用することで, 改善できる.

==== 優先キューの実装方法 ====
優先キューとは, データを優先度によって操作するデータ構造のことである. ダイクストラ法に適用する優先キューは,<code>insert</code>, <code>decrease-key</code>, <code>extract-min</code>と呼ばれる操作に対応している必要がある.
;<code>insert</code>: ポテンシャル<math>d(v)</math>を優先度として, 点<math>v \in V</math>を優先キュー''Q''へ挿入する.
;<code>decrease-key</code>: 優先キュー内に格納されている点 <math>v \in Q</math>の優先度<math>d(v)</math>を, <math>d'(v)</math>に更新する.
;<code>extract-min</code>: 優先度<math>d(v)</math>が最小である点<math>v \in Q</math>を取り出し, 点''v''を次探索点とする.
ダイクストラ法では, 繰り返しこれらの操作を行うことになるため, より効率的なものを適用することで, 高速化が可能になる.

==== データ構造の選択 ====
優先キューは, 木構造による安定した実行が可能なヒープ系データ構造と, データをルールに従いバケットに格納するバケット系データ構造とに分類が可能である. ここでは, それぞれの最も基本的なデータ構造であるバイナリ・ヒープと1レベル・バケットに加え, 実験的に最も高速であるといわれているマルチレベル・バケットを取り上げ, 比較を行う.

===== 2-heap(バイナリ・ヒープ) =====
2-heap<ref name="heap">J. Williams, "Heapsort," Communications of the ACM, 7:347-348, 1964.</ref>は, 図1のように, 親は高々2つの子を持つ木構造で構成される. 常に親の優先度は子より高い. 点数 ''n'', 枝数 ''m'' に対して, 1対全最短路問題の計算量は <math>O((m+n)\log{n})</math> である.

{| border="1" style="text-align:center; margin:0 auto"
|-
! Index
| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14
|-
! Data
| 1 || 2 || 4 || 3 || 2 || 5 || 6 || 6 || 4 || 3 || 5 || 8 || 6 || 7 || 9
|}

[[画像:heap-2.png|thumb|center|300px|図1: バイナリ・ヒープの例]]

2-heapは以下の特徴をもつ.
#木構造により実行性能が安定している.
#メモリ要求量が大変少なく, データの局所性を高めやすい.
#木構造のためデータの読み書きが多発するので,データ交換操作がボトルネックとなりやすい.

===== Buckets(1 レベル・バケット)=====
Buckets<ref name="dial">R. B. Dial, "Algorithm 360: Shortest Path Forest with Topological Ordering, " Comm. ACM, 12:632-633, 1969.</ref>は, 最大枝長''U''に対し, <math>U+1</math>個のバケットの循環リストとして構成される (図2). 点''v''のポテンシャル<math>d(v)</math>に対し, <math>d(v)\mod(U+1)</math>により操作するバケットを決定する. 各バケット内のデータは双方向リストで結ばれており, 同一バケット内に格納されている点の優先度は常に等しい. 1対全最短路問題の計算量は, 点数''n'', 枝数''m'', 最大枝長''U''に対し, <math>O(m+nU)</math>である.

#実行時間・メモリ要求量が, 最大枝長に依存する(重み小:高速, 重み大:低速).
#道路ネットワークグラフと相性が良い.

[[画像:buckets-2.png|thumb|center|250px|図2: 1レベル・バケットの例]]

===== MLB(マルチレベル・バケット) =====
MLB(Multi-Level Buckets)<ref name="mlb">A. V. Goldberg, "A Simple Shortest Path Algorithm with Linear Average Time," Technical Report STAR-TR-01-03, STAR Lab., InterTrust Tech., Inc., Santa Clara, CA, USA. 2001.</ref>は, ヒープ系優先キュー, バケット系優先キューの双方の有効な特性を融合させた優先キューである. グラフ特性の影響は小さく安定かつ高速であるが, 非常にメモリ要求量が大きい. 1レベル・バケットとは異なり,MLBではバケットは <math>\lceil \log{U} \rceil + 1</math>だけ用意すればよい. 点数''n'', 枝数''m'', 最大枝長''U''に対し, 1対全最短路問題の計算量は<math>O(m + n\log{U})</math>となる.

#グラフ特性の影響は小さく, 安定かつ高速
#バケットを決定には高速なビット演算で行う
#メモリ要求量が非常に大きい

=====優先キューの比較=====
点数''n'', 枝数''m'', 最大枝数''U''であるグラフに対して, 計算量をまとめると表1のようになる.1対全最短路問題では, 枝数分の<code>insert</code>と<code>decrease-key</code>, 点数分の<code>extract-min</code>を行うことになる.また, その特性は図3となる. これは, 比較的小さいグラフに対し, 各枝長を<math>2^{t} (t=[-10,-9,..,9,10])</math>倍し, 計算機実験を行った結果である. Buckets の特性がよく表れている.

{| border="1" style="text-align:center"
|+ 表1: 優先キューの計算量
! !! <code>insert</code> !! <code>decrease-key</code> !! <code>extract-min</code> !! 1対全最短路問題の計算量
|-
! 2-heap
| <math>O(\log{n})</math> || <math>O(\log{n})</math> || <math>O(\log{n}) </math> || <math>O((n+m)\log{n})</math>
|-
! Buckets
| <math>O(1)</math> || <math>O(1)</math> || <math>O(U)</math> || <math>O(m+nU)</math>
|-
! MLB
| <math>O(1)</math> || <math>O(1)</math> || <math>O(\log{U})</math> || <math>O(m+n\log{U})</math>
|}

[[画像:length-scaling2.png|thumb|center|500px|図3: 優先キューの特性]]

====優先キューの性能====
2-heap, Buckets, MLB それぞれの全米道路ネットワークに対しての計算機実験を行い, 実行時間とメモリ要求量をまとめると,表2, 表3のようになる. 用いたグラフデータは, 約 2400 万点, 約 5800 万枝にも及ぶ道路ネットワークを変換させた大規模な実データである(TIGER/Line<ref>http://www.census.gov/geo/www/tiger/tigerua/ua\_tgr2k.html</ref>で公開されている). 実行時間は, ランダムに選択した1対1最短路問題を 256 回解いた際の平均である.

最短路問題では計算量に対してデータ量が大規模であるため, データ型によるメモリ使用量や実行時間に対する影響が大きい. 各変数が 32ビット整数型と 64ビット変数型の 2 種類の計算機実験の結果を記載する. グラフデータは大規模であるが, 32ビット整数型の範囲で収まるため, どちらの場合でもアルゴリズムは正しく終了するが, 距離ラベルはいずれも 64ビット整数である.

{| border="1" style="text-align:center"
|+ 表2: 全米グラフの実行時間(単位は秒)
! !! 32ビット整数型 !! 64ビット整数型
|-
! 2-heap
| 2.47 || 3.14
|-
! Buckets
| 1.68 || 2.28
|-
! MLB
| 2.63 || 2.65
|}

{| border="1" style="text-align:center"
|+ 表3: 全米グラフのメモリ要求量(単位はGB)
! !! 32ビット整数型 !! 64ビット整数型
|-
! 2-heap
| 1.27 || 1.99
|-
! Buckets
| 1.09 || 1.62
|-
! MLB
| 2.17 || 2.17
|}

===大規模最短路問題に対する高速処理システム===
現在では Web 上で最短経路を求めるサービスが複数行われている(Google Maps<ref>http://maps.google.com/</ref>や最短路問題オンラインソルバー<ref>http://opt.indsys.chuo-u.ac.jp/portal/</ref>など).

これらのシステムでは, 多くのユーザからの要求に対応する必要があるので, 単にダイクストラ法実行1回の処理を高速化するだけでなく, それらを並列に高速処理する技術が必要である.

ユーザからの要求量は時間帯や突発的な事象によって大きく変動するため, 最大需要を見越した計算資源を保有しておくのは無駄が多くコストも増大してしまう. そこでクラウド・コンピューティング技術を用いて, 高負荷時には自動的に計算機資源の増大を行うシステムなどが必要になってくる.

最近ではカーナビゲーション・システムの拡張として渋滞・事故情報をリアルタイムに把握しながら集約された大規模サーバで最短路を探索してユーザに結果を送信するシステムも構築されている. 動的な情報を考慮した最短路探索を行うことにより, これまでの経路探索に比べてより精度を向上させることができる. 特定の道路への集中を防ぐように交通量の分散を行うことで, 渋滞の緩和, 事故発生率の低下, 排出ガスの削減などを目指した交通管制を行うことも可能になると予想されている.

== 参考文献 ==
<references />

安井雄一郎, 藤澤克樹, 笹島啓史, 後藤和茂, 宮本裕一郎, "大規模最短路問題に対するダイクストラ法の高速化," 2008 年度日本 OR 学会秋季研究発表会. 314-315, 2008.

ファイル:Length-scaling2.png

2009-10-16T11:52:33Z

Fujimoto: ダイクストラ法の優先キューを実装する方法として, バイナリ・ヒープ(2-heap), 1レベル・バケット(buckets), マルチレベル・バケット(MLB)を用いた場合の比較.

ダイクストラ法の優先キューを実装する方法として, バイナリ・ヒープ(2-heap), 1レベル・バケット(buckets), マルチレベル・バケット(MLB)を用いた場合の比較.

ファイル:Heap-2.png

2009-10-16T11:50:07Z

Fujimoto: ダイクストラ法の優先キューを表すデータ構造のひとつである、バイナリヒープの例。

ダイクストラ法の優先キューを表すデータ構造のひとつである、バイナリヒープの例。

ファイル:Buckets-2.png

2009-10-16T11:48:41Z

Fujimoto: ダイクストラ法で用いられるデータ構造の1つである、1レベル・バケットの例。

ダイクストラ法で用いられるデータ構造の1つである、1レベル・バケットの例。

利用者:Fujimoto/最短路問題

2009-10-13T12:03:58Z

Fujimoto: Cite拡張を使って参考文献を埋め込み（いまいち）。いちおう全文整形。画像はまだ。

'''【さいたんろもんだい (shortest path problem)】'''

== 概要 ==


最短路問題は経路探索などの多くの応用を持ち, また他の[[最適化問題]]の子問題として用いられることも多く, 適用範囲の広い組合せ最適化問題である. そのため, 最短路問題を高速に解くことは重要な意味を持つ. 最短路問題に対する解法には, 安定的かつ効率的な高速な[[アルゴリズム]]が存在するが, 実問題は大規模(全米の道路ネットワークでは, 2400万点, 5800万枝にも及ぶ)になるため高速化が不可欠である.本解説では最短路問題の定義・種類を述べた後, 著名なアルゴリズムである[[ダイクストラ法]]に対する高速実装と実験結果等について説明を行う.

== 詳説 ==

=== 最短路問題の定義と種類 ===
最短路問題は次のような問題である.


<blockquote>
ある有向グラフ<math>G = (V, E)</math> と各枝 <math>(v,w) \in E</math> に重み <math>l(v,w)</math> が付与されているネットワーク <math>N = (G,l)</math> が与えられているとする. このとき有向グラフ <math>G</math> の任意の 2 点 <math>s, t \in V</math> に対し, 点 <math>s</math> を始点とし, 点 <math>t</math> を終点とする有向パス <math>p</math> の中で, その長さ(パスに含まれる枝の重みの合計)が最小のパスを点 <math>s</math> から点 <math>t</math> への最短路 (shortest path) といい, 最短路を求める問題を最短路問題 (shortest path problem) という.
</blockquote>

最短路問題は次のように 3 種類に分けることができる.

;1対全(single-source)最短路問題: 1点から全点に対する最短路と最短距離(最短路の長さ)を求める問題. 非負の枝の重みを持つグラフ上ではダイクストラ(Dijkstra)法が, 負の重みを持つ枝がある場合にはベルマン・フォード(Bellman-Ford)法が有名である.
;全対全(all-pairs)最短路問題: 全点間の最短路と最短距離を求める問題. ワーシャル・フロイド(Warshall-Folyd)法が有名であるが, 1対全最短路問題アルゴリズムを各点に対して適用することでも求めることができる.
;1対1(point-to-point)最短路問題: 2点間の最短路と最短距離を求める問題.

=== 探索アルゴリズムと実装方法 ===

最短路問題に関する探索アルゴリズムの中でも, 最も頻繁に利用されるダイクストラ法を取り上げ, アルゴリズムの説明から, 高速化のための優先キューの適用方法・実装方法について示していく.

==== ダイクストラ法 ====

1959年, E. W. Dijkstra<ref name="dijkstra">E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, 1:269-271, 1959.</ref>によって提案された1対全最短路問題に対するアルゴリズムである. 探索するグラフ上の全ての枝の重みが非負でなければならないが, ベルマン・フォード法<ref>R. E. Bellman, "On a Routing Problem," Quarterly of Applied Mathematics, 16:87-90, 1958.</ref>に比べ効率的かつ高速である.ダイクストラ法は, ベルマン・フォード法と同じように動的計画法の一種とみなすことができるが, 点の探索の順序に特徴をもつ. 探索の途中で得られた始点 <math>s</math> からの距離の最小値をポテンシャルもしくは距離ラベルとよび, その値の小さい順に点の探索を行い,最短路および最短距離を確定していく. つまり, 各点に対し, <math>d(s) = 0, d(v) = +\infty (v \in V)</math> とするポテンシャル <math>d</math> を用意し, 探索点 <math>v</math> に接続する枝 <math>(v,w)</math> に対して, <math>d(v) + l(v,w) < d(w)</math> ならば <math>d(w) := l(v,w) + d(v)</math> とする操作を繰り返し行う. 終点 <math>t</math> が探索点になった時点で終了させることで, 1対1最短路問題も効率的に求解可能である.

===== ダイクストラ法のアルゴリズム =====

1: ポテンシャル ''d'' の初期設定
2: ''S'' := ''V''
3: '''while''' <math>S \neq \emptyset</math> '''do'''
4: <math>d(v)</math> が最小の点 <math>v \in S</math> を選択
5: ''S'' := <math>S \backslash \left\{ v \right\}</math>
6: '''for all''' (''v'', ''w'') '''do'''
7: '''if''' <math>d(v) +l(v,w) < d(w)</math> '''then'''
8: <math>d(w) := d(v) +l(v,w)</math>
9: '''end if'''
10: '''end for'''
11: '''end while'''

==== 高速化のための優先キューの利用 ====
ダイクストラ法は, 効率的かつ高速なアルゴリズムだが, 探索点を決定する操作([[#ダイクストラ法のアルゴリズム|アルゴリズム]]中の4行目,5行目)が, ボトルネックであることが知られている<ref name="dijkstra" />. 探索候補点集合(アルゴリズム中の''S'')に対して優先キューを適用することで, 改善できる.

==== 優先キューの実装方法 ====
優先キューとは, データを優先度によって操作するデータ構造のことである. ダイクストラ法に適用する優先キューは,<code>insert</code>, <code>decrease-key</code>, <code>extract-min</code>と呼ばれる操作に対応している必要がある.
;<code>insert</code>: ポテンシャル<math>d(v)</math>を優先度として, 点<math>v \in V</math>を優先キュー''Q''へ挿入する.
;<code>decrease-key</code>: 優先キュー内に格納されている点 <math>v \in Q</math>の優先度<math>d(v)</math>を, <math>d'(v)</math>に更新する.
;<code>extract-min</code>: 優先度<math>d(v)</math>が最小である点<math>v \in Q</math>を取り出し, 点''v''を次探索点とする.
ダイクストラ法では, 繰り返しこれらの操作を行うことになるため, より効率的なものを適用することで, 高速化が可能になる.

==== データ構造の選択 ====
優先キューは, 木構造による安定した実行が可能なヒープ系データ構造と, データをルールに従いバケットに格納するバケット系データ構造とに分類が可能である. ここでは, それぞれの最も基本的なデータ構造であるバイナリ・ヒープと1レベル・バケットに加え, 実験的に最も高速であるといわれているマルチレベル・バケットを取り上げ, 比較を行う.

===== 2-heap(バイナリ・ヒープ) =====
2-heap<ref name="heap">J. Williams, "Heapsort," Communications of the ACM, 7:347-348, 1964.</ref>は, 図1のように, 親は高々2つの子を持つ木構造で構成される. 常に親の優先度は子より高い. 点数 ''n'', 枝数 ''m'' に対して, 1対全最短路問題の計算量は <math>O((m+n)\log{n})</math> である.

2-heapは以下の特徴をもつ.
#木構造により実行性能が安定している.
#メモリ要求量が大変少なく, データの局所性を高めやすい.
#木構造のためデータの読み書きが多発するので,データ交換操作がボトルネックとなりやすい.

===== Buckets(1 レベル・バケット)=====
Buckets<ref name="dial">R. B. Dial, "Algorithm 360: Shortest Path Forest with Topological Ordering, " Comm. ACM, 12:632-633, 1969.</ref>は, 最大枝長''U''に対し, <math>U+1</math>個のバケットの循環リストとして構成される (図2). 点''v''のポテンシャル<math>d(v)</math>に対し, <math>d(v)\mod(U+1)</math>により操作するバケットを決定する. 各バケット内のデータは双方向リストで結ばれており, 同一バケット内に格納されている点の優先度は常に等しい. 1対全最短路問題の計算量は, 点数''n'', 枝数''m'', 最大枝長''U''に対し, <math>O(m+nU)</math>である.

#実行時間・メモリ要求量が, 最大枝長に依存する(重み小:高速, 重み大:低速).
#道路ネットワークグラフと相性が良い.

===== MLB(マルチレベル・バケット) =====
MLB(Multi-Level Buckets)<ref name="mlb">A. V. Goldberg, "A Simple Shortest Path Algorithm with Linear Average Time," Technical Report STAR-TR-01-03, STAR Lab., InterTrust Tech., Inc., Santa Clara, CA, USA. 2001.</ref>は, ヒープ系優先キュー, バケット系優先キューの双方の有効な特性を融合させた優先キューである. グラフ特性の影響は小さく安定かつ高速であるが, 非常にメモリ要求量が大きい. 1レベル・バケットとは異なり,MLBではバケットは <math>\lceil \log{U} \rceil + 1</math>だけ用意すればよい. 点数''n'', 枝数''m'', 最大枝長''U''に対し, 1対全最短路問題の計算量は<math>O(m + n\log{U})</math>となる.

#グラフ特性の影響は小さく, 安定かつ高速
#バケットを決定には高速なビット演算で行う
#メモリ要求量が非常に大きい

=====優先キューの比較=====
点数''n'', 枝数''m'', 最大枝数''U''であるグラフに対して, 計算量をまとめると表1のようになる.1対全最短路問題では, 枝数分の<code>insert</code>と<code>decrease-key</code>, 点数分の<code>extract-min</code>を行うことになる.また, その特性は図3となる. これは, 比較的小さいグラフに対し, 各枝長を<math>2^{t} (t=[-10,-9,..,9,10])</math>倍し, 計算機実験を行った結果である. Buckets の特性がよく表れている.

{| border="1" style="text-align:center"
|+ 表1: 優先キューの計算量
! !! <code>insert</code> !! <code>decrease-key</code> !! <code>extract-min</code> !! 1対全最短路問題の計算量
|-
! 2-heap
| <math>O(\log{n})</math> || <math>O(\log{n})</math> || <math>O(\log{n}) </math> || <math>O((n+m)\log{n})</math>
|-
! Buckets
| <math>O(1)</math> || <math>O(1)</math> || <math>O(U)</math> || <math>O(m+nU)</math>
|-
! MLB
| <math>O(1)</math> || <math>O(1)</math> || <math>O(\log{U})</math> || <math>O(m+n\log{U})</math>
|}

====優先キューの性能====
2-heap, Buckets, MLB それぞれの全米道路ネットワークに対しての計算機実験を行い, 実行時間とメモリ要求量をまとめると,表2, 表3のようになる. 用いたグラフデータは, 約 2400 万点, 約 5800 万枝にも及ぶ道路ネットワークを変換させた大規模な実データである(TIGER/Line<ref>http://www.census.gov/geo/www/tiger/tigerua/ua\_tgr2k.html</ref>で公開されている). 実行時間は, ランダムに選択した1対1最短路問題を 256 回解いた際の平均である.

最短路問題では計算量に対してデータ量が大規模であるため, データ型によるメモリ使用量や実行時間に対する影響が大きい. 各変数が 32ビット整数型と 64ビット変数型の 2 種類の計算機実験の結果を記載する. グラフデータは大規模であるが, 32ビット整数型の範囲で収まるため, どちらの場合でもアルゴリズムは正しく終了するが, 距離ラベルはいずれも 64ビット整数である.

{| border="1" style="text-align:center"
|+ 表2: 全米グラフの実行時間(単位は秒)
! !! 32ビット整数型 !! 64ビット整数型
|-
! 2-heap
| 2.47 || 3.14
|-
! Buckets
| 1.68 || 2.28
|-
! MLB
| 2.63 || 2.65
|}

{| border="1" style="text-align:center"
|+ 表3: 全米グラフのメモリ要求量(単位はGB)
! !! 32ビット整数型 !! 64ビット整数型
|-
! 2-heap
| 1.27 || 1.99
|-
! Buckets
| 1.09 || 1.62
|-
! MLB
| 2.17 || 2.17
|}

===大規模最短路問題に対する高速処理システム===
現在では Web 上で最短経路を求めるサービスが複数行われている(Google Maps<ref>http://maps.google.com/</ref>や最短路問題オンラインソルバー<ref>http://opt.indsys.chuo-u.ac.jp/portal/</ref>など).

これらのシステムでは, 多くのユーザからの要求に対応する必要があるので, 単にダイクストラ法実行1回の処理を高速化するだけでなく, それらを並列に高速処理する技術が必要である.

ユーザからの要求量は時間帯や突発的な事象によって大きく変動するため, 最大需要を見越した計算資源を保有しておくのは無駄が多くコストも増大してしまう. そこでクラウド・コンピューティング技術を用いて, 高負荷時には自動的に計算機資源の増大を行うシステムなどが必要になってくる.

最近ではカーナビゲーション・システムの拡張として渋滞・事故情報をリアルタイムに把握しながら集約された大規模サーバで最短路を探索してユーザに結果を送信するシステムも構築されている. 動的な情報を考慮した最短路探索を行うことにより, これまでの経路探索に比べてより精度を向上させることができる. 特定の道路への集中を防ぐように交通量の分散を行うことで, 渋滞の緩和, 事故発生率の低下, 排出ガスの削減などを目指した交通管制を行うことも可能になると予想されている.

== 参考文献 ==
<references />

安井雄一郎, 藤澤克樹, 笹島啓史, 後藤和茂, 宮本裕一郎, "大規模最短路問題に対するダイクストラ法の高速化," 2008 年度日本 OR 学会秋季研究発表会. 314-315, 2008.

利用者:Fujimoto/最短路問題

2009-09-26T11:08:16Z

Fujimoto: "利用者:Fujimoto/最短路問題" を保護しました。 [edit=sysop:move=sysop]

利用者:Fujimoto/最短路問題

2009-09-26T11:07:41Z

Fujimoto: 新規項目「最短路問題」の途中まで入力。リファレンスを生成する拡張ライブラリが入っていなかったので作業中断。

待ち行列モデル

2009-06-30T08:42:24Z

Fujimoto: GIFアニメーションの例として待ち行列を作成、添付

'''【まちぎょうれつもでる (queueing model)】'''

[[画像:queue.gif|thumb|421px|単一窓口待ち行列の挙動]]

== 概要 ==

混雑現象を解析するための代表的なモデル群の1つ．単一の待ち行列モデルは，客の到着，窓口における客のサービス，サービスを待つ客が成す待ち行列，などから構成され，平均待ち時間などによって混雑の程度が評価される．近年，待ち行列がネットワーク状につながった"[[待ち行列ネットワーク]]"が積極的に解析され，コンピュータシステムや通信システムなどの性能評価に利用されている．

　応用分野については，次の各項目を参照のこと：待ち行列の[[待ち行列の通信への応用|通信への応用]]，待ち行列の[[待ち行列のコンピュータへの応用|コンピュータへの応用]]，待ち行列の[[待ち行列の生産システムへの応用|生産システムへの応用]]．

== 詳説 ==

=== 混雑現象 ===
　われわれの身の回りには，[[混雑現象]]が主因となっている問題がたくさん存在する[5]．たとえば，通勤電車，繁華街，行楽地，イベント会場などにおける混雑，高速道路や幹線道路の渋滞，スーパーのレジや銀行の ATM における行列，病院での待ち，携帯電話の不接続，などなど．また，人間が待たされるわけではないが，商品の在庫，仕事の滞貨，注文残，考えようによっては洪水などというのもある．コンピュータの中では複数のジョブが CPU や I/O (Disk など) で待ち行列を作って処理されているし，情報通信ネットワークでも，情報があちこちのノードで少しずつ待たされながら目的地に運ばれる．

　このような混雑現象は，需要つまりサービス要求量が一時的にサービス能力を超えることから生じており，次のようにいろいろな方法で処理されている．

a.　サービス処理能力を需要にあわせて変動させる (電力会社は，火力発電や水力発電で発電量を細かく調整している)．

b.　サービス品質を落として処理能力を一時的に上げる (通勤電車では客が多くなると尻押しをしてでも詰め込む)．

c.　バッファで一時的な超過分を吸収する (行列で待たせる)．

d.　サービスを拒否する (携帯電話では当然のように行われる)．

=== 混雑現象のためのモデル ===
　a．の追随型とb．の品質低下型は，混雑に対する対応がリアルタイムであるため，需要の変動パターンがわかれば，混雑の程度の解析は比較的容易である．これに対してc．のバッファ型とd．の拒絶型，とくにc.　は，システムの挙動がサービスの仕方とも関連して複雑であり，モデルによる検討が必要になることが多い．そのモデルも，需要の変動パターンによって使い分けが必要である．

　i)　サービス要求量の増大が一定時間続くラッシュアワー型の場合

　ii)　偶然変動による比較的短時間の増大が繰り返し生じる確率型の場合

である．むろんそれらが複合していることもある．

=== 流体近似モデル ===
　i) のラッシュアワー型の解析は，[[流体近似]] (fluid approximation) を使ってなされることが多い．これは水道の水のように，サービス要求がある率でバッファに入ってきて，ある率で流れ出ていく，と考えるものである (図1)．このとき，時刻 <math>t\, </math> における入力率を <math>\lambda_t\, </math>，出力率 (バッファに貯まっているときに出力する率) を <math>\mu_t\, </math> とすると，時刻 <math>t\, </math> におけるバッファの内容量 <math>Q_t\, </math> は，微分方程式

<center>
<table>
<tr>
<td><table>
<math> \frac{\mbox{d} Q_t}{\mbox{d} t} = \Biggl\{ \Biggr. \, \, </math>
</table></td>
<td><table>
<tr>
<td><math> \lambda_t - \mu_t \,\, </math></td>
<td>　　</td>
<td><math> \lambda_t > \mu_t \,\, </math>または<math> Q_t>0 \,\, </math>　のとき</td>
</tr>
<tr>
<td><math> 0 \, \, </math></td>
<td></td>
<td align="left">その他</td>
</tr>
</table></td>
</tr>
</table>
</center>

で記述される．ただしこの微分方程式を使わなくても，時間区間 <math>(0, t]\, </math> における累積入力量<math>\textstyle A_t = \int_0^\infty \lambda_t \, dt\, </math> のグラフから累積出力量 <math>D_t\, </math> のグラフを描くことができ，それらの差 <math>Q_t=A_t - D_t\, </math> から時刻 <math>t\, </math> におけるバッファーの内容量を求めることができる [2,5]．

<center><table><tr><td align=center>[[画像:sk-0112-b-a-01-2.png]]</td></tr>
<td align=center>図１：流体近似 : 水道のイメージ<br>
</td></table></center>



=== 待ち行列モデル ===
　サービス要求量の変動が ii) の確率型の場合は，[[待ち行列モデル]] (queueing model) や [[在庫モデル]] (inventory model)，[[ダムモデル]] (dam model) などを使って解析される [1，2]．ここでは待ち行列モデルを主に説明しよう．

<center><table><tr><td align=center>[[画像:sk-0112-b-a-01-3.png]]</td></tr>
<td align=center>図２：待ち行列のイメージ図<br>
</td></table></center>



　待ち行列モデルは，図2のように，あるサービスステーションに[[客]](customer)が[[到着]]し，そこである種の[[サービス]] (service) をうけ，系外に立ち去る，という[[サービスシステム]] (servicing system) のモデルである．サービスステーションは，通常，サービスが行われる[[窓口]] (channel) と，到着した客がサービスを受けるために待つ[[待ち行列]] (queue) とから成る．この待ち行列が[[バッファ]] (buffer) の役割を果たす．待つことのできる客の数に制限がある場合，待合室という概念を導入することもある．このとき待合室の容量が，待つことのできる客の数の上限となる．

　客，窓口，待合室などは，モデルによってさまざまなものに対応する．ある種の生産システムでは，客は製品や部品であり，窓口は加工機，検査機，組立台など，そして待合室は仮置き台などである．コンピュータの性能評価では，客はジョブであり，窓口は CPU や DISK，待合室は各所のメモリである．また情報通信ネットワークの性能評価では，セルやパケットといった情報の塊が客であり，各種のスイッチ類やチャネルが窓口，バッファメモリが待合室として扱われる．

=== 性能評価指標，混雑指標 ===
　図2のような標準的なモデルでは，[[利用率]] (traffic intensity)，<math>\rho\, </math> というのが重要なシステムパラメータである．これは

<center>
[[画像:sk-0112-b-a-01-1.png]]
</center>



という形で定義される．たとえば客が平均 <math>\lambda^{-1}\, </math> の間隔で到着し，<math>c\, </math> 個の窓口で平均 <math>\mu^{-1}\, </math> のサービスが行われるようなシステムでは，<math>\rho=\lambda/c \mu\, </math> である．多くの場合，<math>\rho<1\, </math> であれば，システムは[[平衡状態]](stationary) とよばれる安定な状態へ向かい，確率論的な解析が可能となる．

　一般に，<math>\rho\, </math> が 0に近いときは混雑はほとんどなく，1に近づくにつれて混雑がひどくなる．このような混雑を評価する指標としては，[[待ち時間]] (waiting time) (客が待ち行列で待たされる時間)，[[滞在時間]] (sojourn time) (客が到着してからサービスが終了するまでの時間)，[[待ち行列長]] (queue length) (待ち行列で待っている客の数)，[[系内人数]] (number of customers in the system) (待ち行列と窓口にいる客の数) などの平均や分散，または分布などが用いられる．

　[[待合室の容量]] (capacity of waiting room) が有限で，システムに入れる客の数に制限がある場合，[[呼損率]] (loss probability) も重要な指標である．これは到着した客のうち待合室が一杯でサービスを受けられずに退去する客の割合である．ここで "呼 (こ，よび)" という耳慣れない言葉が使われているが，これは電話をかけるときの接続要求のことで，待ち行列理論がデンマークの電話技術者[[アーラン, アグナー・K|アーラン]](A. K. Erlang) によって20世紀の初頭に始められ以来，電話の交換機の適正数を評価するのに[[有限待合室モデル|有限待合室のモデル]] (finite-buffer model) がずっと使われてきたという経緯からきている [4]．

=== 読書案内 ===
　近年，待ち行列理論の分野では，情報通信技術の発達などと歩調を合わせて，より複雑でより一般的な状況の下でのモデル解析が進められている．待ち行列理論関係の参考書は，日本オペレーションズリサーチ学会待ち行列研究部会のホームページに「待ち行列関係書籍（和書）」としてまとめられている．[7] 中でも [5] は混雑現象全般にわたって解説されているので，初学者には参考になるだろう．[6] は初学者から専門の研究者まで幅広い読者層を想定して，待ち行列理論の基本的な項目が解説されている．英語の書籍の紹介は [3,4] にある．

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

[1] 森村英典，大前義次，『応用待ち行列理論』，日科技連出版社，1975．ISBN 481715313X

[2] 高橋幸雄，「入門講座，やさしい待ち行列(1)～(4)」，『オペレーションズ・リサーチ』，'''40''' (1995)，649-654，716-721，'''41''' (1996)，35-40，100-105．https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.41_01_035.pdf

[3] 高橋敬隆，高橋幸雄，牧本直樹，「入門講座，やさしい待ち行列 (補遺) ― 待ち行列の本」，『オペレーションズ・リサーチ』，'''41''' (1996)，106-107．https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.41_02_106.pdf

[4] 高橋幸雄，「講座，待ち行列研究の新しい潮流 (1)― 待ち行列研究の変遷」，『オペレーションズ・リサーチ』，'''43''' (1998)，495-499.

[5] 高橋幸雄，森村英典，『混雑と待ち』，朝倉書店，2001．ISBN: 425427517X

[6] 宮沢政清，『待ち行列の数理とその応用』，牧野書店，2006．ISBN-13: 978-4434076978

[7] 日本オペレーションズリサーチ学会待ち行列研究部会
https://orsj.org/queue/
[[category:確率と確率過程|まちぎょうれつ]]

[[category:待ち行列|まちぎょうれつ]]

ファイル:Queue.gif

2009-06-30T08:38:47Z

Fujimoto: 待ち行列の挙動（GIFアニメーション）。

待ち行列の挙動（GIFアニメーション）。

Portal:待ち行列

2009-05-27T11:10:05Z

Fujimoto: 試験的にポータルを作成

このページは、[[待ち行列]]分野のポータルです。待ち行列に関連した項目を探しやすい形で列挙し、利用や発展をうながすことを目的としています。

（'''注意：'''このページは[[OR事典編集委員会]]において試験的に作成されたものであり、情報の正確さは保証されません。）

==主要項目==
{|
|- valign="top"
|width="50%" style="padding-right:0.5em;"|
===基礎===
待ち行列とはどのようなものかを理解する助けになるページ群です。

*[[待ち行列モデル]]
*[[《待ち行列モデルの標準形》]]
*[[ケンドールの記号]]
*[[《待ち行列の各種モデル》]]
**[[待ち行列モデル M/M/1]]
**[[有限待合室モデル]]
***[[待ち行列モデル M/M/c/c]]
**[[待ち行列モデル M/M/c]]
**[[待ち行列モデル M/G/1]]
**[[待ち行列のバケーションサーバモデル]]
**[[ポーリングモデル]]
**[[集団待ち行列]]
**[[再呼モデル]]
**[[優先権待ち行列]]
*[[待ち行列ネットワーク]]
**[[積形式ネットワーク]]

|width="50%" style="padding-left:0.5em;"|
===理論===
待ち行列分野の研究から導かれた、各種の理論的成果です。
*[[アーランの損失式]]
*[[リトルの公式]]
*[[PASTA]]
*[[積形式解]]

===応用===
待ち行列を工学的な諸分野に応用する参考になるページです。[[事例編：待ち行列]]もあわせて参照して下さい。
*[[待ち行列の通信への応用]]
*[[待ち行列のコンピュータへの応用]]
*[[待ち行列の生産システムへの応用]]

|}

==関連分野==
待ち行列解析で重要な役割を果たす関連分野です。
*[[《確率論》]]
*[[確率過程]]
**[[マルコフ連鎖]]
*[[シミュレーション]]

==外部リンク==
*[https://orsj.org/queue/ 日本オペレーションズ・リサーチ学会待ち行列研究部会] - 待ち行列の理論および応用を専門とする研究者の集まりです。

__NOTOC__

[[Category:待ち行列|*]]

利用者・トーク:Sakasegawa

2008-09-25T09:17:03Z

Fujimoto: 業務連絡

==資料の件==
[[利用者:Fujimoto|Fujimoto]]です。本日の資料をメールで送ってありますのでご確認ください。（これで伝わるかなあ）--[[利用者:Fujimoto|Fujimoto]] 2008年9月25日 (金) 18:17 (JST)

待ち行列モデル

2008-09-25T07:30:19Z

Fujimoto: ISBN

'''【まちぎょうれつもでる (queueing model)】'''

== 概要 ==

混雑現象を解析するための代表的なモデル群の1つ. 単一の待ち行列モデルは, 客の到着, 窓口における客のサービス, サービスを待つ客が成す待ち行列, などから構成され, 平均待ち時間などによって混雑の程度が評価される. 近年, 待ち行列がネットワーク状につながった"[[待ち行列ネットワーク]]"が積極的に解析され, コンピュータシステムや通信システムなどの性能評価に利用されている.

== 詳説 ==

=== 混雑現象 ===
　われわれの身の回りには, [[混雑現象]]が主因となっている問題がたくさん存在する[5]. たとえば, 通勤電車, 繁華街, 行楽地, イベント会場などにおける混雑, 高速道路や幹線道路の渋滞, スーパーのレジや銀行の ATM における行列, 病院での待ち, 携帯電話の不接続, などなど. また, 人間が待たされるわけではないが, 商品の在庫, 仕事の滞貨, 注文残, 考えようによっては洪水などというのもある. コンピュータの中では複数のジョブが CPU や I/O (Disk など) で待ち行列を作って処理されているし, 情報通信ネットワークでも, 情報があちこちのノードで少しずつ待たされながら目的地に運ばれる.

　このような混雑現象は, 需要つまりサービス要求量が一時的にサービス能力を超えることから生じており, 次のようにいろいろな方法で処理されている.

a.　サービス処理能力を需要にあわせて変動させる (電力会社は, 火力発電や水力発電で発電量を細かく調整している).

b.　サービス品質を落として処理能力を一時的に上げる (通勤電車では客が多くなると尻押しをしてでも詰め込む).

c.　バッファで一時的な超過分を吸収する (行列で待たせる).

d.　サービスを拒否する (携帯電話では当然のように行われる).

=== 混雑現象のためのモデル ===
　a. の追随型とb. の品質低下型は, 混雑に対する対応がリアルタイムであるため, 需要の変動パターンがわかれば, 混雑の程度の解析は比較的容易である. これに対してc. のバッファ型とd. の拒絶型, とくにc.　は, システムの挙動がサービスの仕方とも関連して複雑であり, モデルによる検討が必要になることが多い. そのモデルも, 需要の変動パターンによって使い分けが必要である.

　i)　サービス要求量の増大が一定時間続くラッシュアワー型の場合

　ii)　偶然変動による比較的短時間の増大が繰り返し生じる確率型の場合

である. むろんそれらが複合していることもある.

=== 流体近似モデル ===
　i) のラッシュアワー型の解析は, [[流体近似]] (fluid approximation) を使ってなされることが多い. これは水道の水のように, サービス要求がある率でバッファに入ってきて, ある率で流れ出ていく, と考えるものである (図1). このとき, 時刻 <math>t\, </math> における入力率を <math>\lambda_t\, </math>, 出力率 (バッファに貯まっているときに出力する率) を <math>\mu_t\, </math> とすると, 時刻 <math>t\, </math> におけるバッファの内容量 <math>Q_t\, </math> は, 微分方程式

<center>
<table>
<tr>
<td><table>
<math> \frac{\mbox{d} Q_t}{\mbox{d} t} = \Biggl\{ \Biggr. \, \, </math>
</table></td>
<td><table>
<tr>
<td><math> \lambda_t - \mu_t \,\, </math></td>
<td>　　</td>
<td><math> \lambda_t > \mu_t \,\, </math>または<math> Q_t>0 \,\, </math>　のとき</td>
</tr>
<tr>
<td><math> 0 \, \, </math></td>
<td></td>
<td align="left">その他</td>
</tr>
</table></td>
</tr>
</table>
</center>

で記述される. ただしこの微分方程式を使わなくても, 時間区間 <math>(0, t]\, </math> における累積入力量<math>\textstyle A_t = \int_0^\infty \lambda_t \, dt\, </math> のグラフから累積出力量 <math>D_t\, </math> のグラフを描くことができ, それらの差 <math>Q_t=A_t - D_t\, </math> から時刻 <math>t\, </math> におけるバッファーの内容量を求めることができる [2,5].

<center><table><tr><td align=center>[[画像:sk-0112-b-a-01-2.png]]</td></tr>
<td align=center>図１：流体近似 : 水道のイメージ<br>
</td></table></center>



=== 待ち行列モデル ===
　サービス要求量の変動が ii) の確率型の場合は, [[待ち行列モデル]] (queueing model) や [[在庫モデル]] (inventory model), [[ダムモデル]] (dam model) などを使って解析される [1, 2]. ここでは待ち行列モデルを主に説明しよう.

<center><table><tr><td align=center>[[画像:sk-0112-b-a-01-3.png]]</td></tr>
<td align=center>図２：待ち行列のイメージ図<br>
</td></table></center>



　待ち行列モデルは, 図2のように, あるサービスステーションに[[客]](customer)が[[到着]]し, そこである種の[[サービス]] (service) をうけ, 系外に立ち去る, という[[サービスシステム]] (servicing system) のモデルである. サービスステーションは, 通常, サービスが行われる[[窓口]] (channel) と, 到着した客がサービスを受けるために待つ[[待ち行列]] (queue) とから成る. この待ち行列が[[バッファ]] (buffer) の役割を果たす. 待つことのできる客の数に制限がある場合, 待合室という概念を導入することもある. このとき待合室の容量が, 待つことのできる客の数の上限となる.

　客, 窓口, 待合室などは, モデルによってさまざまなものに対応する. ある種の生産システムでは, 客は製品や部品であり, 窓口は加工機, 検査機, 組立台など, そして待合室は仮置き台などである. コンピュータの性能評価では, 客はジョブであり, 窓口は CPU や DISK, 待合室は各所のメモリである. また情報通信ネットワークの性能評価では, セルやパケットといった情報の塊が客であり, 各種のスイッチ類やチャネルが窓口, バッファメモリが待合室として扱われる.

=== 性能評価指標, 混雑指標 ===
　図2のような標準的なモデルでは, [[利用率]] (traffic intensity), <math>\rho\, </math> というのが重要なシステムパラメータである. これは

<center>
[[画像:sk-0112-b-a-01-1.png]]
</center>



という形で定義される. たとえば客が平均 <math>\lambda^{-1}\, </math> の間隔で到着し, <math>c\, </math> 個の窓口で平均 <math>\mu^{-1}\, </math> のサービスが行われるようなシステムでは, <math>\rho=\lambda/c \mu\, </math> である. 多くの場合, <math>\rho<1\, </math> であれば, システムは[[平衡状態]](stationary) とよばれる安定な状態へ向かい, 確率論的な解析が可能となる.

　一般に, <math>\rho\, </math> が 0に近いときは混雑はほとんどなく, 1に近づくにつれて混雑がひどくなる. このような混雑を評価する指標としては, [[待ち時間]] (waiting time) (客が待ち行列で待たされる時間), [[滞在時間]] (sojourn time) (客が到着してからサービスが終了するまでの時間), [[待ち行列長]] (queue length) (待ち行列で待っている客の数), [[系内人数]] (number of customers in the system) (待ち行列と窓口にいる客の数) などの平均や分散, または分布などが用いられる.

　[[待合室の容量]] (capacity of waiting room) が有限で, システムに入れる客の数に制限がある場合, [[呼損率]] (loss probability) も重要な指標である. これは到着した客のうち待合室が一杯でサービスを受けられずに退去する客の割合である. ここで "呼 (こ, よび)" という耳慣れない言葉が使われているが, これは電話をかけるときの接続要求のことで, 待ち行列理論がデンマークの電話技術者アーランアグナー・K}{アーラン} (A. K. Erlang) によって20世紀の初頭に始められ以来, 電話の交換機の適正数を評価するのに[[有限待合室モデル|有限待合室のモデル]] (finite-buffer model) がずっと使われてきたという経緯からきている [4].

　近年, 待ち行列理論の分野では, 情報通信技術の発達などと歩調を合わせて, より複雑でより一般的な状況の下でのモデル解析が進められている. これらについては他の項目ならびに文献 [3,4,5] を参照されたい. また関連書籍は [3] にサーベイが載っている. 応用分野も多岐にわたっている. 次の各項目を参照してほしい. 待ち行列の[[待ち行列の通信への応用|通信への応用]], 待ち行列の[[待ち行列のコンピュータへの応用|コンピュータへの応用]], 待ち行列の[[待ち行列の生産システムへの応用|生産システムへの応用]].

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

[1] 森村英典, 大前義次, 『応用待ち行列理論』, 日科技連出版社, 1975. ISBN 481715313X

[2] 高橋幸雄, 「入門講座, やさしい待ち行列(1)～(4)」, 『オペレーションズ・リサーチ』, '''40''' (1995), 649-654, 716-721, '''41''' (1996), 35-40, 100-105.

[3] 高橋敬隆, 高橋幸雄, 牧本直樹, 「入門講座, やさしい待ち行列 (補遺) ― 待ち行列の本」, 『オペレーションズ・リサーチ』, '''41''' (1996), 106-107.

[4] 高橋幸雄, 「講座, 待ち行列研究の新しい潮流 (1)― 待ち行列研究の変遷」, 『オペレーションズ・リサーチ』, '''43''' (1998), 495-499.

[5] 高橋幸雄, 森村英典, 『混雑と待ち』, 朝倉書店, 2001. ISBN 425427517X

[6] 日本オペレーションズリサーチ学会待ち行列研究部会　http://www.is.titech.ac.jp/~kkatou/queue/

[[category:待ち行列|まちぎょうれつ]]

ORWiki:プライバシー・ポリシー

2008-08-21T11:12:17Z

Fujimoto: "ORWiki:プライバシー・ポリシー" を保護しました。 [edit=sysop:move=sysop]

[https://orsj.org 公益社団法人日本オペレーションズ・リサーチ学会]
の
[https://orsj.org/aboutUs/privacy%20policy.htm プライバシーポリシー]
をご覧下さい．

ORWiki:ORWikiについて

2008-08-21T11:12:03Z

Fujimoto: "ORWiki:ORWikiについて" を保護しました。 [edit=sysop:move=sysop]

== 刊行にあたって ==
<p style="text-align:right;">
OR事典編集委員長（前）<BR>
青木　利晴
</p>

　1957（昭和32) 年に創立された
[https://orsj.org/ 日本オペレーションズ・リサーチ（OR）学会]
は、今年6月に創立50周年という大きな節目を迎えました。これを記念して今春より数々の事業を実施していますが、その一つとして「ＯＲ事典」の改訂を行っています。初版は１９７５年に刊行し、１９９７年の創立４０周年には改訂版をＣＤ－ＲＯＭで提供いたしましたが、今回は創立５０周年記念事業として、改訂とともに新たにインターネットでの公開を実現いたしました。

　さて「知の世紀」といわれる21世紀に入った今、新たな時代環境の中で本学会も大きな変化を求められています。本学会は、これまでに築いてきた基盤の上に立って、今後とも発展し続けるように、新たなOR活用分野・研究手法の開拓、広報・研究普及活動の更なる拡充による社会への貢献、国際化の推進とアジア地域との連携などの課題について重点的に取り組み、真に役立つＯＲの研究・実践に努力を積み重ねてまいります。このような時期に「ＯＲ事典」を新たに編集し刊行することは、きわめて意義深いことだと思います。

　今回のＯＲ事典編集作業の結果、[[基礎編：大項目一覧|基礎編]]、
[[用語編]]に関してはＰＤＦベースから、ＷＩＫＩを使った方式に変換し、
より柔軟な使い方ができるようになりました。基礎編の見出し項目としては２８項目を追加、４項目を削除、用語は３００語が追加されました。
[[事例編]]については、「[https://orsj.org/wp-content/or-archives50/ ＯＲアーカイブ集]」より，事例に関する論文等を分類整理しました。
[http://www.ozsons.com/ORstory/ 資料編]では最近までのデータをアップデートしてあります。

　今回の改訂は，センテニアルに向けた新たな半世紀に大きな一歩を踏み出す契機になるものと自負しております。

　おわりに困難な編集事業に取り組まれた[[ＯＲ事典編集委員会]]の皆様、
ご支援いただいたＯＲ学会５０周年記念事業関係者およびＯＲ学会事務局の方々に心から感謝の意を表します。（2007.9.1）

----

　　　　
　　　　
== 執筆協力者一覧 ==

=== 基礎編、用語編執筆者 ===
:浅野孝夫, 朝野煕彦, 穴太克則, 飯島淳一, 飯田耕司, 石井博昭, 石渡徳彌, 一森哲男, 伊藤和憲, 伊藤健, 乾口雅弘, 茨木俊秀, 今井桂子, 今井浩, 今泉淳, 岩城秀樹, 岩田覚, 岩本誠一, 上田徹, 上野哲郎, 上原隆平, 宇野毅明, 梅沢豊, 大内東, 大隅昇, 太田敏澄, 大西匡光, 大野勝久, 大山達雄, 岡田章, 尾崎俊治, 小沢利久, 小澤正典, 海生直人, 嘉数侑昇, 片岡靖詞, 片桐英樹, 片山隆仁, 片山勁, 片山徹, 刈屋武昭, 川崎英文, 川島幸之助, 川島武, 河野浩之, 城川俊一, 菊田健作, 木瀬洋, 紀一誠, 木村武, 木村俊一, 久野誉人, 久保幹雄, 久保田光一, 栗田治, 倉橋（筑波）, 黒田充, 腰塚武志, 小島政和, 小林和朝, 古林隆, 今野浩, 齋藤雄志, 逆瀬川浩孝, 佐藤馨一, 佐藤大輔, 猿渡康文, 澤木勝茂, 三道弘明, 椎塚久雄, 塩浦昭義, 塩出省吾, 繁野麻衣子, 篠原正明, 下村雅彦, 白川浩, 杉原厚吉, 杉原左右一, 杉山学, 鈴木敦夫, 鈴木和幸, 鈴木賢一, 鈴木久敏, 関口恭毅, 関谷和之, 戴陽, 高井英造, 高木英明, 高橋勝, 高橋真吾, 高橋磐郎, 高橋幸雄, 高橋豊, 高橋敬隆, 滝根哲哉, 田口東, 田中環, 田中雅博, 田中雅康, 谷野哲三, 田畑吉雄, 田村明久, 田村隆善, 田村坦之, 佃純誠, 佃良彦, 土谷隆, 角田康夫, 寺野隆雄, 徳山博干, 刀根薫, 土肥正, 中井暉久, 中川覃夫, 中里宗敬, 中島恭一, 中島康之, 中塚利直, 中西昌武, 中野文平, 中丸麻由子, 永持仁, 長山いづみ, 中山幹夫, 生田目崇, 並木誠, 難波和明, 西岡靖之, 西村彰一, 根本俊男, 野々部宏司, 野村淳二, 橋田温, 蜂谷豊彦, 浜田和樹, 枇々木規雄, 平野雅章, 平林, 福川忠昭, 福島雅夫, 福本聡, 藤井進, 藤江, 藤重悟, 伏見正則, 藤本衡, 船木由喜彦, 古川浩一, 宝崎隆祐, 星野朝子, 堀内正博, 牧本直樹, 増山繁, 町原文明, 松井知己, 松井泰子, 真鍋龍太郎, 丸田利昌, 丸山明, 水谷昌義, 宮川（筑波）, 宮沢政清, 三好直人, 巳波弘佳, 六十里繁, 武藤滋夫, 棟近雅彦, 村松正和, 室田一雄, 毛利進太郎, 森清堯, 守口剛, 森平爽一郎, 森戸晋, 森村英典, 柳浦睦憲, 矢島安敏, 矢部博, 山川栄樹, 八巻直一, 山口俊和, 山口浩, 山下信雄, 山下英明, 山田茂, 山田善靖, 山地憲治, 大和毅彦, 由良憲二, 吉川武男, 吉瀬章子, 和光純, 渡辺隆裕

=== 事例編分類作業担当者 ===
:飯田哲夫, 小澤正典, 後藤順哉, 鈴木秀男, 武田朗子, 田中健一, 中田和秀, 福田恵美子, 宮代隆平, 宮本裕一郎, 森雅夫, 矢島安敏

=== 資料編執筆者 ===
:青木兼一, 朝尾正, 石井博昭, 石田甫, 梅根定, 亀澤善一郎, 児玉正憲, 後藤義雄, 権藤元, 田口東, 時永祥三, 中川覃夫, 永次廣, 西田俊夫, 日比野康文, 藤野義一, 三上操, 三根久, 本告光男, 柳井浩, 横山清, 若林信夫, 若山邦紘

ヘルプ:目次

2008-08-21T11:11:39Z

Fujimoto: "Help:目次" を保護しました。 [edit=sysop:move=sysop]

フリー百科事典『ウィキペディア（Wikipedia）』の[http://ja.wikipedia.org/wiki/Help:目次 Help]をご参照ください。

ORWiki:問い合わせ窓口

2008-08-21T11:11:30Z

Fujimoto: "ORWiki:問い合わせ窓口" を保護しました。 [edit=sysop:move=sysop]

[[OR事典編集委員会]]では、利用者の皆様からご意見、ご要望、ご感想などを受け付けております。
[mailto:wiki@orsj.or.jp こちらのリンクをクリックして]お送りください。
今後の内容改訂、運営の改善等に反映させていただきます。

なお、お送りいただいたメールに対する返信は保証致しかねますので、あらかじめご了承ください。

メインページ

2008-08-21T11:11:20Z

Fujimoto: "メインページ" を保護しました。 [edit=sysop:move=sysop]

<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr height="5">
<td bgcolor="#f39518" width="100%" height="5"></td>
</tr>
<tr height="17">
<td align="right" bgcolor="#ef7f1a" width="100%" height="17">[[画像:ortop.jpg]]</td>
</tr>
<tr height="5">
<td bgcolor="#ba7a28" width="100%" height="5"></td>
</tr>
</table>

= '''OR事典Wiki''' =

OR事典Wiki [[ORWiki:ORWikiについて|ORWiki]] にようこそ！

このページは，
[https://orsj.org 公益社団法人日本オペレーションズ・リサーチ学会]
[[OR事典編集委員会]]
によって作成されております．

== '''目　　次''' ==

[[基礎編：大項目一覧|基礎編]]

[[用語編]]

[[事例編]]

[https://orsj.org/wp-content/wiki/shiryou 資料編]

----
[[ORWiki:著作権|著作権]]について

----

AHP

2008-08-21T09:28:41Z

Fujimoto: "AHP" を保護しました。: 保護レベルのテスト中です。 [edit=autoconfirmed:move=autoconfirmed]

'''【えいえいちぴー (AHP (analytic hierarchy process)】'''
=== 概要 ===

階層化意思決定法とも訳されるが, 短くAHPと呼ばれることが多い. 複数の評価基準のもとで,多数の代替案の中からの選択, 複数の要素のすべてあるいはその一部へのリソースの配分, 複数の要素の評価や順位づけ, というタイプの決定問題のツール. 問題全体を, 究極の問題, 評価基準, 代替案という階層図に表現する. その上で, 2要素の一対比較という直感的な判断を基に, 問題全体の大局的な判断に合成する方法.
=== 詳説 ===
　階層化意思決定法とも訳されるが, 通常[[AHP]]と呼ばれる. トマス・サーティー(Thomas L. Saaty)が, アメリカの政府機関でダンツィックらと数理計画の開発や応用をしていた経験から, トップの意思決定者が抱える構造がはっきりしなかったり複雑な問題を扱えるモデルや方法はないかと考えた上で, 開発された方法. 問題の構造を把握し難いときでも, 問題全体を, 究極の狙い, 評価基準, 代替案という[[階層図 (AHPにおける)|階層図]]に表現することで明らかにした上で, 複数の評価基準のもとで, 多数の代替案の中からの選択, 複数の要素へのリソースの配分, あるいは複数の要素の評価や順位づけをする方法. 最終的には問題全体から見た代替案の重要度を求めるが, その基礎は, 2つの要素の一対比較という直感的で単純な判断の積み重ねで, これを基に問題全体の大局的な判断を支援する. 実際に組織の中だけではなく社会や公共の意思決定の場で広く実際に利用されている. [Saaty(1980, 1994), 刀根・真鍋(1990)]

　[方法の概要]: AHPを用いて問題の解決を図るには, まず問題全体の構造を階層図(図1)に表す. もっとも簡単な構造は, 問題－評価基準－代替案の3層の図である. 評価基準の層の要素は互いに従属しないように選ぶ必要がある. その下に代替案を並べた層を設ける.

<center><table><tr><td align=center>[[画像:0224-a-h-01-kiso-zu1r.png|center|図１：階層図]]</td></tr>
<td align=center><br>図１：階層図</td></table></center>

　この階層図の上で, 最上層の問題から見た各代替案の重要度を求めて意思決定の支援をしたいのである. そのためにはまず第1層の問題から見た第2層の評価基準 <math>c_k\, </math> の重要度 <math>u_k\, </math> を求める. さらに各評価基準 <math>c_k\, </math> の下の代替案 <math>a_j\, </math> の(局所)重要度 <math>v_{kj}\, </math> を求める. そのうえで, 代替案 <math>a_j\, </math> ごとに, 各評価基準 <math>c_k\, </math> の下での重要度 <math>v_{kj}\, </math> の, 評価基準の重要度 <math>u_k\, </math> で重み付けをした和 <math>\textstyle \sum u_k v_{kj}\, </math> を取って, 代替案 <math>a_j\, </math> の(総合)重要度とする. この重要度を求める過程で一対比較評価をしている.

　[一対比較から重要度の計算へ]: 例えば評価基準が4つあったらそれらを <math>c_1\, </math>, <math>c_2\, </math>, <math>c_3\, </math>, <math>c_4\, </math>と表し, それぞれを要素と呼ぶ. 4要素あると <math>4(4-1)/2=6\, </math> 組の対があるのでそれらの対の2要素の重要さを比較判断する(一対比較する). 要素 <math>i\, </math> を要素 <math>j\, </math> と比べて値 <math>a_{ij}\, </math> を表1に従って定め, 行列に表したもの <math>A=[a_{ij}]\, </math> を[[一対比較行列]]と呼ぶ.

<center>
<caption>表１：一対比較の基準尺度<br></caption>
<table width="300">
<tr>
<td colspan="2" align="left">要素 <math>i\, </math> が要素 <math>j\, </math> に比べて</td>
<td align="center" width="50"><math>a_{ij}\, </math></td>
</tr>
<tr>
<td colspan="3" align="left">
<hr>
</td>
</tr>
<tr>
<td align="left">同程度に重要なとき</td>
<td align="center" width="50"><math>\rightarrow\, </math></td>
<td align="center" width="50">1</td>
</tr>
<tr>
<td align="left">やや重要 </td>
<td align="center" width="50"><math>\rightarrow\, </math></td>
<td align="center" width="50">3</td>
</tr>
<tr>
<td align="left">かなり重要 </td>
<td align="center" width="50"><math>\rightarrow\, </math></td>
<td align="center" width="50">5</td>
</tr>
<tr>
<td align="left">非常に重要 </td>
<td align="center" width="50"><math>\rightarrow\, </math></td>
<td align="center" width="50">7</td>
</tr>
<tr>
<td align="left">圧倒的に重要</td>
<td align="center" width="50"><math>\rightarrow\, </math></td>
<td align="center" width="50">9</td>
</tr>
<tr>
<td colspan="3" align="left">
<hr>
</td>
</tr>
<tr>
<td colspan="3" align="center">2, 4, 6, 8 という中間値も適宜使う. </td>
</tr>
<tr>
<td colspan="3" align="center"><math>a_{ji}=1/a_{ij}\; ,\; a_{ii}=1\, </math> とする. </td>
</tr>
</table></center>

　要素 <math>c_j\, </math> の重要度(ウエイト (weight)あるいはプライオリティ (priority)とも呼ぶ)を <math>w_j\, </math> とすると, <math>w_i / w_j\, </math> を <math>a_{ij}\, </math> で推定していると考えられる. 行列 <math>A\, </math> の要素 <math>a_{ij}\, </math> を <math>w_i / w_j\, </math> で置き換えた上でベクトル <math>{\boldsymbol w}\, </math> を右から掛けると,

<table align="center">
<tr>
<td><math>A {\boldsymbol w}\, </math></td>
<td><math>=\, </math></td>
<td> <math>\left[ \begin{array}{cccc}<br>
1 & w_1 / w_2 & w_1 / w_3 & w_1 / w_4 \\
w_2 / w_1 & 1 & w_2 / w_3 & w_2 / w_4 \\
w_3 / w_1 & w_3 / w_2 & 1 & w_3 / w_4 \\
w_4 / w_1 & w_4 / w_2 & w_4 / w_3 & 1
\end{array} \right] {\boldsymbol w}\, </math></td>
</tr>
<tr>
<td><br>
</td>
<td><math>=\, </math></td>
<td><math>n [ w_1 \dots w_4 ] ^{\top}\, </math></td>
</tr>
</table>

で, これは固有方程式 <math>A {\boldsymbol w}=\lambda {\boldsymbol w}\, </math> の形をしている. 行列 <math>A\, </math> の階数は <math>1\, </math> であり, <math>A\, </math> の固有値は最大固有値が <math>n\, </math> (要素数), その他のものは <math>0\, </math> であることがいえるので, <math>A=[a_{ij}]\, </math> の最大固有値 <math>\lambda_{\max}\, </math>に対する固有ベクトルを <math>{\boldsymbol w}\, </math> の値とする. この際に <math>{\boldsymbol w}\, </math> のすべての成分の和が <math>1\, </math> であるほうが便利なので, <math>{\boldsymbol w}\, </math> の成分を正規化した(各成分を<math>\textstyle \sum w_j\, </math>で割った)ものを重要度とする.

　[整合性]: 人間は一対比較で次のように整合性に欠ける判断をすることがある. (a)要素 AとBを比べるとBが好ましく, BとCを比べるとCが好ましいのに, AとCを比べるとAが好ましいとする. (b)AはBに比べて4倍程度強い, Cに比べると5倍くらい強いと判断したのに, BはCの7倍強いとする. もし整合性が完全にあれば, 3つの要素 <math>i, j, k\, </math> の間で<math>a_{ij} = a_{ik}a_{kj}\, </math> が成り立つはずである. 実際に整合性が完全にあると一対比較行列の最大固有値が要素の数に一致する(<math>\lambda_{\max}=n\, </math>)のでそのずれを<math>n\, </math>の大きさによらぬようにした <math>(\lambda_{\max}-n)/(n-1)\, </math> を[[整合度 (AHP一対比較の)|整合度]]とする.この値が<math>0.1\, </math>を超えると整合性が欠けることが強いので, 判断を再検討するなりやり直す必要があるとされている.

　また, 一対比較の結果に使われる数値をランダムに配置した同じサイズの多数の行列の整合度の平均値(ランダム整合度)に対するこの整合度の比(整合比)も<math>0.1\, </math>以下が好ましいとされ, 整合性の判断に用いられている.

　[ANPへ]: AHPでは階層図の各層の要素の間には従属性がないものとしている. しかし実際には, 層の中の要素の間どころか, 上下の層の要素の間にも従属性が強い場合もある. そこまで拡張すると問題のモデルは階層図ではなくネットワークになってくるので, その分野はANP(Analytic Network Process)と呼ばれている. 特に1990年前後からそのようなモデルの研究や応用が進んでいる[Saaty(1996), 高橋(1998)].

　[AHPのソフトウエア]: 実際の意思決定にAHPを使うには, そのためのソフトウエアを使うと便利である. 階層図を書くこと, 一対比較をすることの支援, 代替案の総合重要度の計算から, 評価基準の重要度の代替案の重要度に対する感度分析をすることまで助けてくれる.

　海外ではWindows用の "Expert Choice"がMS-DOS時代から数えると10回以上の改良の版を重ねて国際的にも広く使われている(アメリカExpert Choice社, 国内代理店:ディエムエス(株)が日本語版も出している). フィンランドのRaimo Hamalainenはヨーロッパの複数の国語を扱えるソフトを出している. 日本では(株)日本科学技術研修所の「ねまわしくん」がかなり普及している.

----

'''参考文献'''

[1] T. L. Saaty, ''The Analytic Hierarchy Process'', McGraw Hill, 1980. Reprinted as Vol. 1 of the AHP Series by RWS Publications, 1992.

[2] T. L. Saaty, ''Fundamentals of Decision Making and Priority Theory with the Analytic Hierarchy Process'', Vol. VI of the AHP Series, PWS Publications, 1994.

[3] T. L. Saaty, ''Decision Making with Dependence and Feedback: Analytic Network Process'', RWS Publications, 1996.

[4] 刀根薫, 真鍋龍太郎編, 『ＡＨＰ事例集』, 日科技連出版社, 1990.

[5] 高橋磐郎, 「講座:ＡＨＰからＡＮＰへの諸問題, I-V」, 『オペレーションズ・リサーチ』, 1998年1-5月号.

[[category:AHP(階層的意思決定法)|えいえいちぴー]]

AHP

2008-08-21T09:14:41Z

Fujimoto: "AHP" の保護を解除しました。

MVA

2008-08-06T08:12:52Z

Fujimoto: リダイレクトに変更

#REDIRECT [[平均値解析法]]

MVA

2008-08-06T08:11:10Z

Fujimoto: "MVA" の保護を解除しました。

'''【えむぶいえい (MVA (mean value analysis))】'''

:参照：[[平均値解析法]]

ORWiki:問い合わせ窓口

2008-08-06T05:32:55Z

Fujimoto: 問い合わせページの作成

MediaWiki:Sidebar

2008-08-06T05:20:44Z

Fujimoto: ページ名を変更

MediaWiki:Sidebar

2008-08-06T05:19:19Z

Fujimoto: 問い合わせリンクの作成テスト

ジャクソンネットワーク

2008-08-06T04:45:27Z

Fujimoto: "ジャクソンネットワーク" の保護を解除しました。

'''【じゃくそんねっとわーく (Jackson network) 】'''

== 概要 ==

各ノードはひとつまたは複数の[[窓口]]からなり，
[[指数分布]]にしたがうサービス時間でサービスを行い，
ノードでのサービスを終えた[[客]]は次のノードまたは外部を[[確率的経路選択]]に
したがって選ぶ[[待ち行列ネットワーク]]．
客をクラスにより区別しない．
外部から[[ポアソン過程]]にしたがって客が到着する開放型と，
常に一定数の客が網内を循環している閉鎖型に分けられる．
ネットワーク状態の定常確率分布は積形式をもつ．
基本的なモデルとして重要なものであり，広く応用されている．

== 詳説 ==

　ジャクソンネットワークの名は J.R.Jackson[5]に因る．1970年代後半から, 計算機システムの評価に応用されはじめた．待ち行列網の状態変化がマルコフ過程として記述され, 平衡方程式の解である定常確率分布が[[積形式解|積形式]]として陽に表される基本的なモデルとして重要なものとなっている．

　この待ち行列網の各ノードは指数分布に従うサービス時間をもつ窓口からなり, １つのノードのサービスを終えた客が，その客の履歴によらず，[[経路選択確率]]と呼ぶ一定の確率で次のノードを選ぶモデルである．すなわち，<math>M\, </math>個のノード<math>1, 2, \ldots, M\, </math>からなり，ノード<math>i\, </math>のサービス率はそのノードにいる客数<math>n\, </math>の関数で，<math>C_{i}\,(n) </math>と表すことができる．例えば，ノード<math>i\, </math>のサーバー数が<math>c_{i}\, </math>，サービス時間分布がサービス率<math>\mu_{i}\, </math>の[[指数分布]]ならば，<math>C_i(n)=\min(n, c_{i})\mu_{i}\, </math>である．ノード<math>i\, </math>のサービスを終えた客は経路選択確率<math>r_{ij}\, </math>でノード<math>j\, </math>に移動する．

　この網は，外部からの客の到着を仮定する[[開放型ネットワーク|開放型]]と，外部からの到着はなく，常に一定数<math>N\, </math>の客が網内を移動する[[閉鎖型ネットワーク|閉鎖型]]に大別される．開放型の場合，外部からの到着過程は到着率<math>\lambda\, </math>の[[ポアソン到着|ポアソン過程]]とする．外部から到着した客は確率<math>r_{0i}\, </math>でノード<math>i\, </math>に進み，ノード<math>i\, </math>のサービスが終了した客は確率<math>r_{i0}\, </math>で網から退去する．少なくとも一つの<math>i\, </math>について，<math>r_{i0}\,>0 </math>とならなければならない．閉鎖型の場合はすべての<math>i\, </math>について，<math>\textstyle \sum_{j=1}^Mp_{ij} =1\, </math> とする．
経路選択確率<math>r_{ij}\, </math> からなる正方行列を<math>P\, </math>とする．開放型の場合，状態<math>0\, </math>があるため，<math>P\, </math>は<math>M+1\, </math>次となり，閉鎖型の場合<math>M\, </math>次となる．
<math>P\, </math>をマルコフ連鎖の推移確率行列とみたとき，既約であると仮定する．客のクラスが複数の場合の[[混合型待ち行列ネットワーク|混合型]]
については，発展した型である[[BCMPネットワーク|BCMP型]]や[[ケリーネットワーク|ケリー型]]などのネットワークに分類される．また，外部からの到着があるが，系内に入ることができる客数に制限がある[[有限呼源待ち行列|有限呼源]](もしくは損失型)の場合，外部を一つのノードとみなすことにより，閉鎖型に帰着できる（[5]参照）．

=== 積形式解 ===
　この待ち行列網の状態を <math>(n_1, n_2, \ldots, n_M)\, </math> で表す. ここで <math>n_i\, </math> はノード <math>i\, </math> にいる客の数である. 定常状態確率を <math>p_{(n_1, n_2, \ldots, n_M)}\, </math> とすれば, これは次のような積形式になる.

<center>
<math>
p_{(n_1, n_2, \ldots, n_M)}=G^{-1} \prod_{i=1}^M
\, \frac{\alpha_i^{n_i}}{\prod_{n=1}^{n_i} C_i(n)}
</math>
</center>

上記の積で <math>n_i=0\, </math> となる項は1とする. <math>G\, </math> は[[ネットワーク状態分布の正規化定数|正規化定数]]であり, <math>\alpha_i\, </math> <math>(i=1, 2, \ldots, M)\, </math> は[[トラフィック方程式]]と呼ばれるつぎの方程式の解である.

<center>
<math>
\alpha_i = p_{0i}\lambda + \sum_{i=1}^M \alpha_j p_{ji},
\quad i=1, 2, \ldots, M, \qquad
\, </math>　開放型
</center>

<center>
<math>
\alpha_i = \sum_{i=1}^M \alpha_j p_{ji},
\quad i=1, 2, \ldots, M, \qquad
\, </math>　開放型
</center>

この方程式は，各ノード毎に到着率が退去率に等しいとして得られる1次の連立方程式である．開放型の場合，解<math>\alpha_i\, </math>は一人の客が網に到着してから退去するまでにノード<math>i\, </math>を訪問する平均回数にネットワークへの総到着率<math>\lambda\, </math>を乗じたものである．閉鎖型の場合は，トラヒック方程式は<math>P\, </math>の定常確率を求める方程式と同一であり，さらに，例えば<math>\alpha_1=1\, </math>とすれば，<math>\alpha_{i}\, </math>はノード1に到着してからまた次にそこに到着するまでの間にノード<math>i\, </math>を訪問する期待回数という意味をもつ．

定常分布が積形式となることから，開放型の場合，任意時点での，各ノードの列の長さは互いに独立になり，各ノードからの退去過程がポアソン過程になる．また，閉鎖型も含め，どんな部分ネットワークに対しても，部分ネットワーク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができる．
長さは互いに独立になる．また，閉鎖型も含め，各ノードからの退去過程がポアソン過程になる．したがって，どんな部分ネットワークに対しても，部分ネットワー%ク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができ, すなわち，[[ノートンの定理|ノートンの定理]]が任意の部分ネットワークに対して成り立つ[11]．さらに，１つのノードへの各到着時点で，到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する．これを[[到着定理|到着定理]]という．ただし，網が閉鎖型の場合には，任意時点の分布として，到着した客を除いた網を使う．さらにその客の退去時点での分布も同様であり[6]，この分布でのもとで，ノード<math>i\, </math>に到着してから，次にそこに戻るまでの平均周期時間はノードごとの平均訪問回数と平均待ち時間の積の総和となること等が求まる．

=== 正規化定数と性能評価量の計算 ===
　積形式解から定常分布を求めるためには正規化定数の計算が必要である．開放型の場合は容易であるが，閉鎖型の場合には，可能な状態が<math>\textstyle \sum_{i=1}^M n_i =N\, </math>を満たすもに限られるので，工夫が必要である．例えば，閉鎖型正規化定数を計算する方法として，[[たたみ込み法]]や[[平均値解析法]]が知られている．[2]．たたみこみ法では, ノード <math>i\, </math> に対し, <math>N+1\, </math> 次元のベクトルを

<center>
<math>
X_i=(X_i(0), X_i(1), \ldots, X_i(N)),
\quad X_i(0)=1, X_i(n)= \frac {\alpha_i^{n}} {\Pi_{j=1}^n C_{i}(j)} \quad (n>0),
\ n>0
\, </math>
</center>

とし，<math>G=(X_1*X_2*...*X_M){\mathbf 1}\, </math>で与える．<math>*\, </math>はベクトルのたたみ込み演算である．定常分布が求まれば，スループットや平均待ち行列長の計算は比較的簡単である．しかし，正規化定数を計算することなく直接平均待ち行列長を計算する方法もある．例えば，平均値解析法は到着定理と[[リトルの公式|Littleの公式]]を応用し，平均列長などを系内客数<math>N\, </math>について0から繰り返し計算する方法である．各ノードでの平均待ち時間は到着時点での平均列長と平均サービス時間から求まる規律，例えば先着順であることが本質的である．

=== 待ち時間 ===
　待ち時間の分布については，特殊な網について考察されている．開放型で，サーバー数が1のノード(規律は先着順)が直列に並んでいる網もJackson型の一つであるが，この網で一人の客の各ノードでの滞在時間は互いに独立であることが[[バークの定理|バークの定理]]として知られている[1],[9]．これを閉鎖型にした場合，すなわち，最後のノードを退去した客は必ず最初のノードに戻る周期的な網でも，一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる[10]．一人の客が他の客に追い越されることがない(overtake free)という性質が本質的であり，バークの定理は，この影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ．特に最後のノードのサービス時間分布は任意でよい．その他，[[セントラルサーバモデル]]で規律が[[プロセッサシェアリング]]である場合の研究もある．(例えば[8])．

=== 負の客とシグナル ===
　ジャクソンネットワークの特徴は，ネットワーク内の各ノードに滞在する客数を要素とするベクトルを状態に取ると連続時間マルコフ連鎖により表されることにある．1990年代に[4]は，到着すると客数を減らす[[負の客]]という概念を導入し，同様なマルコフ連鎖によるモデル化を行い，ジャクソンネットワークと同様な積形式の定常分布をもつことを証明した．到着客が待ち行列に並んだ後にサービスを受けずに退去することがあるので，各ノードへの通常の客の総到着率は減少し，客の強制退去を考慮した非線形なトラヒック方程式の解として求められる．定常分布はこの変更された総到着率を使って表すことができる．その後，このモデルは，負の客が複数のノードを瞬間的に動き回る[[シグナル到着ネットワーク]]へ拡張され，積形式の定常分布をもつことが証明されている（[3]参照）．例えば，各ノードで集団サービスが行われるジャクソン型と同様なネットワークで，予定された大きさの集団がサービスされた集団のみ1つの客となり経路を選択するモデルは，シグナル到着ジャクソンネットワークの例である．

=== 集団移動型 ===
　ジャクソンネットワークと同様にポアソン到着やサービス時間が指数分布に従うモデルで，集団到着や集団退去があるモデルもあり，[[集団移動型ネットワーク|集団移動型]]と呼ばれる．このモデルは上記で述べた特別な場合を除いて，積形式の定常分布をもたないが，サービス集団の大きさがノードごとに独立であり経路の選択が集団ごとにまとめて行われる場合には，定常分布の補分布の上限を与える積形式分布が知られている（\[7],[12]参照）．また，このモデルは，サービス完了時刻でネットワークの変化を追うと離散時間型のモデルと見なすこともできる．

----

=== 参考文献 ===

[1] P. J. Burke, "The Output Process of a Stationary M/M/s Queuing System, ''The Annals of Mathematical Statistics'', '''39''' (1968), 1144-1152.

[2] K. M. Chandy and C. H. Sauer, "Computational Algorithms for Product Form Queueing Networks," ''Communications of the Association for Computing Machinery'', '''23''' (1980), 573-583.

[3]X. Chao, M. Miyazawa and M. Pinedo, ''Queueing Networks; customers, signals and product form solutions,'' Wiley, 1999.

[4]E. Gelenbe, ``Product-form queueing networks with negative and positive customers,'' Journal of Applied Probability}, (1991), 656--663.

[5] J. R. Jackson, "Jobshop-like Queueing Systems," ''Management Science'', '''10''' (1963), 131-142.

[6]T. Kawashima,
``A Property of two Palm measures in queueing networks and its applications,''Journal of the Operations Research Society of Japan, (1982), 16--28.

[7]M. Miyazawa, P. Taylor,
``A geometric product-form distribution for a queueing network with nonstandard batch arrivals and batch transfers,'' Advances in Applied Probability 29, (1997), 523--544.

[8] J. A. Morrison and D. Mittra, "Heavy-usage Asymptotic Expansions for the Waiting Time in Closed Processor-sharing Systems with Multiple Casese," ''Advances in Applied Probability'', '''17''' (1985), 163-185.

[9] E. Reich "Note on Queues in Tandem," ''The Annals of Mathematical Statistics'', '''34''' (1963), 338-341.

[10] R. Schassberger and H. Daduna. "Sojourn Times in Queueing Networks with Multiserver Nodes," ''Journal of Applied Probability'', '''24''' (1987), 511-521.

[11] J. Walrand, ''An Introduction to Queueing Networks'', Prentice Hall, 1988.

[12]H. Yamashita, M. Miyazawa,``Product form queueing networks with concurrent movements,''
. ''Advances in Applied Probability, '' '''30''' (1998), 1111--1129.

[[category:待ち行列ネットワーク|まちぎょうれつねっとわーく（じゃくそんがたとそのおうよう）]]

利用者:Fujimoto

2008-04-03T11:15:29Z

Fujimoto: とりあえず作成

藤本です。

== 専門分野 ==
*[[待ち行列]]
*[[確率過程]]