精华内容
下载资源
问答
  • A*算法之八数码问题 python解法

    千次阅读 多人点赞 2020-11-02 09:18:02
    A*算法之八数码问题 python解法 文章目录A*算法之八数码问题 python解法问题描述A*算法与八数码问题状态空间的定义各种操作的定义启发式函数的定义 人工智能课程中学习了A*算法,在耗费几小时完成了八数码问题和野人...

    A*算法之八数码问题 python解法


    系列文章



    人工智能课程中学习了A*算法,在耗费几小时完成了八数码问题和野人传教士问题之后,决定写此文章来记录一下,避免忘记

    问题描述

    在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
    也就是移动下图中的方块,使得九宫格可以恢复到目标的状态
    在这里插入图片描述

    A*算法与八数码问题

    主要来介绍一下A*算法与该题目如何结合使用,并且使用python语言来实现它

    首先对于A*算法,来做一个简单的介绍


    在这里插入图片描述


    那么对于八数码问题,我们需要做的是把他和A*问题联系在一起
    这里就需要解决3个问题

    1. 状态空间的定义
    2. 各种操作的定义
    3. 启发式函数的定义

    状态空间的定义

    在这里插入图片描述
    首先,本题的状态空间已经很明确了, 就是一个3*3的九宫格,里面充满1-8的数字,加上一个空格,为了方便表示,我们可以把空格用0来表示
    那么状态空间就可以用数组来表示(这里使用numpy来表示)

    import numpy as np
    start_data = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]])
    end_data = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
    

    各种操作的定义

    对于操作,可以理解为更改状态空间的一些规则
    很容易就能想到,如果以每一个元素为对象来讨论,那么它们的上下左右移动最后导致的数组元素交换会稍稍有些复杂,我们不如换一个角度,从空格的移动来考虑
    那么操作(转换规则如下所示)

    1. 空格上移
    2. 空格下移
    3. 空格左移
    4. 空格右移

    当然,这些移动还需要判断一些因素,因为有些情况是无法移动的
    在这里插入图片描述
    如上图情况下就不能下移,所以可以编写一个函数来表示各种操作及其产生的影响
    注: 下面代码是我自己写的,仅供参考,建议按自己的思路写一遍

    def find_zero(num):
        tmp_x, tmp_y = np.where(num == 0)
        # 返回0所在的x坐标与y坐标
        return tmp_x[0], tmp_y[0]
    def swap(num_data, direction):
        x, y = find_zero(num_data)
        num = np.copy(num_data)
        if direction == 'left':
            if y == 0:
                # print('不能左移')
                return num
            num[x][y] = num[x][y - 1]
            num[x][y - 1] = 0
            return num
        if direction == 'right':
            if y == 2:
                # print('不能右移')
                return num
            num[x][y] = num[x][y + 1]
            num[x][y + 1] = 0
            return num
        if direction == 'up':
            if x == 0:
                # print('不能上移')
                return num
            num[x][y] = num[x - 1][y]
            num[x - 1][y] = 0
            return num
        if direction == 'down':
            if x == 2:
                # print('不能下移')
                return num
            else:
                num[x][y] = num[x + 1][y]
                num[x + 1][y] = 0
                return num
    

    测试一下

    num = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
    print('初始状态:')
    print(num)
    print('-' * 50)
    print('左移')
    print(swap(num, 'left'))
    print('-' * 50)
    print('右移')
    print(swap(num, 'right'))
    print('-' * 50)
    print('上移')
    print(swap(num, 'up'))
    print('-' * 50)
    print('下移')
    print(swap(num, 'down'))
    print('-' * 50)
    
    初始状态:
    [[1 2 3]
     [8 0 4]
     [7 6 5]]
    --------------------------------------------------
    左移
    [[1 2 3]
     [0 8 4]
     [7 6 5]]
    --------------------------------------------------
    右移
    [[1 2 3]
     [8 4 0]
     [7 6 5]]
    --------------------------------------------------
    上移
    [[1 0 3]
     [8 2 4]
     [7 6 5]]
    --------------------------------------------------
    下移
    [[1 2 3]
     [8 6 4]
     [7 0 5]]
    --------------------------------------------------
    
    Process finished with exit code 0
    
    

    启发式函数的定义

    f(n)=d(n)+w(n)f(n)=d(n)+w(n)


    其中d(n)d(n)为搜索树的深度,也可以理解为当前是第几轮循环
    w(n)w(n)为当前状态到目标状态的实际最小费用的估计值, 在八数码问题中,可以采用放错位置的数字个数,也可以采用数字到正确位置的曼哈顿距离,因人而异
    在本文中采用的是 w(n)=放错位置的数字个数


    如果将空格位置的正误计算进入,则函数如下

    def cal_wcost(num):
        return sum(sum(num != end_data))
    

    如果不将空格位置的正误计算进入,则函数如下

    def cal_wcost(num):
            return sum(sum(num != end_data)) - int(num[1][1] != 0)
    
    

    也可以用思路最简单的遍历方法

    def cal_wcost(num):
        '''
        计算w(n)的值,及放错元素的个数
        :param num: 要比较的数组的值
        :return: 返回w(n)的值
        '''
        con = 0
        for i in range(3):
            for j in range(3):
                tmp_num = num[i][j]
                compare_num = end_data[i][j]
                if tmp_num != 0:
                    con += tmp_num != compare_num
        return con
    
    

    A*算法代码框架

    先给出我自己定义的代码框架,如果感兴趣的朋友可以用自己的思路去完善它

    import queue
    opened = queue.Queue()  # open表
    closed = {}  # close表
    def method_a_function():
        while len(opened.queue) != 0:
        	# 取队首元素
            node = opened.get()
            # 判断是否为目标值.是则返回正确值
            1.这里需要一条代码/函数
            # 将取出的点加入closed表中
            2.这里需要一条代码/函数
            # 产生取出元素的一切后继,即执行四个操作
            for action in ['left', 'right', 'up', 'down']:
                # 创建子节点
                3.这里需要一条代码/函数
                # 判断是否在closed表中
                4.这里需要一条代码/函数
                	#如果不在close表中,将其加入opened表
                	5.这里需要一条代码/函数(并且考虑到与opened表中已有元素重复的更新情况)
            # 排序
            '''为open表进行排序,根据其中的f_loss值'''
            6.这里需要一条代码/函数
    
    

    A*算法代码代码详解


    根据上面的框架,我们可以一步一步的来完善它


    位置1函数

    只要判断一下是否相等就可以了,非常简单

    if (node.data == end_data).all():
        return node
    

    一、Node类

    首先我创建了一个Node类 ,它具有如下一些属性

    • data很明显用来记录当前的状态
    • step用来记录当前的步数,也就是 g(n) :初始状态到当前状态的距离
    • parent用来记录父节点 (这样可以在得到结论之后通过遍历来获取所有的父节点,从而得到最佳路径)
    • f_loss用来计算f(n)的值
    # 创建Node类 (包含当前数据内容,父节点,步数)
    class Node:
        f_loss = -1  # 启发值
        step = 0  # 初始状态到当前状态的距离(步数)
        parent = None,  # 父节点
    
        # 用状态和步数构造节点对象
        def __init__(self, data, step, parent):
            self.data = data  # 当前状态数值
            self.step = step
            self.parent = parent
            # 计算f(n)的值
            self.f_loss = cal_wcost(data) + step
    

    那么就可以创建初始节点,并且加入opened表中

    start_data = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]])
    opened = queue.Queue()  # open表
    start_node = Node(start_data, 0, None)
    opened.put(start_node)
    
    位置3函数
    child_node = Node(swap(node.data, action), node.step + 1, node)
    

    二、data_to_int函数

    在这里,我定义closed表为一个字典,因为它的键不能放numpy.array,所以我手动写了一个函数把numpy的数组转换为一个int类型的数字
    这里的函数类似于hash函数,不一定要跟我一样,只要保证各种状态产生的结果不同即可

    # 将data转化为不一样的数字 
    def data_to_int(num):
        value = 0
        for i in num:
            for j in i:
                value = value * 10 + j
        return value
    
    位置2的函数
    closed[data_to_int(node.data)] = 1  # 奖取出的点加入closed表中
    

    三、opened表的更新/插入

    这里要判断档要插入的节点是否已经在opened表中出现过,如果出现过,则f_loss更小的节点保留

    # 编写一个比较当前节点是否在open表中,如果在,根据f(n)的大小来判断去留
    def refresh_open(now_node):
        '''
        :param now_node: 当前的节点
        :return:
        '''
        tmp_open = opened.queue.copy()  # 复制一份open表的内容
        for i in range(len(tmp_open)):
            '''这里要比较一下node和now_node的区别,并决定是否更新'''
            data = tmp_open[i]
            now_data = now_node.data
            if (data == now_data).all():
                data_f_loss = tmp_open[i].f_loss
                now_data_f_loss = now_node.f_loss
                if data_f_loss <= now_data_f_loss:
                    return False
                else:
                    print('')
                    tmp_open[i] = now_node
                    opened.queue = tmp_open  # 更新之后的open表还原
                    return True
        tmp_open.append(now_node)
        opened.queue = tmp_open  # 更新之后的open表还原
        return True
    
    位置4,5的函数
    index = data_to_int(child_node.data) # 获取当前节点转换后的index值
    if index not in closed:
        refresh_open(child_node)
    

    四、opened表排序

    按照f_loss从小到大排序,这里我使用最传统的排序方法,有许多可以改进的地方,也可以用python的排序方法结合lambda函数来使用

    # 编写一个给open表排序的函数
    def sorte_by_floss():
        tmp_open = opened.queue.copy()
        length = len(tmp_open)
        # 排序,从小到大,当一样的时候按照step的大小排序
        for i in range(length):
            for j in range(length):
                if tmp_open[i].f_loss < tmp_open[j].f_loss:
                    tmp = tmp_open[i]
                    tmp_open[i] = tmp_open[j]
                    tmp_open[j] = tmp
                if tmp_open[i].f_loss == tmp_open[j].f_loss:
                    if tmp_open[i].step > tmp_open[j].step:
                        tmp = tmp_open[i]
                        tmp_open[i] = tmp_open[j]
                        tmp_open[j] = tmp
        opened.queue = tmp_open
    
    位置6的函数
    sorte_by_floss()
    

    五、结果的输出

    首先编写output_result函数,依次获取目标节点的父节点,形成一条正确顺序的路径
    然后使用循环将这条路径输出
    这里为了输出的好看,我使用了prettytable这个库,当然也可以直接输出

    def output_result(node):
        all_node = [node]
        for i in range(node.step):
            father_node = node.parent
            all_node.append(father_node)
            node = father_node
        return reversed(all_node)
    
    
    node_list = list(output_result(result_node))
    tb = pt.PrettyTable()
    tb.field_names = ['step', 'data', 'f_loss']
    for node in node_list:
        num = node.data
        tb.add_row([node.step, num, node.f_loss])
        if node != node_list[-1]:
            tb.add_row(['---', '--------', '---'])
    print(tb)
    
    
    总共耗费6轮
    +------+-----------+--------+
    | step |    data   | f_loss |
    +------+-----------+--------+
    |  0   |  [[2 8 3] |   4    |
    |      |   [1 6 4] |        |
    |      |  [7 0 5]] |        |
    | ---  |  -------- |  ---   |
    |  1   |  [[2 8 3] |   4    |
    |      |   [1 0 4] |        |
    |      |  [7 6 5]] |        |
    | ---  |  -------- |  ---   |
    |  2   |  [[2 0 3] |   5    |
    |      |   [1 8 4] |        |
    |      |  [7 6 5]] |        |
    | ---  |  -------- |  ---   |
    |  3   |  [[0 2 3] |   5    |
    |      |   [1 8 4] |        |
    |      |  [7 6 5]] |        |
    | ---  |  -------- |  ---   |
    |  4   |  [[1 2 3] |   5    |
    |      |   [0 8 4] |        |
    |      |  [7 6 5]] |        |
    | ---  |  -------- |  ---   |
    |  5   |  [[1 2 3] |   5    |
    |      |   [8 0 4] |        |
    |      |  [7 6 5]] |        |
    +------+-----------+--------+
    
    Process finished with exit code 0
    
    

    六、代码

    可能还是给全代码比较省力

    # -*- coding: utf-8 -*-
    # @Time    : 2020/10/29 21:37
    # @Author  : Tong Tianyu
    # @File    : 八数码问题.py
    # @Question: A* 算法解决八数码问题
    import numpy as np
    import queue
    import prettytable as pt
    
    '''
    初始状态:             目标状态:
    2 8 3                1 2 3
    1 6 4                8   4
    7   5                7 6 5   
    '''
    start_data = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]])
    end_data = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
    
    '准备函数'
    
    
    
    
    # 找空格(0)号元素在哪的函数
    def find_zero(num):
        tmp_x, tmp_y = np.where(num == 0)
        # 返回0所在的x坐标与y坐标
        return tmp_x[0], tmp_y[0]
    
    
    # 交换位置的函数 移动的时候要判断一下是否可以移动(是否在底部)
    # 记空格为0号,则每次移动一个数字可以看做对空格(0)的移动,总共有四种可能
    
    def swap(num_data, direction):
        x, y = find_zero(num_data)
        num = np.copy(num_data)
        if direction == 'left':
            if y == 0:
                # print('不能左移')
                return num
            num[x][y] = num[x][y - 1]
            num[x][y - 1] = 0
            return num
        if direction == 'right':
            if y == 2:
                # print('不能右移')
                return num
            num[x][y] = num[x][y + 1]
            num[x][y + 1] = 0
            return num
        if direction == 'up':
            if x == 0:
                # print('不能上移')
                return num
            num[x][y] = num[x - 1][y]
            num[x - 1][y] = 0
            return num
        if direction == 'down':
            if x == 2:
                # print('不能下移')
                return num
            else:
                num[x][y] = num[x + 1][y]
                num[x + 1][y] = 0
                return num
    
    
    # 编写一个用来计算w(n)的函数
    def cal_wcost(num):
        '''
        计算w(n)的值,及放错元素的个数
        :param num: 要比较的数组的值
        :return: 返回w(n)的值
        '''
        # return sum(sum(num != end_data)) - int(num[1][1] != 0)
        con = 0
        for i in range(3):
            for j in range(3):
                tmp_num = num[i][j]
                compare_num = end_data[i][j]
                if tmp_num != 0:
                    con += tmp_num != compare_num
        return con
    
    
    # 将data转化为不一样的数字 类似于hash
    def data_to_int(num):
        value = 0
        for i in num:
            for j in i:
                value = value * 10 + j
        return value
    
    
    # 编写一个给open表排序的函数
    def sorte_by_floss():
        tmp_open = opened.queue.copy()
        length = len(tmp_open)
        # 排序,从小到大,当一样的时候按照step的大小排序
        for i in range(length):
            for j in range(length):
                if tmp_open[i].f_loss < tmp_open[j].f_loss:
                    tmp = tmp_open[i]
                    tmp_open[i] = tmp_open[j]
                    tmp_open[j] = tmp
                if tmp_open[i].f_loss == tmp_open[j].f_loss:
                    if tmp_open[i].step > tmp_open[j].step:
                        tmp = tmp_open[i]
                        tmp_open[i] = tmp_open[j]
                        tmp_open[j] = tmp
        opened.queue = tmp_open
    
    
    # 编写一个比较当前节点是否在open表中,如果在,根据f(n)的大小来判断去留
    def refresh_open(now_node):
        '''
        :param now_node: 当前的节点
        :return:
        '''
        tmp_open = opened.queue.copy()  # 复制一份open表的内容
        for i in range(len(tmp_open)):
            '''这里要比较一下node和now_node的区别,并决定是否更新'''
            data = tmp_open[i]
            now_data = now_node.data
            if (data == now_data).all():
                data_f_loss = tmp_open[i].f_loss
                now_data_f_loss = now_node.f_loss
                if data_f_loss <= now_data_f_loss:
                    return False
                else:
                    print('')
                    tmp_open[i] = now_node
                    opened.queue = tmp_open  # 更新之后的open表还原
                    return True
        tmp_open.append(now_node)
        opened.queue = tmp_open  # 更新之后的open表还原
        return True
    
    
    # 创建Node类 (包含当前数据内容,父节点,步数)
    class Node:
        f_loss = -1  # 启发值
        step = 0  # 初始状态到当前状态的距离(步数)
        parent = None,  # 父节点
    
        # 用状态和步数构造节点对象
        def __init__(self, data, step, parent):
            self.data = data  # 当前状态数值
            self.step = step
            self.parent = parent
            # 计算f(n)的值
            self.f_loss = cal_wcost(data) + step
    
    
    '算法'
    opened = queue.Queue()  # open表
    start_node = Node(start_data, 0, None)
    opened.put(start_node)
    
    closed = {}  # close表
    
    
    def method_a_function():
        con = 0
        while len(opened.queue) != 0:
            node = opened.get()
            if (node.data == end_data).all():
                print(f'总共耗费{con}轮')
                return node
    
            closed[data_to_int(node.data)] = 1  # 奖取出的点加入closed表中
            # 四种移动方法
            for action in ['left', 'right', 'up', 'down']:
                # 创建子节点
                child_node = Node(swap(node.data, action), node.step + 1, node)
                index = data_to_int(child_node.data)
                if index not in closed:
                    refresh_open(child_node)
            # 排序
            '''为open表进行排序,根据其中的f_loss值'''
            sorte_by_floss()
            con += 1
    
    
    result_node = method_a_function()
    
    
    def output_result(node):
        all_node = [node]
        for i in range(node.step):
            father_node = node.parent
            all_node.append(father_node)
            node = father_node
        return reversed(all_node)
    
    
    node_list = list(output_result(result_node))
    tb = pt.PrettyTable()
    tb.field_names = ['step', 'data', 'f_loss']
    for node in node_list:
        num = node.data
        tb.add_row([node.step, num, node.f_loss])
        if node != node_list[-1]:
            tb.add_row(['---', '--------', '---'])
    print(tb)
    
    
    展开全文
  • 回溯法解决八数码问题python

    千次阅读 2017-04-11 21:18:59
    这次人工智能的作业就是用回溯法解决八数码问题,经过一天多的功夫,终于写出来了。下面是正题回溯法是人工智能领域的一种重要的盲目搜索算法,何为盲目算法,即是基于规则,不断的尝试可能的路径,直到到达目的的解...

    这次人工智能的作业就是用回溯法解决八数码问题,经过一天多的功夫,终于写出来了。下面是正题

    回溯法是人工智能领域的一种重要的盲目搜索算法,何为盲目算法,即是基于规则,不断的尝试可能的路径,直到到达目的的解为止。
    回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
    回溯法一般需要三张表
    ps表:用于保存当前路径的状态,如果找到目标状态,ps就是解题路径上的状态有序集。
    nps表:新的路径状态表。它包含了等待搜索的状态,其后裔状态还未被搜索到即未生成扩展。
    nss表:不可解状态集,列出了找不到解题路径的状态,如果在搜索中扩展出的状态是该表的元素,则将该状态排除。
    此外,八数码还有一个书否有解的条件,即初始状态和目标状态的逆序数奇偶性相同。
    逆序数:一个状态表示成一维的形式,求出除0之外所有数字的逆序数之和,也就是每个数字前面比它大的数字的个数的和,称为这个状态的逆序。
    回溯法搜索过程示意图如下所示:
    这里写图片描述
    其搜索起点为A初始值:ps=[A], nps=[A],nss=[],目标点为G

    0 搜索点 ps nps nss
    1 A [A] [A] [ ]
    2 B [BA] [BCDA] [ ]
    3 E [EBA] [EFBCDA] [ ]
    4 I [IJEBA] [IJEFBCD] [ ]
    5 J [JEBA] [JEFBCDA] [I]
    6 F [FBA] [FBCDA] [EJI]
    7 K [KFBA] [KFBCDA] [EJI]
    8 C [CA] [CDA] [BFKEJI]
    9 G [GCA] [GHCDA] [BFKEJI]

    在搜索过程中,先进行深度搜索,直到到达指点深度,或者不可解点返回,并将该状态置为不可解点,然后回到上一节点进行扩展。直到找到结果或者搜完所有深度为止。
    回溯法实现八数码思路亦是如此
    初始状态 :
    2 8 3
    1 6 4
    7 0 5

    目标状态:
    1 2 3
    8 0 4
    7 6 5

    下面是python代码,数码的状态用一维数组表示
    节点状态类Node.py

    #encoding:utf-8
    from Node import *
    class back:
        def __init__(self,orignate,target,length):
            self.origate=orignate  #初始状态
            self.target=target  #目标状态
            self.ps=[]  #PS表,用于保存当前搜索路径的状态
            self.nps=[] #nps表,用于保存等待搜索的状态
            self.nss=[] #nss表,用于保存不可到达目的地的状态集
            self.spce=[-3,3,-1,1] #上下左右四个移动方向
            self.length=length
            self.MaxDegree=5  #深度限制,到达此深度回溯
    
        def issolve(self): #判断到目标状态是否有解
            targetVer=self.getreVersNum(self.target.state)
            orinateVer=self.getreVersNum(self.origate.state)
            if(targetVer%2!=orinateVer%2):
                return False
            else:
                return True
    
    
    
        def getreVersNum(self,state):  #获取逆序数
            sum=0
            for i in range(0,len(state)):
                if(state[i]==0):
                    continue
                else:
                    for j in range(0,i):
                        if(state[j]>state[i]):
                            sum+=1
    
            return sum
    
        # def getspaceIndex(self): #获得空格所在的位置
        #     for i in range(len(self.origate)-1):
        #         if(self.origate[i]==0):
        #             return i
    
        def copyArray(self,state):
            arr=[]
            return arr+state
    
    
        #判断状态数码是否存在
        def isexit(self,node,table):
            for i in table:
                if(i.state==node.state):
                    return True
            return False
    
    
    
    
        #主要算法,回溯过程
        def backMainProcess(self):
            self.ps.append(self.origate)
            self.nps.append(self.origate)
            while(len(self.nps)):
                originateState=self.ps[-1]
    
                spacIndex=originateState.state.index(0)
                if(originateState.state==self.target.state):
                    return True
                else:
    
                    #到达指定深度,回溯
                    if(originateState.degree>=self.MaxDegree):
    
    
                        self.ps.pop()
                        self.nps.pop()
                        if(self.nps[-1]!=self.ps[-1]):
    
                          self.ps.append(self.nps[-1])
                        self.nss.insert(0,originateState)
                        continue
                    flag=False
                    for i in range(len(self.spce)):
    
                        if((i==0 and (spacIndex+self.spce[i])>=0) or
                        (i==1 and (spacIndex+self.spce[i])<len(self.target.state)-1)
                        or(i==2 and (spacIndex%self.length!=0 )) or
                        (i==3 and ((spacIndex+1)%self.length)!=0)):
                            state=self.copyArray(originateState.state)
                            #扩展状态
                            temp=state[spacIndex+self.spce[i]]
                            state[spacIndex+self.spce[i]]=0
                            state[spacIndex]=temp
                            #判断新的状态是否已经存在
                            nodeState=Node(state,originateState.degree+1)
    
                            if(self.isexit(nodeState,self.nps))or (self.isexit(nodeState,self.nss)):
                                continue
                            else:
                                flag=True
    
                                self.nps.append(nodeState)
                    if(not flag):
    
                        self.ps.pop()
                        self.nps.pop()
                        if(self.nps[-1]!=self.ps[-1]):
                          self.ps.append(self.nps[-1])
                        self.nss.append(originateState)
                    if(flag):#展开有子节点
                        self.ps.append(self.nps[-1])
        #输出结果路径
        def showLine(self):
            for node in self.ps:
                i=0
                print(node.state[i],node.state[i+1],node.state[i+2])
                print(node.state[i+3],node.state[i+4],node.state[i+5])
                print(node.state[i+6],node.state[i+7],node.state[i+8])
                print('->:')
    
    
    
    
    
    
    
    
    if __name__ == '__main__':
    
    
        originate=[2,8,3,1,6,4,7,0,5]
        target=[1,2,3,8,0,4,7,6,5]
        node1=Node(originate,0)
        node2=Node(target,0)
        c=back(node1,node2,3)
        if(c.issolve()):
            if(c.backMainProcess()):
                print('已找到解!!!!,路径如下')
                c.showLine()
        else:
            print('此过程无解')
    
    
    
    
    
    
    
    
    
    
    
    
    

    运行结果:

    已找到解!!!!,路径如下
    (2, 8, 3)
    (1, 6, 4)
    (7, 0, 5)
    ->:
    (2, 8, 3)
    (1, 0, 4)
    (7, 6, 5)
    ->:
    (2, 0, 3)
    (1, 8, 4)
    (7, 6, 5)
    ->:
    (0, 2, 3)
    (1, 8, 4)
    (7, 6, 5)
    ->:
    (1, 2, 3)
    (0, 8, 4)
    (7, 6, 5)
    ->:
    (1, 2, 3)
    (8, 0, 4)
    (7, 6, 5)
    ->:
    
    展开全文
  • def DFS(): deq = [] appear = set()#使用set进行检索极快,hash检索 temp = board() appear.add(list2str(temp.groud)) for x in temp.can_move(): b = board() b.move_one(x) b.route.append(x) ...
  • class board(object): def __init__(self): # self.groud = [1,0,2,3,4,5,6,7,8] # 棋盘,0代表空 self.groud = [7, 2, 4, 5, 0, 6, 8, 3, 1] #移动的路径 self.route = [] def __lt__(self,other): ...
  • 上一年的人工智能课就已经把八数码的BFS DFS A* ...题目如图,首先我们先建立一个棋盘类来进行八数码问题的操作. class board: def __init__(self): # self.groud = [1,0,2,3,4,5,6,7,8] # 棋盘,0代表空 self.groud

    上一年的人工智能课就已经把八数码的BFS DFS A* 遗传算法都试了一遍.昨天上传旧的时候觉得实现的不是很优雅,现在想重新用python来一遍.这次我实现了一个很大的突破,起码比原来的算法实现的速度提高了几十倍~
    在这里插入图片描述
    题目如图,首先我们先建立一个棋盘类来进行八数码问题的操作.

    class board:
        def __init__(self):
            # self.groud = [1,0,2,3,4,5,6,7,8]
            # 棋盘,0代表空
            self.groud = [7, 2, 4, 5, 0, 6, 8, 3, 1]
            #移动的路径
            self.route = []
    # 是否到达正确状态
        def guiwei(self):
            flag = True
            for i in range(9):
                if self.groud[i] != i:
                    flag = False
                    break
            return flag
    # 两个位置数字进行交换
        def exchange(self, index1, index2):
            temp = self.groud[index1]
            self.groud[index1] = self.groud[index2]
            self.groud[index2] = temp
    # 空格向左移动
        def left(self):
            index = self.groud.index(0)
            if index % 3 != 0:
                self.exchange(index, index-1)
    # 空格向右移动
        def right(self):
            index = self.groud.index(0)
            if index % 3 != 2:
                self.exchange(index, index+1)
    # 空格向上移动
        def up(self):
            index = self.groud.index(0)
            if int(index/3) != 0:
                self.exchange(index, index-3)
    # 空格向下移动
        def down(self):
            index = self.groud.index(0)
            if int(index/3) != 2:
                self.exchange(index, index+3)
    # 返回空格能移动的方位的列表,比如[0,1,2,3]代表空格能向左右上下进行移动
        def can_move(self):
            index = self.groud.index(0)
            can = []
            if index % 3 != 0:
                can.append(0)
            if index % 3 != 2:
                can.append(1)
            if int(index/3) != 0:
                can.append(2)
            if int(index/3) != 2:
                can.append(3)
            return can
    # 展示棋盘
        def show_board(self):
            print(self.groud)
    # 路径
        def show_route(self):
            print(self.route)
            print(len(self.route))
    # 通过route路径进行移动,route是路径列表
        def move(self, route):
            for i in route:
                if i == 0:
                    self.left()
                elif i == 1:
                    self.right()
                elif i == 2:
                    self.up()
                else:
                    self.down()
    # 仅移动一步
        def move_one(self, i):
            if i == 0:
                self.left()
            elif i == 1:
                self.right()
            elif i == 2:
                self.up()
            else:
                self.down()
    # 测试如果向目标方向移动,棋盘的变化,返回变化的棋盘
        def test(self, i):
            groud = []
            if i == 0:
                self.left()
                groud = self.groud[:]
                self.right()
            elif i == 1:
                self.right()
                groud = self.groud[:]
                self.left()
            elif i == 2:
                self.up()
                groud = self.groud[:]
                self.down()
            else:
                self.down()
                groud = self.groud[:]
                self.up()
            return groud
    
    

    然后我先写出来了一个没有任何优化的极简BFS

    from board import board
    def BFS_waste_time():
        deq = []
        b = board()
        for x in b.can_move():
            deq.append([x])
        flag = 0
        while True:
            flag+=1
            temp = deq.pop(0)
            if flag%10000==0:
                flag=0
                print(temp)
                print(len(temp)) 
            b_temp = board()
            b_temp.move(temp)
            if  b_temp.guiwei():
                print(temp)
                break
            for x in b_temp.can_move():
                new_temp=temp[:]
                new_temp.append(x)
                deq.append(new_temp)   
    

    很简单通过队列,先进后出就能实现.这个算法是没有问题的,实现也没有问题,就是这么个暴力计算的话需要算很久才能算出来.接下来这个是经过我优化的.

    import copy
    def list2str(li):
        s = ""
        for x in li:
            s+=str(x)
        return s
    def BFS():
        deq = []
        appear = set()#使用set进行检索极快,hash检索
        temp = board()
        appear.add(list2str(temp.groud))
        for x in temp.can_move():
            b = board()
            b.move_one(x)
            b.route.append(x)
            appear.add(list2str(b.groud))
            deq.append(b)
        flag = 0
        while True:
            flag+=1
            temp = deq.pop(0)
            if flag%10000==0:
                flag=0
                temp.show_board() 
                temp.show_route()
    
            if  temp.guiwei():
                temp.show_board() 
                temp.show_route()
                break
            for x in temp.can_move():
                # 筛选掉重复的棋盘情况,加快搜索速度
                if list2str(temp.test(x)) not in appear:
                    new_temp=copy.deepcopy(temp)
                    new_temp.move_one(x)
                    new_temp.route.append(x)
                    deq.append(new_temp)
                    appear.add(list2str(new_temp.groud)) 
    

    提高的速度比简单的BFS提升速度少说几千倍~比优化过的JAVA版快了几十倍.优化重点:

    • 重复的棋盘就不要入队了.在移动过程中大概率会出现这种情况,移动了几步回到了原来的棋盘的情况.我们将出现过的棋盘情况全部记录下来放在appear,移动后如果是新棋盘就入队,如果不是就不再入队进行搜索.
    • 由于每次都需要进行appear的检索,如果单纯地使用路径列表进行检索的话很慢很慢.我搜索了一下知道一件事情,set()集合的搜索是可以使用哈希值进行搜索的,复杂度为O(1),所以,将路径转化为字符串(字符串才是可哈希的),然后使用字符串进行检索,速度直接起飞~

    其它尝试了的优化,这些优化可能影响不大

    • 尝试过使用cython提高效率,但是不是很明显
    • test函数的出现是因为觉得复制可能比较耗时,所以就使用test函数进行.
    代码 时间
    JAVA没注意哈希检索版 658.932 s
    python哈希优化版 13.831229 s

    在这里插入图片描述
    在这里插入图片描述
    说明:JAVA的路径是指0的位置(设计的不是很优雅,前面两个4就是0一开始就在4的位置) python的路径是移动的方向

    总结:在BFS中尝试了很多方法进行速度优化,从算法层面来讲,剪枝应该就是BFS中比较好用的优化方法了,后面的哈希表以及cython个人觉得属于代码方面的优化了.不过哈希也是算法,第一次切身体会到数据结构上的优化带来的巨大提升.

    展开全文
  •  之前看过经典的搜索路径方法,印象较深的也就BFS(广度优先),DFS(深度优先)以及A*搜索,但没实践过,就借八数码问题,来通通实现遍,观察下现象呗~~~ 首先,怎么说也得把数码这玩意基本操作实现了呗!上代码~...

        哎,好久没写博文了,其实仔细想来,时间还是蛮多的,以后还是多写写吧!

        之前看过经典的搜索路径方法,印象较深的也就BFS(广度优先),DFS(深度优先)以及A*搜索,但没实践过,就借八数码问题,来通通实现遍,观察下现象呗~~~

            首先,怎么说也得把数码这玩意基本操作实现了呗!上代码~

    class puzzled:
        def __init__(self,puzzled):
            self.puzzled=puzzled
            self.__getPuzzledInfo()
            
        def __getPuzzledInfo(self):
            self.puzzledWid=len(self.puzzled[0])
            self.puzzledHei=len(self.puzzled)
            self.__f1=False
            for i in range(0,self.puzzledHei):
                for j in range(0,self.puzzledWid):
                    if(self.puzzled[i][j]==0):
                        self.zeroX=j
                        self.zeroY=i
                        self.__f1=True
                        break
                if(self.__f1):
                    break
        def printPuzzled(self):
            for i in range(0,len(self.puzzled)):
                print self.puzzled[i]
            print ""
                
        def isRight(self):
            if(self.puzzled[self.puzzledHei-1][self.puzzledWid-1]!=0):
                return False
            for i in range(0,self.puzzledHei):
                for j in range(0,self.puzzledWid):
                    if(i*self.puzzledWid+j+1!=self.puzzled[i][j]):
                        if(i!=self.puzzledHei-1 or j!=self.puzzledWid-1):
                            return False
            return True
        def move(self,dere):#0 up,1 down,2 left,3 right
            if(dere==0 and self.zeroY!=0):
                self.puzzled[self.zeroY-1][self.zeroX],self.puzzled[self.zeroY][self.zeroX] = self.puzzled[self.zeroY][self.zeroX],self.puzzled[self.zeroY-1][self.zeroX]
                self.zeroY-=1
                return True
            
            
            elif(dere==1 and self.zeroY!=self.puzzledHei-1):
                self.puzzled[self.zeroY+1][self.zeroX],self.puzzled[self.zeroY][self.zeroX] = self.puzzled[self.zeroY][self.zeroX],self.puzzled[self.zeroY+1][self.zeroX]
                self.zeroY+=1            
                return True
            
            
            elif(dere==2 and self.zeroX!=0):
                self.puzzled[self.zeroY][self.zeroX-1],self.puzzled[self.zeroY][self.zeroX] = self.puzzled[self.zeroY][self.zeroX],self.puzzled[self.zeroY][self.zeroX-1]
                self.zeroX-=1
                return True
            
            elif(dere==3 and self.zeroX!=self.puzzledWid-1):
                self.puzzled[self.zeroY][self.zeroX+1],self.puzzled[self.zeroY][self.zeroX] = self.puzzled[self.zeroY][self.zeroX],self.puzzled[self.zeroY][self.zeroX+1]
                self.zeroX+=1
                return True
            return False
        def getAbleMove(self):
            a=[]
            if(self.zeroY!=0):
                a.append(0)
            if(self.zeroY!=self.puzzledHei-1):
                a.append(1)
            if(self.zeroX!=0):
                a.append(2)
            if(self.zeroX!=self.puzzledWid-1):
                a.append(3)             
            return a
        def clone(self):
            a=copy.deepcopy(self.puzzled)
            return puzzled(a)
        def toString(self):
            a=""
            for i in range(0,self.puzzledHei):
                for j in range(0,self.puzzledWid):
                    a+=str(self.puzzled[i][j])
            return a
        def isEqual(self,p):
            if(self.puzzled==p.puzzled):
                return True
            return False
        def toOneDimen(self):
            a=[]
            for i in range(0,self.puzzledHei):
                for j in range(0,self.puzzledWid):
                    a.append(self.puzzled[i][j])
            return a
        
        
        def getNotInPosNum(self):
            t=0
            for i in range(0,self.puzzledHei):
                for j in range(0,self.puzzledWid):
                    if(self.puzzled[i][j]!=i*self.puzzledWid+j+1):
                        if(i==self.puzzledHei-1 and j==self.puzzledWid-1 and self.puzzled[i][j]==0):
                            continue
                        t+=1
            return t
        def getNotInPosDis(self):
            t=0
            it=0
            jt=0
            for i in range(0,self.puzzledHei):
                for j in range(0,self.puzzledWid):
                    if(self.puzzled[i][j]!=0):
                        it=(self.puzzled[i][j]-1)/self.puzzledWid
                        jt=(self.puzzled[i][j]-1)%self.puzzledWid
                    else:
                        it=self.puzzledHei-1
                        jt=self.puzzledWid-1
                    t+=abs(it-i)+abs(jt-j)
            return t    
        @staticmethod
        def generateRandomPuzzle(m,n,ran):
            
            tt=[]
            for i in range(0,m):
                t=[]
                for j in range(0,n):
                    t.append(j+1+i*n)
                tt.append(t)
            tt[m-1][n-1]=0
            a=puzzled(tt)
            i=0
            while(i<ran):
                i+=1
                a.move(random.randint(0,4))
            return a

    稍微注解一下,puzzled类表示一个数码类,初始化利用

    a=puzzled(  [1,2,3],
                [4,5,6],
                [7,8,0])

    其中呢,0表示空格位置,上面初始化的便是一个正确的,未被打乱的位置~

    其他的成员函数,看名称就很好理解了呗~

    ok,基础打好了,接下来就该上节点类了:

    class node:
        def __init__(self,p):
            self.puzzled=p
            self.childList=[]
            self.father=None
        def addChild(self,child):
            self.childList.append(child)
            child.setFather(self)
        def getChildList(self):
            return self.childList
        def setFather(self,fa):
            self.father=fa
        def displayToRootNode(self):
            t=self
            tt=0
            while(True):
                tt+=1
                t.puzzled.printPuzzled()
                t=t.father
                if(t==None):
                    break
            print "it need "+str(tt)+ " steps!"
        def getFn(self):
            fn=self.getGn()+self.getHn() #A*
            #fn=self.getHn() #贪婪
            return fn
            
        def getHn(self):
            Hn=self.puzzled.getNotInPosDis()
            return Hn
            
        def getGn(self):
            gn=0
            t=self.father
            while(t!=None):
                gn+=1
                t=t.father
            return gn

    对于节点类吧,也还是很好理解的,初始化方法

        a=node(
        puzzled([1,2,3],
                [4,5,6],
                [7,8,0])
                )

    基础都搭好了,重点人物该闪亮登场了呗~

    class seartchTree:
        def __init__(self,root):
            self.root=root
            
        def __search2(self,hlist,m):  #二分查找,经典算法,从大到小,返回位置
                                      #若未查找到,则返回应该插入的位置
            low = 0   
            high = len(hlist) - 1   
            mid=-1
            while(low <= high):  
                mid = (low + high)/2  
                midval = hlist[mid]  
        
                if midval > m:  
                    low = mid + 1   
                elif midval < m:  
                    high = mid - 1   
                else:  
                    return (True,mid)   
            return (False,mid)   
            
        def __sortInsert(self,hlist,m):#对于一个从大到小的序列,
                                        #插入一个数,仍保持从大到小
            t=self.__search2(hlist,m)
            if(t[1]==-1):
                hlist.append(m)
                return 0
            if(m<hlist[t[1]]):
                hlist.insert(t[1]+1, m)
                return t[1]+1
            else:
                hlist.insert(t[1], m)
                return t[1]    
        
        def breadthFirstSearch(self):#广度优先搜索
            numTree=NumTree.NumTree()
            numTree.insert(self.root.puzzled.toOneDimen())
            t=[self.root]
            flag=True
            generation=0
            while(flag):
                print "it's the "+str(generation)+" genneration now,the total num of items is "+str(len(t))
                tb=[]
                for i in t:
                    if(i.puzzled.isRight()==True):
                        i.displayToRootNode()
                        flag=False
                        break
                    else:
                        for j in i.puzzled.getAbleMove():
                            tt=i.puzzled.clone()
                            tt.move(j)
                            a=node(tt)
                            if(numTree.searchAndInsert(a.puzzled.toOneDimen())==False):
                                i.addChild(a)
                                tb.append(a)
                t=tb
                generation+=1
                
        def depthFirstSearch(self):#深度优先搜索
            numTree=NumTree.NumTree()
            numTree.insert(self.root.puzzled.toOneDimen())        
            t=self.root
            flag=True
            gen=0
            while(flag):
                bran=0
                print "genneration: "+str(gen)
                if(t.puzzled.isRight()==True):
                    t.displayToRootNode()
                    flag=False
                    break
                else:
                    f1=True
                    for j in t.puzzled.getAbleMove():
                        tt=t.puzzled.clone()
                        tt.move(j)
                        a=node(tt)
                        if(numTree.searchAndInsert(a.puzzled.toOneDimen())==False):
                            t.addChild(a)
                            t=a
                            f1=False
                            gen+=1
                            break
                    if(f1==True):
                        t=t.father
                        gen-=1
                        
                        
        def AStarSearch(self):#A*
            numTree=NumTree.NumTree()
            numTree.insert(self.root.puzzled.toOneDimen())        
            leaves=[self.root]
            leavesFn=[0]
            while True:
                t=leaves.pop()  #open表
                print leavesFn.pop()
                if(t.puzzled.isRight()==True):
                    t.displayToRootNode()
                    break
                for i in t.puzzled.getAbleMove():
                    tt=t.puzzled.clone()
                    tt.move(i)
                    a=node(tt)
                    if(numTree.searchAndInsert(a.puzzled.toOneDimen())==False):#close表
                        t.addChild(a)
                        fnS=self.__sortInsert(leavesFn,a.getFn())
                        leaves.insert(fnS, a)

        注意到里面存在一个 NumTree,这个是个啥玩意了,这个吧,其实是一个closed表,啥是Closed表呢?

        就是呀,在搜索的时候,得记录已经扩展的节点,不然的话很有可能成为不完备的搜索了(对于深度搜索),而且已经扩展的状态,也对于数码问题没必要在扩展一次,那么怎么来实现记录已经扩展的节点呢?

        一个最简单的方法就是建立一个链表,将扩展的节点加进去,但这样存在一个问题,就是由于每次在扩展节点时都得遍历closed表,查找是否存在同样的节点已经被扩展,这样,复杂度就简直太高了,完全不行呗~

        那么咋办呢?从上面代码注意到,node对象里面有一个Puzzled成员,实际上puzzled对象主要就由一个二维数组构成呗~这时候呀,我就把这个二维数组变为一维呗

    [1,2,3],                  
    [4,5,6],         ->   [1,2,3,4,5,6,7,8,0]    
    [7,8,0]

    然后呢,利用trie树存储该数组,这样一来,查找添加一步到位!

    也就是上面代码中的这个啦~

    numTree.searchAndInsert(a.puzzled.toOneDimen())

    贴上numtree代码:

    class NumTree:
        def __init__(self):
            self.root = Node()
    
        def insert(self, key):      # key is of type string                                                                                                                
            # key should be a low-case string, this must be checked here!                                                                                                  
            node = self.root
            for char in key:
                if char not in node.children:
                    child = Node()
                    node.children[char] = child
                    node = child
                else:
                    node = node.children[char]
            node.value = key
    
        def search(self, key):
            node = self.root
            for char in key:
                if char not in node.children:
                    return None
                else:
                    node = node.children[char]
            return node.value
    
        def display_node(self, node):
            if (node.value != None):
                print node.value
            for char in node.children.keys():
                if char in node.children:
                    self.display_node(node.children[char])
            return
    
        def display(self):
            self.display_node(self.root)
            
        def searchAndInsert(self,m):
            if(self.search(m)==None):
                self.insert(m)
                return False
            return True
            
                
    """test
    
    trie = NumTree()
    print trie.searchAndInsert([1,2,3,4,5,6,7,8])
    print trie.searchAndInsert([1,2,3,4,5,6,7,8,9])
    
    trie.display()
    """

    好了,这样再看searchTree的代码就比较清晰了呗,

    哎,好吧,我承认这等低劣之作也只有我等渣渣才能写出,其实再看时,可以发现很多地方都可以优化的,比如二维转一维,这个其实花费的不少时间,其实可以在内部以一维形式存在的~


    本文出自 “Rainlee的随笔记” 博客,请务必保留此出处http://rainlee.blog.51cto.com/7389753/1758071

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,433
精华内容 2,573
关键字:

八数码问题python

python 订阅