シリーズ「現代人の数理」 巡回セールスマン問題への招待

山本 芳嗣/久保 幹雄【著】

朝倉書店（1997/02発売）

• サイズ A5判／ページ数 174p／高さ 22cm
• 商品コード 9784254126150
• NDC分類 417
• Cコード C3341

出版社内容情報

対話形式と100枚の魅力的な図を用いて，組合せ最適化問題の女王である本テーマについて初学者・実務家向けに解説。〔内容〕巡回セールスマン問題の歴史／計算量の理論とNP完全問題／精度保証のある近似算法／近似算法／最適巡回路を求めて

【目次】
1.　どないしたんや
2.　巡回セールスマン問題の歴史
3.　計算量の理論とNP-完全問題
4.　精度保証のある近似算法
5.　近似算法―精度保証にはこだわらない―
6.　最適巡回路を求めて―割当問題を用いて―
7.　最適巡回路を求めて―対称な問題―
8.　最適巡回路を求めて―branch and cut―
9.　歴史の時間
10.　欄外ゼミナール
11.　索　引

内容説明

本書は、巡回セールスマン問題（Ｔｒａｖｅｌｉｎｇ　Ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ）という１つの問題をめぐるお話です。この壮大な展開をみせる１つの問題に対する、ほんの入り口を紹介するものです。

目次

どないしたんや
巡回セールスマン問題の歴史
計算量の理論とＮＰ‐完全問題
精度保証のある近似算法
近似算法―精度保証にはこだわらない
最適巡回路を求めて（割当問題を用いて；対称な問題；ｂｒａｎｃｈ　ａｎｄ　ｃｕｔ）

感想・レビュー

※以下の感想・レビューは、株式会社ドワンゴの提供する「読書メーター」によるものです。

[Phi-san☭]

TSPとは何かという導入から、有名な近似解法の紹介や解説が載っており、丁寧に「招待」していたと思う。大まかな流れや、どんなアルゴリズムがあるのか掴んでおきたい人におすすめ。但し部分部分で厳密な理論や証明を省いているところがあった。

2013/03/06