# 八数码问题（A-star 解）

## A-star

A-star 算法的核心是引入代价，有限选择代价低的边界点进行访问。代价等于历史代价+未来代价

### 代价

A * 的代价计算公式：

• 当估计代价变为 `0` 时，A* 退化为 Dijkstra 算法

## 代码说明

### 代码整体结构

`````` 1<!DOCTYPE html>
2<html lang="en">
3
5    <meta charset="UTF-8">
6    <meta http-equiv="X-UA-Compatible" content="IE=edge">
7    <title>8-puzzle</title>
9
10<body>
11    #样式表#
12    <div id="app">
13        <pre id="stdout"></pre>
14        <div id="ans"></div>
15    </div>
16    <script>
17    	#工具函数#
18        write("Welcome to the 8-puzzle game!");
19        let goalState = [
20            [0, 1, 2],
21            [3, 4, 5],
22            [6, 7, 8]
23        ];
24        do {
25            initState = generateState();
26        }
27        while (!isResolvable(initState, goalState));
28        writeln("<p>Initial state:</p>");
29        displayState(initState);
30        writeln("<p>Goal state:</p>");
31        displayState(goalState);
32        writeln("<p>Start searching...</p>");
33		#寻路算法#
34        let path = aStar(initState, goalState);
35        for (let i = 0; i < path.length; i++) {
36            let state = unhashState(path[i]);
37            displayState(state, "ans", (str) => {
38                return `<div class="state">\${str}</div>`
39            });
40        }
41    </script>
42</body>
43
44</html>
``````

### 样式表

`````` 1    <style>
2        .num-0 {
3            background-color: #ffffff;
4        }
5
6        .num-1 {
7            background-color: #bcffde;
8        }
9
10        .num-2 {
11            background-color: #52ffac;
12        }
13
14        .num-3 {
15            background-color: #00ff84;
16        }
17
18        .num-4 {
19            background-color: #00ce6a;
20        }
21
22        .num-5 {
23            background-color: #00a153;
24        }
25
26        .num-6 {
27            background-color: #008344;
28        }
29
30        .num-7 {
31            background-color: #006434;
32        }
33
34        .num-8 {
35            background-color: #00381d;
36        }
37
38        .num {
39            display: inline-block;
40            width: 32px;
41            height: 32px;
42        }
43
44        #stdout {
45            box-sizing: border-box;
46        }
47
48        #app {
49            margin: 1em;
50            box-sizing: border-box;
51        }
52
53        #ans {
54            display: flex;
55            flex-flow: wrap;
56        }
57
58        /* clear broswer style*/
59        html,
60        body,
61        html {
62            margin: 0;
64        }
65        .state {
66            display: block;
67            width: 120px;
68            height: 120px;
69        }
70        pre {
71            font-family: monospace;
72        }
73    </style>
``````

### 输入输出

• `write(params, target = "stdout")`: 向标准输出输出字符串
• `params`: 字符串

• `target`: 可选参数，默认为 `stdout`，表示输出到标准输出，可以是 `stdout``ans`

``````1        function write(params, target = "stdout") {
2            document.getElementById(target).innerHTML += `\${params}`;
3        }
``````
• `writeln(params, target = "stdout")`: 向标准输出输出字符串，并在末尾添加换行符
• `params`: 字符串

• `target`: 可选参数，默认为 `stdout`，表示输出到标准输出，可以是 `stdout``ans`

``````1        function writeln(params, target = "stdout") {
2            document.getElementById(target).innerHTML += `\${params}\n`;
3        }
``````
• `function read(hint, postproc)`: 读取用户输入，并返回输入的字符串
`````` 1        function read(hint, postproc) {
2            var input = prompt(hint);
3            if (input == null) {
4                return null;
5            }
6            if (postproc != null) {
7                input = postproc(input);
8            }
9            return input;
10        }
``````
• `generateState = ()` 随机初始化拼图状态
• `return`: 初始状态
`````` 1        let generateState = () => {
2            let state = [];
3            let left = [1, 2, 3, 4, 5, 6, 7, 8, 0];
4            for (let i = 0; i < 3; i++) {
5                state[i] = [];
6                for (let j = 0; j < 3; j++) {
7                    let randIndex = Math.floor(Math.random() * left.length);
8                    state[i][j] = left[randIndex];
9                    left.splice(randIndex, 1);
10                }
11            }
12            return state;
13        }
``````
• `displayState(state, target = "stdout", postproc = null)`: 显示拼图状态
• `state`: 拼图状态

• `target`: 可选参数，默认为 `stdout`，表示输出到标准输出，可以是 `stdout``ans`

• `postproc`: 可选参数，默认为 null，表示不进行任何处理，可以是函数

`````` 1        function displayState(state, target = "stdout", postproc = null) {
2            var str = "";
3            // 3x3 board
4            for (var i = 0; i < 3; i++) {
5                for (var j = 0; j < 3; j++) {
6                    s = state[i][j]
7                    str += `<span class="num num-\${s}">\${s}</span>`;
8                }
9                str += "\n";
10            }
11
12            if (postproc != null) {
13                str = postproc(str);
14            }
15            write(str, target);
16        }
``````
• `numberOfInversions(seq)`: 计算序列中的逆序数
• `seq`: 序列

• `return`: 逆序数

`````` 1        function numberOfInversions(seq) {
2            let count = 0;
3            for (let i = 0; i < seq.length; i++) {
4                for (let j = i + 1; j < seq.length; j++) {
5                    if (seq[i] > seq[j]) {
6                        count++;
7                    }
8                }
9            }
10            return count;
11        }
``````
• `flatten(state)`: 将拼图状态转换为一维数组
• `state`: 拼图状态

• `return`: 一维数组

``````1        function flatten(arr) {
2            return arr.reduce((a, b) => a.concat(b), []);
3        }
``````
• `isSolvable(state)`: 判断拼图是否可解
• `state`: 拼图状态

• `goalState`: 拼图目标状态

• `return`: 可解性

``````1        function isResolvable(state, goalState) {
2            let seq = flatten(state);
3            let goalSeq = flatten(goalState);
4            return numberOfInversions(seq) % 2 == numberOfInversions(goalSeq) % 2;
5        }
``````
• `calcNum2loc(state)`: 计算拼图状态中每个数字的位置
• `state`: 拼图状态

• `return`: 数字位置映射

`````` 1
2        function calcNum2loc(state) {
3            // 计算每个数字的位置，相当于一个反向索引
4            let num2loc = {};
5            for (let i = 0; i < 3; i++) {
6                for (let j = 0; j < 3; j++) {
7                    num2loc[state[i][j]] = [i, j];
8                }
9            }
10            return num2loc;
11        }
``````
• `cost(state, goalState)`: 计算拼图距离目标状态的代价（这里采用曼哈顿距离）
• `state`: 拼图状态

• `goalState`: 拼图目标状态

• `return`: 代价

`````` 1        // 采用曼哈顿距离，即当前各棋子均移动到目标位置的总移动距离
2        function cost(state, goalState) {
3            let goalNum2loc = calcNum2loc(goalState);
4            let cost = 0;
5            for (let x = 0; x < 3; x++) {
6                for (let y = 0; y < 3; y++) {
7                    let num = state[x][y];
8                    if (num == 0) {
9                        continue;
10                    }
11                    let goalX = goalNum2loc[num][0];
12                    let goalY = goalNum2loc[num][1];
13                    cost += Math.abs(x - goalX) + Math.abs(y - goalY);
14                }
15            }
16            return cost;
17        }
``````
• `state2hash(state)`: 计算拼图状态的哈希值
• `state`: 拼图状态

• `return`: 哈希值

``````1
2        let state2hash = (state) => {
3            let flat = flatten(state);
4            let hashval = 0;
5            for (let i = 0; i < flat.length; i++) {
6                hashval = hashval * 10 + flat[i];
7            }
8            return hashval;
9        }
``````
• `unhashState(hashval)`: 将哈希值转换为拼图状态
• `hashval`: 哈希值

• `return`: 拼图状态

`````` 1        let unhashState = (hashval) => {
2            let state = [
3                [0, 0, 0],
4                [0, 0, 0],
5                [0, 0, 0]
6            ];
7            for (let i = 0; i < 3; i++) {
8                for (let j = 0; j < 3; j++) {
9                    state[2 - i][2 - j] = hashval % 10;
10                    hashval = Math.floor(hashval / 10);
11                }
12            }
13            return state;
14        }
``````
• `minFxStateHash(open, fx)`: 计算拼图状态的最小fx值对应的哈希值
• `open`: 开放列表，即“待访问”列表

• `fx`: fx值映射

`````` 1
2        // 寻找 open 中代价最小的状态
3        function minFxStateHash(open, fx) {
4            let minFxHash = open[0];
5            for (let i = 1; i < fx.length; i++) {
6                if (fx[i] < minFxHash) {
7                    minFxHash = fx[i];
8                }
9            }
10            return minFxHash;
11        }
``````
• `swap(newState, zeroLoc, newLoc)`: 交换拼图状态中的两个数字
• `newState`: 拼图状态

• `zeroLoc`: 数字0的位置

• `newLoc`: 数字0的新位置

``````1        function swap(newState, zeroLoc, newLoc) {
2            let temp = newState[zeroLoc[0]][zeroLoc[1]];
3            newState[zeroLoc[0]][zeroLoc[1]] = newState[newLoc[0]][newLoc[1]];
4            newState[newLoc[0]][newLoc[1]] = temp;
5        }
``````

### 关键算法

`````` 1        function aStar(initState, goalState) {
2            // 初始化. fx = gx + hx
3            let openStates = [], // 待访问列表，存储一系列 open 状态。相当于边界列表
4                openState2fx = {}, // fx 用于存储每个 open 状态的总代价
5                openState2gx = {}, // gx 用于存储每个 open 状态的现代价
6                // 我们这里不用 hx，因为 hx 可以通过代价函数计算
7                closed = {}, // 关闭列表，存储一系列 closed 状态。相当于障碍列表，表示已经访问过的状态
8                parent = {}; // 父节点，用于路径回溯
9            // 可能的移动方向。主语是空格
10            let moves = [
11                [1, 0], // 向右移动
12                [-1, 0], // 向左移动
13                [0, 1], // 向下移动
14                [0, -1] // 向上移动
15            ];
16            // 初始化 open 列表。将起点状态加入 open 列表，并计算其 gx ,fx 值
17            let curHash = state2hash(initState);
18            let goalHash = state2hash(goalState);
19            let curState = initState;
20            openStates.push(curHash);
21            openState2gx[curHash] = 0;
22            openState2fx[curHash] = cost(curState, goalState);
23
24            // 开始搜索
25            while (openStates.length > 0) {
26                // 寻找 open 列表中代价最小的状态，将其加入 closed 列表并从 open 列表中移除，设为当前状态
27                curHash = minFxStateHash(openStates, openState2fx);
28                curState = unhashState(curHash);
29                openStates.splice(openStates.indexOf(curHash), 1);
30                closed[curHash] = true;
31                // 如果当前状态是目标状态，则结束搜索
32                if (curHash == goalHash) {
34                    break;
35                }
36                // 对当前状态的每一个可能的移动方向进行搜索
37                let curNum2loc = calcNum2loc(curState);
38                let zeroLoc = curNum2loc[0];
39                let success = false
40                for (let i = 0; i < moves.length; i++) {
41                    let newLoc = [zeroLoc[0] + moves[i][0], zeroLoc[1] + moves[i][1]];
42                    // 如果移动后的位置不合法，则跳过
43                    if (newLoc[0] < 0 || newLoc[0] > 2 || newLoc[1] < 0 || newLoc[1] > 2) {
44                        continue;
45                    }
46                    // 计算新状态。即通过向 moves[i] 方向移动数字0
47                    let newState = curState.map(row => [...row]);
48                    swap(newState, zeroLoc, newLoc);
49                    // 计算新状态的 gx, fx 值
50                    let newHash = state2hash(newState);
51                    let newGx = openState2gx[curHash] + 1;
52                    let newFx = newGx + cost(newState, goalState);
53                    openState2fx[newHash] = newFx;
54                    openState2gx[newHash] = newGx;
55                    if (newHash == goalHash) {
57                        success = true
58                        break;
59                    }
60                    // 如果新状态不在 open 列表中，则加入 open 列表
61                    if (!(newHash in closed)) {
62                        openStates.push(newHash);
63                        // 记录新状态的父节点，完善回溯向量场
64                        parent[newHash] = curHash;
65                    }
66                }
67                if (success) {
68                    break;
69                }
70            }
71            // 回溯路径
72            let path = [];
73            let initHash = state2hash(initState);
74            while (curHash != initHash) {
75                path.push(curHash);
76                curHash = parent[curHash];
77            }
78            // 逆序
79            path.reverse();
80            path.push(goalHash)
81            return path;
82        }
83
84        let path = aStar(initState, goalState);
85        for (let i = 0; i < path.length; i++) {
86            let state = unhashState(path[i]);
87            displayState(state, "ans", (str) => {
88                return `<div class="state">\${str}</div>`
89            });
90        }
``````