Comments
Description
Transcript
PDF File
序文
組合せ最適化は離散数学の分野で 年ほど前に始まった最新の研究分野である．現
在では最も活発に研究されている分野の一つであり，離散数学の研究の駆動力になっ
ているといえるだろう．
本書は，組合せ最適化における最も重要な概念，理論的成果，およびアルゴリズム
を解説している．最近の研究成果も概観できる大学院の先端のテキストとして本書を
使用することを想定している．本書には，グラフ理論，線形・非線形計画法，計算量
理論の本質的な基本的成果も含めている．さらに，組合せ最適化の古典的なトピック
スとともに最新のトピックスも取り上げている．特に，理論的成果とよい精度保証の
できるアルゴリズムに重点を置いて解説している．応用とヒューリスティックスにつ
いてはわずかにしか述べていない．
組合せ最適化のルーツは，組合せ理論，オペレーションズリサーチ，および理論情
報科学にある．現実の多くの問題が組合せ最適化の問題として抽象化して定式化でき
ることが組合せ最適化の研究の主たる原動力となっているといえるだろう．様々な形
で現実の問題として現れてくるこのような古典的問題が，背後に横たわる理論ととも
に詳細に研究されてきたことに焦点を当てる．
組合せ最適化問題は，グラフを用いて 整数 線形計画問題として自然に定式化でき
るのものが多い．そのようなことから，本書では，第 章で本書の全体を概観した後，
まずはじめにグラフ理論の基礎を簡単に復習し，組合せ最適化に最も関係のある線形・
非線形計画法の重要な成果を証明する．
その後，組合せ最適化の古典的なトピックスである，最小全点木，最短パス，ネッ
トワークフロー，マッチング，マトロイドを詳しく解説する．このように第 章から
第 章までで取り上げる問題はほとんどが多項式時間の 効率のよい アルゴリズ
ムが存在するものである．これに対して，第 章から第 章までで取り上げる問題
は，ほとんどが多項式時間のアルゴリズムが存在しないだろうといわれている 困
難問題である．それでも，ある程度の性能をもつ近似解を多項式時間で求める近似ア
ルゴリズムは少なくとも開発できることが多い．このような 困難な 問題に対処す
るその他のいくつかの戦略も解説する．
本書は，組合せ最適化のこれまでの本と様々な点で異なり，困難な部分にも大胆に
踏み込んでいる．たとえば，全次元有界多面体での 最適化問題と分離問題の等価性，
序文
耳分解に基づく のマッチングアルゴリズムの実装，チューリング機械，パー
フェクトグラフ定理，困難性，ビンパッキングに対する アルゴリズム，多品種フロー，サバイバルネットワーク設計，ユークリッド空間の巡
回セールスマン問題に対する最新の近似アルゴリズムも取り上げている．いずれも詳
細な証明とともに解説している．
もちろん，組合せ最適化のすべてを完璧に取り上げた本など書けるはずがない．簡
単に述べるだけであったり，あるいは全く取り上げなかったトピックスも多い．その
ような例としては，木分解，分離点集合，劣モジュラーフロー，パスマッチング，デ
ルタマトロイド，マトロイドパリティ問題，配置とスケジューリング問題，非線形計
画問題，半正定値計画問題，アルゴリズムの平均 計算時間，性能 解析，最先端デー
タ構造，並列およびランダム化アルゴリズム，確率的検証可能証明の理論 定理
は証明なしで引用している などが挙げられる．
各章末には多数の演習問題を与えている．それらは，その章で取り上げた話題に対
するさらなる成果と応用なども含んでいる．なかにはかなり難しい問題も含まれてい
るが，それらは星印を付けて区別している．各章末には参考文献のリストとより深い
内容についての案内も載せている．
本書は，組合せ最適化の複数の講義科目および組合せ多面体理論や近似アルゴリズ
ムなどの特論科目を通してまとめられたものである．したがって，基本コ−スあるい
は先端コース向けに内容を選択することもできる．
本書をまとめるに当たって，多くの同僚や友人から貴重な議論やコメントを頂いた．
もちろん，組合せ最適化のこれまでの本からも多くのことを学ばせて頂いた．特に，
!"# #$! %&'( "&)& '*(+$& ,#"-
!(.&-(
に心から感謝したい．また，ボン大学の同僚や学生の *(-#* "/&'*- 01"
23
1.&" 4*# 5&6&(&- -*( 71- $& &8& %/& $#
%#9 & %#*& -( 4*( :3
1.& 6&/& は，本書の原稿を詳細に読
んでくれた．そのおかげで本書を大幅に改善することができた．最後に，シュプリン
ガーフェアラーク社にご協力頂き，早く出版に至ったことを感謝する．
ボンにて，
年 月
ベルンハルト コルテ 2&* #-&
イェンス フィゲン :& ;8.&
第 版への序文
出版から 年で本書の初版が売り切れるほどになったことは大変な驚きであった．
同僚や一般読者からの本書に対する多数の好意的で情熱的なコメントや手紙も，私た
ちにとってこの上ない喜びであった．同僚の何人かは，印刷時のタイプミスなどを見つ
2& <3
-& %#"= 3
#*(.
けてくれた．特に，0"('* 2&& にはこの点で感謝する．もちろん，これまでに見つけられた間違いは第 版ではすべ
て修正している．また，参考文献も更新している．
初版の序文では忘れてしまったことがある．本書の準備で手伝ってくれた人をすべ
て挙げはしたが，研究機関からのサポートに触れることを忘れてしまった．そこで改
めてここで名前を挙げて感謝したい．
本書の出版プロジェクトは > 年間に渡ったが，多くの機関からの研究助成を受けて
初めて達成できたものであることは明らかである．特に，ハンガリー科学アカデミー
とドイツ学術振興会がスポンサーのハンガリー・ドイツ相互交流研究プロジェクト，ド
イツ学術振興会からの つの特別研究ユニット，フランス調査研究科学技術省とアレ
クサンダーフンボルト財団からの () "&)& & 71/#"- によるサポートおよ
びヨーロッパ共同体のコミッションからの つの参加プロジェクト ?54，から援
助を受けた．科学・人間学のドイツアカデミー連合とノルトラインヴェストファーレ
ン州科学アカデミーには最高の感謝をしたい．ドイツ連邦文部科学省 22 とノル
トラインヴェストファーレン州科学アカデミーがサポートしてくれた長期プロジェク
ト 離散数学とその応用 が本書では決定的に重要な役割を果たした．
ボンにて，
年 月
ベルンハルト コルテ 2&* #-&
イェンス フィゲン :& ;8.&
第 版への序文
年の歳月が経ち，全面的な改訂と本質的な拡張を行った第 @ 版の出版の時機が来
たといえるだろう．今回の第 @ 版の最大の特徴は，施設配置問題を取り上げて完全に
新しい章 第 章 を加えた点であろう．この重要な 困難な問題のクラスに対す
る定数近似のアルゴリズムは A 年前までは知られていなかった．しかしながら，今日
いくつかの全く異なる興味深い手法によって，よい近似保証が達成されている．これ
により，この分野は，研究の観点からだけでなく教育の観点からも極めて魅惑的な分
野になっている．実際，この第 章は施設配置問題の特別講義に基づいてまとめられ
たものである．
他の章も多くの点で本質的に拡張している．より具体的には，フィボナッチヒープ，
藤重 1+(*(.& の新しい最大フローアルゴリズム，時変 動的 フロー，'*(+$& に
よる劣モジュラー関数の最小化アルゴリズム，シュタイナー木問題に対する %#/(
,&"(#$8 近似アルゴリズムなどを新しく加えている．また，いくつかの証明はより
系統的でわかりやすくしている．さらに，新しい演習問題と最新の成果への参考文献
も追加している．
本書第 版に対して貴重なコメントをくれた人々に感謝したい．特に，4# #
B1*(-# # 0"('* 2&& -&* 7&" 4#(# 7(- ?( 3
1""&
!1# 1#- ?(&-& %1-&/'* -( 1-&"" 1 -1!8 および
:3
1.& 6&/& に感謝する．なかでも，4# # のノートと :3
1.& 6&/& の
第 章の精密な検証により，本書の表現が大幅に改善できた．
科学・人間学のドイツアカデミー連合とノルトラインヴェストファーレン州科学ア
カデミーには再度感謝する．ドイツ連邦文部科学省 22 とノルトラインヴェスト
ファーレン州科学アカデミーの長期プロジェクト 離散数学とその応用 を通しての
サポートに心から感謝する．
ボンにて，
年
月
ベルンハルト コルテ 2&* #-&
イェンス フィゲン :& ;8.&
日本語版への序文
原書の日本語版に向けて積極的に活動してくれた浅野孝夫教授に感謝する．彼は，
彼の子の浅野泰仁博士と同僚の平田富夫教授と小野孝男博士とともに，真摯に取り組
み翻訳を成し遂げてくれた．彼ら全員に心から感謝する．
組合せ最適化の分野における日本の研究者の貢献は多大なものがある．日本におけ
るこの分野の教育と研究に，この日本語版がより一層の手助けになってくれればと心
から願っている．最後に，シュプリンガー・フェアラーク東京と浅野教授の尽力によ
り，日本語版の出版が実現される運びになったことを大変嬉しく思っている．
ボンにて，
年 月
ベルンハルト コルテ 2&* #-&
イェンス フィゲン :& ;8.&
訳者序文
本翻訳書は，組合せ最適化の最先端の研究を行っている 2&* #-& :&
;8.& による原書 #/(-#(" -((!-(#C 4* ".#(-* @
&(-(# の全訳である．
インターネットに代表される情報ネットワークの情報通信や鉄道・道路網に代表さ
れる物流などで生じる自然な問題は，整数計画問題として定式化できることが多い．
その意味でこれらの問題は本来数理計画の問題であるが，現存の数理計画のソルバー
ソフトウエア，アルゴリズム では計算時間の観点から大規模な問題を解くのは極め
て困難であるといわれている．この打開策として，ネットワークの構造を利用するグ
ラフ理論やネットワークの接続行列のもつ性質 完全ユニモジュラー性など に基づい
て，組合せ的なアルゴリズムが展開され，大きな成功をおさめてきている．
また，情報科学のアルゴリズム理論においても，数理計画問題としてモデル化し
て，数理計画法の双対定理や最適相補条件の双対理論に基づいた組合せ的アルゴリ
ズムが理論と応用の両面から脚光を浴びている．実際，情報科学の分野の国際規模の
代表的な学会である 国際情報学会，D555国際電気電子学会，D国際応
用数理学会 および 国際数理計画法学会 が主催する世界的権威の国際会議の
48#(1 # 4* #= #1-(.，#1-(# #= #1-&
'(&'&，?8#(1 # ?('&-& ".#(-* および DD-&.& #/(-#(" -((!-(# などでも，組合せ的アルゴリズムは最も発表件数が多
く主たる研究テーマと認識されている．
原書は，現在このようにアルゴリズム研究の最先端を行く組合せ最適化の分野の最
新の成果を，系統的にかつ直観的にわかりやすくまとめて解説し，現場の仕事の応用
やこの分野のさらなる発展への道標になることを目的としている．
年の初版の
出版から極めて好評で，
年後に第 版が出版され，そして今回第 @ 版が出版された．
著者の第 @ 版の序文にもあるように，第 版にはなかった内容が大幅に付け加えられ，
その後に発表された最新の研究成果も第 @ 版には含められている．第 @ 版は，このよ
うに最新の研究動向も含めると同時に，組合せ最適化の研究分野がより理解しやすく
系統的に学べるように改良も施されている．
一方，著者の指摘にもあるように，日本における組合せ最適化の研究も極めて活発に
行われてきている．特に，伊理正夫東京大学名誉教授の &-9# "#9 4#-
序文
-(# '*&1"(.C 4* ".#(-* '&(' & EE，西関隆夫
東北大学教授と千葉則茂岩手大学教授の " <*C 4* ".#(-*
" #= ?('&-& -*&-(' ;#"F@
#-*7#"" EAE，藤重悟京都大
学教授の 1/#1" 1'-(# -((!-(# " #= ?('&-& -*
&-(' ;#"F> #-*7#"" EE および室田一雄東京大学教授の ?('&-&
#$&) "8( D @ と -('& -#( =# 8-& "8(
(.& などは，組合せ最適化の発展に大きく貢献してきている．さらに，
永持仁京都大学教授と茨木俊秀関西学院大学教授のグラフスパース化と最小カットの
アルゴリズム，岩田覚東京大学助教授の劣モジュラー関数最小化アルゴリズム，渡邉
敏正広島大学教授のグラフ連結度増加アルゴリズムなどは，先駆的なアルゴリズムと
して高く評価されている．
このように日本のこの分野における研究は世界的にも第一線のものであるが，日本
の研究者・学生にこのことが広く認識されているとはいい難い．そのような点から，著
者も期待しているように，これからの日本の情報技術を担う現場の人々や大学・研究
所の情報科学・数学系の学生・研究者が，日本が大きく貢献している組合せ最適化の
分野に関心をもち，その学習・研究にこの日本語版がより一層の手助けになってくれ
ればと心から願っている．
なお，日本語版の利便性を考えて，原書の記法一覧は目次の前に置いている．また，
原書で取り上げられた問題とアルゴリズムにも番号を付けて検索しやすいようにし，
この序文のすぐ後に一覧としてまとめている．さらに，原書の特徴である簡潔性と明
快性を保ちながら，日本語による内容の理解がより確実にできるように，意訳に心が
けコメントを訳注として加えている．
原書の翻訳に当たり多くの人から協力援助を頂いた．ボン大学の 2F #-& 教授と
:F ;8.& 教授からは 45 のファイルを頂き，翻訳作業の困難さを格段に軽減でき
た．さらに，実際の翻訳の大半は，ボン大学離散数学研究所にて所長の #-& 教授の
ご厚意のもとで行った．;8.& 教授にはたびたびの質問に快く答えて頂いた．またボ
ン大学の日本学研究所の F -!& 教授婦人の (#( -!& さんには，原書のド
イツ語部分の翻訳でコメントを頂いた．シュプリンガー・フェアラーク東京の編集部の
スタッフには，翻訳書の原稿の編集に際し翻訳の脱落や誤訳および 45 の体裁につ
いてのご意見を頂いた．以上の人に心から感謝する．なお，最終的な翻訳に不適切な
箇所があればすべて訳者の責任であり，読者からのご意見を歓迎したい．最後に，訳
者の１人の浅野孝夫は，不断の応援で支えてくれた両親と妻に感謝する．
年 E 月
浅野孝夫
平田富夫
小野孝男
浅野泰仁
問題一覧
問題 ドリル穴あけ問題 問題 ジョブ割当問題 問題 線形計画問題 問題 分離問題 問題 弱分離問題 問題 弱最適化問題 問題 整数計画問題 " 問題 %
最大重み森問題 &'( ) * 問題 %
最小全点木問題 &( + 問題 %
最大重み有向森問題 &'( ) ,-) 問題 %
最小重み有向木問題 &( ) -- 問題 %
最小重み根指定有向木問題
問題 $
問題 $
問題 $
問題 問題 問題 問題 問題 問題 問題 #
問題
問題
! &( ) ./ -- 最短パス問題 ) ) 全点間最短パス問題 ) ) 最小平均長閉路問題 &( & 01- 最大フロー問題 &'( *2 有向 無向 辺 点 素パス問題
-/ 3/-/ 4/5 6'5 7 ) 最小容量カット問題 &( 0-1 0( 最小費用フロー問題 &( 0 *2 ヒッチコック輸送問題 8-)-- 最大時変フロー問題 &'( *2 9 + 辺数最大マッチング問題 0/1 &-) 最大重みマッチング問題 &'( ) &-) 問題 問題 独立性システムに対する最大化問題
問題 &'! * "//- 1
問題 %
%
$#
$
#
$
$
$
$
$
最小重み完全マッチング問題
&( ) :- &-) 最大重み 5マッチング問題 &'( ) 5&-) 最小重み 5ジョイン問題 &( ) 5 最小容量 5カット問題 &( 0-1 50( 問題 #$
#
#
%
%
$
#
#%
独立性システムに対する最小化問題
&! * "//- 1
問題一覧
問題 マトロイド交差問題 &/ "- 問題 マトロイド分割問題 &/ 問題 $
重み付きマトロイド交差問題 )/ &/ "- 問題 劣モジュラー関数最小化問題
問題 問題 問題 問題 問題 問題 %
問題 $
問題 問題 問題 #
問題 問題 問題 問題 問題 問題 %
問題 %
問題 %
問題 %
問題 %
問題 %%
問題 $
問題 $
問題 $
問題 $
問題 $
問題 問題 問題 問題 問題 #
問題 #
問題 問題 問題 問題 問題 問題 問題 (/( *(- &! ハミルトン閉路問題 8 0-(
線形不等式問題 ";(
整数線形不等式問題 " ";(
充足性決定問題 <1+
+ 充足性決定問題 5<1
安定集合問題 点カバー問題 6' 09
クリーク問題 0;(
次元マッチング問題 5 &-) &
部分集合和問題 (5(
分割問題 素数決定問題 巡回セールスマン問題 +9 +
番目に重い部分集合問題 5) 89 (
最大重みカット問題 &'( ) 0( 最小重み集合カバー問題 &( ) 09 点彩色問題 6'50( 辺彩色問題 4/50( 最大充足化問題 &'( <1 &=5+
最大 充足化問題 &=5+
5出現最大充足化問題 5 --(- &=5+ ナップサック問題 >- 小数ナップサック問題 *- >- 重み付き中央値問題 )/ &/ 選択問題 - 5支配問題 5- ビンパッキング問題 ,5
- 有向多品種フロー問題 -/ &(-/1 *2 無向多品種フロー問題 3/-/ &(-/1 *2 最大多品種フロー問題 &'( &(-/1 *2 サバイバルネットワーク設計問題 (99 ?2 シュタイナー木問題 + メトリック +
&- +
ユークリッド +
4(-/ +
制限付きハミルトン閉路問題 .-/ 8 0-(
+
ファセット問題 +
*-
別のハミルトン閉路問題 ) 8 0-(
容量制約なし施設配置問題 3--/ *-1 - 普遍的施設配置問題 39 *-1 - %%
#
#
$
##
#
#
#
#$
%#
%
%
$
#
$#
$
#
% %
アルゴリズム一覧
アルゴリズム パス列挙アルゴリズム ) 4( )
アルゴリズム マージソートアルゴリズム &5 )
アルゴリズム グラフ走査アルゴリズム @) - )
アルゴリズム 強連結成分アルゴリズム
アルゴリズム アルゴリズム アルゴリズム アルゴリズム アルゴリズム アルゴリズム アルゴリズム アルゴリズム %
アルゴリズム %
アルゴリズム %
アルゴリズム $
アルゴリズム $
アルゴリズム $
アルゴリズム $
アルゴリズム アルゴリズム アルゴリズム アルゴリズム アルゴリズム アルゴリズム %
アルゴリズム 1 0-/ 0 )
4( のアルゴリズム
単体法 ' )
ユークリッド互除法 4(-/ )
連分数展開 0(/ *- 4'
ガウスの消去法 @( 4
楕円体法 4/ &)/
@A-)59B!5-)79 アルゴリズム
>( のアルゴリズム
のアルゴリズム
4// の有向森アルゴリズム 4//C ,-) )
7 のアルゴリズム
&5,5*/ アルゴリズム
*1/5) アルゴリズム
最小平均長閉路アルゴリズム &( & 01- )
*/5*( アルゴリズム
4//5> アルゴリズム
- のアルゴリズム
藤重のアルゴリズム *(7)C )
プッシュ再ラベルアルゴリズム ()5. )
@158( アルゴリズム
最小平均長 費用 閉路解消アルゴリズム
&( & 01-50- )
%
%
%%
%
$
$
#
##
アルゴリズム 最短パス反復アルゴリズム
(--9 ) ) )
アルゴリズム 容量スケーリングアルゴリズム 0-1 - )
アルゴリズム のアルゴリズム
アルゴリズム # 耳分解アルゴリズム 45- )
$
アルゴリズム # 4// の辺数最大マッチングアルゴリズム
0/1 &-) )
%
アルゴリズム一覧
重み付きマッチングアルゴリズム )/ &-) ) %
アルゴリズム 最悪棄却グリーディ法 5 (5@/1 )
%
アルゴリズム 4// のマトロイド交差アルゴリズム
&/ "- )
%
アルゴリズム 重み付きマトロイド交差アルゴリズム
)/ &/ "- )
アルゴリズム グリードイドに対するグリーディ法
@/1 ) * @//
%#
アルゴリズム ポリマトロイドグリーディ法 1/ @/1 )
%
アルゴリズム -)79 のアルゴリズム
%
アルゴリズム % 集合カバーに対するグリーディ法
@/1 ) * 09
アルゴリズム % 点カバーに対するグリーディ法
@/1 ) * 6' 09
#
アルゴリズム % ,5D)(/549 アルゴリズム
アルゴリズム % グリーディ彩色アルゴリズム @/1 0( )
%
アルゴリズム % 最大充足化問題に対する ) のアルゴリズム
アルゴリズム %% 最大充足化問題に対する @5 アルゴリズム
%
アルゴリズム $ 重み付き中央値アルゴリズム )/ &/ )
%#
アルゴリズム $ 動的計画ナップサックアルゴリズム
1- >- )
%
アルゴリズム $ ナップサック近似スキーム >- ' -)
%
アルゴリズム ?'5* アルゴリズム ?*
$
アルゴリズム *5* アルゴリズム **
$
アルゴリズム *5* 減少アルゴリズム **
$
アルゴリズム */!5/5565( アルゴリズム
$$
アルゴリズム 多品種フロー近似スキーム
&(-/1 *2 ' -)
アルゴリズム # 1:(5 アルゴリズム
アルゴリズム # >(5&21, アルゴリズム
$
アルゴリズム # .5E91 アルゴリズム
アルゴリズム # ネットワーク設計に対する主双対アルゴリズム
5( ) * ?2 #
アルゴリズム # のアルゴリズム
アルゴリズム 木二重化アルゴリズム (5+ )
アルゴリズム 0)</ のアルゴリズム
アルゴリズム のアルゴリズム
%
アルゴリズム 5 アルゴリズム
%
アルゴリズム 5>) アルゴリズム
%$
アルゴリズム % 分枝限定法 ,-)5/5,(/ &)/
アルゴリズム )15+/5/ アルゴリズム
アルゴリズム 56! アルゴリズム
アルゴリズム 双対フィットアルゴリズム ( * )
$
アルゴリズム
アルゴリズム 最良選択グリーディ法 ,5"5@/1 )
記法一覧
すべての自然数の集合
すべての整数の集合 すべての非負整数の集合
すべての有理数の集合 すべての非負有理数の集合
すべての実数の集合 すべての非負実数の集合
真部分集合
集合 と の対称差
部分集合
直和
/ ベクトル のユークリッドノルム
ベクトル の無限大ノルム
を で割ったときの余り
# かつ
F
を満たす唯一の数 ベクトル の転置ベクトル，行列 の転置行列
G G H !
J K
L
L
の切り上げ 以上の最小の整数
の切り捨て 以下の最大の整数
5記法
H5記法
の符号長I の 進数表現の長さ
の底 の対数
グラフ の点集合
グラフ の辺集合
で誘導される の部分グラフ
で誘導される の部分グラフ
から辺 を除去して得られるグラフ
に辺 を付加して得られるグラフ
グラフ と の和
から点の部分集合 を縮約して得られるグラフ
と の間にまたがる辺の集合
から へと向かう有向辺の集合
Æ F Æ ， Æ F Æ 点集合 から出ていく辺の集合，点 から出ていく辺の集合
Æ F Æ 点集合 に入ってくる辺の集合，点 に入ってくる辺の集合
$F $F %
%
%
%
%
$
$
$
$
$
$
記法一覧
M F M に含まれる点集合 の隣接点集合，点 の隣接点の集合
点の完全グラフ
上の 5 5部分パス
/ のべき集合
最短な 55パスの長さ
かつ N を仮定している
点と 点の完全 部グラフ
!
多角形
の平面的双対グラフ
F ベクトル と のスカラー積
ベクトル と に対して各成分毎に不等式が成立する
/ 行列 のランク
"
単位行列 恒等行列
# 番目の単位ベクトル 第 # 成分のみが
の辺I 辺 の双対辺
Æ
O
F '()
Æ P P
' 9( 非空な集合 の次元
で他が # のベクトル
に含まれる行からなる の部分行列
添え字が
-9 / $ % 9( と直線 ! の交差回数
に含まれる成分からなる
成分がすべて
の部分ベクトル
のベクトル
に含まれるすべてのベクトルからなる凸包
行列 の行列式
置換 $ の符号
楕円体
中心が で半径 のユークリッド球
非空集合 の体積
行列 のノルム
の極集合
多面体 の整数包
行列 の小行列の最大絶対値
の第
番目 & 番目 の @150)9B
切り取り
ラグランジュ緩和
多分割カット
辺 の $ に関する簡約コスト
のメトリック閉包
におけるフロー の正味流入量 への流入量 からの流出量
*5+5フロー の流量
からすべての辺の逆辺を加えて得られる有向グラフ
, フロー に関する辺 の残容量
有向辺 の逆辺
フロー に関する残容量グラフ
のレベルグラフ
)
* と + を分離するカットの最小容量
)
のカットの最小容量 辺連結度
$
$
F %
%
%
%
%
%
%
%
%%
$
$
$
#
#
#$
#
$
%
$
#
#
#
#
記法一覧
- のマッチングの最大辺数
. の点カバーの最小点数
ベクトル に依存する の +( 行列
/ の奇数連結成分の個数
0
の安定集合の最大点数
1 の辺カバーの最小辺数
独立性システムでの のランク
2 独立性システムでの の閉包
3 / 4 無向グラフ の閉路マトロイド
# +
独立性システムでの の下方ランク
独立性システム のランク商
に対して に含まれる唯一の閉路
のときは と考える
独立性システム の双対
劣モジュラー関数 に対するポリマトロイド
空白記号
すべての 進文字列 すべての #5 5文字列 の集合
多項式時間で決定可能な問題のクラス
15インスタンスに対する証明の存在する問題のクラス
リテラル の否定
の問題の補問題のクラス
インスタンス の最適解の値
最適化問題のインスタンス におけるアルゴリズム の出力の値
5
6 4' 3&" 7 " " 8 " インスタンス に現れる最大整数
%%
%%
%
%
L
L L L の彩色数
のクリークの最大点数
ランダム変数 の期待値
事象 の確率
" のすべての要素での和
インスタンス " に対する ?'5* アルゴリズムの出力
インスタンス " に対する *5* アルゴリズムの出力
インスタンス " に対する *5* 減少アルゴリズムの出力
シフトしたグリッド
9
でのすべてのツアーの接続ベクトルの凸包
+
のインスタンス に対する 8/5> 下界
F 解の施設開設コスト
F 解の利用コスト
%
#
#%
#
#
#
%
%
%
$
$
$
$
$
$
F % %
F % %
目 次
問題一覧
アルゴリズム一覧
記法一覧
第 章 はじめに
アルゴリズムの計算時間 線形の最適化問題 ソーティング 演習問題 参考文献 F
F
F@
F
列挙
第 章 グラフ
木，閉路，カット 連結性 オイラーグラフと 部グラフ 平面性 平面的双対性 演習問題 参考文献 F
F
F@
F
F
F
基礎的な定義
第 章 線形計画法
E
@
@F 多面体 A
@
@A
A
目 次
@F
単体法 @F@ 双対性 >
@F 凸包と有界多面体 >
演習問題 >@
参考文献 >
第 章 線形計画アルゴリズム
*'*(8 の定理 分離問題と最適化 演習問題 参考文献 ユニモジュラー変換 完全双対整数性 完全ユニモジュラー行列 切除平面法 ラグランジュ緩和 演習問題 参考文献 最小重み有向木 多面体的表現 全点木と有向木のパッキング 演習問題 参考文献 F
F
F@
F
F
F
連分数 ガウスの消去法 楕円体法 頂点と面のサイズ
第 章 整数計画法
F
F
F@
F
F
F
多面体の整数包
第 章 全点木と有向木
F
F
F@
F
最小全点木問題
第 章 最短パス
>>
A
A
AE
E
E>
A
@
@
@@
@
@
>
>F 点からの最短パス >F
全点間の最短パス >
>F@ 最小平均長閉路 >@
演習問題 >
参考文献 >>
第 章 ネットワークフロー
&.& の定理 5# アルゴリズム ブロックフローと藤重 1+(*(.& のアルゴリズム <#"/&.4+ アルゴリズム <##871 木 無向グラフの最小カット 演習問題 参考文献 AF
AF
AF@
AF
AF
AF
AF>
最大フロー最小カット定理
第 章 最小費用フロー
最適性基準 最小平均長閉路解消アルゴリズム 最短パス反復アルゴリズム "( のアルゴリズム 時変フロー 演習問題 参考文献 EF
EF
EF@
EF
EF
EF
問題の定式化
第 章 最大マッチング
A
A
A>
AE
E
E>
A
A
@@
@
@E
部グラフのマッチング @
41--& 行列 41--& の定理 >
因子臨界的グラフの耳分解 5# のマッチングアルゴリズム 演習問題 参考文献 >
F
F
F@
F
F
第 章 重み付きマッチング
重み付きマッチングアルゴリズムの実装 事後最適性 マッチング多面体 演習問題 参考文献 F
F
F@
F
F
割当問題
重み付きマッチングアルゴリズムの概略
第 章 マッチングと ジョイン
>
>
>A
E
E
E>
EE
F マッチング @
目 次
F
最小重み ジョイン @
F@ ジョインと カット @
F /&.%# の定理 @@
演習問題 @>
参考文献 @
第 章 マトロイド
@F
@F
@F@
@F
@F
@F
@F>
独立性システムとマトロイド
双対性 グリーディ法 マトロイドの共通独立集合 マトロイド分割 重み付きマトロイド交差 演習問題 参考文献 他のマトロイド公理系
第 章 マトロイドの一般化
劣モジュラー関数の最小化 '*(+$& のアルゴリズム 対称劣モジュラー関数 演習問題 参考文献 F
F
F@
F
F
グリードイド
ポリマトロイド
第 章 完全性
@
@
>
@@
@@
@
@
@A
@ @ @ >
@
@
@E
@>
@>
@>E
チューリング機械 @A
*1'* の提唱 @A
と @AE
## の定理 @E
いくつかの基本的な 完全問題 @EA
クラス 困難問題 >
演習問題 参考文献 F
F
F@
F
F
F
F>
第 章 近似アルゴリズム
F 集合カバー A
F
彩色 @
F@ 近似スキーム @
F 最大充足化問題 @@
F 定理 @A
F 帰着 @
演習問題 参考文献 @
第 章 ナップサック問題
第 章 ビンパッキング問題
第 章 多品種フローと辺素パス
>F 小数ナップサック問題と重み付き中央値問題 A
>F
擬似多項式時間アルゴリズム >F@ 完全多項式近似スキーム @
演習問題 参考文献 >
AF グリーディ法 >
AF
漸近的近似スキーム >
AF@ アルゴリズム >E
演習問題 A@
参考文献 A
有向辺素パス問題 無向辺素パス問題 演習問題 参考文献 %#/(,&"(#$8 アルゴリズム サバイバルネットワーク設計 主双対近似アルゴリズム :( のアルゴリズム 演習問題 参考文献 EF
EF
EF@
EF
多品種フロー
多品種フローのアルゴリズム
第 章 ネットワーク設計問題
F
F
F@
F
F
シュタイナー木
第 章 巡回セールスマン問題
AA
E
E
A
@
A
A
@
F 4 の近似アルゴリズム E
F
ユークリッド 4 F@ 局所探索 目 次
F 巡回セールスマン多面体 >
F 下界 >A
F 分枝限定法 A
演習問題 A@
参考文献 A
第 章 施設配置問題
線形計画問題の解のラウンディング 主双対アルゴリズム スケール変換とグリーディ増加操作 開設施設数の制約 局所探索 容量制約付き施設配置問題 普遍的施設配置問題 演習問題 参考文献 F
F
F@
F
F
F
F>
FA
容量制約なし施設配置問題
E
E
E
E
A
>
E
著者索引
問題索引
用語索引
第 章 はじめに
つの例から始めよう．
プリント回路基板にドリルで穴をあける機械をある会社がもっている．この会社で
は，このようなドリルで穴をあける基板を大量に生産するので， つの基板のドリル穴
あけに要する時間はできるだけ短くなるように機械を自動化したい．実際にドリルで
穴あけをしている時間は最適化できないが，ドリル穴の位置を機械が次々と移動して
いくのに要する時間は最小化することができる．通常，ドリル穴あけ機械は 方向に
移動できる．実際，テーブルは水平 軸 方向に，ドリル穴あけアームは垂直 軸
方向に移動できる．これらの移動は同時に行えるので，あるドリル穴の位置から次の
ドリル穴の位置への移動に機械が要する時間は，水平方向距離と垂直方向距離の大き
い方に比例する．この距離は，通常， 距離と呼ばれている．古い機械では，同時
には，水平あるいは垂直のいずれか一方にしか移動できない．この場合には，移動時
間は，水平方向距離と垂直方向距離の和，すなわち 距離に比例する．
ドリル穴の位置 に対して， が最小となるようなドリ
ル穴の位置の順番付けが，最適なドリル穴あけパスとなる．もちろん，上述の理由に
距離であり，平面上の 点 G と G に対しては，
となる．ドリル穴の位置の順番付けは，順列，す
なわち，全単射関数 C で表現できる．
より，
は
CG )
最適な順列は，もちろん，ドリル穴の位置に依存する．与えられるドリル穴の位置
が全体として異なれば，異なる問題 のインスタンス となる．したがって，この問題
のインスタンス 入力 は，平面上のドリル穴の位置の座標リストであると考えること
ができる．すなわち，問題は，以下のように定式化できる．
問題
ドリル穴あけ問題 ?(""(. #/"&
インスタンス 平面上の
タスク
個の点 ．
が最小となるような順列 C を求める．
次に 番目の例を説明しよう．指定された処理時間を有するジョブの集合と，従業
第
章
はじめに
員の集合が与えられる．ただし，担当可能なジョブ集合は従業員ごとに異なる．各ジョ
ブは担当可能な従業員の部分集合から担当者が選ばれて処理される．さらに，どの従
業員も担当できるジョブに対しては対等で処理能力は等しいと仮定する．同一のジョ
ブに対して，同時に複数の担当者が従事できる．各従業員は，複数のジョブを担当で
きる が，同時には従事できない．このとき，目的はできるだけ早くすべてのジョブ
を完了することである．
このモデルでは，各従業員が，どの仕事にどのくらいの時間従事できるかを決めれ
ば十分である．従業員がどのような順番で割り当てられたジョブをこなしても問題な
い．すべてのジョブを完了する時刻は，従業員に割り当てられたジョブの最大のべ時
間数にのみ依存するからである．したがって，次の問題を解けばよいことになる ．
問題
ジョブ割当問題 :#/ (.&- #/"&
インスタンス 個のジョブの処理時間である 個の非負実数 ，
人の従業員および各ジョブ に対する担当可
能な空でない従業員の部分集合 ．
各 G G を満たす G のうちで，) が最小となるような
を求める．
タスク
で
これらは組合せ最適化で生じる つの典型的な問題である．実際的な問題を抽象的
な組合せ最適化問題としてどのようにモデル化するかについては，本書では取り上げ
ない．実際，そのようなことを可能にする一般的な方法はないからである．入力と要
求される出力の正確な記述を与えるだけでなく，不要なことをきちんと識別して除外
することも極めて大切である たとえば，ドリル穴あけ問題では，実際にドリルで穴
をあけている時間は一定で最適化できないし，ジョブ割当問題では各ジョブに従事す
る担当者の順番も無関係である．
もちろん，ある会社の つの特別なドリル穴あけ問題やジョブ割当問題の解に関心
があるのではなく，これらの問題として定式化できるすべての問題に適用できる解法
を求めたいわけである．この点を，まず最初にドリル穴あけ問題を通して，詳しく眺
めていこう．
列挙
ドリル穴あけ問題 問題 F の解はどのようなものになるだろうかH 平面上の有
限個の点からなる インスタンスは無限にあり，それらすべてに対して最適な順列を
訳注
ドリル穴あけ問題 問題
同様に，
とジョブ割当問題 問題
で，
はすべての自然数の集合を表す．
はすべての実数 すべての有理数，すべての整数 の集合，
の非負実数の集合 すべての非負有理数，すべての非負整数 の集合を表す．記法一覧参照．
はすべて
列挙
表としてもっておくことはできない．そこで，インスタンスが与えられたなら，最適
解を計算するようなアルゴリズムが欲しいということになる．そのようなアルゴリズ
ムは存在する．実際， 個の点の集合が与えられたなら，単に I 通りのすべての可能
な順列を求めて，それぞれに対応するパスの 長さを計算し，最小の長さのものを
出力すればよい．
アルゴリズムを記述するにしてもいろいろなやり方がある．どの程度詳細に記述す
るかにもよるし，使用する言語にもよる．ただし，次のような形でアルゴリズムを記
述することはできないものとしているC 与えられた
個の点の集合に対して，最適な
パスを見つけてそれを出力する．これでは，最適解を見つける具体的な方法が何も示
されていないからである．上で述べたすべての順列を列挙する方法はより有効である
が，どのようにしてすべての順列を列挙するかが曖昧である．順列を列挙する つの
方法としては，以下のようなものが考えられる．
のすべての 組，すなわち， の
個のすべてのベクトル，
を列挙する．これは数え上げと同様の手法で以下のようにできる． から
始めて FFF まで進み，次に へ行き，同様に，
FFF FFF FFF まで数えていく．
すなわち， 桁の 進数と考えて各段階で 加えていくわけである．通常の 進数と
異なる点は， の代わりに ， の代わりに ， の代わりに G を
用いている点である． 加えるには 最後の成分 最下位の桁 に を加えるが， で
ないならば単に 増やせばよい．また ならば 加えて繰り上がりが生じて下位の桁
から順次上位の桁に移っていき， でない最初の桁の値を 増やし，それより下位の
桁をすべて とする．この技法は，バックトラッキングとも呼ばれている．なお，こ
のとき のベクトルが列挙される順番は，以下の定義のように辞書式順と
呼ばれている．
を つのベクトルとする．すべての G で G となるような添え字 が存在するとき，ベクトル
はベクトル より辞書式順で小さい "&)('#.*('""8 ""& という．
定義
であり，かつ のすべてのベクトルを列挙する方法がわかったので，あとは単に各ベク
トルで成分がすべて異なることを確かめる．すべて異なっていればそのベクトルは順
列になるので，それまでに得られた順列の一番短いパスといま得られた順列のパスの
長さを比較して，短いときは新しくいま得られた順列が一番短いパスであるとして更
新していけばよい．
このアルゴリズムは
個のベクトルを列挙するので，少なくとも
のステップ
の時間がかかる 実際にはそれ以上かかる．これは最適ではない． の順列
の総数は I であり， I は
よりも格段に小さいからである -("(. の公式によれ
I のステップ
である -("(. J>@KL 演習問題 参照．ほぼ
ですべてのパスを列挙する方法を示すことにしよう．そこで，すべての順列を辞書式
ば I
順で列挙する以下のアルゴリズムを考えてみよう．
第
章
はじめに
アルゴリズム
パス列挙アルゴリズム -* 51&-(# ".#(-*
入力
自然数
出力
パスの長さ
@ と平面上の
個の点の集合
．
CG ．
が最小となる順列
各 G に対して CG とする． CG ， CG
C
とする．
CG ( M M とする．
C
CG とする．
G かつ CG とする．
M CG ， CG M とする．
G M CG とする．
へ行く．
G @ および G
と初期設定して，アルゴリ
ズムは，各ステップで の を用いない 可能な次の値を求める．
の可能なそのような値がなくなった すなわち， G M ならば，アルゴリズ
ムは の値を 減じてバックトラックする．そうでないときは， に新しい値を設
定する． G のときは新しい順列 の長さ が評価される． のときは，アルゴリ
ズムは， M のすべての可能な値を確かめてみるために M CG とおいて， の値を 増やす ．
したがって，すべての順列ベクトル が辞書式順に生成される．た
とえば， G のケースで最初の反復は以下のようになる．
CG @ CG
CG CG @ CG CG CG @ H
CG >
CG
CG >
CG CG CG @ CG
CG CG @ CG H
CG CG @ 訳註
このアルゴリズムは慣れないと理解しにくいので，もう少し詳しく説明しよう．アルゴリズムは， から で用いられていない最小の数 を選び，
とする．そして を固定して残りの のすべての可能な 個の 順列 を求めて につなげ
て 列挙する．そのような が存在しないときは は と設定され， を固定し
を満たす．こ
た順列の最後まで列挙したことになり，現在の順列 は のときは，アルゴリズムは の値を 減じてバックトラックする．
で現在の
の代わりに
で改めてそれを
列挙
アルゴリズムは，新しい順列に対応するパスのコスト 長さ とこれまで見つけられ
た最適な順列 に対応する最適なパスのコストを比較して良い方を最適な順列とし
て更新しているので，実際に最適なパスが出力される．それでは，このアルゴリズム
で必要となるステップ 初等的操作 数はどのくらいになるだろうかH もちろん， 回
の初等的操作をどのように定義するかで，答えは変わってくる．実際の具体的な実装
を詳細に与えることは考えていないので，定数倍の範囲での誤差を許した初等的操作
数で見積もることにする．合理的な計算機 納得のいく計算モデル のもとでは， は
少なくとも M 回の初等的操作が必要である 変数への代入が M 回行われる
が，一方，ある定数 を用いて高々 回であるともいえる．定数倍の誤差を許す見積
もりにおいては，以下の記法が広く用いられている．
定義 つの非負関数 C に対して，すべての で M となるような定数 が存在するとき， は であるという
G とも書く． G かつ G のときは， G N であり もちろ
ん G N でもある， と は同じ増加率 -& #= .#9-* をもつという．
記法における等号は対称的ではない 左辺と右辺の交換はできない ことを注意
しておきたい．この定義をもう少し詳しく説明しよう． G とおき， を で
の初等的操作の回数とし， G とする．すると，明らかに G で
ある 実際には G N であるL すなわち は 時間 線形時間 で実行できる．
の 回の実行は， かつ G でないかぎりは，定数個の初等的操作 時
間，すなわち定数時間 で実行できる． かつ G のときは，
つのパスのコス
ト 長さ を比較しなければならないので， 時間かかる．
はどうであろうかH すべての M とすべての で G かどうかを調べていく素朴な実現法では， 回初等的操作
のより効率的な実現法は，添え字 をもつ作
が必要で N 時間となる． 業用の配列 を用いて以下のようにすることである．
CG CG とする．
CG CG とする．
CG M とする．
かつ G CG M とする．
このように実現すると，明らかに， の 回の実行は 時間でできることにな
る．本書では，このような簡単な技法は通常取り上げない．そのような単純な技法は
読者が見つけられるものとしているからである．
アルゴリズムの各ステップの計算時間を見積もることができたので，全体の計算時
間を見積もることにしよう．順列は I 個存在するので，
つの連続する順列が出力さ
れる間になされる仕事の計算時間を見積もればよいことになる．カウンター の値は，
からある添え字 まで戻され，新しい値 が見つけられる．その後， G
まで再び進められる．カウンター が一定の間は， と
はいずれも 回だけ実行される かつ G
かつ G
でないかぎり
のときは 回実行される．
第
章
はじめに
したがって，
つの順列の間では，
と
は高々 回しか繰り返されないので，合計
の計算時間は となる．これから，パス列挙アルゴリズム アルゴリズム F の
全体の計算時間は I となることが得られる．
もう少し改善することも可能である．実際，注意深く解析すれば計算時間は I
になることが得られる 演習問題 ．
しかし，それでもこのアルゴリズムは
が大きいときには膨大な計算時間になって
しまう．パスをすべて列挙する手法での問題点は，パス数が与えられた点数の指数関
数で増加する点にある．実際，
点でも I G @
E
A> 個
の異なるパスが存在し，全パスの列挙には現在の最速の計算機でも数年もかかってし
まうのである．したがって，すべてを列挙する方法では，中規模サイズのインスタン
スでも解くのは不可能であるといえる．
組合せ最適化の主題は，このような種類の問題に対して，よりよいアルゴリズムを
提供することであるといえる．そこでは，ある有限個の実行可能解から最良の解を求
めるという形で定式化できるものも多い 上記のドリル穴あけ問題の例では，実行可
能解集合は，すべてのパスあるいは順列の集合である．この集合は，上記のように，
明示的には列挙できないことが多いが，内在する問題の構造に暗に関係している．し
たがって，アルゴリズムでは問題に内在する構造を十分に利用することが必要である．
ドリル穴あけ問題 問題 F では，平面上の 個の点のインスタンスの全情報は，
個の座標値で与えられる．素朴なアルゴリズムでは I 個のすべてのパスを列挙し
ていたが，内在する構造を用いて 最適なパスを格段に高速に，たとえば の計算
時間で，求めてくるようなアルゴリズムも存在するかもしれない．なお，現在そのよ
うなアルゴリズムが存在するかどうかは未知である 第 章の成果からはそれはあり
得ないと思われている．それにもかかわらず，素朴なアルゴリズムより格段に高速な
アルゴリズムが実際に存在する しかしこれらのアルゴリズムの計算時間は などで
は抑えられない．
アルゴリズムの計算時間
アルゴリズムの形式的な定義をきちんと与えることもできる．実際， F 節で与え
ている．しかしながら，そのような形式に基づいたモデルでは，アルゴリズムが少し
複雑になるだけで，極めて長くて面白みのない退屈なものになってしまう．これは数
学の証明と似ているC 証明の概念はきちんと形式的に与えることもできるが，誰もそ
のような形式に基づいて証明を書いたりしない．そうすると，極めて長くなりほとん
ど誰も読み通せないものになってしまうからである．
したがって，本書ではアルゴリズムを形式から離れた記述で与えている．それでも
少し経験を積んだ読者なら，それらのアルゴリズムをそれほど困難なく実際に実装し
てどんな計算機でも走らせることができる程度に詳しく記している．
計算時間を評価する際定数倍の誤差は気にしないことにするので，現実の具体的な
計算モデルに限定されない議論ができる．初等的操作数を数えるが，初等的操作がい
アルゴリズムの計算時間
かなるものかについては，それほど厳密には述べようと思わない．簡単にいってしま
えば，本書での初等的操作とは，変数の割当，インデックスで指定された ポインター
で指された 変数への直接アクセス，(= O -*& O .# -# などの条件付きジャンプ，単
純な算術演算 数の加算，減算，乗算，除算，比較など などである．
アルゴリズムとは，正しい入力の集合と初等的操作の指令の系列からなり，正しい
入力に対してアルゴリズムの計算の過程がその初等的操作の有限系列で記述され，正
しい出力を出してくれるようなものである．通常，実行される初等的操作数が有限であ
ることでは満足できず，入力サイズに依存する初等的操作数のよい上界が要求される．
アルゴリズムの入力は，通常，数のリストで与えられる．これらの数がすべて整数な
らば， 進数表現 /(8 &&&--(# でコード化でき，整数 は "#. M ビット用いるだけで記憶できる．有理数は分子と分母をそれぞれ別にコード化して記
憶できる．有理数データからなるインスタンス 入力 に対して，入力サイズ (1(!& (!& はすべての数の 進数表現に必要なビット数と定義される．
定義
集合 の要素を入力として受け取るアルゴリズムを
とする．ある定数 が存在して，任意の入力 に対して
とし， C
がその計算を高々
(!& 回の初等的操作 算術演算を含めて 後に終了するならば，
間で走るという．このとき，
は 時
の計算時間 1(. -(&あるいは時間計算量 -(&
'#"&)(-8 は であるということも多い．
有理数入力に対するアルゴリズムは，ある整数 が存在して，入力サイズ
のどの入力に対しても， 時間で走りかつ計算の途中で生じる数もすべて 定義
ビットで記憶できるとき，多項式時間 #"8#(" -(& で走るという．
有理数とは限らない 任意の入力に対するアルゴリズムは，ある整数 が存在して，
個の数のどの入力に対しても 時間で走り，かつ有理数入力に対しても多項式
時間で走るとき，強多項式時間 -#."8 #"8#(" -(& で走るという． G の
ときは線形時間アルゴリズム "(&-(& ".#(-* という．
計算時間はサイズが同じでも入力によって異なることがあることに注意しよう パ
ス列挙アルゴリズム アルゴリズム F ではサイズが同じならば計算時間は同じ．本
書では，最悪計算時間，すなわち，入力サイズ
時間を とする関数 C
のすべての入力のうちで最大の計算
を考える．あるアルゴリズムに対しては， の増
加率がわからず上界のみわかるということもある．
最悪のケースが起こるのがまれなときは，最悪計算時間ではあまりに悲観的かもし
れない．確率モデルがきちんとしているときは平均計算時間も考えられているが，本
書では取り上げないことにする．
が各入力 C!
に対して !
を出力するアルゴリズムのとき，
は関数
を計算する '#1-& という．関数は，ある多項式時間アルゴリズムで
計算されるとき多項式時間で計算可能 '#1-/"& ( #"8#(" -(& と呼ばれる．
多項式時間アルゴリズムは，よい.## あるいは 効率的&Æ'(&- であるとも
呼ばれている．この概念は，#/* JEK と 5# JE K により導入された．
第
表
章
はじめに
様々な時間計算量をもつアルゴリズムの計算時間 単位のないものはすべて秒
@
@
E
@
F A
AA
@
A 時間
A
@ @
A
@
年
@ 時間
@E 年
@
日
年
@年
@ 年
E 時間
@ 年
日
@ 年
"#.
@
A
E
@
@
@ 日
@
@> 年
時間
> 年
A 年
>
I
年
年
年
@
年
@
@ 年
表 F は様々な時間計算量をもつアルゴリズムの仮想的な計算時間を示したものであ
るが，この概念が極めて的を射たものであることがこれからわかる．より具体的には，
I の初等的操
作数をもつアルゴリズムの計算時間を示しているL 回の初等的操作は ナノ秒で実行
できる したがって 秒間に 億回の初等的操作を実行できる と仮定している．な
お本書を通して "#. は底が の対数を表している．
表 F からわかるように，十分大きいサイズのインスタンス 入力 に対して多項式
時間アルゴリズムは圧倒的に速く走る．漸近的な計算時間 十分大きいサイズのイン
スタンスに対する計算時間 を考えるときは，中程度の大きさの定数係数はそれほど
入力サイズ
をパラメータにとり， "#. 問題にならないこともこの表からわかる．
表 F
は上記の つの仮想的なアルゴリズムに対して， 時間以内に解ける問題の
最大入力サイズを示している． では 回の初等的操作が ナノ秒で実行できると
きを，/ では 倍高速な計算機で実行する 回の初等的操作が F ナノ秒で実行
できる ときを示している．多項式時間アルゴリズムでは，現実的な時間でかなり大
線形の最適化問題
表
様々な時間計算量をもつアルゴリズムで 時間で解ける問題の最大入力サイズ は
回の初等的操作が ナノ秒で実行できるとき， は 回の初等的操作が # ナノ秒で実行
できるとき
"#.
I
E @AA
A>
/
A AE>@>
>A
きいサイズまで取り扱えるようになることがわかる．一方，多項式時間でない 指数
時間アルゴリズムでは， 倍計算機が高速化されても，解ける問題のサイズがほとん
ど増加しないのに対して，多項式時間アルゴリズムでは解ける問題のサイズがかなり
増加している．
強 多項式時間アルゴリズム，できれば線形時間アルゴリズム，が欲しいアルゴリ
ズムである．多項式時間アルゴリズムの存在しない問題も存在するし，アルゴリズム
の存在しない問題も存在する．たとえば，有限時間では解けるが多項式時間では解け
ない問題として，与えられた正規表現で定義される集合が空であるかどうかを決定す
る問題などが挙げられるL 詳細は *# 7#'#=- 0"" JE>K を参照されたい．
アルゴリズムも存在しないような問題としては，第 章の演習問題 で議論してい
る停止問題などがある．
しかしながら，本書で取り上げる問題はほとんどすべてが以下の つのクラスに属
する．第一のクラスの問題には多項式時間アルゴリズムが存在する．第二のクラスで
は，属するどの問題に対しても，多項式時間アルゴリズムが存在するかどうかはオー
プン 公開未解決 問題であるが，このクラスの問題の つにでも多項式時間アルゴリ
ズムが存在すれば，このクラスの他のすべての問題に多項式時間アルゴリズムが存在
することがいえる．第二のクラスの正確な定義とこの主張の正しいことの証明は第 章で与える．
ジョブ割当問題 問題 F
は第一のクラスに属し，ドリル穴あけ問題 問題 F は
第二のクラスに属する．
これら つのクラスの問題で本書は大きく つの部分に分けられている．最初の部
分では多項式時間アルゴリズムが既知の扱いやすい問題を取り上げている．その後，第
章から難しい問題を取り上げ議論している．多項式時間アルゴリズムは未知でも，
すべてを列挙して解を求めるよりもずっとよい方法も多数ある．さらに，ドリル穴あ
け問題 問題 F も含む 多くの問題に対して，最適解からあるパーセント程度しか
悪くならないような精度の保証された近似解を多項式時間で求めることもできる．
線形の最適化問題
次に，最初に与えた第二の例のジョブ割当問題 問題 F
について議論し，後の章
の中核となるいくつかのトピックスについても簡単に触れることにしよう．
第
章 はじめに
ジョブ割当問題 問題 F
は，自明でないような 各インスタンスに対して実行可
能解が無限個あるという点で，ドリル穴あけ問題 問題 F と大きく異なる．すべて
のジョブが完了する時刻を表す変数 を用いて問題を以下のように定式化できる ．
(
F-F
G F
すなわち，数 と集合 G が入力として与えられて，変数 と の
値を求める問題がジョブ割当問題である．このように線形の目的関数と線形の制約式
をもつ最適化問題は，線形計画問題 "(& #. と呼ばれる． F のすべての
実行可能解の集合は，多面体 #"8*&# と呼ばれるが，簡単に凸であることがわ
かる．さらに最適解が存在するときには，必ずこの集合の有限個の端点 頂点 のいず
れかで最適解となることが証明できる．したがって，線形計画問題は理論的にはすべ
ての端点解を列挙することで解けることになる．しかし，もっとよい方法があり，そ
れは後で眺めることにしよう．
線形計画問題を一般的に解くアルゴリズムがいくつか知られているが，そのような
一般的な手法は，問題に内在する構造を利用した特別なアルゴリズムと比べると，通
常効率的ではない．この例では，集合 G をグラフ .* でモデル化
すると好都合である．各ジョブ と各従業員 に対して，点あるいは頂点と呼ばれる
点を考え，従業員がこの仕事を担当できるとき すなわち のとき 従業員 と
ジョブ を辺で結ぶ．グラフは基本的な組合せ構造であり，多くの組合せ最適化問題
がグラフ理論を用いて極めて自然に定式化されている．
便宜上，どのジョブも処理時間は 時間であるとして， 時間以内でジョブを全部完了
できるかという問題を考える．これは，すべての と に対して であり，か
つ各 G に対して
となるような G ，各 G に対して を求める問題になる．そのような解が存在
すれば整数解，すなわちどの も か の解，も存在することがいえる．したがっ
て，各ジョブを 人の従業員に割り当て，かつどの従業員も 個以上ジョブが割り当
てられないように割り当てることと等価になる．グラフ理論の用語を用いると，すべ
てのジョブをカバーするマッチング -'*(. を求めることになる．最適なマッチ
ングを求める問題は，組合せ最適化問題の最もよく知られている問題の つである．
グラフ理論と線形計画法の基礎をそれぞれ第 章と第 @ 章で復習する．第 章で線
訳注
式
は制約式 のもとで を最小化せよ，という線形計画問題のよく用いら
れる定式化である．本書では，しばしばこの形式を用いる．
章を参照されたい．なお，
と
細は第
ときは
の代わりに
を用いる．
は
と
と書かれることも多い．詳
の省略形である．最大化の
ソーティング
形計画問題が多項式時間で解けることを証明し，第
章で整数多面体について議論す
る．その後の章で古典的な組合せ最適化問題をいくつか選び詳細に議論する．
ソーティング
ドリルで穴あけをしたい穴の箇所が 直線上 水平線上 に位置している特殊ケース
のドリル穴あけ問題 問題 F について考えて本章を終わることにしよう．この問題
では，各点 G は つの座標だけで与えられる．そのため，ドリル穴あ
け問題は簡単になる．点の座標で小さい順にソートし，ドリルを左から右に動かして
行くだけでよいことになる．ここでも I 個の順列があるが，最適なドリルパス，すな
わちソートされたリスト，を求めるのに，すべての順列を考えなくてもよいことは明
らかである．実際， 時間で
個の数を非減少順に簡単にソートする 並べる こ
とができる．
個の数を "#. 時間でソートするにはさらに少し工夫が必要である．これを
達成するアルゴリズムは多数知られているが，ここではよく知られているマージソー
トアルゴリズムを与えることにする．それは以下のように動作する．まず与えられた
個の数のリストをほぼ等しいサイズの つの部分リストに分割する ．次に，各部
分リストを同一のアルゴリズムを再帰的に用いてソートする．最後に，
つのソート
された部分リストをソートされた 本のリストにマージする．ここで利用されている
技法は，分割統治法 と呼ばれるもので，効率的アルゴリズム設計ではしばしば用い
られる手法である．>F 節で他の例も挙げている．
再帰的アルゴリズムについてはこれまで議論してこなかったが，実際には，任意の
再帰アルゴリズムを，計算時間を増加させることなく，再帰呼び出しをしない 通常
のアルゴリズムで書けるので，議論する必要がないともいえる．しかし再帰を用いて
記述し 実装し た方がずっと楽なアルゴリズムもあるので，本書ではその方が好都合
のときには再帰を用いることにする．
アルゴリズム
すべての G ．
で を満たす置換 C G CG とし終了する を返す．
CG
" CG
# CG
訳注
マージソートアルゴリズム &.&#- ".#(-*
個の実数のリスト ．
入力
出力
とする．
とする．
とする．
通して，
個の数のリストを 個の数のリストと 個の数のリストに分割する．本書を
は 以下の最大の整数， は 以上の最小の整数を表す．
与えられた
第
章 はじめに
CG $ CG とする．
かつ $ C
M $ CG " CG M とする
M $ CG M # $ $ CG $ M とする．
C M $ CG " CG M とする．
$ C M $ CG M # $ $ CG $ M とする．
例としてリスト E@
> @EE
A が与えられたとしよう．アルゴリズムはこ
のリストを E@
と > @EE
A の つの部分リストに分割し，各部分リスト
を再帰的にソートする．ソートされたリスト @
E と A@> EE のそれぞれ
に対応して置換 " G @ と # G @ が得られる．そしてこれらのリストが
以下のようにマージされる．
" G " G "
G @
"
G @
"@ G 定理
証明
# G # G # G # @ G # @ G # @ G # G @
G @
G @
G G G E
G A
G @
G @
G > G > G > G EE
CG >
CG @ CG CG @
CG CG > CG CG $ CG $ CG CG $ CG @
CG @
CG $ CG $ CG
マージソートアルゴリズムは "#. 時間で正しくソートする．
正当性は明らかである． 個の数からなる入力に対する計算時間 初等的操作数
を とする．すると， G であり，かつ G M M @ M となることがわかる 項 @ M の係数は初等的操作をどのように定義するかで変わっ
てくるが，本質的なことではない．
これから "#. M が得られることを主張したい．帰納法で証明する．
G のときは明らかに不等式が成立する． とし，すべての で不
等式が成立したと仮定する．すると，"#. @ かつ であるので，
"#.
M M "#.
MM@ M
@
@
G "#. M "#. @ M @ M A
@
"#. M @ M A "#. M が得られる．
¾
もちろんどんな全順序集合の要素のソーティングもこのアルゴリズムで実行できる．
演習問題
任意の つの要素の大小比較が定数時間で実行できれば計算時間も "#. であ
る．それでは，より高速な線形時間アルゴリズムは存在するだろうかH 比較でしか
つの要素の大小が判定できないと仮定する．このときは， 個の要素をソートする
のにどのアルゴリズムも最悪の場合少なくとも N "#. 回の比較を必要とするこ
とがいえる．実際，比較の結果を または と見なすことができるので，アルゴリ
ズムのすべての比較の結果は 文字列 と の系列 と見なせる．アルゴリズム
の入力における つの異なる置換は つの異なる 文字列を出力することに注意
しよう そうでないとするとアルゴリズムはそれらの置換を識別できないことになっ
てしまう． 個の要素の入力では I 個の可能な置換が存在するので， I 個の異なる
文字列が対応する計算結果となりうる． "#. より短い 文字列の個数は
G I となるので，比較に基づくソートアルゴリ
ズムの計算時間に対応する 文字列の最大の長さは， "#. G N "#. 以上に
なる．
上記の意味では，マージソートアルゴリズムの計算時間は定数倍の範囲内で最適で
あるといえる．しかしながら，整数の入力に対しては計算時間が入力サイズの線形と
なるアルゴリズムも知られている ただし入力の整数の最大桁数は定数と見なしてい
る．文字列の辞書式順ソートに対しても同様である．演習問題 > を参照されたい．
個の整数を "#. "#. 時間でソートするアルゴリズムも 7 J
K で提案されて
いる．
自明な線形の下界以外の 上記のような下界はごく限られた問題でしか得られてい
ない．線形でない下界を得るためには演算の集合に何らかの制限が必要なことも多い．
演習問題
F すべての
に対して
&
&
I&
&
であることを証明せよ．
ヒント すべての で M & であることを用いよ．
F "#. I G N "#. であることを証明せよ．
@F 任意の % で "#. G であることを証明せよ．
F パス列挙アルゴリズム アルゴリズム F の計算時間は Iであることを証
明せよ．
F 計算時間が N M
となるアルゴリズムが得られたとする．なお，
は入
力サイズで， は任意に選べる正のパラメータとする．このとき， を に応じ
て どのように選べば，計算時間が の関数として 増加率最小となるかH
F を長さがともに の 文字列とする．ある添え字 が存在
してすべての G で G でありかつ となるとき， は辞
書式順で より小さいという．長さ の 個の 文字列が与えられて，それら
第
章 はじめに
を辞書式順にソートする問題に対して線形時間のアルゴリズム 計算時間 のアルゴリズム が存在することを証明せよ．
ヒント まず最初のビットに関してソートしてグループ分けする．次に各グルー
プをソートする．
>F 自然数 のリストを線形時間でソートするアルゴリズム，すなわち，
G となる置換 を "#. MM
M"#. M
時間で求めるアルゴリズムを与えよ．
ヒント まず最初に符号化した 進数の長さでソートする．次に演習問題 のア
ルゴリズムを適用する．
注意 この演習問題と演習問題 で取り上げたアルゴリズムは基数ソートと呼ば
れている．
参考文献
一般文献N
>()F 4 J %KN +) : 0( I 6 //51F
./ % / /N $
引用文献N
)F 6F 8-:F 4F / 3F J $KN +) / 1 : 05
( ) //51F ./ $
0)F J %KN +) - -( /Æ-(1 : :(- -/ :
) % 0 : - &)/1 / ))1 : -- D ,58F
/F ?)58/F / %F 5#
4//F J %KN )F F / Q2 0/ ( : &)- $
%F 5%$
8F D J##KN - : / - (
: ) # ##F %R #
F J $#KN &)/( S / $#