組合せ問題の並列アノレゴリズム
今井正治
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111l

考察する.まず， 2. では，組合せ問題の代表的な解法のはじめに並列化の可能性と適合性について述べる.

整数計画法などによって定式化される組合せ問題の多次には，組合せ問題の並列型アルゴリズムの実現に適した並

くは NP 完全であることが知られている.すなわち，こ列計算機システムを紹介する.の種の組合せ問題の最適解を求めるのに必要な計算量はアルゴリズムにおける異常現象について解説する.

問題の規模の増加に対して指数関数的に増加する.計算機技術の発展の結果，現在では，数 GFLOPS (数 10億3. で

4. では，並列型分校限定2. 組合せ問題の並列アルゴリズム浮動小数点演算/秒)の演算速度をもっスーパー・コン

これまでに知られている組合せ最適化問題の代表的なピュータが製造されている.しかし，このような超高速解法には，分校限定法，動的プログラミングなどがあ計算機を用いても，大規模な組合せ問題を解くためにはる.どちらの解法が与えられた問題を解くのに適していばく大な待聞が必要である場合が多い.

るかは，問題の性質および定式化による.ただし，これこれまで，組合せ問題の効率のよい解法として，

分枝限定法 (Branch-and-Bound method) ，動的計画法(Dynamic Programming)などが用いられてきたらの解法は L 、ずれも，広い意味で・の分割統治法 (divide­and‑conquer method)にもとづいている.

分割統治法を適用して組合せ最適化問題を解く過程で[4J , [IIJ. これらの解法の共通の特徴の 1 つは与は，多数の未解決な部分問題が生成される.このとき，えられた問題を複数の部分問題に分割し，個々の部分問これらの部分問題が互いに独立である場合には，それぞ題の解を求めることによって，原問題の解を得る」といれの部分問題を並行して解くことができる [3J ，う点である.原問題を分割して得られた部分問題は，多分枝限定法および動的プログラミングで、は，多数の独立くの場合それぞれ独立に解くことができる.この場合，な部分問題を扱う場合が多いので，この 2 種類の解法はこれらの部分問題を並列に処理することによって，原問L 、ずれも効率のよい並列化が可能である.

題を解くのに必要な計算時聞を短縮することが可能である.したがって，組合せ問題の並列処理は実用的な見地からも重要な問題である.

[13J.

3. 並列計算機システムのモデル
3.
1 並列計算機システムの分類

並列型分校限定アルゴリズムのふるまいに関しては，興味深い現象が知られている.すなわち，組合せ問題の並列処理の研究は，すでに 1970年代に開ρ 台の処理装始されている.

しかし，当時に計算機の処理速度も遅置をもっ並列計算機、ンステム上並列型分校限定アルゴリ

く，大規模な並列計算機システムを実現することは非常ズムで組合せ問題を解くために必要な計算時聞を T( ρ)に困難であった.しかし，近年の VL S 1 (超大規模集とする.このとき，ある条件のもとで ，となる場合がある.

この現象は，

T(1)/T(p)>p積回路)技術の発展の給果，多数の処理装置をもっ並列加速異常 (accelera­

計算機システムを実現することが容易になり，数千~数tionanomaly) と呼ばれ，並列型分校限定アルゴリズ万台の処理装置をもっ超並列計算機 (Highly Parallel

ムに特有の現象である.他の並列アルゴリズムでは ，Compter System)(1)/T(p) 壬 P となるのが普通であり，Tこのような異常現象は報告されていない.

も試作されている.

計算機システムの構成方法は，命令列およびデータ列の形態にもとづいて，次の 4 種類に大別できる [2 ].

本論文では，組合せ問題の並列アルゴリズムについて(1) S 1SD :Single‑Instruction Stream ,Single‑Data Stream

いまいまさはる

豊橋技術科学大学情報工学系〒 441 豊橋市天伯町雲雀ケ丘 1-1

384(10)(2) S 1M D:Single‑Instruction Stream ,Multiple‑Data Stream© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

(3) M 1SD :Multiple‑Instruction Stream.
Single‑Data Stream~列型分校限定法でも，これらの探索戦略を用いるこ(4) M 1M D:Multiple‑InstructionStream.
Multiple‑Data Streamとができる.この場合，理論的な興味は，次の 2 点であろう.

(1 ) プロセッサの台数および探索戦略と記憶容量の3.
2 組合せ問題向き並列計算機システム
2. で述べたように，分枝限定法や動的計画法の並列アルゴリズムでは，部分問題の独立性に着目して，部分問題をそれぞれ異なる処理装置に独立したタスクとして割りつけて解くと L 、う方針が有望である.

に対して指数関数的に増大する [4 ].

したがって，MIMD 型のシステムは，組合せ問題の並列アルゴリズ関係(2) プロセッサの台数および探索戦略と計算時間の関係

4.
2 プロセ .
.
，サの台数と記憶容量複雑さの関係深さ優先探索を用いる並列型分校限定アルゴリズムでムの実行に適していると考えられる.組合せ問題の並列必要な記憶容量は，問題の規模 (n)アルゴリズムの主要目的は，問題を多数のプロセッサで数 (ρ) の積 (n.p) に比例する[ 5].とプロセッサの台処理することによって問題を解くのに要する時間を短縮

また，並列型分枝限定アルゴリズムで最良優先探索をすることである.したがって，多数のプロセッ+を効率用いた場合に必要な記憶容量は，逐次的分校限定法の場よく稼働させられるようにシステムを構成することが望合と同様に，問題の規模 (n) に対して指数関数的に増ましい.

大する[ 5J.

組合せ問題向きの並列計算機システムのアーキテク
チャとしては，主に以下のような構成が提案されている.

4.
3 プロセ.~サの台数と計算時間との関係
並列型分枝限定アルゴリズムでは，プロセッ+の台数と計算時間との関係に関して，異常現象 (anomalies)(1) MIMD 型密結合システムと呼ばれる興味深い現象が観察され，問題的解析も行な(2) M IMD 型疎結合システム

われている〔ラ J ，・環状(ring)・木状 (tree)
・超立方体

プロセッサ [18J

プロセッサ [1 J , [6J , [8J. [13J(hypercube)[9J.[10J.[12J.[16J.[
19J.

この現象について説明するために，分校限定アルゴリ

プロセッ-Ij-[14J

これまで，組合せ問題の並列アルゴリズムは，主として MIMD 型の並列計算機をモデルとした研究が中心でズムの計算時聞を，アルゴリズム中で処理される部分問題の個数で評価することにする.

以下では，ρ 台 (p 註1)のプロセッサをもっ並列計算機上での，並列型分校限定アルゴリズムの計算時間を T(p) で表わす.また，あったが，最近 S IMD 型の計算機を対象にしたアルゴアルゴリズムの加速率 (speed-up)

リズムの研究も行なわれている[ 7].

(ρ) で表わす.

4. 並列型分枝限定アルゴリズム
4.1

を S(P) 三 T(I)jT

一般に，総計算量が同一であれば，逐次型アルゴリズムの計算時間 T(I) と並列型アルゴリズムの計算時間 T(p) の聞には，明らかに，探索戦略

分校限定法で，部分問題の処理の順序は探索戦略(searchstrategy) と呼ばれる.アルゴリズムを実行するのに必要な記憶空間の複雑さ(space complexity)

およびアルゴリズムの計算時間の効率( efficiency) は，採用される探索戦略に大きく依存する.最もよく用いられる基本的な探索戦略は次の 2 種類である.

search)(1) 深さ優先探索(depth-first(2) 最良優先探索(best-first search)

逐次的な深さ優先探索では，問題の規模に比例する記憶容量があれば，問題を解くことができる.一方，最良T (1) ミ T(p) ミ T(I)jρ( 1)という関係が成り立つ.したがって，加速率 S( ρ) は

(2)

1~玉 S(p)~pとなる.

分校限定法の場合には，アルゴリズムを並列化することによって，部分問題の探索順序が変化し，総計算量自体力:変化する.したがって，次の 2 通りの異常現象が起こりうる.
T(p)<T(I)jρ(S(p)> ρ)(3)T( ρ )>T(I)

(S(p)
<I)

(4)

優先探索では，最適解を得るために処理される部分問題

式 (3 )が成り立つ場合には，プロセッサの台数分以の個数が最小であるが，必要な記憶容量は，問題の規模上に処理速度が増加することになる.この現象を加速異1992 年 8 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(11)385したがって，最良優先探索を用いた場合には，異常現Sp田d-up

象は生じない.

T(l)
T(P)

4.
3.
2 深さ優先探索

Acceleration
Anomaly(SuperUnear
Spee‑up)

次に，深さ優先探索を用いた場合について考える.深
さ優先探索を用いた並列型アルゴリズムて・は，異常現象

T(1)
T(P)が生じうる.これは，以下の理由による.

P く一一一

まず，深さ優先探索を用いる場合，逐次型分校限定ア

NormalSpeed up

ルゴリズムにおいては，臨界部分問題はすべて処理する

•T(I)
T(P)

l 三五ー←一一三五 P必要があるのは当然であるが，臨界部分問題に含まれない部分問題も処理する可能性がある.したがって，T(I) ミ ICIv'dmoh主唱nは処理しなければならないので，i

く旧、ノ一、ノn

一

図 1

叫 1-Pcee1

7i(
凹 T一TD0(8)となる.並列型分校限定アルゴリズムでも臨界部分問題

T(p) 己 ICI/ρPno.0
1pro四回ors

並列型分枝限定アルゴリズムにおける異状現象(9)となる.ところが，T(p) ・ ρ <T(q) ・ q(10)となるような探索木および p ， q(p>q 註 1) が存在するこ常 (acceleration anomaly) または超線形加速 (super­linear speed-up) と呼ぶ.また，式 (4 )が成り立つ場
合を減速異常 (deceleration anomaly) と呼ぶ(図 1参照).

もちろん，

I 正常 J な状態では，S(ρ) の上界とこれらの異常現象は，探索戦略および目的関数の下界と深い関係がある.探索戦略によって，探索される部分問題の集合が異なるからである.以下の節では，最良優先探索および深さ優先探索の 2 種類の戦略で，異常現象

4.
3.
1 最良優先探索
まず，最良優先探索を用いた場合には，異常現象は起以下の理由による.

臨界部分問題(criticalsubproblem) の集合 C を次式で定義する.
(5)

C={sllow(s) 豆 Copt}

上式で ， s は部分問題を表し， low(s) は s の最適解の下界(l ower bound)(11)となり，加速異常が生ずる.
また，式 (9 )より ，T( ρ ).p の下界は ICI であるの場合には，(12)S(p)<1となり減速異常が生ずる.

このように，深さ優先探索を用いる並列型分校限定アルゴリズムでは，加速異常および減速異常が生じうる.

が起きうる可能性について述べる.

これは，S(P)>pで，式 (4 )を満足するような探索木も存在する.この下界は式 (2 )で与えられる.

こらない.とが知られている[ 5J ，日 OJ. q=1 の場合には，を表す.また，Copt は，原問題

5. おわりに木論文では，分校限定法を中心として，組合せ問題の並列型アルゴリズムについて述べた.また，並列型分校限定アルゴリズムに特有の，異常現象について簡単に紹介した.

頁数の制約もあり，分校限定法以外の解法(動的プロの最適解の目的関数の値を表わす.最良優先探索を用グラミング法，分割l統治法など)の並列化については，

いる逐次型分校限定アルゴリズムの計算時間 T(I) は，わずかしか述べられなかった.しかし，これらの解法もICI と等しい.すなわち，ICI は総計算量の下界を与え並列化に適しており，多数の研究成果が報告されている.

る.並列型分校限定アルゴリズムでも，すべての臨界部VLSI 技術の発展の結果，計算機の処理速度自体も高分問題の処理が終了するまて、は，アルゴリズムは停止し速化され，多数の処理装置をもっ超並列計算機の実現もない.したがって，容易になった.もちろん，並列化によって組合せ問題のT(p) 註 T(I)/ρとなる.

また ，

(6)

T( ρ) の上界は次式て‘与えられる [IOJ.

T (1) 孟 T(p)

3
8
8(12)

(S(P) 壬 p)

(S(p) 註 1)

(7 )本質的な困難さ自体が変化するわけではない.しかし，これらの超並列計算機を用いることにより，従来計算時間の制約のために解くことができなかった.大規模な組© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

合せ最適化問題のいくつかが実用的な時間内で解けるよraJ
lelBranch‑and‑Bound Algorithms'\CACM ,うになると期待される.

Vo 1.27, No.6 , pp.594‑602(1984).
[IIJ E.L. Lawlerand D. Wood: “ Branch-and-参芳文献

Bound Methods:a Survey ヘ Oper. Res. , Vol.

[1J S.H.Fu Jl er , J.K.Ousterhout , eta l.:“ Multi-14, No.4, pp.699‑719 (1966).

Microprocessors:An Overview and working.J. Li and B. W. Wah: “ Coping with
[12J Gof IEEE , Vol.66 , No.2, pp.

ies in Parallel Branch‑and‑Bound AlｭAnoma1Example に Proc.

gorithms" , IEEE , Trans. on Comp. , Vol.35 ,216‑
228(1978).
[2J M. J. Flynn: “ Some Computer Organiza.
tions and their EffectivenessぺIEEE ，Trans.

. C-21 , No.9 , pp.948‑960(1972).
on Comp.., Vol[3J E. Horowitz and A. Zorat: “ Divide-andConquerforParaJ
lelProcessing ヘ IEEE ， Trans.

.C-32 , No.6 , pp.582‑585(1983).
on Comp. , Vol[4J 茨木俊秀:組合せ最適化一分校限定法を中心として，産業図書(講座数理計画法 8) (1983).

[5J 今井正治，No.6 , pp.568‑573 (1986).
[I3J F.J.Peters: “ The TreeMachinesandDiｭ

nvide‑and‑Conquer algorithms ぺ Lect. Note i1981).
Comp. Sc i., Vo 1. 111 , pp.25‑36 (口 4J

M. J. Quinn: “ Analysis and Implementaｭtionof Branch‑and‑Bound Algorithms on aHypercube Multicomputer" , IEEE , Trans. on
Comp. , Vol.39 , No.3 , pp.384‑387 (1990).

福村晃夫: r 分校限定アルirst[15J V.N.RaoV.Kumar: “ Para Jl el DepthF

ゴリズムの並列化とその評価 J ，電子通信学会論文誌，.Implementation ヘ In t' l Jour.ofSearch.Part1

吉田雄二，Vo 1. 62-D , No.6 , pp.403‑410 (1979).
[6J M. Imai:“ A Double‑Tree StructuredMul.

Para. Prog.., Vo l. 16 , No.6 , pp.479‑499 (1987).
日 6J

E. A. Rpuul and G. L
. Nemhauser: “ Bra-ticomputer System and its App1ication tonch‑and‑Bound and P
arallel Computation:ACombinatorial Problems ヘ電子情報通信学会論文

HistoricalNote" , Oper.Res. Let t., Vol.7, No.

誌，Vol. E-69 , No.9 , pp.1002‑101O(1986).

[7] 岩本市造，

岩間一雄: r 組合せ問題に対する RS型ベクトノL アルゴリズム J ，電子情報通信学会論文誌，

Vol. J75-D-I , No.3 , pp.143‑151 (1992).
[8J A.K. Jones and P. Schwarz:“ Experience1988).
2, pp.65‑69 (日7]中島利朗，

他: r 動的計画

法の並列計算 J ，情報処理学会論文誌，

瀬口靖幸，田中正夫，

Vo 1. 26 , No.

6, pp.824‑
830(1985).
〔日1同8回叫JB. W. Wa油h and Y. W. Ma:

using Multiprocessor Systems‑A Status Reｭ

勘Multic∞ompu
凶te目rport" , ComputingSurveys , Vol.12 , No.2 , pp.

bina悶atωorial Ex
剖tr陀ememum-Search Problemsピ"， IE­

121‑165(1980).

EE , Trans. on Comp. Vol. C-33 , No.5 , pp.377[9J V.KumarandV.N.Rao:“ Para Jl el Depth'lJour.
Fir
st Search. Part II. Analysis"., Int

Architecturefor Solving Comｭ

390(1984).
日 9JB. W. Weide: “ Modeling Unusual Beha ・Para. Prog. , Vo l. I6 , No.6 , pp.501‑519 (1988).

viorofParaJ
lel Algorithms ヘ IEEE ， Trans.on[IOJ T.H.LaiandS. Shani: “ Anomalies inPa‑

Comp. Vol
.C-31 , No.11 , pp.1126‑1130(1982).

1992 年 8 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(13)367