A_算法求解十五数码问题

问题描述

数码问题是一类比较经典的图搜索问题，它给定如下表所示的某个初始状态（这里以 4*4 的十五数码问题为例）：

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

每次可将 0 上下左右移动一格，要求寻找某个移动策略，使整个局面达到目标状态，例如：

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

算法描述

一般图搜索算法

视每种状态为一个节点。在某节点下，通过移动 0 的位置可以得到新的节点，这称为“扩展一个节点”。理论上讲，整个牌局可能出现的局面数，也就是节点数是有穷的，因此通过暴力搜索肯定能找到解（若有解的话）。但是 15 数码问题局面总数是 16!，这使暴力搜索没有实践价值。

一般的图搜索算法通过维护两个表：OPEN 表与 CLOSE 表，分别存放未被扩展过的节点与已经被扩展过的节点，并通过某种策略来优化搜索过程。其基本过程是：

1. 将初始状态加入 OPEN 表，清空 CLOSE 表
2. 若 OPEN 表为空，失败，退出
3. 移除 OPEN 表中的第一个节点，将其加入 CLOSE 表，该节点记为 n
4. 若 n 是目标节点，搜索成功，退出

5. 扩展 n 节点，舍弃扩展出的子节点中与 n 的父节点相同的节点，对剩下的子节点做如下处理：

   • 若该子节点不在 OPEN 表与 CLOSE 表中，则将其加入 OPEN 表
   • 否则，记与该子节点相同的已存在的节点为 P，舍弃该子节点，按照某种原则判断是否应该修改 P 的父节点指向
6. 按照某种原则重排 OPEN 表
7. 跳转至第二步

这个过程给出了图搜索算法的一般流程。在进行算法实现时还需要指定重排 OPEN 表的准则：也就是确定哪些节点应该被优先扩展与留在搜索树中。

A 算法

A 算法通过一个估价函数 f 来对节点进行评价，估计出该节点到达目标节点的“希望”，并有限扩展最有希望的节点。其估价函数定义为：

$$f(n)=g(n)+h(n)$$

其中 n 代表被评价的节点。特别的，定义

$$g^*(n)：从起始节点到n的最优路径的代价$$

$$h^*(n)：从n到目标节点的最优路径的代价$$

$$f^*(n)：从起始节点到目标节点的最优路径的代价$$

因此 $f(n),g(n),h(n)$ 是 $f^*(n),g^*(n),h^*(n){{#bodyData}}nbsp;的估计值。一般选择 $g(n)$ 为起始节点到 n 的实际代价，$h(n)$ 为 n 到目标节点的代价估计。$h(n)$ 是基于某准则制定的启发函数，用于描述 n 到目标节点的“难度”。

在一般图搜索算法的第 6 步，A 算法对 OPEN 表中的所有节点使用 $f(n)$ 进行评价并由小到大排序，每次都有限扩展 $f(n)$ 最小的节点。另外在第 5 步，当 P 已存在时，若新生成的子节点的 $f(n)$ 相对 P 的更小，则更新 P 的父节点为当前节点，并递归地更新 P 的所有子节点的估价。

A* 算法

在 A 算法中，若有

$$h(n)\leq h^*(n)$$

则称为 A* 算法。

算法实现

这里使用 C++ 进行算法实现。设初始与目标状态为问题描述中的两个表。选取 $h(n)$ 为当前节点中所有数码相对目标位置的曼哈顿距离和。

节点类

extern int start[4][4];
extern int target[4][4];
extern int trans[4][2];

class node
{
public:
    int m_State[4][4];
    int m_Zero[2];    
    node* m_Parent;  
    vector<node*> m_Childern;   
    int m_H; // 代价    
    int m_G; // 深度

    node();
    node(int from[4][4]);
    node(int from[4][4], node* parent);

    void init(int from[4][4]);
    void calcH();
    void calcG();
    static void findZero(int state[4][4],int pos[2]);
    void findZero();
    int getPrice();
    void expand();
    bool check(int t[4][4]);

    // 重载操作符，判定节点是否等价
    bool operator==(node b) {
        return this->check(b.m_State);
    }

    bool operator==(int t[4][4]) {
        return this->check(t);
    }
};

void print(int t[4][4]);
int output(node* n);
node* findP(int t[4][4]);
node* get();
void updateAll(node* n);

大部分成员及方法这里只给出声明，实现见附件中的 node.cpp。其中的 expand() 方法值得注意：

int trans[4][2] = { { -1,0 },{ 1,0 },{ 0,1 },{ 0,-1 } };
void node::expand() {
    for (int index = 0; index < 4; index++) {
        int newZP[2] = { m_Zero[0] + trans[index][0],m_Zero[1] + trans[index][1] };
        if (newZP[0] < 0 || newZP[0]>3 || newZP[1] < 0 || newZP[1]>3) continue;

        // 新的数码位置
        int newState[4][4];

        // 初始化为当前状态
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                newState[i][j] = m_State[i][j];
            }
        }

        // 交换 m_Zero 与 newZP 两个位置的数
        int t = newState[m_Zero[0]][m_Zero[1]];
        newState[m_Zero[0]][m_Zero[1]] = newState[newZP[0]][newZP[1]];
        newState[newZP[0]][newZP[1]] = t;

        // 排除与父节点相同的节点
        if (this->m_Parent && *(this->m_Parent) == newState) continue;

        node* P = findP(newState);
        if (!P) {
            // 新建节点并加入 OPEN
            node *newN = new node(newState, this);
            OPEN.push_back(newN);
            m_Childern.push_back(newN);
        }
        else {
            // 已存在，若当前节点代价更小，更改已存在的节点指针及其子节点代价
            node *newN = new node(newState, this);
            if (P->getPrice() > newN->getPrice()) {
                // 修改 P 的父节点为当前节点
                P->m_Parent = this;
                P->calcG();
                updateAll(P);
            }
            else {
                delete newN;
                newN = NULL;
            }
        }
    }
}

其中的 updateAll() 递归地更新了 P 的所有子节点的估价。

OPEN 表与 CLOSE 表

使用 std::vector 作为容器：

extern vector<node*> OPEN;
extern vector<node*> CLOSE;

算法执行

执行函数：

node* execute() {
    // OPEN 为空
    if (OPEN.size() < 1) {
        return NULL;
    }
    
    // 获得估价最小的节点
    node *now = get();
    
    // 删除 OPEN 表中元素
    vector<node*>::iterator it;
    for (it = OPEN.begin(); it != OPEN.end(); it++) {
        if (*it == now) {
            OPEN.erase(it);
            break;
        }
    }

    // 放入 CLOSE 表
    CLOSE.push_back(now);
    // 若抵达目标
    if (*now == target) return now;
    
    // 扩展该节点
    now->expand();
    cout << "OPEN: " << OPEN.size() << "\tCLOSE: " << CLOSE.size() << '\n';

    // 递归调用
    node*n = execute(); 
    
    // 返回目标
    if(n) return n;

    // 查找失败
    return NULL;
}

int main(){
    OPEN.clear();
    CLOSE.clear();
    node *st = new node(start);
    OPEN.push_back(st);
    return output(execute());
}

测试结果

G	H	OPEN 表大小	CLOSE 表大小
41	0	172546	188600

最终寻找到的路径步数为 41 步，已扩展节点数 188600 个，待扩展节点数 172546 个，也就是说算法搜索了接近 400000 个节点最终找到了一个路径。路径变换见附件 out.txt（从下到上为转变路径）。

讨论与总结

有解性判断

对 15 数码问题，并非任何两种状态之间都可以相互转换，当前节点 n 相对目标节点 S 的有解性可以用以下准则判断：(n 逆序数奇偶性==S 逆序数奇偶性)==(0到目标位置的行距%2==0)。其中逆序数为将节点排成一列，其中每个数码前方比自己大的数码个数之和。

有解性判断可用在初始节点的判断上，当判断其无解后就无需再进行搜索了。但是该性质不能帮助搜索过程中的剪枝，因为一旦初始节点有解，由初始节点扩展出的节点都有解。

算法不足

影响该算法性能的主要原因是 OPEN 表的排序这一步。实际实现过程中无需对 OPEN 表全局排序，只需要挑出其中估价最小的节点即可，但是这也需要遍历比较。在节点较多时，这是一个瓶颈。

另外估价函数的设计会使算法性能差别很大。当估价函数的启发性不足时，会生成大量的无用节点，延长搜索时间。

---

附件：main.cpp | node.h | node.cpp | out.txt