人工智能：搜索算法在问题空间的求解示例

本文將以八数码问题为例，讨论在解决问题时候的搜索算法的选择和优化。

人工智能-搜索算法

jskyzero 2017/10/11

以简单的问题切入

其实不用特别关注八数码究竟是什么问题，总之也是给我们一个输入，输出，变化规则，我们需要想办法找到从输入到输出的一个变化的过程，

我们来具体看下输入和输出，输入的是包含0的九个数，代表九个格子现在上面的数字，输出是按照1-8，最后是0的顺序。也就是要把数字放到对应的格子的意思，然后变化方法就是，移动0和上下左右的数字交换。

将问题转化到搜索上

每个状态可以理解为，一个节点，由一个状态转化到另一个状态可以理解为一条有向边，发现重复的状态的话就不在生成，这样我们就把这个问题变成了一个有向无环图（树），我们只要遍历这棵树，找到符合的目标状态，就算解决问题了。

那么树的遍历我们是熟悉的，无外乎深度优先广度优先。

广度优先可以找到最优解，但是相对而言对内存和时间的需求要高一些，深度的话可以在内存不足的时候起到关键作用。

随便实现一下逻辑

引入头文件

import heapq  # 优先队列，用于按启发式评分取出“看起来更接近目标”的状态。

# 8 数码状态用长度为 9 的一维数组表示，0 表示空格。
initial = [8, 7, 6, 5, 4, 3, 2, 1, 0]
final = [1, 2, 3, 4, 5, 6, 7, 8, 0]

一些基本函数

def sub_move_choice(now_state):
    # 返回当前状态移动空格后可以到达的所有下一状态。
    next_state = []
    # 一维下标和 3x3 棋盘位置的对应关系：
    # 0 1 2
    # 3 4 5
    # 6 7 8
    # index 是空格 0 的位置，空格只能和上下左右相邻格交换。
    index = now_state.index(0)
    if index % 3 == 0:
        # 最左列只能向右交换。
        next_state.append(swap(now_state, index, index + 1))
    if index % 3 == 1:
        # 中间列可以向左或向右交换。
        next_state.append(swap(now_state, index, index - 1))
        next_state.append(swap(now_state, index, index + 1))
    if index % 3 == 2:
        # 最右列只能向左交换。
        next_state.append(swap(now_state, index, index - 1))
    if index // 3 == 0:
        # 第一行只能向下交换。
        next_state.append(swap(now_state, index, index + 3))
    if index // 3 == 1:
        # 中间行可以向上或向下交换。
        next_state.append(swap(now_state, index, index - 3))
        next_state.append(swap(now_state, index, index + 3))
    if index // 3 == 2:
        # 最后一行只能向上交换。
        next_state.append(swap(now_state, index, index - 3))
    return next_state


def swap(now_state, left, right):
    # 复制一份状态，避免原列表被修改后影响其他搜索分支。
    new_state = now_state[:]
    temp = new_state[left]
    new_state[left] = new_state[right]
    new_state[right] = temp
    return new_state

核心部分

def BFS(initial_state, end_state):
    # next_states 保存当前深度的全部状态，逐层扩展就是广度优先。
    next_states = [initial_state]
    # traveled 用 tuple 存储访问过的状态，因为 list 不可哈希，不能直接放 set。
    traveled = set(tuple(initial_state))
    depth = 0
    while not end_state in next_states and not len(next_states) == 0:
        depth = depth + 1
        new_next_states = []
        for next_state in next_states:
            for sub_next_state in sub_move_choice(next_state):
                # 跳过已访问状态，否则搜索图中会来回移动空格形成环。
                if not tuple(sub_next_state) in traveled:
                    new_next_states.append(sub_next_state)
                    traveled.add(tuple(sub_next_state))
        # 一层处理完后再整体替换，保证 depth 的含义是搜索层数。
        next_states = new_next_states[:]
        # print("depth = ", depth,
        #       "len = ", len(new_next_states),
        #       "traveled = ", len(traveled))
    print( "FAILED" if len(next_states) == 0 else "traveled = ", len(traveled))


def DFS(initial_state, end_state, Afunction):
    next_states = []
    # heapq 是小根堆，所以取负数，让评分越高的状态越先被弹出。
    heapq.heappush(
        next_states, (-Afunction(initial_state, end_state), initial_state))
    traveled = set(tuple(initial_state))
    while not len(next_states) == 0:
        # top_state 是当前启发式评分最高的待探索状态。
        top_state = heapq.heappop(next_states)[-1]
        if top_state == end_state:
            print("traveled = ", len(traveled))
            return
        else:
            for next_state in sub_move_choice(top_state):
                if not tuple(next_state) in traveled:
                    # 将启发式评分和状态一起入堆，下一轮优先探索更接近目标的状态。
                    heapq.heappush(
                        next_states, (-Afunction(next_state, end_state), next_state))
                    traveled.add(tuple(next_state))
    print("FAILED")


def diferent_bit(one_state, another_state=final):
    # 统计位置不同的格子数，差异越少越接近目标；取负数表示“代价”。
    return -sum([0 if x == y else 1 for(x, y) in zip(one_state, another_state)])

def diferent_sum(one_state, another_state=final):
    # 直接比较数字差值只是一种粗糙启发，未考虑棋盘空间位置。
    return -sum([abs(x - y) for(x, y) in zip(one_state, another_state)])

def manhadun_space(one_state, another_state):
    space = 0
    for i in range(0, 9, 1):
      # 找到当前数字在目标状态中的位置 j，计算当前位置 i 到 j 的曼哈顿距离。
      j = another_state.index(one_state[i])
      space = space + abs(j % 3 - i % 3) + abs(j // 3 - i // 3)
    return -space

我们可以看到这个差别，还是挺明显的。

# 基准 BFS：不使用启发式，遍历量最大。
BFS(initial, final)
# 后三项使用不同启发函数，越接近问题结构，遍历状态越少。
DFS(initial, final, diferent_sum)
DFS(initial, final, diferent_bit)
DFS(initial, final, manhadun_space)

# traveled =  181447
# traveled =  18656
# traveled =  1327
# traveled =  247