半順序の最適系列分割問題の構造と算法構成

(1)

半順序の最適系列分割問題の構造と算法構成

加地太一

1.はじめに

Kernighanの最適系列分割問題 1)･4)は,1からnまでの連続的な番号を各頂点に付与したグラフにおいて,各ブロックの頂点の重みの総和がブロックサイズ B以下であり,かっ頂点番号の連続性が保持される頂点集合の分割で, カット辺のコストの総和が最小となるものを求める問題である｡すなわち]見点間が全順序な関係をもつ一列化グラフに対する分割を扱ったものである^｡この問題の一つの応用例としては,プログラムを一定の大きさの単位で記憶容量に割当を行うページングの問題などがある｡しかし,多くのシステムの構成は単純な全順序関係で構成されるより,より複雑な半順序関係で構成される｡

本論分ではより一般化した半順序関係をもっ無閉路有向グラフの系列分割問題に展開し,より応用性の広い問題に拡張する｡このとき対象となる問題として半順序なグラフ構造を利用するスケジューリング問題,ラインバランシング問題,および並列処理等の問題が上げられる｡

全順序の系列分割問題の場合は系列性を頂点の連続番号の保持によって表し, また分割を単純にブレーク･ポイントを用いることによって表現することなどができた｡これらによって問題を単純に体系づけることができ,また効率的な算法を組むことができた｡しかし,より一般化した半順序の系列分割問題の場令,問題を体系化し,効果的な解法を構築するためには,いくつかの点においてより詳細化した構成と再定義が必要となる｡

〔185〕

(2)

186 _商 _学 _討 _究 _第45巻 _第 _2号

本論分では,半順序の系列分割について理論的考察を行い,その性質を明らかにする｡まずKernighanの頂点番号の連続性の保持より一般化した系列性の保存の定義を示す｡またブレーク･ポイントの切断に対して,半順序集合のグラフの切断を明確化し,部分集合を分離する概念から分割の定義を導く｡このとき,部分集合問にサイクルが存在しないとき,推移律が存在する｡以上の系列性の保持,分離可能性,非サイクル性より半順序の系列分割が定義される｡

また,その性質より,系列分割から切断の鎖が導かれることができ,逆に切断の鎖から系列分割が一意に導かれることを示し,切断を考慮することによって系列分割の概念を導出する｡

次に,カット辺の総和を最小にする系列分割を最適系列分割と呼び,切断を切断決定子で表すことによって,最適系列分割問題を効果的に定義できることを示す｡

さらに,最適系列分割問題の効果的な解法を考察する｡まず,任意の切断決定子からレベルの一つ高い切断決定子を生成する基本操作とその生成過程の関係式を明らかにする｡この基本操作の展開によってすべての切断決定子を含む木が導出される｡次に,探索空間の縮小を試みるために,先の木を既約化する算法について述べる^｡この算法過程において,切断決定子の生成が,また同レベルの切断決定子の判定が効率的に行えることを示す｡さらに, この既約化グラフをもとにした探索空間上で最適性の原理を用いて効果的に解を導き出すことを示す｡具体例として,標準的な動的計画法による算法構成を提示する｡また,増分コストの計算が漸化式により効率的に計算でき,さらに分枝限定法の手法および細分化禁止別を導入することによって計算の負担を軽減することができる可能性について付記する｡

2.半順序の系列分割と切断の鏡

無閉路有向グラフD (V,E)が与えられたとき,Dの有向辺が定めるV 上の関係の反射的かつ推移的な閉包を与える関係を≦とし,それから導かれる

(3)

半順序の最適系列分割問題の構造と算法構成 187

半順序集合を (Ⅴ,≦) とする｡これをグラフDから導かれた半順序集合と呼ぶことにする｡このとき,Dについて次の性質が成り立っ｡(V,≦)の2元 U,Wに対して U≦Wが成立するならば, Uから出発^Lwに至るD上の有向路が存在する｡またDが入口 (source)と出口 (sink)を持っとき, これら

に対応して,(V,≦)は最小元と最大元を持つ^｡

ここで,空でない部分集合 U⊂Vから誘導されたDの部分グラフをHとする｡Hの任意の2点を結ぶDの有向路がすべてHの有向路となるとき,Hは半順序の系列を保持するDの部分グラフであるという^｡これは (V, ≦)の部分半順序集合 (U, ≦)が H から派生された半順序集合 (U, ≦) と一致することを意味している｡

また,Vの部分集合AがAcxAから選んだ2元対 (x,y)に関して,"x とyが比較可能ならば常にx<yが成立する" という性質を持っとき,(Ac, A)をAによって定まるVの切断という^｡そしてAcをこの切断の下租,Aを上組とい^う ^｡

2つの切断(Ac,A),(Bc,B)に対して関係Ac⊆Bcが成立するとき,(Bc, B)は (Ac,A)より優位にあるといい,(Ac,A)<‑ (Bc,B)で表す｡

また真に優位であることを記号 (Ac,A)<≠ (Bc,B)で表す｡Vの切断集合の上でこの関係は半順序関係となる｡ 2つの切断 (Ac,A),(Bc,B) を合成して新しい切断を生成することができることを以下に示す｡

補題 1. (Ac,A), (Bc,B)が切断ならば (AcnBc,A uB)もまた切断である｡

証明 : AcnBc‑(A UB)Cであるから,(AcnBc,A uB)‑ ((A UB)C,A uB)である｡x∈AcnBcとy∈A UBは比較可能な 2元であるとすれば,x

∈Acかつ Ⅹ∈Bcであり,y∈Aまたはy∈Bである｡y∈Aのとき,x∈Acより,Ⅹ<y,またy∈Bのとき,x∈Bcより,x<yとなる｡いずれにしてもx

<yが導かれる^｡ □

(4)

Jgg _商 _学 _討究第45巻第 2号

さらに,V の互いに素な部分集合XとYがそれぞれ V のある切断の下組と上組に含まれるならば,X とY は切断により分離されるといい,X IYで表す｡

X とY についてX iY またはY IX が成り立つとき,XとY は分離可能であるという｡ X IYはXが Yより入口に近いことを表しているO ここで Kernighanの系列分割の2つの特徴を拡張して,半順序の系列分割を次のよ

うに定義する｡

D (V^,E)の頂点集合 Ⅴの分割 Vl,V2,･･･,V^kが次の性質を満たすとき, これをVの系列分割という｡

(1) 各Viは半順序の系列を保持するVの部分集合である｡

(2)任意に選ばれた2つの部分集合VlとVJは分離可能である｡

(3) 任意に選ばれた部分集合の3つの組Vt,V,,V^k^の間にはVilV^,,

V^j 弓V^k,V^k LVlというサイクルを形成する関係は存在しない.

このとき,(1)はKernighanの連続番号の保持と相応し,(2)と(3)は分割を形成している各部分集合の前後関係が決定できることを保障する｡図 1は半順序関係を表す無閉路有向グラフの系列分割の一例である｡

以後,半順序の系列分割が切断の鎖によって一意に表現できることを論証する｡まず,切断によって分離可能な集合に対して成り立っ性質を以下に述べる｡

一一 ■ 一一一■ 一一一一一一一■一一一一一一‑一一一^{‑ ‑}^I 図 1 無閉路有向グラフの系列分割

(5)

補題 2. XとYがある切断により分離可能であるとき,条件 ∃ (x,y)∈X xY ;x<yが成立するならば,X IYである｡

証明 : X iYでなくY JXが成立したとすると,Yはある切断の下組に,X は上組に属するのだから,比較可能なすべてのx∈X,y∈ Yに対してγ<xが成立しなければならない｡これは定理の条件に矛盾する｡ □

X を半順序集合 (V, ≦)の部分集合とする｡X から導かれるV の部分集合P (X)を次のように定義する.

p (x)dgfxせズ(yly∈V,y≧xI (1)

P (X)は部分集合Xの後続者集合であり,P (X)について次の補題が成立する｡

補■題3. Xが Vの半順序の系列を保持する部分集合とすれば,(Pc(X), P (X))はVの切断である｡

証明 : x∈ Pc(X)とy ∈ P(X)が比較可能とする｡まずP(X)の定義より,y ∈ P(X)から∃ Z∈X ; Z≦y が成立する｡今,x<yが成立せず, x≧ yとなったとすると,上式より Z≦xが導かれ,x∈ P(X)が結論され

る｡これはx∈ Pc(X)に矛盾する｡口

また,P(X)は和集合に関して次の補題を持つ｡

#3 4. P(X UY)‑P(X)UP(Y)

証明 : ∀ Z∈ P(X UY)とすると, ∃x∈X UY ; Z≧xとなる｡よってx∈ X ならば,Z∈ P(X)であり,x∈ Yならば,Z∈ P(Y)である｡それゆえ,x∈ P(X)uP(Y)となる｡

逆に,x∈ P(X)uP(Y)ならば,x∈ P(X)で, これより∃Z∈X ;x≧ Z

またはx∈ P(Y)で, これより∃Z∈Y ;x≧Zが成立する｡この 2つの命題を一つにまとめると,P(X)uP(Y)の属する任意のxに対して, ∃Z∈X

uY ;x≧Zすなわちx∈ P(X UY)となる｡口

(6)

190 商学討究第45巻第 2号

補題 5. XIYならば,X ⊆ Pc(Y),Y ⊆ P(Y)が成立する｡

証明 : Y ⊆ P(Y)は自明であるO次に,X CIPc(Y)の成立を背理法によって示す.X ⊆ Pc(Y)を否定すると,

jxE X ; xEP(Y)

を満たす元xが存在する｡そうすると,P(Y)の定義より

∃y ∈ Y ; y≦x

(2)

(3) をみたす元yが存在する^｡*) xrYよりx<yが成立しなければならない｡

(2),(3)式は互いに矛盾する関係式となる｡

注 *) X とYが比較可能な元を持たぬとき,(3)式の成立それ自身がすでに

矛盾である｡ □

定理 1. X,Y,Zは互いに分離可能である^｡またX IY,YIz^,ZIX というサイクルを作らないとする｡このとき,X IY,YIZからX IZが導かれる^｡

証明 : X IYよりX ∈Pc(Y),Y ∈ P(Y)が成立し,YiZよりY ∈ Pc(Z), Z∈ P(Z)が成立する｡また ,切断 (P c(YUZ),P(YUZ))‑ (Pc(Y)n

Pc(Z),P(Y)uP(Z))をっくる｡これより,明らかにZ⊆ P(Y)uP(Z)である｡ここで,X ⊆ Pc(Y)も成り立っので,今,X ⊆ Pc(Z)は成立しないと仮定すると, ∃x∈ X ; x∈ P(Z)である｡X とZは互いに素であるから,x∈ P(Z)‑Zでなければならない｡これより ∃Z∈ Z ; x>Zが成立する｡X とZは分離可能であるから,X EZまたはZ IXの何れか一方が成立する｡条件x>Zに適合する分離はZ l̲Xである^｡これはX IY,Y IZ, Z IX というサイクルは作られないという仮定に反し,X ⊆ Pc(Z)の成立を示している｡

よってX ⊆ Pc(Y)nPc(Z),Z⊆ P(Y)uP(Z)が成立し,定理の主張が

正しく成立する事が示される □

定理2. 系列分割 V^l, V2, ‑ ･, Vhから選ばれた任意の 3つ組 Vf,

(7)

V,, V'^kについて,VilV,･かつ V,･FV^kが成立すれば,V.rV^kが成り立 i<

証明 : これは定理 1より成り立^っ ^｡ □

補題6. Vt･を系列分割 Vl,V2,･･･,Vkのある成分とするとき,P(V.I) に属するxが Viに属していないとすれば^,xを含む分割成分 V,はV,･IV, をみたす｡

証明 : ^x∈ P(V7･)であるから, ∃y ∈ Vt;y≦ xである.x毎 Vt･よりy

≠ xであり,y ∈ Vt,x∈ V,･,y<xである｡よって補題 2よりVz‑lV,

が導かれる｡ □

与えられた系列分割 V^l, V2, ‑ ･,Vkの各要素Viに Q(Vz･) 竺 p(vz･) ∪ (u p(v s))

VHVs

によって定義された集合 Q(V‑)を対応させる｡

(4)

このとき,以下の補題が成り立^っ ^｡

補題7. (Qc(Vi),Q(Vi))は切断である｡

証明 : 各Vj(j‑ 1,2, ･･･,h)に対して補題 3から (Pc(V,⁾, P (Vj))は Vの切断となる｡補題 1とQ(Vj)の定義を用いれば,

((P(Vz･)∪ ( U P(Vk)))C, (P(Vi･)∪ (U P(Vk)))) は切断となる^｡

Vr,lVh V,iVk

[コ

この切断をp(Vl)で表す.またこの切断は明らかに上組にP(Vi),Viを含む｡

補題8. 系列分割 Vl, V2, ･‑ ,Vkから取り出されたVi, Vjに対して,V7EV,･が成立するための必要かつ十分条件はQ(V7)⊃ Q(V,)である｡

証明 : 必要性を示す｡VzEV,と定理2より,VjlVkに対して VtlVk

が成立することから,

(8)

192 商学討究第45巻第 2号 Q(V,A)=P(VJ)∪(U P(Vk)) ⊆ U P(Vk)⊂ Q(Vi)

VjIVk V.EVk

逆にQ(V‑)⊃ Q(V,)のとき,V.･とVjが切断 (Qc(V,･),Q(V,･))により分離可能であることを示す.V,⊆ Q(V,)は明かである｡次にVz･⊆ Qc(V,･) を背理法によって示す｡これを否定すると,∃x∈ Vi ;X∈ Q(V,)となる｡

(4)式より,x∈P(V,)か,またはViIVkを満たすあるVkについて,x∈

P(Vk)である｡前者に対しては ∃y∈V,;y<xよりVjLvi,後者に対しては ∃y∈Vh;y< xよりVklviが導かれ,VilvhとあわせてV,7vi

となる｡いずれにしても(4)式より,Q(VJ)⊃ Q(Vi)が導かれ,定理の前提に

矛盾する^｡ロ

系列分割Vl,V2,‑ ･,Vkの各要素集合V昌こ切断p (Vt)‑(Qc(Vt･), Q(Vi))を対応づけると,切断の集合M‑ tp(Vl),P(V2),･･･,FL(Vh)) が得られる｡この集合に関して次の定理が成り立^っ ^｡

定理3. 系列分割 V^l, V², ･･･,V^kに対応する切断の集合 M‑(p(Vl), P(V2), ･･.,P(Vk))

は切断の優位関係 <‑に関して全順序集合を形成する｡

証明 :

(1) 反射律をみたす｡すなわち任意の VEに対して,p(Vi)<‑P(Vi) となる｡これはQc(Vi)⊆ Qc(V.･)より自明である.

(2) 反対称律をみたす｡すなわちp(Vl)<‑FL(V,)かつP(V,)<‑FL(Vi) が成立すれば,FL(Vt･).‑p(V,)となる^｡

これは p(V7)<‑P(V,)より,Qc(Vi)⊆ Qc(V,)

また, FL(V,)<‑FL(Vi)より,Qc(V,)⊆ Qc(Vi) となり, この両者より,Qc(Vi)‑Qc(VJ),またはQ(Vi⁾‑Q(V,)が導かれ,切断p(Vi)

‑〟(VJ)となる｡

(3) 推移律が成立する｡すなわちFL(Vi)<‑P(Vj),FL(V,)<‑FL(Vh)

(9)

が成立すれば,p(Vi)<‑P(Vk)が成立する｡ FL(Vi)<≠FL(V,) より,Q(Vi)⊃ Q(V,I)であり, VtIVjが成立する｡ FL(V,)<≠p(Vh) より,Q(V,)⊃ Q(Vk)であり,VjlVhが成立する｡よって, VilVh が成立し,Q(Vi)⊃ Q(Vh) となる｡すなわち FL(Vt･)<≠p(Vh)がみたされる｡

Mが全順序集合となることを示すために,Mの任意の2元の比較可能性を示せばよい｡

(4)任意のp(Vi) とp(V,) は比較可能である｡

VfとV,は分離可能である｡一般性を失うことなくVlIV,とすれば, 補題 8より,Q(Vt.)⊃Q(Vi)である^｡よってFL(Vi)<≠p(V,)が成

立する｡ □

これより,Mを優位性に関して,その各要素を大きさの順に並べ変えると, FL(Vl)<≠p(V2)<≠ ･･･<≠(Vk)

とただ一通りに並べることができる｡次に〃についての性質を以下に表す｡

補題9. Mの要素p(Vi)‑(Qc(Vi),Q(Vi))の直後の要素を p(V,)‑

(Qc(V,･),Q (V,)) とすると,Q(Vz)‑P(Vt･)u Q(V,･)が成立する｡

証明･. p(Vt･)≪p(V,)であり, これら2つの要素の間に位置する要素は存在しない｡それゆえ,FL(V,)以外の p(Vl)の後続要素p(Vk) について

は,条件y(Vi)≪p(Vk) ば条件 p(Vj)≪p(Vk) と同等である｡

p(Vz･)≪p(Vk)⇔Q(Vi)⊃Q(Vk)‑ Vz･iVkとなるので次の和の計算が成り立っ｡

Q(Vt)=P(Vz･)∪(耽 ^P(^Vh⁾⁾

=p(vz･)∪(p(V,)uv,VvhP(Vh))

‑P(Vi)u Q(Vj) [コ

補題10. M の要素fL(Vl)の直後の要素をFL(V]) とするとき, VilVkが

(10)

成立するならば,VI･とVkは切断 (Qc(V,･),Q(Vj))によって分離される｡

証明 : p(Vj)がp(Vz･)の直後の要素であることからp(Vi)の後続要素 p(Vm) に対して p(Vz･)≪FL(V,･)<FL(Vm),ただしVt･≠Vmが成立するO

優位関係の定義より,Q(Vl･)⊃ Q(V,･)⊃ Q(Vm) となり, さらに補題 8より Vt･lV,･および VI.lVm が導かれる｡これに補題5を適用すると,

Vi⊆ Pc(V,I),Vj⊆P(V,) および Vi⊆Pc(Vm),Vm⊆P(Vm)

が得られる｡一方,

Q(Vj)=P(V,･)∪(^V^沈 P(Vm))= vIVvmP(Vm)

(5)

上式と(5)式より,Vt･はQ(V,･)に含まれず,Vt･FVhをみたす V^kはQ(VJ)

に含まれることが結論される｡ □

定理 4. M の要素p(Vi)の直後の要素をFE(V,)とすると, Vi‑Q(Vi)‑Q(Vj)

と書き表すことができる｡

(Viが出口を含む分割成分のとき,V,･‑￠,p(V,I)‑(V,￠)とする.) 証明 : 補題9を使うと,

Q(Vz･)‑Q(V,･)‑Q(V,)n^Qc⁽^Vj⁾

‑(P(Vl)uQ(Vj))nQc(V,)

‑P(Vz･)nQc(V,)

補題10よりViと V)は (Qc(V,),Q(Vj))により分離されるからVt⊆

Qc(Vj),またVl⊆P(Vt.)であるから,V,.⊆P(Vi)nQc(Vj)である｡

次にP(V.･)nQc(Vj)に属するあるxがViに属さないとすると,補題 6よりxを含む分割成分 VmはViIVmをみたす｡補題10の証明の中で用いた等式 Q(V,･)‑vHvmP(V‑) より,x ⊆ Vm ⊆ P(V‑)⊆ Q(V,･)となり,^{x ∈} Qc(Vj)であることに矛盾する｡よってP(Vt･)nQc(Vj)⊆Vi □

(11)

系列分割の成分 Viに対応する切断をFL7‑FL(Vt･)で表すO定理3によれば切断の集合 (pilは,''<‑"に関して全順序集合であり,その要素を優位性の順に並べて切断の単調増加列にすることができる｡さらにダミー要素としての切断 (Ⅴ, ￠)を列の右端に加えて, この単調増加列を拡大する｡列の要素の並びの僧にしたがって系列分割の成分番号を付け直し,pk.1‑ (V, ￠)

とおくと

pl<≠ p2<≠ ･･･く≠^{p h<} ≠^{FL k}十1 (6) となる｡この新しい番号付けによる系列分割の表現を正規表現,対応する切断の単調増加列(6)を正規化された切断の鎖という^｡これに対して,単調増加列に並べ替え可能な切断の集合から作られた切断の単調増加列を切断の鎖という^｡

正規化表現のもとで補題 9と定理 4の結果は,Qi‑Q(V,･),Pi‑P(Vi)

とすると,次のように書くことができる｡

FLi‑(QiC,QI･) (i‑ 1,2, ･･･,h) (7) Qt･‑PiUQⁱ^.1 (i‑1,2, ･･･,h) (8)

Vz･‑Qz･‑Qi.1 (i‑1, 2, ･･･,h) (9) これまでは系列分割から切断の鎖を導いたが,逆に鎖を形成する切断の集合

(FLl･)から系列分割を一意に導くことができる.まず,要素番号を入れ替えて正規化した鎖にする｡各pt･の上組をAt･とし,

V‑‑A,.‑At･^.1 (i‑¹, 2, ･･･,k) (10) を作ると, tVt･)は V の系列分割となる｡これは,容易に示すことができるように, iVf)が系列分割の定義(1), (2),(3)を満たすことから明かである｡

以上を以下の定理によってまとめる｡

定理5.任意の半順序の系列分割は切断の鎖によって生成できる｡

3.最適系列分割問題

最適系列分割問題で考えるネットワークは,入り口と出口を持つ n個の頂点からなる無閉路有向グラフD(V,E )として与えられており,すべての頂

(12)

196 _商 _学 _討 _究 _第₄₅_巻 _第 ₂_号

点U∈Vには重みW(U)が,各有向辺 (U,W)∈ EにはコストC(U,W)が付与されている｡これらの値はすべてのU,W ∈Vについて,条件 o<W(U)≦

B,0≦C(U,W)を満たす整数であり,またBはブロックサイズと呼ばれる問題に固有な正の整数である^｡

Kernighanのブレーク･ポイントの考え方はDedekindの切断の概念と密接に関連している｡ブレーク･ポイントは切断の上組の最小元として定義され, これを与えることによって切断が一意に定まる^｡半順序集合の場合にもこの考えを拡張して切断決定子の概念を導入する｡半順序集合 (V, ≦)の切断 FL‑ (A c,A)の上組 A の極小元の集合を γとし, これを切断 pの切断決定子 γと呼ぶ｡このγから (Pc(γ),P(γ))によって切断 (Ac,A)を復元できる^｡

切断決定子の列

γ 1,72, ●●●,γ h ⁽川

に対し,各7,‑に対応する切断FLlと,FLh.1‑(V, ￠)からなる列

pl,P2, ･･･,Pk,FLh.1

( 1 2 )

が(6)式を満たし,正規化された切断の鎖を形成するとき,列(ll)を切断決定子の許容列という｡すなわち,切断決定子の許容列を与えるとそれに対応して正規化された切断の鎖が得られ, これから⁽¹⁰⁾式により決定される分割成分を持っ系列分割が定まる｡これを切断決定子の許容列が定める系列分割という,その各成分 VⅠより誘導されるDの部分グラフをブロックと呼び,[γ,I,γi.1)で表す｡また,Viに属するすべての頂点Uの重みW(U)の総和をブロック長といい l[γi, γi･1)巨 ∑ ,E:,E,㌔+I)W(U,)と書く^〇一万,どのブロックにも属さないDの辺の集合をカット･セットという^｡

ブロック長がブロックサイズBを越えないという制約のもとで,カット･

セットに属する辺のコストの総和を最小にする系列分割を求める問題を最適系列分割問題という｡

切断決定子の許容列から定まる系列分割について次の補題が成り立^っ ⁰

補題11. カット･セットに属するカット辺 (U,W)について,始点Uが成

(13)

分Vt･に終点 W が成分V,に属するならば,i<jが成立する｡また,入り口は Vlに出口はV^kに含まれる｡

証明 : 半順序に関して,U<Wであるから,楠題 2よりVi王V^jとなる｡補題 8を用いれば,p(V壬)<≠FL(V^,) となり, pの単調性よりi<jが成立す

る｡ □

この補題 11から, カット辺の総和は A

I (71,† 2, ‑ ･,γk)=.1!lC ([γt, γt･1))

と書き表すことができる｡ここで,C ([^γ .･, γt.1))は切断決定子 ^γ 7･の後ろに^γ ‥ 1を置いたときの増分コストと呼ばれる量で,始点がVlの中にあり, 終点がj>iであるVjの中にあるすべてのカット辺のコストの総和を表して

いる｡

C ([7,i,γH l))‑ ∑ C(U,W)

U∈[11,γ..I),

W∈P(γ川) qSE

以上より,最適系列分割問題は,すべての切断決定子の許容列 <71, γ 2,

･･･,γh>の集合E2の上で, 制約条件

L[γi, γi.1) E ≦ B のもとで, 目的関数

A

I (71, γ 2, ･･･,γk)=Z写^{1C ([γ}^‑ ^γ7･l⁾⁾

を最小化する問題として定式化される｡

4.アルゴリズム

列挙法による解法では膨大な数の可能解の中から最適解を導くこととなる｡

ここでは切断の鎖を可能解の列挙のプロセスと考え,状態問の遷移から解を効果的に導きだす｡まず,すべての切断を生成する算法を考察し,またそれがすべての切断を含んでいることを示す｡さらに生成過程で同一な切断を既約する

ことによって, グラフの切断数に依存する計算が可能なデータ構造を構成す

(14)

る｡これを利用することによって,最適解を見失うことなく,探索領域を効果的に限定し解を導きだすことを示す｡

4. 1 すべての切断決定子の生成

切断FL‑(Ac,A)に対応する切断決定子を γとするO このとき,下組Ac

の要素数を〝または γのレベルと呼ぶ｡優位関係 "<‑''について〟より優位にあり,かつレベルの差が 1であるような切断を〝ーとすると,〟一は〝の上組の極小元の一つをその下組に移すことによって得られたものであり,またそれに限る｡すなわち, γから適当に選んだUをピボットとし, これを用いて,

(I)AJ‑A‑ (U), (A')‑AcuIuI を作ると,

(Ⅱ) 〟′‑((Aつ,Aつ

となる｡

このとき, 〟に対応する切断決定子 γから直接〝一に対応する切断決定子γーを導く操作をγの基本操作という^｡ここで Vの元 x,yについてx< yでx<

2< yをみたす V の元 Zが存在しないとき,yをxの直後の元と呼び,x≪

yで表す｡U(∈ γ)の直後の元で,P(γ‑tu))に含まれていない要素の集合をW とする｡すなわち,

W ‑(w lu≪ w and w 毎 P(γ‑tu)))

となる｡さらにWの極小元の集合をⅣ^{ノとすると,}

(Ⅲ) γJ‑(7‑(ui)UWJ

によって,γより〝に対応する切断決定子が生成され,それは基本操作となる｡また, 両こ対して生成される切断決定子数,すなわち, pの極小元の数は非決定的な値となる｡以下にこの事実の正当性を示す｡

定理6. 基本操作により決定された ((AJ)C,A')は切断であり,かつγ

は対応する切断決定子である｡

証明 : 了の元はすべてAーの極小元であることはγノの構成から明かである

(15)

半順序の最適系列分割問題の構造と算法構成 ¹⁹⁹ ので,P(γJ)‑A一が成立することを示すことによって,定理が証明できる｡

P(γ')‑A'の成立はP(γ')‑P(γ)‑ iulを示すことによって導かれる｡

また集合関数P(X)に関して次の性質を利用する｡

P(XUY) ‑P(X)UP(Y)

x≦ yならP(fx‡)uP(ty ))‑P((x)) x∈ X ならP(ix))uP(X)‑P(X)

Xの極小元の集合‑X一ならP(X)‑P(X') 以上の性質より,

P(γ)‑(U)

‑(P(γ‑iul)uP((U)))‑fu)

‑P(7‑fu))U(P(iu))‑(U))

‑P(γ‑⁽^U⁾^)uP(W)

‑P(γ‑iu))uP(W ')

‑P((γ‑ tu))uW /)

‑P(γ‑) [コ

すべての切断を決定するのに切断を節点とする木を生成する｡切断〟に対応する切断決定子を γとしたとき, (i), (Ⅱ)を適用することによって, 1レベル高い切断pl, P2, ･･･,Pkが作りだされ,それらの対応する切断決定子は (Ⅱ)より導かれる｡このとき, pを親節点,pl,FL2, ･･･,Pk を展開して得られる子節点と考える｡さらに切断 (申,Ⅴ)を根として, この操作を繰り返すことによって,高さ n+1の多分岐平衡木が得られる｡図3

は図2のグラフの木となる｡また葉はレベル値がnの切断 (V, ￠)に対応する｡この木によってすべての切断が得られる｡なぜならば,いかなる切断に対しても,必ずその親となる切断が存在し,かっ有限回繰り返すことによってレベル値0の切断 (￠,Ⅴ )に到達することから明かである｡

また木の各節点にその直接の親節点が展開するのに用いたピボットを割り当てることによって,根から葉までの一つの経路は V の一列化に対応し,葉の赦

(16)

200

は一列化の数となる｡

商学討究第45巻第 2号

図2 無閉路有向グラフ

(5)4

(6)5

□ 6

5日u4′‑ノI︹ nnu61口nHJHHHu 46 5円リ4nHU 46日HHu6′･‑･□nu nHHuHHHu41,6‑ロ

‖＼{

図3 すべての切断決定子を生成する多分木平衡木

(17)

4.2 既約化されたグラフの生成

この基本操作を用いて木を生成することによって,すべての切断を生成できることを上記によって示した｡このとき,切断の下組の一列化の組み合わせの可能性を考慮することによって,ある切断が複数生成されることが示される｡

複数の同一な切断を伴う木において,切断〝fを根とする部分グラフと切断 FL)を根とする部分グラフが等しいなら

ば, これら2つの節点を根とする部分グラフは同形である｡したがってFLt‑ FLj

と置くことによって既約化することが可能である｡また同一な複数な切断はその切断の下組の数が等しいことより同レベルな切断の集合中にしか存在しない｡この性質を用いて, (少,n)の根から横型に探索することによって効果的な既約化が行われる｡この既約化によるすべての切断の生成算法を以下に示す｡これによって切断の優位関係において半順序な関係をもつ既約化グラフが生成される (図 4参照)｡またオープン･リストから取り出される順に並べた切断の列は既約化グラフが一列化されたものとなる｡

(1)

. 2 ,

ⁱ

3

′‑

Jヽ･し ( 4 1人Y いRU 3 琶i ) ノ上Y I nHu5 ^＼ R U 上Y侵 ← 射RU Ru52 nHu

ヽ 6 (

J□

図4 すべての切断決定子を含む既約化グラフ

(1) OpenList:‑￠;OpenList:‑γ S ;

(2) While (OpenList≠ ￠) begin

(3) "OpenListの先頭要素 γtを取り出す ";

(4) for (aErt ) begin

(5) "aをピボットとして γ,からγ gを生成する";

(6) "^{γ g}からγtへのポインタを確保する";

半順序の最適系列分割問題の構造 と算法構成