最大クリーク問題に対する地形解析
上野伸郎・片山謙吾＊・南原英生＊・成久洋之＊
岡山理科大学大学院工学研究科情報工学専攻
＊岡山理科大学工学部情報工学科
（2005年９月30日受付、2005年11月７日受理）
1．まえがき
メタ戦略に基づく高性能なアルゴリズムを構成するためには，対象とする最適化問題の構造をうまく利 用することが重要である['1．
特定の組合せ最適化問題に対して局所探索法などを用いた地形解析(landscapeanalysis)の研究が行われ ている．地形(landscape)[2,3]とは，探索空間における構造の複雑さの尺度である．その解析によって，対 象とする最適化問題を発見的に解くことの困難さをある程度見積もることが可能になり，さらにその構造 を利用した高性能なメタ戦略アルゴリズムの設計も可能と考えられている．現在までに，巡回セールスマ ン問題[4]，グラフ分割問題[4,5]，フローシヨツプスケジューリング問題[31,バイナリー２次計画問題[6]など に対する地形解析の研究が知られており，その多くでは「大谷構造」[4]が観測されている．大谷構造とは，
探索空間の地形が真の最適解に向かって－つの大きな谷となるような構造をしていることである．対象問 題が大谷構造として構造化された空間を持つならば，集中化と多様化の相反する探索戦略をバランス良く 有するメタ戦略アルゴリズムによって最適解への接近が可能であると考えられている．
本研究では,代表的な組合せ最適化問題の一つである最大クリーク問題(maximumcliqueproblemMCP）
に対して，我々がすでに提案しているh-opt局所探索法[7]を用いて，ＭＣｐの地形解析を行う．解析の結果，
大谷構造を観測できない問題例が多く，一般的なメタ戦略アルゴリズムにとって悲観的であることを示す．
2．最大クリーク問題
頂点(vertex)の集合Ｖ＝｛11…'､｝とそれらの頂点の対を両端とする無向辺(undirectededge)の集合 Ｅｃｖ×ｖが与えられたとき，Ｇ＝(ⅨＥ)を無向グラフという．特に，全ての２頂点間に，つの辺が存在す る無向グラフを完全グラフという．ｖの部分集合ｖにｖによる誘導部分グラフＧ(v,)＝{v,,Ｅｎｖ,×ｖ,｝
が完全グラフのとき，すなわち，ｗ,ＪＥＶ',ｊ≠jiに対して(j,j)ＥＥであるとき，ｖ,をクリークと呼ぶ．
MCp[81とは，与えられたグラフＧに含まれるクリークＫの中で，次の目的（評価）関数
九。P(Ｋ）＝｜Ｋ’ (1)
を最大にするクリークを求める問題である．
ＭＣＰは実用上重要な問題であり，通信，符号理論，並列計算，パターン認識，等の分野の基本問題とし て頻繁にあらわれ，様々な組合せ最適化問題と等価であることがよく知られている[８１．そのような組合せ最 適化問題として，最大独立集合問題，最小集合被覆問題がある．
ＭＣＰはNP-困難[９１に属する問題であることから，多項式時間で厳密な最適解を求めるアルゴリズムは存 在しないと考えられている．さらに悲観的なことに，ＭＣＰにおいて，多項式時間で一定の近似度を保証す るアルゴリズムは存在しないと考えられている[10,11,121
ＭＣＰを厳密に解くために幾つかのアルゴリズムが提案されている．その多くが分枝限定法にもとづく 厳密解法であるが，実行可能時間内で厳密解を得ることができる問題のサイズは小さいグラフもしくは疎 なグラフである[13,14,15,16,171そのため，厳密解に近い解（近似解）を実用時間内に算出する近似解法の
研究が盛んに行われている[18,19,20,211
上野伸郎・片山謙吾・南原英生・成久洋之
9８3．ＭＣＰに対する舟opt局所探索法
MWCP-h-opt-Local-Search(ＣＯ,ＰＡ,ＯＭｄｅ９Ｇ(pA)）
ｂｅｇｉｎ
ｒｅｐｅａｔＯＯ…沙:＝ＣＯ,Ｄ:＝ＣＯ…妙,Ｐ:＝｛1,…,、),ｇ:＝０，９７…:＝Ｏ；
ｒｅｐｅａｔ
ｉｆｌＰＡｎＰ|＞Ｏthen ／／AddPhase
ifmultipleverticeswitｈｔｈｅｓａｍｅｍａｘｉｍｕｍｄｅｇｒｅｅａｒｅｆｂｕｎｄｔｈｅｎｓｅｌｅｃｔｏｎｅｖｅｒｔｅｘｕ ａｍｏｎｇｔｈｅｍｒａndomlyi
OO:＝ＣＣＵ{ひ),ｇ:＝ｇ＋1,Ｐ:＝ＰＷ）}；
ｉｆ９＞ｇｎｚＱ⑩ｔｈｅｎ９ｍＱ⑰：＝９，ｏＯ６ｅｓｒ＝ＣＯ；
ｅｌｓｅ
／／DropPhase(if(ＰＡｎＰ｝＝Ｏ）
ifmultipleverticeswiththesamesizeoftheresultinglPAlarefbundthenselectonevertexu amongthemrandomly；
ＣＯ:＝ＯＯＷｊ},ｇ:＝９－１，Ｐ:＝Ｐ({Ｕ}；
ifUiscontainedinCq,…ｔｈｅｎＤ＝Ｄ({u}；
ｅｎｄｉｆ
ｕｐｄａｔｅＰＡ,○Ｍ,anddegC(PA)(j),ViePAi untilD=伽
ｉｆｇｍａ⑩＞ＯｔｈｅｎＯＣ：＝ＯＯ６ｃｓｆｅｌｓｅＯＯ：＝ＯＯｐ７ｅｕ；
until９ｍ…≦Ｏ；
ｒｅｔｕｒｎＣＯｉ
ｅｎｄ
１２３４５６７８９０１２３４５６７１１１１１１１１
図１ＭＣＰに対するAo-opt局所探索法の擬似コード
本節では，本研究で地形解析に用いるＭＣＰに対するA-opt局所探索法（KLS）［71の概要を述べる．ＫＬＳ は可変深度探索（VaJFiableDepthSearch,VDS)[221のアイデアにもとづいている．ＶＤＳとは，与えられた 解に対して比較的小さな近傍操作を連鎖的に適用することで到達可能な解の集合を改めて大きな近傍と捉 える近傍探索のアイデアである．
ＫＬＳの擬似コードを図１に示す．以下では，用語や記号の定義について記述する．ＫＬＳは外ループ（Linel‐
18）と内ループ（Line3-16）の処理を有する．以降，外ループに関しては「反復｣，内ループに関しては「繰
り返し」と呼び区別する．
ｃｃ(z)は内ループの繰り返しｌの時点における解（クリーク）である．ＰＡ(z)はＣＯ(z)の全頂点に隣接す る，ＣＯ(【)に追加可能な頂点の集合
ＰＡ(【)＝{u:uEmCO(z)),(u,j)ＥＥ,ＶｅＯＯ(J)｝
である．○Ｍ(z)はＰＡ(z)の定義を若干緩和した１辺不足集合と呼ぶ辺集合
○Ｍ(z)＝{(仏j):ＵｅＷＥＣＯ(z),(u,j)＄E,(Ｗｉ)ＥＥ,V(jieOC(z),ｊ≠j｝
である．なお，○Ｍ(z)はＣＯ(')に含まれる頂点群の中のいずれか一つの頂点ｊＥＯＯ(')だけに辺が存在し
ない頂点の集合と捉えることもできる（なお，ＣＯＣＯＭ）．degG(pA(』)）はＰＡ(z)により誘導される部分 グラフＧ(PA(z))内の各頂点りＥＰＡ(z)の次数である．
次いで，ＫＬＳの各反復における基本アルゴリズム（ﾙｰopt局所探索処理）について簡潔に説明する．まず；
与えられた初期クリーク（初期解）ｃｃ(o)を対象として，複数個の頂点を連鎖的に追加する操作（Add移動 操作）および削除する操作（Drop移動操作）により到達可能な近傍解の集合ｃｃ(1),…,ＣＯ(ｋ),…,ＯＣＣ）
を得る．（その生成途中では，移動候補頂点集合Ｐ（Line2）を利用することで，追加または削除された頂点
は再び追加・削除されることはない）．その近傍解の集合から最良解ＣＯ(h)(１≦A≦γ）を選び（Line8），
次反復の初期クリークＣＯ(o):＝ＣＯ(ん)とする（Linel7)．ＫＬＳは常に実行可能領域を探索空間としており，
各反復の初期クリークに応じて，ルーopt近傍のサイズ（上記のγに対応）が適応的に変動する．
上記のA-opt近傍探索処理は，Add移動操作を施す「Addフェーズ」（Line5-8）とDrop移動操作を施す
｢Dropフェーズ」（LinelO-13）の二つのフェーズで構成される．
4．ＭＣＰの地形解析
地形解析は，一般に次のように行われる．
（i）真の最適解（もしくは，良く知られている最良解）が既知である問題例を選ぶ．
（ii）ランダム解を初期解として局所探索法によって算出される，異なった局所最適解を複数個得る．
(iii）得られた各局所最適解の目的関数の値と各局所最適解から他の局所最適解への距離を調べる．
(iv）各局所最適解の目的関数の値と各局所最適解から真の最適解への距離を調べる．
上述の準備に基づいて(iii)と(iv)のそれぞれの相関を調べる．また，多くの場合，（iii)と(iv)のそれぞ
れの関係図から視覚的に地形を観測する
本研究では，上述した研究[3,4,ＭIと同様に，地形をＬ＝(Ｘ,ｆ,｡)で表現する．なお，Ｘは探索空間，ノ は目的関数，ｄは探索空間上で定義された距離である．これは，地形の複雑さと最適化の難しさとの関連付 けを可能にするが，対象とする最適化問題に対する探索法で扱う評価関数，解の表現，距離の定義に依存 する．
4.1評価関数
本研究では，ＭＣＰの目的関数式(1)を探索する解の評価関数とする．
４２解表現
解はＶの各頂点にクリークとして選択しているとき１，選択していないときＯのビットを与えて１次元 ベクトルとして表現する．従って探索空間は，ｘ＝{0,1}池となる．
4.3距離
距離ｄは探索空間Ｘ＝{0,1}”における二つの解のハミング距離（Hammingdistance）とする．
4.4ＭＣＰの地形解析結果
実験はＭＣＰの代表的なベンチマークグラフであるＤＩＭACSの問題例群に対して，ランダム解(Ｖから ランダムに－つの頂点を選択したクリーク)より開始するA-opt局所探索法の10万回の試行により到達可
能な複数の局所最適解を得て，探索空間の地形を解析する．
真の最適解（もしくは，既知の最良解）が複数ある場合は，その局所最適解に最も距離の近い真の最適解 (もしくは，既知の最良解）を選択する．
表１は，左から，問題例名，最適解値Opt，最適解の個数ＯｐｔＮ，１０万回のA-opt局所探索法により算
出された異なった局所最適解の数Ｍ４ｍ，最適解と得られた局所最適解の平均距離面｡pt，局所最適解同士の 平均距離凪肋，及び最適解と局所最適解の相関係数Ｏｏｐｔ，局所最適解同士の相関係数○hJ｡の結果である．
距離の定義(4.3節参)から，面｡pt，Ｚｉｂｍの最大値は最適解値Optの２倍である．Zioj,t，魂Z・の値が最大値
に近づくほど最適解及び局所最適解同士の共通性が少ないと考えることができる．
ＭＣＰは最大化問題であるため，Ｃｏｐｔ，Cdzoの値が共に－１に近いとき最適解及び局所最適解同士に強い
正の相関があり，大谷構造が観測されると考えることができる．
表ｌで選択した３５個の問題例中，８個の問題例で相関係数ｑp２，ｃｄわが共に負の値となり，そのうち最
適解及び局所最適解同士に強い相関が確認でき，大谷構造が観測できた問題例は５～６個だけであった．残
りの約30個の問題例については，最適解及び局所最適解同士に強い相関が確認できず大谷構造は観測でき
なかった．
上野伸郎・片山謙吾・南原英生・成久洋之
100表１ DIMACSの問題例群に対してAD-opt局所探索法により得られた局所最適解の距離解析結果と相関係数
Ｎｕｍ
uLUH組tⅧ０－Ｊ ILhⅧ５００－Ｊ 固巨菖望』口ご胃〕
１１１１ ６４２０８６４２０1６
Ⅱ
、タ
●用、》△●、
←一・二制、。．、、）・・、
ヨヤ｜▲『凸一合・・凹
邑ｎＪ拙いいい日Ｆ己田
迂》ご〆乢．』殺軍一錘軍騨趨絶必、 幻》》》狂》》》
ＵＦＯも》（》》侭摩然〉野 ．．〈（・斑〈。“・畷》〉。．〈 ．、．》へ像γ螺〉に・ず魂 礼ロハーク・・・似乳似チダ凡へ ．⑬》・〉卯〈‐翠一，〈
由叺‐。。一ｄ０ｈＯ‐Ｐみ、』■●、胡轡へ強“
Ｐ巳。■Ｓ▲
・作凸ユハ。、。．》
２０８５４２０１１
８５出室已宣豐〕
蕊〕笈窺〕２準>:悪人>(な(甚薙頚蕊率珍:v>､X塗？』
６０７０８０９０１００１１００２０４０６０８０
Ａ､．$mgeDisl血､心e Di1Btgmcet⑥ouDtiummn
(a)p-hatl500-3-avg （b)phatl500-3-opt 図２p-hatl500-3-avg
100１２０
§0 4０
instance
Ｏｐｔ OptlV
Ｎｕｍ 。OｐＺ 。α皿 ○。
ｐｔCｂ
ルＣ125.9
C2509 C500､９
Ｃ1000.9 Ｃ2000.9４４７８８３４５６７
393 363 ３ 4８ １１
０４０１１２３６４３６８９０８００２９９１６９９９ ０９８８０４８３
●●●●７１６８１４７９ ８９
０３２１ ５５０２７７
●●●２７９３５７ １３０３
●●７５０２１１ ６０５８８７５１００ｐｐＤｐ０ ０４９４５６３０３４０ ●●●●００００
ＤSJC500.5
ＤSJC1000.5
３５１１ ０８５１
9754 18843
1８２５ ２４．３１
21.36 24.27
-0.05 ０．２３
0.96 0.98
Ｃ2000.5
Ｃ4000.5
６８１１ ７１７１
31358 45734
25.90 31.47
26.88 2929
024 0.44
0.99 ０９９
ＭＡＮＮ－ａ２７
ＭＡＮＮ－ａ４５ ＭＡＮＮ－ａ８１
126 345 1100
681 ２ ７
100000 100000 100000
96.55 437.76 1351.37
167.34 457.03 1465.33
-0.04 0.01 0.02
４４６９９８
●●●０００
brock200-2 brock200-4 brock400-2 brock400-4 brock800-2 brock800-4
２７９３４６１１２３２２ １１１１１１
2705 6088 31057 31870 31470 31011
２６２２７８８０８８４２
●●●●●●９８８１１３１２４５４４ ０７７２４９５１８３６４
●●●●●●６４８９４４１２３３３３ ３１５５７６３４３３５５
●●●●●●００００００ １９５７５１９４４５８９
●●●●●●００００００
gen200-pO､９４４ gen200-pO､9-55 gen400-pO､9-55 gen400-pO､９６５ gen400-pO､9-75
４５５５５４５５６７ ４４１１１
47447 35995 93490 92167 92234
３８１７４７６０
●●●●２４９６６７８９ ６４
●７０１ １５２５９５０４０１
●●●●●６３９４３４４６７７
叫加Ⅱ鮒川
ＯＤ０ｐｐⅡ加川町Ⅲ
●０００一一 ■●００keller4 keller5 keller6
１７９１２５
444 673 1４
16530 96271 100000
9.30 31.01 1０１．７１
０２１９４４
●●●６６８１４９ ４１７７３４ｐｐ０ １９０９９０●●●００１
p-hat700-1 p-hat700-2 p-hat700-3 p｣latlOOO-1 p上atlOOO-2 p上atlOOO-3 p上atl500-1 p-hatl500-2 p-hatl5003
１４２０６８２５４１４６１４６１６９ ２ ７０１４１２
価朗皿１
８６４３４５6853 '9974 54000 10736 45435 85660 17690 63407 94305
０９８４７７２１８９９９８２１８０１●●●●●●●●●７３３２８８０１６１２２１２５２３４ ９７４２２４４１６２１４４２９２９０●●●●●●●●●５８３６４１８１４１３４１４６１５６
咀乃〃Ⅳ畑脳灯川Ⅶ
０ＯＤｐＤＤ０ｐｐ０９６ -070 -0.35 ０９６ -0.49 -0.28 ０．９７ -0.68 -076
最大クリーク問題に対する地形解析
101』一一＠
ＭＡＮＮｉｈ８１。－『ログ』｜｜ ｛一マユエＴ》 ｒＩｌ８８０Ｐ０Ｉ１００Ⅱ０７２１；００Ｉｂ０００９ｌ０ｉ０ｉ０００Ｌｒ００００１Ｉ１Ｉ００Ｉｒ０Ｉ０ｌＹＩ０Ｉ０８ｌＩＩ０Ｑｌ００ｄ００ｂＩＩ０ＩＩＩ００Ｉ００ケーローⅡ■Ⅱ５－１■・△ロー『． ■一』》（亜｝｜「．，，。一一一二一函一一一」ニーロームロ一一一・、ＺやＰ一一一ロエ’一ユロ■■■一一エエキ叩一■■■■一 一鯵 一一
－１
１４６８
１
１
。ｐ〉 ＩＩｉＩＩＩＩ険１１１１トー’しＩＬＮ ｒＪグヘ〉Ｐ』ロ》。□■ロ七二℃》へ〃。■■ユの｛叩）（叩「シ ②与昌⑰邑糾》」［岩Ｓ』湧色巳 E麹譲霞翻窺 ､.~メタ
しご富む出色』窟Ｓ》輯◎｛〕
R'；喝
愚.<漆；
穀騨鰹蕊F鍾麹窪1蕊ﾛ窪轤璽寧蟻ug露$0璽鐸ス◆-bUc--.--
1-06＄
D-c-c,---」c－－－．ﾏｰﾜｰ.－－－－．－缶一一一一・-－．－－－－－－⑤」｡..-－－－－－－－．-.-.Ｌ－…,－
１判４１４６５Ｍ6６ｌ４６７ ＡＴＧｒｌＤｇｅＤ態tiWBCoP
(a)MANN-a81-avg
－－－△ＰＣ～－
１０(１０
－⑤＋己－０－－－，－－－－－■－．Ｌ～-◆－－－．。-…－－，－～▲←-．．－－．－－－－－の‐●.･･６．L--.-.-.-ＰＣＳ｡｡▲－．－－－．－
１１００】ＺＯＯ１３０Ｕ１４０(）１５００
，捌汕lcet⑰⑪ＩＤ'|IlillIllII11lUmnl
(b)MANN-a81-Iopt
図３ＭＡＮＮ１８１
６１１１１１１１１「ＩＩ１１Ｊ０－１
Ａや》－４ □》一一一一一一一一一一一一一騨一》 －０－０－１－ｅ’ｃ－８ｎ －９跡 ６－ －》咄
Ⅱ一七一 Ⅱ一 脳一 一無
」２－９
一色蟻
－８一心‐叺・ｑ‐・昨ｆｐ
－８ｌ６ＩＩＩＩＩＩＩＩ「ＩＩＬ３０８６４２０８６４２Ⅱワー１１１１１
日目閨当】署一選〕声〕
朏阯ｒ６
￣－－－~アーーー￣￣~７－－－－~－Ｆ－－－－.Ｔ－－－△･－｡－丁－－－－－一壱-－－－－Ｔ-－．－－－－－－－－－
０８６４２０８６４２０２１１１１１
’
,"1-
(.ｂ（」/
巴Ｕ■④■臼罰宕ご』晩。｛〕
タグ●■
ｊ二ＬｃＧｑＵい▽Ｂ■》ひ■
把り■、００■●■ＬＡ少
（惨」・
グｂＬ、、、‐シシ へ
■●■ロロ門し‐し’よｑらｊのり●
５■ひ■６ｄ０Ｂ〃００ｌｂ■１げ。ｂログ
少」。
０９＄）▽谷。〆。？□祝・■もし００〆０。〆、■ず〆・‐０
，■ゲーバロ。
、ノ。■、ひ
々。、与少０Ｐ●もり０●け■』
ｆｂや。６，Ｆ、。、◆、》
へ少●、、ケュ⑪Ｌ〃０｜□ｄ紋■■ゲーハＬ （□》’ ん‐〉
〆Ｏｌｑか、。〃ｂ０・
ＰⅡ。▲勺ムクロ▲。△も〃
ｂ】、ひらＰグロロ●。↑イ ロ、。〆、●▲。●Ｐ０ ｓ‐｜、β口ｑ△■▽Ｑｑｑ、けタ、▲口。■。▲幻。●リヴ０Ｐｑ、△ＰＣＬも夕？弘。・づ・ｐｑロワー。ＬＰ・ロＰ●け
へ亜Ｃ
ｓ□ず■β●■〆・‐．〃０可』Ｐも。Ｐａ△Ｌヴい‐ｐＱ－、▽。●‐■●ｑＰ▽《．、、一、■０Ｐ●ＤＪ０，点・ゲロ０屯ア．。、
■ｑｂｒ■ｂヴー■■。．■▲ワ、ロノト山へ》Ｐ●■。『Ⅱ●い■｜己も供Ｊ‐缶
０F｣▼
-$◇,'･UOL,-1-『」Ｌ
ｻﾞ’--.。"･ﾛ、ｸﾞ.､･ハ！｡、
１０二ＤＱｊ、Ｐ‐．’。。Ｌ〃机Ｃ
Ｑの〃－へ〉〆‐。。＄０６‐０△マミゲ■ｇｈ
Ｃ／ ヒワゴグ”も■●ご●十．▽ＰＪシ６
凸，イ■ＦもじみＣ少一ト、。・・。。。、↓ｆ｜、｜
曲】■‐》門｜ｕザｒクワ』凸 口Ｔ６ｄｐ〆■
。己△・〆’邪。っ典。。．▽、ｂ
◇００Ｊ⑩ロい■。。Ｆ
■ＯｑＡＬＴ．。〃‐‐呵埒〆。》へ。》，・
・■ｒ。Ｐ、．‐
●■
》〈〃》．｝舟ヨハ．．
」、ノ，、ゲグ ー・・も→。■▲『〈）０
Ｊ■６Ｆグｕ‐、耳βＡＣ
巳■●げ むＳＳＰ●①、０、。・ケ
、〈｝》
》》０ヤゴ・■
グ◆
鈩守ザ●●、‐Ｆ
ｑ
Ｑｆ▲巳ロ
ハ・』
》６Ａ
“￣Ｊ－Ｊｗ丘い］
－－－－－－－－－一一一一一Ｌ一一一一」
７５８(）８５’０９５１００１０５１１０１１５
，曲t8uncetlDoIDtmum
（b)keller6-opt
7０
Ｌ
(a)keller6
avg図４keller6
特徴的な結果を得られた問題例を例に，局所最適解が探索空間内にどのように分布するかを視覚的に観 測する．図２，図３，図４は，異なる局所最適解同士の平均距離(a)と最適解との距離(b)をそれぞれ目的
関数値との関係でプロットした図である．（a),(b)どちらの図も縦軸は，最適解の値と目的関数値との差で 表示しているため，縦軸の値が０に近づくほど，良質な局所最適解である．
図２において，p-hatl5003は，（a)，（b)のともに局所最適解がクラスタとして分布していることが確認 できる．さらに相関係数が共に-0.7以下であることから強い正の相関がある．すなわち，ｐ」atl500-3は
大谷構造として構造化されている．
一方で，図３のMANN-a81，図４keller6は共に，大谷構造として構造化されていない問題例である．図 3の(a)のプロット図と，図４の(a)のプロット図から，MANN-a81，keller6共に，目的関数値が良くな るにつれて，各局所最適解同士の距離が大きくなっていくことがわかる．また相関係数の値ｑｌｏはこのと き，MANNa81，keller6共に0.85以上と強い負の相関を示している．さらに最適解と局所最適解との間に
も正の相関は確認できない．
5．むすび
ＭＣＰに対する地形解析により，ＭＣＰの多くの問題例の探索空間は大谷構造として構造化されていない ことを示した．このネガティブな結果はＭＣＰの問題構造自体，一般的なメタ戦略アルゴリズムにより最適
解を算出することが非常に困難であることを裏付けている．
上野伸郎・片山謙吾・南原英生・成久洋之
102
今後の課題としては，この悲観的な地形解析の結果を克服可能なメタ戦略アルゴリズムの設計が挙げら
れる．
参考文献
[1］柳浦睦憲,茨木俊秀,組合せ最適化-メタ戦略を中心として-,朝倉書店,2001．
[2］ORBeevesm,``Landscapes,operatorsandheuIFisticse虹ch,，，AnnalsofOperationsResea正ch,voL86，
pp473-90,1999．
[3］山田武士,ORBeeves,``フローシヨップスケジューリング問題の地形解析と遺伝的局所探索による解 法,，，情処学論,voL39,ｎｏ､7,ｐｐ､2112-2123,Ｊｕｌｙ1998．
[4]KDBoese,Ａ・BKahng,andSMuddu,``Anewadaptivemulti-stamechniquefOrcombinatorial globaloptimizations,，,OperationsReseaJechLetters,voLl6,ｐｐ,101-113,1994．
[5]Ｐ・MerzandBFreisleben,"Fitnesslandscapes,memeticalgorithms,andgreedyoperatorsfOrgmph bipartitioning,，，EvolutionaryComputation，vol８，ｎｏ.’，ｐｐ､61-1,2000．
[6]片山謙吾,谷昌史,成久洋之,“バイナリー２次計画問題の地形解析と遺伝的局所探索の性能,，，電子情報
通信学会論文誌(A),volJ84-A,ｎｏ､１０，ppl258-l271,2001
[7]Ｋ・Katayama,AHamamoto,andHNarihisa,"AnEf][bctiveLocalSe麺chfOrtheMaximumClique Problem,，，InfbrmationProcessingLetters,ＶＯＬ９５，，０５，ｐｐ､503-511,2005Ｊ
[8］IBomze,MBudinich,PPardalosandM・Pelillo,``TheMaximumCliqueProblem,，，ｐｐｌ－７４,I、
Ｄ－ＺＤｕ,PMPardalos(Eds.),HandbookofCombinatorialOptimizatio、(suppLh1.Ａ),Kluwer，
Dordrecht(1999）
[9］ＭＧ麺eyandDJohnson,“Compute近sandlntractability:AGuidetotheTheoryofNPComplete- ness,，，Freeman,ＮｅｗＹｏｒｋ(1979）
[10］SArora,ＣＬｕｎｄａｎｄＲ､Motwani，MSudanandMSzegedy,``Proofverificationandthehard‐
nessofapproximationproblems,，，Proceedingsofthe33rdAnnualSymposiumonFbundationsof ComputeZScience,Pittsburgh,ＰＡ,ｐｐｌ４－２３(1992)．
[11］Ｕ､Feige,SGoldwasser,LLovasz,Ｓ､SafraandMSzegedy,``ApproximatingcliqueisalmostNP- complete,，，Proceedingsofthe32ndAnnualSymposiumonFoundationsofComputerScience，San Juan,PuertoRico,ｐｐ２－１２(1991)．
[12］JHAstad,``Cliqueishardtoapproximatewithi、、1-`,，，ActaMathematica,VOLl82pp､105-142
（1999）
[13］亀田宗克，富田悦次，“最大クリークを抽出するより効率的な分枝限定アルゴリズム,，，信学技報
COMP2003-48(2003)．
[14］EIbmitaandT・Seki,``AneHicientbranch-and-boundalgorithmfOrfindingamaximumclique,，，
ProcDiscreteMathematicsandTheoreticalComputerScience(DMTCS2003),pp278-289(2003）
[15］PRJOstergAI6d,``Afastalgorithmfbrthemaximumcliqueproblem,，，DiscreteAppliedMathemat‐
ics,ＶｂＬｌ２０,ｐＰｌ９７－Ｏ７(2002）
[16］Ｍ・Labbe,Ｐ・MaJecotte,ＧＳａﾊﾞﾉardand]BOSewell,``AbranchandboundalgorithmfOrthestability numberofasparsegmph,”INFORMSJournalonComputing,Ｖｂ1.10,No.４，ｐｐ４３８－４７(1998）
[17]』.-MBourjolly,Ｐ・Gil1,Ｇ.LaporteandHMeIcure,``AnexactquadraticO-1algomthmfbrthestable setproblem,'’１，Ｊ・AbelloandJVitter，editors，Externalmemoryalgorithmsandvisualization，
DIMACSSeriesonDiscreteMathematicsandTheoreticalComputerScience，ＶＯＬ５０，American MathematicalSociety，pp53-3-130(1996)．
[18］Ｊ・Abello,PMPardalosandMGOResende,``OnmaximumcliqueproblemsinverylaJPgegraphs,'’
１，Ｊ・AbelloandJVitter,editors,Externalmemoryalgorithmsandvisualization1DIMACSSerieson DiscreteMathematicsandTheoreticalComputerScience,ＶＯＬ50,AmericanMathematicalSociety，
ｐｐｌｌ9-30(1999）
[19］RBattitiandM・Protasi,“ReactivelocalsearchfOrthemaximumcliqueproblem,，，Algorithmica，
ＶＯＬ29,No.４，ｐｐ､６１０６３７(2001）
[20］Ｄ・SJohnsonandMA.'mck,`Cliques,Coloring,andSatisfability,，，DIMACSSeriesinDiscrete MathematicsandTheoreticalComputerScience,ＶＯＬ26,AmericanMathematicalSociety）(1996）
[21］EMarchiori,``Genetic,iteratedandmultistartlocalseamhfOrthemaximumcliqueproblem,，，
ApplicationsofEvolutionaryComputing,LNCS2279,Springer,ppll2-121(2002)．
[221s.Ｌin,andBKernighan,``AneectiveheuristicalgorithmfOrthetravelingsalesmanproblem,，，
OperationsResearch,Ｖ01.21,ｐｐ４９８－ｌ６(1973）
上野伸郎・片山謙吾・南原英生・成久洋之
104
SearchSpaceAnalysisoftheMaximumCliqueProblem
