たのしい探索アルゴリズムの世界【後編：探索手法で実社会の様々な問題を斬る！】

# 目次

* [たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】](https://qiita.com/e869120/items/25cb52ba47be0fd418d6)

からの続きです！

### [前編](https://qiita.com/e869120/items/25cb52ba47be0fd418d6)
| 章 | タイトル | 備考 |
|:----------|:-----------|:------------|
| 0. | [はじめに](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#0-はじめに) |        |
| 1. | [探索アルゴリズムとは](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#1-探索アルゴリズムとは) | ここからサポートしていきます |
| 2. | [すべての基本、全探索](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#2-すべての基本全探索) |  |
| 3. | [種々の全探索　～bit全探索、順列全探索など～](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-種々の全探索bit全探索順列全探索など) | 2 章より複雑な構造を扱います |
| 4. | [効率的な探索手法　～二分探索と三分探索～](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#4-効率的な探索手法二分探索と三分探索) |  |
| 5. | [はやい探索法　～半分全列挙～](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#5-はやい探索法半分全列挙) |  |
| 6. | [意外と強い、枝刈り全探索](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#6-意外と強い枝刈り全探索) |  |

### 後編
| 章 | タイトル | 備考 |
|:----------|:-----------|:------------|
| 7. | [「おねえさん問題」で役立つ、全探索](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#7-おねえさん問題で役立つ全探索) | 後編では探索が役立つ事例を紹介します |
| 8. | [「高次方程式の解の発見」で役立つ、二分法](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#8-高次方程式の解の発見に役立つ二分法) |  |
| 9. | [「15パズル」で役立つ、半分全列挙と枝刈り全探索](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#9-15-パズルで役立つ半分全列挙と枝刈り探索) |  |
| 10. | [更なる探索アルゴリズムの奥深さ](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#10-更なる探索アルゴリズムの奥深さ) |  |
| 11. | [おわりに](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#11-おわりに) |  |

<br />

# 7. 「おねえさん問題」で役立つ、全探索
[1 章](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#1-探索アルゴリズムとは)では、以下の問題を紹介しました。（俗に「お姉さん問題」[^1]といわれるものです）

> $N \times N$ の碁盤目状道路がある。左上座標を $(0, 0)$、右下座標を $(N, N)$ とするとき、左上の座標から右下の座標まで、同じ交差点を通らずに行くような方法は何通りあるか。

例えば、$N = 2$ の場合は $12$ 通りの行き方しか存在しません。
![1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/486cf631-8439-f5cc-49b3-7bb27547990d.png)
一方で、$N \geq 3$ のとき答えは次表のようになり、$N$ が $1$ 増えたら一気に答えが大きくなる、「組合せ爆発」の有名問題として知られています。[^2]

| $N$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 答え | $2$ | $12$ | $184$ | $8512$ | $1262816$ | $575780564$ |

## 7-1. 単純な全探索だと上手くいかない
さて、この問題の答えをどのようにして求めるのでしょうか。できれば $5 \times 5$ くらいまでは数秒で計算したいですが、複雑な構造を扱うため、単純な for 文ループでの全探索をすると、ループが $20$ 重あるいは $30$ 重以上になってしまい、実装が大変なことになってしまいます。

また、どのような行き方をしても、「上下左右の交差点に移動する回数」は高々 $(N+1)^2$ 回です。例えば下のような場合は $(N+1)^2$ 回になります。
![31.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/982dd4c2-2eff-458f-a2f5-7db30c20aefb.png)
そこで、[3-5. 節](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-5-bit-全探索の拡張)で扱ったような $3$ 進数以上の bit 全探索を利用して、最大 $(N + 1)^2$ 回の移動の方向を全探索することもできます。しかし、$4$ 方向に移動できるので、計算量が $O(4^{(N + 1) \times (N + 1)})$ などといった莫大なものになります。したがって、$N = 4$ の場合ですら数秒で計算できません。

## 7-2. ここで役立つ「再帰関数による全探索」
ここで役立つのが [3-3. 節](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-3-再帰関数を用いた全探索)で紹介した「再帰関数を用いた全探索」です。

* 今どの交差点にいるかの情報 $(px, py)$
* 既にどの交差点を通ったかの情報 $S$

という 2 つの状態を管理しながら再帰関数で処理を行うことを考えます。（$S$ の情報は struct などで型や構造体を予め作っておくと実装が楽です）

既に通ったことのある交差点は次通ることができないので、例えば $N=2$ で以下の図のような状態の場合、次のように $2$ 通りの遷移ができます。
![22.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/86f260fa-be95-5873-839f-84cbadd79d59.png)

したがって、以下のように実装できます。ここでは <code>dfs</code> が扱う再帰関数です。

~~~cpp
#include <iostream>
using namespace std;

struct State {
	bool used[7][7];
};

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int dfs(int N, int px, int py, State S) {
	if (px == N && py == N) return 1;

	int sum = 0;
	for (int i = 0; i < 4; i++) {
		// 次通る交差点を (sx, sy) とする
		int sx = px + dx[i];
		int sy = py + dy[i];
		if (sx < 0 || sy < 0 || sx > N || sy > N) continue;
		if (S.used[sx][sy] == true) continue;

		State NextState = S; NextState.used[sx][sy] = true;
		sum += dfs(N, sx, sy, NextState);
	}
	return sum;
}

int main() {
	// 入力
	int N; cin >> N;

	// 初期化
	State InitS;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) InitS.used[i][j] = false;
	}
	InitS.used[0][0] = true;

	// 答えを求める
	cout << dfs(N, 0, 0, InitS) << endl;
	return 0;
}
~~~

計算には次表の通りの時間がかかりました。再帰関数による全探索（深さ優先探索）は意外と無駄が少なく、最大でも答えの数十倍程度の状態数しか探索していないことがわかります。$N = 5$ でも **0.4秒以内**で計算できており、とても高速です。

| N | 通り数（答え） | 探索した状態数 | 計算時間 |
|:---:|:---:|:---:|:---:|
| 2 | 12 通り | 51 個 | 0.023 ミリ秒 |
| 3 | 184 通り | 1271 個 | 0.066 ミリ秒 |
| 4 | 8512 通り | 90111 個 | 2.142 ミリ秒 |
| 5 | 1262816 通り | 18470411 個 | 309.507 ミリ秒 |

---

補足ですが、現在の最新技術を使えば $N = 16$ でもわずか数分で計算することができます。[ZDDのアルゴリズム](https://www.slideshare.net/reew2n/zdd-51678560)という効率的な数え上げ手法があるので、興味ある方は是非調べてみてください。また、2013 年に $25 \times 25$ の結果が計算され、世界記録が塗り替えられているように、現在も記録更新が続いている面白い問題です。詳しくは以下の参考文献をお読みください。[^3]

* [岩下 洋哲、フカシギおねえさん問題の高速計算アルゴリズム](http://www.edu.kobe-u.ac.jp/istc-tamlab/cspsat/pdf-open/cspsat2_mtg203_iwashita.pdf)

<br />

# 8. 「高次方程式の解の発見」に役立つ、二分法
一次方程式 $ax+b = 0$ の解は、

$$x = -\frac{b}{a}$$

となります。また、二次方程式 $ax^{2} + bx + c$ の解は、

$$x = \frac{-b-\sqrt{b^2-4ac}}{2a}, \frac{-b+\sqrt{b^2-4ac}}{2a}$$

となります。しかし三次方程式以上になると求めるのが難しくなり、特に五次方程式以上であれば解の公式が存在しません。したがって、[数値解析的](https://ja.wikipedia.org/wiki/%E6%95%B0%E5%80%A4%E8%A7%A3%E6%9E%90)に解く必要があります。しかし、本記事で紹介した**二分探索**というアルゴリズムを用いると、$N$ 次方程式を $O(N^3 \log 精度の逆数)$ などの高速な計算量で求めることができます。まずは三次方程式から考え、次に一般の $N$ 次方程式の場合に解いてみましょう。


## 8-1. 三次方程式の解を求める
三次方程式 $ax^3 + bx^2 + cx + d = 0$ を解くことを考えましょう。
まず、三次関数 $f(x) = ax^3 + bx^2 + cx + d$ は以下の性質を持ちます。

* [極値](https://mathtrain.jp/kyokuchi)を高々 $2$ つ持つ。
* 極値と極値の間は、単調増加あるいは単調減少である。

例えば、$y=x^3+x$ と $y=x^3-x$ のグラフは、以下の図の通り条件を満たします。（高校数学が分からない方へ：「極値」は下図のように「山の頂上」「谷の底」のような形をする場所です。）
![23.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/703b34b7-f265-df89-2a25-73ca392aa758.png)

そこで、以下の 2 パターンに場合分けしてみましょう。

#### パターン 1. 極値をもたない場合
極値をもたない場合、 $f(x)$ は単調増加か単調減少です。したがって、[4-2. 節]()で扱った「二分法」を利用すれば解くことができます。例として、方程式 $x^3+x-1=0$ の解を求めることを考えます。$0 \leq x \leq 1$ に解があることは簡単にわかるので、以下のようにして解けます。（ここでは、$f(x) = x^3+x-1$ とします）

| 現在分かっている $x$ の範囲 | 行う計算 | 計算結果 |
|:---:|:---:|:---:|
| $0.0000 \leq x \leq 1.0000$ | $f(0.5000) \leq 0$ か？ | 正しい（$f(0.5000) \fallingdotseq -0.38$） |
| $0.5000 \leq x \leq 1.0000$ | $f(0.7500) \leq 0$ か？ | 間違い（$f(0.7500) \fallingdotseq 0.17$） |
| $0.5000 \leq x \leq 0.7500$ | $f(0.6250) \leq 0$ か？ | 正しい（$f(0.6250) \fallingdotseq -0.13$） |
| $0.6250 \leq x \leq 0.7500$ | $f(0.6875) \leq 0$ か？ | 間違い（$f(0.6875) \fallingdotseq 0.01$） |
| $0.6250 \leq x \leq 0.6875$ | $f(0.6563) \leq 0$ か？ | 正しい（$f(0.6563) \fallingdotseq -0.06$） |

上の表は $f(x)$ 単調増加の場合の例ですが、$f(x)$ が単調減少の場合も逆のことをすれば、計算量 $O(\log_2 精度の逆数)$ で解くことができます。

#### パターン 2. 極値をもつ場合
極値 $x=a_1, a_2$ で持つとしましょう。$x^3$ の項が正だと仮定するとき、

* $-\infty \leq x \leq a_1$ の区間では<font color="red">**単調増加**</font>
* $a_1 \leq x \leq a_2$ の区間では<font color="blue">**単調減少**</font>
* $a_2 \leq x \leq +\infty$ の区間では<font color="red">**単調増加**</font>

となります。したがって、3 つの区間それぞれについて、パターン 1 と同様に**二分法**のアイデアを使って解を求めることができます。ただし、3 つのうち 1 つか 2 つの区間に解が存在しない場合があることに注意してください。（例えば中央の区間について、$f(a_1)$ と $f(a_2)$ の間に $0$ が存在しなければ、$a_1 \leq x \leq a_2$ を満たす解が存在しないといえます）

なお、極値は $f(x)$ を[微分](https://sci-pursuit.com/math/differential-1.html)することで求めることができます。一般に、三次関数 $f(x) = ax^3 + bx^2 + cx + d$ の極値となる $x$ の値は、

$$3ax^2 + 2bx + c = 0$$

の解であるため、[解の公式](https://ja.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E6%96%B9%E7%A8%8B%E5%BC%8F%E3%81%AE%E8%A7%A3%E3%81%AE%E5%85%AC%E5%BC%8F)などを用いて二次方程式を解けば、極値を求めることができます。

## 8-2. 四次以上の方程式の解を求める
次に、$n$ 次多項式 

$$a_nx^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_0 = 0$$

の解を求めることを考えましょう。

$$f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_{0}$$

とするとき、$n$ 次関数 $f(x)$ が $x = a_1, a_2, ..., a_t$ で極値を取るとします。そのとき、以下の性質が必ず成り立ちます。

* $-\infty \leq x \leq a_1$ の区間では<font color="red">**単調増加**</font> または <font color="blue">**単調減少**</font>
* $a_1 \leq x \leq a_2$ の区間では<font color="blue">**単調減少**</font> または <font color="red">**単調増加**</font>
* $a_2 \leq x \leq a_3$ の区間では<font color="red">**単調増加**</font> または <font color="blue">**単調減少**</font>

:

* $a_t \leq x \leq +\infty$ の区間では<font color="red">**単調増加**</font> または <font color="blue">**単調減少**</font>

したがって、$n$ 次関数は単調増加または単調減少である $t+1$ 個の区間に分けることができます。$t < n$ なので、区間の数は最大でも $n$ 個です。単調減少あるいは単調増加の区間に対して問題を解くためには、三次方程式の場合と同様に**二分法**を使えば良いので、$O(nt \times \log 精度の逆数)$ といった計算量で解けます。

最後に、極値はどのようにして求めることができるのでしょうか。一般に、$n$ 次関数

$$f(x) \ = \ a_{n}x^{n} \ + \ a_{n-1}x^{n-1} \ + \ ... \ + \ a_{1}x \ + \ a_{0}$$

の極値は、$n-1$ 次方程式

$$na_nx^{n-1} \ + \ (n-1)a_{n-1}x^{n-2} \ + \ ... \ + \ 2a_{2}x \ + \ a_{1} \ = \ 0$$

の解となります。（$f(x)$ を微分すると導出できます）
したがって、$n$ 次方程式は $n-1$ 次方程式に帰着させることができました。

---

#### n-1 次方程式に帰着させると…
* $n$ 次方程式は $n-1$ 次方程式に帰着でき、
* $n-1$ 次方程式は $n-2$ 次方程式に帰着でき、
* $n-2$ 次方程式は $n-3$ 次方程式に帰着でき、…　（以下省略）

となっていくため、最終的には $1$ 次方程式の解を求めることになります。精度の逆数を $A$ とすると、計算量は以下のようになります。

* $n$ 次方程式を $n-1$ 次方程式に帰着するのに、$O(n^2 \times \log A)$ かかる
* $n-1$ 次方程式を $n-2$ 次方程式に帰着するのに、$O(n(n-1) \times \log A)$ かかる
* $n-2$ 次方程式を $n-3$ 次方程式に帰着するのに、$O(n(n-2) \times \log A)$ かかる　…（以下省略）

したがって、合計計算量は以下の通りとなり、$n = 100$ 程度でも数秒で解けます。
$$O(n^2 \times \log A) + O(n(n-1) \times \log A) + ... + O(2n \times \log A) = O(n^3 \times \log A)$$
実装例は次の通りです。（<code>solve</code> は $|A|-1$ 次多項式 $A_{|A|-1}x^{|A|-1}+A_{|A|-2}x^{|A|-2}+...+A_{0}$ を入力し、解となる $x$ を返す関数です）

~~~cpp
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

double getvalue(vector<double> A, double x) {
	// f(x) の値を求める
	double rem = 0;
	for (int i = 0; i < A.size(); i++) rem += 1.0 * A[i] * pow(x, 1.0 * i);
	return rem;
}

vector<double> solve(vector<double> A) {
	// 1 次方程式の場合
	if (A.size() == 2) {
		if (A[1] == 0) return vector<double>{};
		return vector<double>{-1.0 * A[0] / A[1]};
	}

	// A を微分して極値 {K1, K2, ..., KT} を得る
	vector<double> B(A.size() - 1, 0);
	for (int i = 0; i < B.size(); i++) B[i] = 1.0 * (i + 1) * A[i + 1];
	vector<double> K = solve(B);

	// 各区間に対して二分法をする
	vector<double> ret;
	for (int i = 0; i <= K.size(); i++) {
		double cl = -100000; if (i >= 1) cl = K[i - 1];
		double cr = 100000; if (i < K.size()) cr = K[i];
		double val1 = getvalue(A, cl), val2 = getvalue(A, cr);
		bool flag = false;
		if (val1 > val2) { val1 *= -1.0; val2 *= -1.0; flag = true; }
		if (val2 < 0.0 || 0.0 < val1) continue;

		double cm;
		for (int j = 0; j < 60; j++) {
			cm = (cl + cr) / 2.0;
			double val = getvalue(A, cm); if (flag == true) val *= -1.0;
			if (val < 0) { cl = cm; }
			else { cr = cm; }
		}
		ret.push_back(cm);
	}
	return ret;
}
~~~

<br />

# 9. 「15 パズル」で役立つ、半分全列挙と枝刈り探索
最後に紹介する例は「15 パズル」です。
皆さん、「15 パズル」というパズルをご存知でしょうか。
![24.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/92e0258d-29be-2d31-d7da-555c1550678f.png)
そこで、ある 15 パズルの盤面が与えられたときに、最短手数を求めるためにはどうすれば良いのでしょうか。

## 9-1. 基本手法 - 全探索
ある状態からスライドさせる（1 手動かす）方法が何通りあるか考えましょう。空マスの上下左右に隣接するピースの個数なので、高々 **4 通り** です。例えば、以下の場面だと $4$ 通りの手を打つことができます。
![25.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/c51158f4-b5b9-5044-86c3-77fddff31467.png)
したがって、全探索をする場合、考える最大手数を $A$ としたとき $4^A$ 通り探索する必要があります。したがって、$10$ 手以内までなら解けます。プログラムの実装は、

* [3-3. 節で紹介した、再帰関数を用いた全探索](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-3-再帰関数を用いた全探索)
* [3-5. 節で紹介した、bit 全探索の拡張](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-5-bit-全探索の拡張)

のいずれかを利用すると、書くことができます。また、以下の図のように「直前の手と逆の向きに動かすのは無駄である」という発想に気づけば、$O(4 \times 3^{A-1})$ 通りに絞ることができ、$15$ 手以内までなら解けます。実際は、近傍が $2$ つや $3$ つのマス（角など）があるので、$20$～$25$ 手くらいまでなら数秒以内で解けます。
![26.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/688979e5-d2c1-6d3a-56de-7ab76c416d4a.png)

## 9-2. 半分全列挙を用いた解法
しかし、このままだと **20-25 手**までしか探索できません。もっと多くの手数がかかる問題であっても、最適解を見つける方法は存在するのでしょうか。ここで用いるのが**半分全列挙のアイデア**です。例えば、「ちょうど $30$ 手でゴールできるか」を考えましょう。

* 最初の盤面から $15$ 手動かしたときのあり得る状態を、$(W1_1, W1_2, ..., W1_{T1})$ とする
* 目標の盤面から $15$ 手動かしたときのあり得る状態を、$(W2_1, W2_2, ..., W2_{T2})$ とする

そのとき、$W1_i = W2_j$ となるような $(i, j)$ の組が存在すれば、ちょうど $30$ 手で目標の状態まで動かすことができます。このような組が存在するかは、$W1, W2$ を適切な順序でソートした後、二分探索をすれば判定できます。（[map](https://qiita.com/e869120/items/518297c6816adb67f9a5#3-15-map) などのデータ構造を用いても解けます）
![27.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/bc97fea3-7381-fe3b-c354-9c796c627b85.png)
ただし、この手法だと最初に手数を決めなければ計算できないので、[6-2. 節](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#6-2-枝刈り全探索が通用する例)で紹介した「反復深化」のアイデアを利用して、

* $1$ 回ではできるか？
* （できなかった場合）$2$ 回ではできるか？
* （できなかった場合）$3$ 回ではできるか？
* （できなかった場合）$4$ 回ではできるか？　…（以下省略）

といった感じに解けば、最短手数が求まります。

半分全列挙を利用したアイデアでは、最短手数**約36手**まで解くことができます。実際に、$W1, W2$ の大きさは以下の表の通りになり、$36$ 手の場合でも高々数百万程度の状態しか考えなくて良いです。計算量は二分探索とソートがボトルネックになって $O((|W1| + |W2|) \log (|W1| + |W2))$ となるので、数秒で計算できます。

| 操作回数 | 全探索する手数 | $W2$ のサイズ | $W1$ のサイズ（最大値） |
|:---:|:---:|:---:|:---:|
| 20 | 10 | 2204 | 3666 |
| 24 | 12 | 9880 | 16774 |
| 28 | 14 | 44972 | 75986 |
| 32 | 16 | 204216 | 344758 |
| 36 | 18 | 925980 | 1565618 |

## 9-3. ＜発展＞ハッシュを用いて計算速度改善
盤面の状態を例えば struct で構造体を作って記録すると、<code>int</code> 型配列をマス目の数と同じ 16 個持つ必要があります。したがって、状態遷移・ソート・二分探索に時間がかかってしまいます。そこで利用するのが、bit 全探索のアイデアのもととなった、盤面の状態を数値として表す手法**「ハッシュ」**です。

左上のマスから順に $1, 2, ..., 16$ マス目として、$i$ マス目に置かれているピースの番号を $P_i$（空マスの場合は $0$）で表します。そのとき、

$$V = 16^0P_0 + 16^1P_1 + 16^2P_2 + 16^3P_3 + ... + 16^{15}P_{15}$$

とすると、盤面の状態を $0$ 以上 $2^{64}$ 未満の $1$ つの 64 ビット型整数で表現できてしまうのです。例えば以下の図の場合は $V = 1147797409030816545$とります。
![28.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/370106f9-f53a-98c8-8b85-15b1d31e4ee1.png)
そうすると、状態遷移・ソート・二分探索にかかる時間が短縮でき、考えるべき状態数が $10^7$ 程度になっても数秒で計算できます。したがって、最短手数**約40手**の場合まで対応できます。（このように、計算量オーダー自体は改善しないが、処理を単純化するなどして高速化することを、**定数倍高速化**といいます）

## 9-4. ＜発展＞IDA* を用いて更に改善
最後に、[枝刈り全探索](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#6-意外と強い枝刈り全探索)の一つの手法である**「IDA*」**という手法を用いて状態数を絞り込み、さらに手数の多い問題にも対応できるようにします。（ここでは一旦「半分全列挙の解法」を忘れます。）

まず、[6-3. 節](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#6-3-枝刈り全探索のアルゴリズムida-と-a)で紹介した IDA* について再掲しておきます。

> IDA* アルゴリズムは、反復深化に枝刈りを加えたものである。「$D$ 手以内に操作してください」という問題を解くとき、現在 $g$ 手操作しており、残りの最短手数の推定値（正確でなくて良い）を $h$ 手するとき、$g + h > D$ の場合枝刈りをして、遷移を打ち切る。

さて、この問題にどうやって IDA* のアルゴリズムが適用できるのでしょうか。例えば、残りの最短手数 $h$ の推定値を以下のように定義できます。

* ピース $i$ の位置を $(X_i, Y_i)$ として、目標状態でのピース $i$ の位置を $(P_i, Q_i)$ とする。
* $E_i = |X_i - P_i| + |Y_i - Q_i|$（2 点間のマンハッタン距離）とする。
* そのとき、$h = E_1 + E_2 + ... + E_{15}$ とする。

例えば、下図の場合は $h = 5$ になります。なお、最短手数は $h$ 以上であることが証明できるので、解を見逃すということは絶対にありません。
![29.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/f30b25d7-8a81-2493-b41e-edae6c809698.png)
このように推定値を計算して、枝刈り全探索を行った場合、探索すべき通り数が大幅に減り、[9-1. 節](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#9-1-基本手法---全探索)で扱った全探索の**10000分の1以下**になります。例えば以下の盤面を考えましょう。

~~~
14 7 6 4
2 3 1 11
5 9 12 15
13 0 10 8
~~~

この盤面における最短手数は $40$ 手ですが、IDA* を用いたアルゴリズムだと **4378257個**しか状態を探索する必要がありません。また、ほとんどの 15 パズルでは最短手数となるような動かし方が複数存在し、**10 通り以上**となるものも多いです。したがって、解が一つ見つかった場合に探索を終了すれば、実質的には **100万個以下**の状態探索で解を求めることができるのです。

---

このように、

* 本節で紹介した IDA* アルゴリズム
* [9-3. 節](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#9-3-%E7%99%BA%E5%B1%95%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%82%92%E7%94%A8%E3%81%84%E3%81%A6%E8%A8%88%E7%AE%97%E9%80%9F%E5%BA%A6%E6%94%B9%E5%96%84)で紹介したハッシュによる定数倍高速化

を使うと、最短手数 $40$ 手の場合は **0.02秒以内**、$55$ 手の場合でも数秒以内に計算を終わらせることができます。とても高速に計算を行うことができました。

#### ソースコード
この問題で扱ったソースコードは 70 行以上と長いので、リンクを貼り付けておきます。
以下の実装例は、両方 C++ のコードです。

* [9-2. 節で扱った、半分全列挙の解法](https://gist.github.com/E869120/707c539013346aaa881092aa6ad06f44)
* [9-4. 節で扱った、ハッシュと IDA* を用いた解法](https://gist.github.com/E869120/c921a0605edd9af8f33cbe9d20c2c96a)

---

ちなみに、「有限手数で解ける 15 パズル」の解は必ず **80 手以内**であることが証明されています。[^4]最も難しい $80$ 手の場合を解くのは難しいですが、IDA* の「残り手数推定値」をもう少し工夫すると、$65$ 手前後の問題でも数秒以内で実行できるようになります。

そして、現在最先端の探索アルゴリズム技術を使えば、$80$ 手のものでもすんなり計算できてしまいます。探索アルゴリズムは単純さがありながら、とても奥深く、応用範囲が広いです。

<br />

# 10. 更なる探索アルゴリズムの奥深さ
7 章・8 章・9 章では、「探索アルゴリズム」が役立つ例として、

* [再帰関数を用いた全探索で、「お姉さん問題」を実際に解く](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#7-お姉さん問題で役立つ全探索)
* [二分法を利用して、「高次方程式の解」を求める](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#8-高次方程式の解の発見に役立つ二分法)
* [半分全列挙や枝刈り全探索で、「15 パズル」を解く](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#9-15-パズルで役立つ半分全列挙と枝刈り探索)

を挙げました。しかしながら、探索アルゴリズムが役立つ範囲はそれだけではありません。実際にはもっとたくさんあるのです。皆さんが日常的に使っているモノの中にも「探索アルゴリズム」が役立っていたりするのです。

## 10-1. 巡回セールスマン問題
以下のような問題を考えてみましょう。

> $N$ 個の都市があって、$i$ 個目の都市は座標 $(x_i, y_i)$ にある。$2$ つの都市間を移動するのに、ユークリッド距離だけ時間がかかる。都市 $1$ から出発し、すべての都市を通って都市 $1$ に戻ってくるような移動方法のうち、時間ができるだけ短くなるようなものを出力してください。
> 制約：$1 \leq N \leq 200$

この問題は、$N \leq 10$ ならば [3-2. 節](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-2-順列全探索)で紹介した順列全探索のアルゴリズムを利用することで解けます。また、$N \leq 16$ のとき、ビットDP[^5] という別の方法を使うことで解くことができます。しかし、巡回セールスマン問題は NP 困難[^6]であり、多項式時間[^7]では解けません。

そこで、近似解（最適解にできるだけ近い解）を求めることを考えるのですが、この問題では、全探索と[貪欲法アルゴリズム](https://ja.wikipedia.org/wiki/%E8%B2%AA%E6%AC%B2%E6%B3%95)を組み合わせた[局所探索法（山登り法）](https://ja.wikipedia.org/wiki/%E5%B1%80%E6%89%80%E6%8E%A2%E7%B4%A2%E6%B3%95)という手法が通用します。局所探索法とは、大まかにいえば「解を少しずつ改善していくこと」を繰り返すことによって、最適に近い解を得るアルゴリズムのことを指します。

特に、巡回セールスマン問題を解くにあたっては、

* [2-opt アルゴリズム](https://qiita.com/hotpepsi/items/424f9491e7baaa63b6ce)

がよく使われます。それを利用すると、最適解に比べて数パーセントしか悪くない[^8]答えを見つけることができるのです。

## 10-2. オセロ AI の作成
オセロは、皆さんの多くがプレイしたことのあるような、有名なゲームです。 
![30.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507979/9ff59ddb-00ee-e724-b6a8-5d26427a0114.png)
実はこのオセロでも、「AI の実装」や「現在の形勢判断」に、探索アルゴリズムが使われているのです。例えば、再帰関数を用いた全探索の応用である、

* [Minimax 法のアルゴリズム](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95)

が利用されています。しかし、MiniMax 法には、最善手から悪手まで含めて全部探索してしまうという欠点があります。したがって、$1$ 手読む手数を増やしただけで状態遷移が数十倍に膨れ上がるほど、探索通り数が大きくなってしまいます。それを改善するために利用されているのは、評価値の高い状態を優先して計算する枝刈り探索アルゴリズムの一つである、

* [アルファベータ法（αβ法）のアルゴリズム](https://uguisu.skr.jp/othello/alpha-beta.html)

です。この手法を用いると、多くの人間に勝てる AI を実装することができます。

#### 一方、最近のAIは…
しかし、最近は探索アルゴリズムではなく**機械学習を用いた最適化**も主流になっています。例えば将棋 AI では強化学習や[機械学習](https://ledge.ai/machine-learning)が用いられており、その影響で近年 AI が急激に進化しています。[αβ法]()だけでも相当強いのですが、機械学習によって AI がプロと互角に戦えるようになったり、タイトルを持つような人にも勝てるようになったりしてきています。

<br />

# 11. おわりに
探索アルゴリズムの最も基本的なアルゴリズムは「全探索」で、あり得るものを全通り探索するという本当に単純なものでした。しかし、これを応用すると、現実社会で活用されているような、様々な効率的なアルゴリズムが生まれます。これこそが探索アルゴリズムの奥深さ、難しさ、そして面白さなのです。

プログラムを書くにあたって、アルゴリズムを使うだけでなく、問題を「探索視点で見ること」はとても重要です。本記事を通して少しでも「探索視点の考え方」のイメージを深めていただけたならば、とても嬉しいです。

記事は以上です。高校生が書いた記事ですので、文章が分かりづらかったかもしれませんが、最後までお読みいただきありがとうございました。

[^1]: 「おねえさん問題」とは、組合せ爆発のすごさとアルゴリズム技術の重要性を分かりやすく伝えることを目的にした、2012 年 8 月から 2013 年 4 月にかけて日本科学未来館で上映された動画に出てくる問題です。動画は、[Youtube のリンク](https://www.youtube.com/watch?v=Q4gTV4r0zRs)から閲覧することができます。
[^2]: 例えば、$N = 25$ の場合は $8.403 \times 10^{150}$ というものすごい通り数になります。[オンライン整数列大辞典 A007764](https://oeis.org/A007764) に載っています。
[^3]: 2020 年 7 月 26 日時点で、$26 \times 26$ までが解かれています。
[^4]: 詳しくは、こちらの [Wikipediaのページ](https://ja.wikipedia.org/wiki/15%E3%83%91%E3%82%BA%E3%83%AB)をご覧ください。
[^5]: ビットDPについては、[ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜　の第11章](https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361#11-bit-dp) をご覧ください。
[^6]: 多項式時間で解くことが難しいとされている問題のことです。詳しくは[こちらの記事](https://qiita.com/drken/items/5187e49082f7437349c2)をご覧ください。
[^7]: 多項式時間とは、処理時間の上界が $N$ の多項式で表現できることを指します。例えば $O(N^{869120})$ は多項式時間ですが、$O(1.001^N)$ は多項式時間ではありません。
[^8]: 例えば、Beneteley は $10^6$ 個の都市を持つような問題について、3～4%程度しか悪くない答えを出しています。[こちらの文献](https://www.jstage.jst.go.jp/article/ieejeiss1987/114/4/114_4_411/_pdf)の p.415 を参照してください。