这是一个关于人工智能启发式和非启发式搜索算法的测试。

我们有一个3×3的网格，其中B表示黑骑士，W表示白骑士，类似于国际象棋中的骑士。

+---+---+---+            +---+---+---+| W |   | W |            | B |   | B |+---+---+---+            +---+---+---+|   |   |   |    ---->   |   |   |   |  +---+---+---+            +---+---+---+| B |   | B |            | W |   | W |+---+---+---+            +---+---+---+

B和W可以像国际象棋中的骑士一样进行”L”形移动。

将黑骑士移动到当前白骑士的位置，将白骑士移动到当前黑骑士的位置，最佳的搜索算法是什么？

1. A星算法
2. 广度优先搜索
3. 深度优先搜索
4. 爬山算法

我感到很困惑，不知道正确的选择是什么。

回答：

一个重要方面是可能的位置数量相当少：

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;}