パズルで鍛えるアルゴリズム力
- 大槻兼資 著
- 定価
- 2,948円（本体2,680円＋税10%）
- 発売日
- 2022.4.20 2022.4.15
- 判型
- A5
- 頁数
- 288ページ
- ISBN
- 978-4-297-12679-7 978-4-297-12680-3
サポート情報
概要
さまざまな問題を解決するためには、適切なアルゴリズムを判断したり、ときには自分で生み出したりできる力が必要です。そして、自在に使いこなせるようになるためには、知識をためるだけではなく実践してみることも大切です。
本書では、「テンパズル」「数独」「4×4オセロ」といったさまざまなパズルのソルバーを実装することで、楽しく効率的にアルゴリズムの設計力が磨けます。各アルゴリズムの概要は、図解でしっかり解説。数学的解法といった発展的な内容も盛り込みました。競技プログラミングに挑戦したい方の第一歩としてもお勧めの1冊です。
こんな方にオススメ
- 楽しくアルゴリズムを学びたい人
- 競技プログラミングに興味がある人
目次
第1章 アルゴリズム入門
- 1-1 テンパズル 〜力まかせ探索
- テンパズル
- パズルに挑戦
- テンパズルを解くアルゴリズム
- コラム スタックとキュー Part 1
- コラム コンピュータの計算力
- テンパズルソルバーの実装
- テンパズルの掘り下げ
- まとめ
- パズルの解答
- コラム アルゴリズムとプログラムの違い
- もう一歩 トランプゲーム「四則」
- 1-2 小町算 〜再帰関数
- 小町算
- 手で解いてみる
- 小町算を解くアルゴリズム
- コラム 再帰呼び出しの効率化
- 小町算ソルバーの実装
- まとめ
- もう一歩 小町算の問題を作る
- 1-3 虫食算 〜枝刈り
- 虫食算
- パズルに挑戦
- 虫食算を解くアルゴリズム
- 枝刈り
- コラム 組合せ爆発
- 虫食算ソルバーの部品の準備
- 虫食算ソルバーの実装
- まとめ
- パズルの解答
- もう一歩 虫食算を作る
第2章 グラフアルゴリズム
- 2-1 数独 〜深さ優先探索1
- 数独
- 数独の手筋の紹介
- グラフ
- コラム ケーニヒスベルクの橋と四色問題
- 数独を解くアルゴリズム
- 数独ソルバーの部品の準備
- 数独ソルバーの実装
- 高速化のための工夫
- まとめ
- パズルの解答
- コラム 数独の最小ヒント数は17
- もう一歩 数独を作る 〜山登り法
- 2-2 覆面算 〜深さ優先探索2
- 覆面算
- コラム パズルの巨匠紹介 Part 1：デュードニー
- パズルに挑戦
- コラム 言葉パズルで覆面算を作る！
- 覆面算ソルバーの実装
- 覆面算を作るアルゴリズム
- リストアップ法による覆面算メイカーの実装
- ワイルドカード法による覆面算メイカーの実装
- まとめ
- パズルの解答
- もう一歩 虫食算と覆面算の融合！
- 2-3 迷路 〜幅優先探索
- 迷路
- コラム パズルとは何か
- 迷路に関連するパズル
- 今回解く問題の設定
- 迷路ソルバーの実装
- コラム サム・ロイドの『ハンモック・パズル』
- グラフ上の幅優先探索
- コラム スタックとキュー Part 2
- 油分け算への応用
- まとめ
- パズルの解答
- もう一歩 碁石拾い
第3章 発展的なアルゴリズム
- 3-1 15パズル 〜反復深化A*
- 15パズル
- コラム サム・ロイドの『14-15パズル』
- 手で解いてみる
- コラム 一般サイズの15パズル
- 15パズルソルバーの方針
- 反復深化深さ優先探索
- 反復深化A*
- 15パズルソルバーの実装
- まとめ
- コラム ルービックキューブのGod's Number
- 3-2 4×4オセロ 〜ゲーム探索
- 4×4オセロ
- 「ゲームを解く」ということ
- 各ゲームの解析状況
- 手で解いてみる
- ゲーム解析をグラフ探索で考える
- ゲーム探索の実装
- 4×4オセロソルバーの実装
- まとめ
- 3-3 編集距離 〜動的計画法
- 編集距離
- パズルに挑戦
- コラム 編集距離の実応用
- 編集距離をグラフで表す
- 動的計画法
- 編集距離ソルバーの実装
- コラム アルゴリズムの計算量
- まとめ
- パズルの解答
- コラム ダイクストラ法
- 3-4 ドミノタイリング 〜マッチング
- ドミノタイリング
- コラム パズルの巨匠紹介 Part 2：ロイド
- 手で解いてみる
- コラム テトロミノ
- 二部マッチング問題への帰着
- 二部マッチング問題の解法
- ドミノタイリングソルバーの実装
- まとめ
プロフィール
大槻兼資
1988年生まれ。2014年東京大学大学院情報理工学系研究科修士課程修了。修士（情報理工学）。現在、株式会社NTTデータ数理システム顧問、株式会社アルゴ式執行役員（共同創業）。アルゴリズムをはじめとしたコンピュータサイエンスの諸分野の啓蒙活動に従事。「けんちょん」の愛称で親しまれている。
著書に『問題解決力を鍛える!アルゴリズムとデータ構造』（講談社、2020）がある。数理最適化や機械学習を活用した数理コンサルティング業務の経験も多数。趣味は競技プログラミング、虫食算作り、ボルダリング、国内旅行など。
著者の一言
パズルは、論理的思考と試行錯誤によって楽しく解くことを目的とした問題のことです。頭を使う娯楽として、古くから世界中で親しまれてきました。じっくり考えることで少しずつ問題の構造が見えていき、最後にこれしかないという答えに到達するおもしろさ。じっくり考えてもなかなか答えが見つからず、それでも諦めずに考え続けることで閃く瞬間が訪れる喜び。パズルは、そんな楽しい時間と心地よい達成感を私たちにもたらしてくれます。
一方、アルゴリズムは問題を解くための手順のことです。世の中には、アルゴリズムの力で解決されている問題が数多くあります。カーナビは「現在地から目的地へと至る経路を求める」という問題を解いていますし、diffコマンドは「与えられた2つの文書の差分を求める」という問題を解いています。アルゴリズムのもつ優れた特徴として、解きたい問題において想定されるどのようなケースに対しても「同じ方法で」答えを導けることが挙げられます。数独を解くアルゴリズムを正しく実装すれば、どんな数独の問題を入力しても答えを出力するソルバーとなるのです。
本書では、パズルのソルバーを作ることをとおして、アルゴリズムを考える力を楽しく鍛えます。各節の冒頭では、さまざまなパズルを紹介します。まずは実際に手を動かして、それらのパズルを楽しく考察してみましょう。虫食算、数独、オセロなど、古くから広く親しまれてきたパズルは、ただ楽しいだけではなく、アルゴリズムを考える力を鍛えるのに役立つ要素を多く含んでいます。たとえば数独を解くとき、「このマスにはこの数字は入らない」「この数字はこのマスには入らない」といった考え方を活用する方は多いでしょう。これらの考え方は、アルゴリズムの世界では「探索の枝刈り」ともとらえられます。このことからもわかるように、パズルを考察して、ソルバーを実装していくうちに、アルゴリズム的思考力も自然に体得できるのです。
本書に掲載するソルバーは、パズルを解くのに必要最小限の機能のみを備えたものです。より高速化したり、機能を追加したり、例外処理を加えたりなど、工夫の余地が大いにあります。ぜひこれらのソルバーを改良して、読者のオリジナルのソルバーを作ってみてください。