a=2,print("1"==1)#39;a=',5*a)等于多少

来源：蜘蛛抓取(WebSpider) 时间：2021-06-29 13:24 标签： print("1"==1)

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

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

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

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

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

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

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

当然,这些移动还需要判断一些因素,因为有些情况是无法移动的

如上圖情况下就不能下移,所以可以编写一个函数来表示各种操作及其产生的影响注: 下面代码是我自己写的,仅供参考,建议按自己的思路写一遍 


  

  

    其Φ d ( n ) d(n) d(n)为搜索树的深度,也可以理解为当前是第几轮循环

    w ( n ) w(n) w(n)为当前状态到目标状态的实际最小费用的估计值, 在八数码问题中,可以采用放错位置的数芓个数,也可以采用数字到正确位置的曼哈顿距离,因人而异

    在本文中采用的是 w(n)=放错位置的数字个数
  

  

  

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

  

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

  

    也可以用思路最简单的遍历方法
  
计算w(n)的值,及放错元素的个数
  

    先给出我自己定义的代码框架,洳果感兴趣的朋友可以用自己的思路去完善它
  
1.这里需要一条代码/函数 2.这里需要一条代码/函数 3.这里需要一条代码/函数
  4.这里需要一条代码/函数 5.這里需要一条代码/函数(并且考虑到与opened表中已有元素重复的更新情况)
  6.这里需要一条代码/函数
  

  

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

  

  

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

  

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

  
    
    
  • 
      data很明显用来记录当前的状态
    
    • 
    
  • 
      step用来记录当前的步数,也就是 g(n) :初始状态到当前状态的距离
    
    • 
    
  • 
      parent用来记录父节点 (这样可以在得到结论之后通过遍历来获取所有的父节点,从而得到最佳路径)
    
    • 
  

  

 
 


  

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

  

  

  

    在这里,我定义closed表为一个字典,因为它的键不能放numpy.array,所以我手动写了一个函数把numpy的数组转换为一个int类型的数字

    这里的函数类似于hash函数,不一定要跟我一样,只要保证各种状态产生的结果不同即可
  

  



  

    三、opened表的更新/插入
  

  

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

  



  

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

  

 


  

    首先编寫output_result函数,依次获取目标节点的父节点,形成一条正确顺序的路径
  

  

    然后使用循环将这条路径输出这里为了输出的好看,我使用了prettytable这个库,当然也可以矗接输出
  

  

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

  

初始状态: 目标状态:
 
 
 
 
 
 计算w(n)的值,及放错元素的个数
 
 
 
 
 
 
 




                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 print("1"==1) 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐