• 検索結果がありません。

【書評】組合せ最適化（茨木俊秀 著）

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "【書評】組合せ最適化（茨木俊秀 著）"

Copied!
1
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 1 ページ )

全文

(1)

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ・ 1111111111111111 ・ 11 1I 11 1t1l 111111111111111111111 1T1 1111111111111111111111111111111 f1 111111 講座数理計画法 8

回回

組合せ最適化一分枝限定法を中心として一

茨木俊秀著 B5 版 211 頁産業図書 1983年発行 3400 門 1 lU IJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII Il llllllllllllllllllllllllllllllllllll 1ll 11111 l1 111111111111111111111111111111111111111111111111111111111111111111111111111111 ・ 1111111111111111111111111111 “"“"“"“ 111111111111111111111 組合せ最適化問題のなかには，線形計画，整数計画， 越テストなどの強さが計算効果に与える影響を知り，探 グラフ，ネットワーク，最適配置，スケジューリング間 索関数のもつ特性を熟知しなければならないが，ここで 題などがあり，この講座でも他の成書で扱われているも は行商人問題など， \，、くつかの具体的な問題に対し，そ のもある.これらの問題のうちで解〈のがむずかしい組 の適用例を示している. 合せ問題に対して適用されるのが分校限定法である.こ 4 章では，計算効率の良い分校限定法のアルゴリズム の本でその基本的な考え方が理論的に述べられるととも とはという観点から，経験的に得られている性質につい に，実用化に際してのポイントがていねいに解説されて て述べる.計算目標，コンピュータ性能，プログラムの いる.本書の構成は以下のようになっている. 容易さなどによって評価は変わるが，シミュレーンヨン 1 章組合せ最適化問題とその複雑さ を使って種々の探索法の特性を比較検討している. 2 章 分校限定法の基本構造 5 章では，同じく計算効率について，理論的に，下界 3 章 " 構成例 値関数，上界値関数，優越関係および発見的関数をどの 4 章 5 章

"

η 特性と評価 ように設計すべきかを述べている. 挙動の理論的評価 6 章では，動的計画法との関連を解説している. 6 章動的計画法と分校限定法 最適性の原理が成立する問題について最適方策を効率 7 章分校限定法による近似最適解の計算 よく求めるのが DP であるが，これは下界値テストをや 8 章分校限定アルゴリズムの実現 めて幅優先探索法を用いる分校限界法でもある.よって 分校限定法を有効に生かすためには，問題の特殊性を 両者の聞には計算効率という点からみて少し差があるか 考慮した工夫が必要であるが，整数計画法をはじめとし もしれないが，本質的には同じであること. て多くの場合，現在，実用に耐えうる唯一の手法である 7 章では，分校限定法で近似最適解を求める計算法を から，十分に検討に値するものではないかと思われる. 種々検討している.厳密な最適解でなくても，適当な近 1 章では，組合せ最適化問題の一般的な定義を与え，い 似解が得られればそれで・十分である場合は多いが，むず くつかの具体例が扱われている.このなかには簡単に解 かしい大規模な問題でも実用的に解けるようにするため けるものからむずかしいものまでいろいろあるが，ある の工夫が述べられている. 問題がむずかしいことを証明するのに有効な NP 完全性 8 章では，分校限定法のプログラム開発に際し，部分 の概念を述べ，どれが NP 完全問題なのか，そのリスト 問題のデータ処理，探索に要するデータ処理をどうする を与えている. かを説明している.プログラム化に際して参考となろ 2 章では，主に NP 完全問題に代表されるようなむず う.さらに，並列コンピュータを使った分校限定法の並 かしい問題を解くための技法としての分校限定法につい 列化についても論文が示されている. て，その基本的な考え方を説明し，アルゴリズムとして の一般的手順をフローチャートにまとめる.そのなかで どの活性節点を探索の候補にするかについて，実際に利 用される探索法の特質を述べる.さらに，分校限定法の 歴史が体系的にまとめられている. 3 章では，代表的な組合せ最適化問題について，分校 限定法による解き方を示している.実際にコンピュータ で問題を解くためには，それぞれの下界値や上界値，優

6

3

2

(56) 以上，各章にはそれぞれのまとめと背景となる文献が あげられている.分校限定法を詳しく論じた最初の成書 であり，組合せ最適化問題を扱う向きには理論と実際の 両分野の人身にとって，アルゴリズム設計の際のガイド ブックとなろう.一読をおすすめしたい. (前野拓也東亜燃料) オペレーションズ・リ+ーチ © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

参照

今ダウンロードする ( PDF - 1 ページ - 74.33 KB )

関連したドキュメント

不確実性を考慮した最適化手法

ü  modeling strategies and solution methods for optimization problems that are defined by uncertain inputs.. ü  proposed by Ben-Tal & Nemirovski

組合せ最適化における双対性

Max-flow min-cut theorem and faster algorithms in a circular disk failure model, INFOCOM 2014...

組合せ最適化問題に対する 多面体的手法とその発展

Hungarian Method Kuhn (1955) based on works of K ő nig and

組合せ最適化に対する代数的厳密アルゴリズム

of IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pp..

代数的組合せ最適化 part III

最大消滅部分空間問題 MVSP Maximum Vanishing Subspace Problem.. MVSP:

オンライン最適化の競合比解析

参考文献 Niv Buchbinder and Joseph (Seffi) Naor: The Design of Com- petitive Online Algorithms via a Primal-Dual Approach. Foundations and Trends® in Theoretical Computer

安定マッチングと 組合せ最適化

"A matroid generalization of the stable matching polytope." International Conference on Integer Programming and Combinatorial Optimization (IPCO 2001). "An extension of

田中 輝雄 広島市立大学

ポートフォリオ最適化問題の改良代理制約法による対話型解法 仲川 勇二 関西大学 * 伊佐田 百合子 関西学院大学 井垣 伸子