这是一个关于人工智能启发式和非启发式搜索算法的测试。
我们有一个3×3的网格，其中B表示黑骑士，W表示白骑士，类似于国际象棋中的骑士。
+---+---+---+ +---+---+---+| W | | W | | B | | B |+---+---+---+ +---+---+---+| | | | ----> | | | | +---+---+---+ +---+---+---+| B | | B | | W | | W |+---+---+---+ +---+---+---+B和W可以像国际象棋中的骑士一样进行”L”形移动。
将黑骑士移动到当前白骑士的位置，将白骑士移动到当前黑骑士的位置，最佳的搜索算法是什么？
- A星算法
- 广度优先搜索
- 深度优先搜索
- 爬山算法
我感到很困惑，不知道正确的选择是什么。
回答：
一个重要方面是可能的位置数量相当少：
420 = Binomial(8,2) * Binomial(6, 2)这意味着无论选择哪种算法，都必须注意不要多次经过同一个节点，即同一个位置。传统上，国际象棋程序在分析棋子数量少的位置时使用哈希表。这里，考虑到可能位置的数量较少，可以选择一种“完美”的哈希，即没有冲突的情况。
关于这些算法：
- 爬山算法提供的是局部最小值，而不是绝对最小值。这里不适合回答这个问题
- 深度优先搜索（例如使用回溯实现）在这里似乎不是最佳选择，因为你有可能会深入到错误的路径
- A星算法通常非常有效。然而，它依赖于对给定节点的良好启发式估计。在这里，通过手动寻找解决方案后，很明显，骑士需要在小范围内长时间地转圈（疯狂的马）。在这种情况下，很难找到一个好的启发式
- 广度优先搜索通常的缺点是它可能会产生大量的内存消耗，从而导致花费大量时间来访问这些节点。但在这里，由于可能节点（位置）数量有限以及使用了哈希，这不会发生。此外，使用广度优先搜索，一旦找到一个解决方案，我们可以确定它是最短的
因此，我在C++中实现了广度优先搜索。结果几乎是即时提供的。
以下是16个半步的移动情况：
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | W | | W | | | | W | | | | W | | | | |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | | | | | | | | | | | B | | W | | B |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | B | | B | | B | W | B | | | W | B | | | W | B |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | B | | | | B | | W | | B | B | W | | B | B | W |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | W | | | | W | | | | W | | | | | | |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | | W | B | | | | B | | | | | | | | W |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | B | | W | | B | W | W | | B | W | W | | B | W | |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | | | | | | | | | | | B | | W | | B |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | B | | W | | B | | | | | | | | | | |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | | W | | | | W | | | | W | B | | | | B | | B | | B |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | W | | B | | | | B | | | | B | | | | B | | | | |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ | | B | | | | B | W | | | | W | | W | | W | | W | | W |+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ 以下是程序代码：
#include <iostream>#include <array>#include <vector>#include <tuple>#include <algorithm>int depl[9][2] = { {5,7}, {6,8}, {3,7}, {2,8}, {-1,-1}, {0,6}, {1,5}, {0,2}, {1,3}};struct position { std::array<int, 2> B; std::array<int, 2> W; int hash; position *up = nullptr; position (int w0, int w1, int b0, int b1) { if (w0 > w1) std::swap (w0, w1); if (b0 > b1) std::swap (b0, b1); B[0] = b0; B[1] = b1; W[0] = w0; W[1] = w1; cal_hash(); } position() {}; void cal_hash () { hash = 1000*B[0] + 100*B[1] + 10*W[0] + W[1]; } std::vector<position> gene_mov (int white_black) { std::vector<position> res; if (!white_black) { // White for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { int pos = depl[W[i]][j]; bool test = (pos == W[1-i]) || (pos == B[0]) || (pos == B[1]); if (!test) { res.push_back (position(pos, W[1-i], B[0], B[1])); } } } } else { // Black for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { int pos = depl[B[i]][j]; bool test = (pos == B[1-i]) || (pos == W[0]) || (pos == W[1]); if (!test) { res.push_back (position(W[0], W[1], pos, B[1-i])); } } } } return res; } void print (int shift = 0) { char displ[3][3] = {{' ',' ',' '}, {' ',' ',' '}, {' ',' ',' '}}; displ[1][1] = ' '; displ[2 - W[0]/3][W[0]%3] = 'W'; displ[2 - W[1]/3][W[1]%3] = 'W'; displ[2 - B[0]/3][B[0]%3] = 'B'; displ[2 - B[1]/3][B[1]%3] = 'B'; Wshift(shift); std::cout << "+---+---+---+\n"; for (int i = 0; i < 3; ++i) { Wshift(shift); for (int j = 0; j < 3; j++) { std::cout << "| " << displ[i][j] << " "; } std::cout << "|\n"; Wshift(shift); std::cout << "+---+---+---+\n"; } std::cout << "\n"; } void Wshift (int shift) { for (int i = 0; i < shift; ++i) std::cout << " "; }};std::tuple<bool, int, std::vector<position>> find_moves (position &first, position &end) { std::vector<position> moves; std::array<bool, 10000> pos_found = {false}; std::vector<std::vector<position>> dfs; using pvector = std::vector<position>; dfs.push_back(pvector(1, first)); int iter = 1; int white_black = 0; while (true) { int n = dfs[iter-1].size(); if (n == 0) return std::make_tuple(false, 0, moves); dfs.push_back(pvector(0)); for (int i = 0; i < n; ++i) { auto candidates = dfs[iter-1][i].gene_mov(white_black); for (auto &c: candidates) { if (pos_found[c.hash]) continue; c.up = &dfs[iter-1][i]; if (c.hash == end.hash) { // Last position attained: get the previous moves moves.resize(iter+1); moves[iter] = c; for (int i = iter - 1; i >= 0; i--) { moves[i] = *(moves[i+1].up); } return std::make_tuple(true, iter, moves); } pos_found[c.hash] = true; dfs[iter].push_back (c); } } iter++; white_black = 1 - white_black; } return std::make_tuple(false, -1, moves);}int main () { position first(6, 8, 0, 2); position end(0, 2, 6, 8); bool success; int n_iter; std::vector<position> moves; std::tie (success, n_iter, moves) = find_moves (first, end); std::cout << "success = " << success << "\n"; std::cout << "n_iter = " << n_iter << "\n"; for (auto &m: moves) { m.print(); std::cout << "\n"; } return 0;}