本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-07(4)

2020-08(27)

Python实现用BFS、DFS和A*算法解决8数码问题

发布于2021-01-26 19:23     阅读(180)     评论(0)     点赞(5)     收藏(4)



作为小白的我写这篇博客的时候内心瑟瑟发抖,表达文案能力有限,以下是我对8数码问题的一下小见解,如内容有错误,请在评论区讨论(最好改正并告知我),请大家多多包涵。

思路参考博客:https://blog.csdn.net/u013300280/article/details/106234521

8数码问题:

8数码问题又称九宫格问题,在3x3的棋盘上,问题的解决是移动空格使得8数码从初始状态到目标状态。

8数码是否有解
判断8数码逆序的奇偶性
若两个状态的逆序奇偶性相同,则可相互到达,否则不可相互到达
可以参考:https://blog.csdn.net/hnust_xiehonghao/article/details/7951173

BFS(宽度优先搜索):

其基本思想是优先搜索当前顶点的所有邻接结点。
基本步骤:
①建立只含有初始节点S的搜索图G,把S放到open表中;
②建立closed表,其初始值为空表;
③若open表是空表,则失败退出;
④选择open表中第一个节点,把它从open表移出并放进closed表中,称此节点为当前节点;
⑤若当前节点为目标节点,则有解并成功退出。
⑥扩展当前节点,并把子节点放到open表的后面。

代码:

'''
author:Ning_Y_N
date:2020-10-27
'''
import random  # 引入导包

#修改索引,方便接下来交换
def move(str,index):
    if str=='up':
        return index-3
    if str=='dowm':
        return index+3
    if str=='left':
        return  index-1
    if str=='right':
        return index+1

#生成新的结点并且记录路径
def path(array1,array2):
    p=array1[:]
    p.insert(0,array2)
    for i in close:
        if i[0] == p[0]:
             return False
    open.append(p)
    return True

#打印
def out(list):
    for j in range(len(list)):
        if j % 3 == 0:
            print('\t')
        print(list[j], end=' ')
    print('\t')

#判断8数码逆序的奇偶性
#若两个状态的逆序奇偶性相同,则可相互到达,否则不可相互到达
def issolution(array):
    num = 0
    for i in range(len(array) - 1):
        for j in range(i + 1, len(array)):
            if array[i] == 0 or array[j] == 0:
                continue
            if array[i] < array[j]:
                num += 1
    return num%2

'''
#随机生成初始状态
def rand(list):
    a = random.randint(0, 8)
    list.append(a)
    for i in range(8):
        i = random.randint(0, 8)
        while 1:
            if i not in list:
                list.append(i)
                break
            else:
                i = random.randint(0, 8)
'''
if __name__=="__main__":
    #start=[]
    #rand(start)
    # orgin=input(">>").split()    #自行输出8数码初始状态
    # start=[int(x) for x in orgin]
    start=[2,8,3,1,6,4,7,0,5]
    #start = [2, 8, 3, 1, 0, 4, 7, 6, 5]
    goal = [1, 2, 3, 8, 0, 4, 7, 6, 5]
    #如果初态和终态的逆序奇偶性不同则无解
    if issolution(start) != issolution(goal):
        print('该始末状态的8数码无解')
        exit()
    open=[]
    close=[]
    creatp=serchp=step=0
    open.append([start])
    while 1:
        if start==goal:
            print('初始状态即为解!')
            break
        if len(open)==0:
            print('未找到解')
            break
        else:
            this=open.pop(0)
            #print(this)
            if len(this)>9*8*7*6*5*4*3*2:
                break
            serchp+=1
            close.append(this)
            #print(close)
            if this[0]==goal:
                print('搜索成功')
                print('共创建{}个结点,共搜索{}个结点,共{}步'.format(creatp,serchp,len(this)-1))
                for i in this[::-1]:
                    out(i)
                exit()

            #上,下,左,右扩展结点

            if this[0].index(0)>2 :
                node=this[0].copy()
                a=this[0].index(0)
                b=move('up',a)
                node[a],node[b]=node[b],node[a]
                path(this, node)
                creatp += 1

            if this[0].index(0) < 6 :
                node = this[0].copy()
                a = this[0].index(0)
                b = move('dowm', a)
                node[a],node[b]=node[b],node[a]
                path(this, node)
                creatp += 1


            if this[0].index(0) != 0 and this[0].index(0) != 3 and this[0].index(0) != 6:
                node = this[0].copy()
                a = this[0].index(0)
                b = move('left', a)
                node[a],node[b]=node[b],node[a]
                path(this, node)
                creatp+= 1


            if this[0].index(0) != 2 and this[0].index(0) != 5 and this[0].index(0) != 8:
                node = this[0].copy()
                a = this[0].index(0)
                b = move('right', a)
                node[a],node[b]=node[b],node[a]
                path(this, node)
                creatp += 1

示例截图:

在这里插入图片描述

DFS(深度优先搜索):

基本步骤:
①建立只含有初始节点S的搜索图G,把S放到open表中;
②建立closed表,其初始值为空表;
③若open表是空表,则失败退出;
④选择open表中第一个节点,把它从open表移出并放进closed表中,称此节点为当前节点;
⑤若当前节点为目标节点,则有解并成功退出。
⑥扩展当前节点,并把子节点放到open表的前面。

代码:

'''
author:Ning_Y_N
date:2020-10-27
'''
import random  # 引入导包

#返回索引,方便接下来交换
def move(str,index):
    if str=='up':
        return index-3
    if str=='dowm':
        return index+3
    if str=='left':
        return  index-1
    if str=='right':
        return index+1

#生成新的结点并且记录路径
def path(array1,array2):
    p=array1[:]
    p.insert(0,array2)
    for i in close:
        if i[0] == p[0]:
            return False
    open.insert(0,p)
    return True

#打印
def out(list):
    for j in range(len(list)):
        if j % 3 == 0:
            print('\t')
        print(list[j], end=' ')
    print('\t')

def issolution(array):
    num = 0
    for i in range(len(array) - 1):
        for j in range(i + 1, len(array)):
            if array[i] == 0 or array[j] == 0:
                continue
            if array[i] < array[j]:
                num += 1
    return num%2

'''
def rand(list):
    a = random.randint(0, 8)
    list.append(a)
    for i in range(8):
        i = random.randint(0, 8)
        while 1:
            if i not in list:
                list.append(i)
                break
            else:
                i = random.randint(0, 8)
'''

if __name__=="__main__":
    # start=[]
    # rand(start)
    # orgin=input(">>").split()
    # start=[int(x) for x in orgin]
    # 如果初态和终态的逆序奇偶性不同则无解
    start=[2,8,3,1,6,4,7,0,5]
    #start=[2,8,3,1,0,4,7,6,5]
    goal=[1,2,3,8,0,4,7,6,5]
    if issolution(start) != issolution(goal):
        print('该始末状态的8数码无解')
        exit()
    open=[]
    close=[]
    creatp=serchp=step=0
    open.append([start])
    while 1:
        if start==goal:
            print('初始状态即为解!')
            break
        if len(open)==0:
            print('未找到解')
            break
        else:
            this=open.pop(0)
            #print(this)
            serchp+=1
            close.append(this)
            if this[0]==goal:
                print('搜索成功')
                print('共创建{}个结点,共搜索{}个结点,共{}步'.format(creatp,serchp,len(this)-1))
                for i in this[::-1]:
                    out(i)
                exit()

            #上,下,左,右
            if this[0].index(0)>2 :
                node=this[0].copy()
                a=this[0].index(0)
                b=move('up',a)
                node[a],node[b]=node[b],node[a]
                path(this, node)
                creatp += 1

            if this[0].index(0) < 6 :
                node = this[0].copy()
                a = this[0].index(0)
                b = move('dowm', a)
                node[a],node[b]=node[b],node[a]
                path(this, node)
                creatp += 1

            if this[0].index(0) != 0 and this[0].index(0) != 3 and this[0].index(0) != 6:
                node = this[0].copy()
                a = this[0].index(0)
                b = move('left', a)
                node[a],node[b]=node[b],node[a]
                path(this, node)
                creatp += 1

            if this[0].index(0) != 2 and this[0].index(0) != 5 and this[0].index(0) != 8:
                node = this[0].copy()
                a = this[0].index(0)
                b = move('right', a)
                node[a],node[b]=node[b],node[a]
                path(this, node)
                creatp += 1

截图:

在这里插入图片描述

在这里插入图片描述

A*算法:

1、A算法的基本原理分析;
在搜索过程的步骤中,加入估价函数f(n)=g(n)+h(n)对open表中的节点进行排序,则该搜索算法为A*算法。
g(n):从初始节点到当前节点的层数。
h(n):启发函数,当前节点对比目标节,错误数字的个数(可能使用错误位置的曼哈顿位置会更好些)。

我此处使用的估计函数是f(n)=h(n),h(n)在此处是当前状态与目标状态数字相同的个数,并且我以相同个数最多的排序在最前面。(即错误数字个数最少的反面)

代码:

'''
author:Ning_Y_N
date:2020-10-27
'''
import random
#修改索引,方便接下来交换
def move(str,index):
    if str=='up':
        return index-3
    if str=='dowm':
        return index+3
    if str=='left':
        return  index-1
    if str=='right':
        return index+1

#生成新的结点并且记录路径
def create(array1,array2):
    p=array1[:]
    p.insert(0,array2)
    for i in close:
        if i[0] == p[0]:
            return False
    open.append(p)
    return True

#打印
def show(list):
    for j in range(len(list)):
        if j % 3 == 0:
            print('\t')
        print(list[j], end=' ')
    print('\t')

#估计函数,与目标结点对比,返回当前数码与目标数码相同位置的个数
def hx(current):
    count=0
    goal = [1, 2, 3, 8, 0, 4, 7, 6, 5]
    for i in range(len(current)):
        if current[i]==goal[i]:
            count+=1
    return count

def parity(array):
    num = 0
    for i in range(len(array) - 1):
        for j in range(i + 1, len(array)):
            if array[i] == 0 or array[j] == 0:
                continue
            if array[i] < array[j]:
                num += 1
    return num%2

'''
def rand(list):
    a = random.randint(0, 8)
    list.append(a)
    for i in range(8):
        i = random.randint(0, 8)
        while 1:
            if i not in list:
                list.append(i)
                break
            else:
                i = random.randint(0, 8)
'''
if __name__=="__main__":

    #orgin=input(">>").split()
    #start=[int(x) for x in orgin]
    #start=[]
    #rand(start)
    # start=[2,8,3,1,6,4,7,0,5]
    start=[2,8,3,1,0,4,7,6,5]
    goal=[1,2,3,8,0,4,7,6,5]
    # 如果初态和终态的逆序奇偶性不同则无解
    if parity(start) != parity(goal):
        print('该始末状态的8数码无解')
        exit()
    open=[]
    close=[]
    creatpoint=serchpoint=step=0
    open.append([start])
    while 1:
        if start==goal:
            print('初始状态即为解!')
            break
        if len(open)==0:
            print('未找到解')
            break
        else:
            this=open.pop(0)
            #print(this)
            serchpoint+=1
            close.append(this)
            if this[0]==goal:
                print('搜索成功')
                print('共创建{}个结点,共搜索{}个结点,共{}步'.format(creatpoint,serchpoint,len(this)-1))
                for i in this[::-1]:
                    show(i)
                exit()

            #上
            if this[0].index(0)>2 :
                node=this[0].copy()
                a=this[0].index(0)
                b=move('up',a)
                node[a],node[b]=node[b],node[a]
                create(this, node)
                creatpoint += 1

            #下
            if this[0].index(0) < 6 :
                node = this[0].copy()
                a = this[0].index(0)
                b = move('dowm', a)
                node[a],node[b]=node[b],node[a]
                create(this, node)
                creatpoint += 1

            #左
            if this[0].index(0) != 0 and this[0].index(0) != 3 and this[0].index(0) != 6:
                node = this[0].copy()
                a = this[0].index(0)
                b = move('left', a)
                node[a],node[b]=node[b],node[a]
                create(this, node)
                creatpoint += 1

            #右
            if this[0].index(0) != 2 and this[0].index(0) != 5 and this[0].index(0) != 8:
                node = this[0].copy()
                a = this[0].index(0)
                b = move('right', a)
                node[a],node[b]=node[b],node[a]
                create(this, node)
                creatpoint += 1

            #对与目标数码结点相同个数最多的数码结点放到open表最前面
            for i in range(len(open)-1):
                for j in range(i+1,len(open)):
                    if hx(open[i][0])<hx(open[j][0]):
                        open[i],open[j]=open[j],open[i]


示例截图:

在这里插入图片描述






所属网站分类: 技术文章 > 博客

作者:小鬼来了

链接:https://www.pythonheidong.com/blog/article/793946/bd1a30ebf05a999f4981/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

5 0
收藏该文
已收藏

评论内容:(最多支持255个字符)