- 著者
-
今井 浩
- 出版者
- 公益社団法人日本オペレーションズ・リサーチ学会
- 雑誌
- Journal of the Operations Research Society of Japan (ISSN:04534514)
- 巻号頁・発行日
- vol.26, no.1, pp.61-83, 1983-03
枝に容量制約が与えられたネットワーク上で相異る2点間の最大流量の流れを求める最大流問題は、最短路問題と並んでネットワーク・フロー理論の基礎を成している。そして、実際に最大流を求めるための算法は、交通流。通信網解析等に直裁的に応用されるばかりでなく、他のネットワーク問題の部分問題として頻繁に現われるという意味で重要である。最大流算法としてはFordとFulkersonがラベリング法を与えて以来、理論的に計算の手間を改良した様々な算法が発表されてきた。特にここ数年の進展には驚くべきものがあり、現在では、最悪の場合でもO(|A| |V| log |V|)の手間で最大流を求める算法がSleatorとTarjanにより与えられている(|A|:枝数、|V|:点数)。しかし、実用に際してどの最大流算法が最も役に立つかという問題に関しては、あまり研究が成されていなかった(理論的に最悪の場合力)かる手間のオーダが低い算法が、実用に際して最も役に立つというわけではない)。最近、この問題に対してCheung、またGlover et al。が計算機実験による興味深い結果を得ているが、Cheungの計算機実験にはデータ構造。試験ネットワークの点で問題があり、Glover et a1。は全体として優れているもののKarzanovの算法を試していない点など不十分なところもある。本論文では組織的かつ大規模な計算機実験に基づいて、各種最大流算法の実用に際しての有用性を評価する。そのためにまず、各種算法をプログラム化する段階でそれらの効率化を図る。一般に論文での算法と現実のプログラム上の算法との問にはかなりの隔りがあるが、この"効率化"はそれを埋めるものであり、具体的には如何に最適のデータ構造を選び、用いるかという議論が中心になる。そして実際の計算機実験における試験ネットワークとしては、単にランダム・ネットワーク、格子状ネットワークといった人為的なものだけでなく、他に現実の道路網を用意し、それを"加工"したネットワークも用いる。この方法は、ネットワーク算法の有用性を計算機実験により評価する際には非常に有効である。他にも試験ネットワークとして特殊構造を持つものを考え、各算法の特徴をより明らかにすることも行う。上記のような綿密な計算機実験の結果から、本論文では次のような結論を得ている。(結論)実用上、最も役に立つのはDinicの算法とKarzanovの算法である。Dinicの算法は簡単(プログラムのし易さはラベリング法と変らぬ程)であり、通常の場合ではこれで十分である。Karzanovの算法は最悪の場合の保証という点でDinicの算法より優れているが、記憶領域をより多く必要とする。