著者

関根 京子 今井 浩

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1996, no.100, pp.25-32, 1996-10-17

---

ネットワーク信頼度計算の問題は,一般に#P完全な問題で,大規模ネットワークの信頼度を厳密に実用的時間内で求めることは難しいと思われている.そのため,近似解法として,信頼度の上限下限を多項式時間で求めること,またモンテカルロ法で確率的に近似解を求めることが考えられてきた.後者について,計算量・アルゴリズム理論的観点から,近年,ランダム化(andomizatio)を用いたランダム化FPTAS (andomized Fully Polynomial?Time Approximation Schem)が開発されている.一方,関根,今井は,BDDを援用したネットワーク信頼度の厳密求解法を提案している.本稿では,ネットワーク信頼度計算に対するランダム化FPTAS解法(モンテカルロ法)とBDDを援用する厳密解法の2つについて,後者で得たある程度大きいグラフの厳密な信頼度関数とモンテカルロ法で得た値の比較などを行ない,両者の種々の場面での性質について論じる.Computing the network reliability is a #P-complete problem, and is believed hard to solve if the problem size is large. Recently, randomized fully polynomial-time approximation schemes for computing the network reliability have been developed by Alon, Frieze, Welsh [1] and Karger [15]. There are also proposed several enhanced Monte Carlo methods which utilize lower and upper bounds for the reliability, etc. On the other hand, Sekine and Imai [24] propose an exact approach based on BDDs. By this method, the reliability of a moderate-size network can be computed rigorously. They also present a polynomial-time algorithm for the case of complete graphs. This paper performs compurational experiments, and discusses features of these methods.

著者

今井 浩

出版者

公益社団法人日本オペレーションズ・リサーチ学会

雑誌

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の算法より優れているが、記憶領域をより多く必要とする。