チューリング賞、京都賞などを受賞しているドナルド?E?クヌース先生による有名な教科書The Art of Computer Programmingシリーズの五冊目となる第4B巻の日本語訳です。

既刊の第4A巻とともに「第7章 組合せ探索」の一部となる内容が含まれています。

名誉教授　田村直之

「組合せアルゴリズムは、私たちを多数の場合を含む問題に対処させる方法である。そういう技術の知識の爆発的な増加は、その記述に数巻の書を必要とする。… 本書はそのシリーズの2番手であり、第4A 巻の後継である。」(本書「序」より)。

この巻では、組合せアルゴリズムの重要な部分となる「バックトラック」を解説します。バックトラックの概論に続いて、厳密被覆問題などの解決に有効な手法となる「ダンシングリンク」を取り上げます。後半では、計算機科学の全分野で基本的な問題の1つとなる「充足可能性(Satisfiability：SAT)」について詳解します。バックトラックアルゴリズムを理解するために必要となる確率論の概論について、「数学的準備拾遺」が特別に用意されています。 この巻には1,000問を超える演習問題があり、アルゴリズムの本格的な理解に役立てることができるでしょう。

KADOKAWA　書籍紹介より

目次

• 数学的準備拾遺
• 第7章 組合せ探索
  • 7.2. すべての可能性の生成
  • 7.2.2. Backtrack Programming
  • 7.2.2.1. ダンシングリンクス
  • 7.2.2.2. 充足可能性(Satisfiability)
• 演習問題の解答
• 付録A 数表
• 付録B 表記法索引
• 付録C アルゴリズムと定理の索引
• 付録D 組合せ問題の索引
• 付録E 解答のパズルの解