CS188-Pacman P1 Search Q1 DFS_cs188 project1_YYGQYRW的博客-程序员宅基地

CS188 | Introduction to Artificial Intelligence

此题目要求使用深度优先搜索（DFS） 来完成吃豆人对食物的搜索，也就是完成search.py里的DFS功能。其原理较为简单，如下图笔记所示：
在这里插入图片描述
参考伪代码如下：
图搜索算法
注意图搜索与树搜索算法的区别（需不需要检索closed）
深度优先搜索要求满足先入后出的策略，因此fringe应选用栈来实现，可直接通过调用util.py里写好的栈结构来完成。
具体python代码实现如下：

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print("Start:", problem.getStartState())
    print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
    print("Start's successors:", problem.getSuccessors(problem.getStartState()))
    """
    "*** YOUR CODE HERE ***"
    
    temp = problem.getStartState()
    past = []
    fringe = util.Stack()
    fringe.push((temp, []))
    while not fringe.isEmpty():
        temp, path = fringe.pop()
        past.append(temp)
        if problem.isGoalState(temp):
            return path
        for child in problem.getSuccessors(temp):
            if child[0] not in past:
                fringe.push((child[0], path + [child[1]]))

    util.raiseNotDefined()

值得注意的是，这里以及接下来的几个问题的past（closed）均使用了列表，从原理上讲是不对的。因为图搜索算法需要频繁的检索当前展开节点是否已经被展开过了，即该节点是否在closed集中，这里如果使用set则可通过hash来达到O(1)的查找时间，这对于搜索算法是至关重要的。但由于本次作业数据量不大，就懒得改了。

转载请注明作者及来源

本文链接：https://blog.csdn.net/weixin_42328465/article/details/105729907

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

介绍关于IBM MQSeries的使用指南_iteye_20954的博客-程序员宅基地

随着计算机网络和分布式应用的不断发展，远程消息传递越来越成为应用系统中不可缺少的组成部分。商业消息中间件的出现保证了消息传输的可靠性，高效率和安全性，同时也减少了系统的开发周期。目前应用最多的消息中间件产品为IBM MQSeries。本文就针对MQ的基本操作与配置进行详细的阐述，希望对读者有所帮助。　　　　一．MQ基本操作　　　　MQ中有几个很重要的组件：队列管理器（QueueManager）、队...

Google谷歌需要什么样的员工？_Hustudent20080101的博客-程序员宅基地

Google谷歌需要什么样的员工？2006-10-14 22:22:00 10357 人阅读作者：且听枫吟编辑：且听枫吟 [复制链接] [我要爆料]在复旦·GoogleCamp成立仪式上，复旦同学与Google谷歌大中华区总裁李开复教授就Google在中国招聘员工的观点进行了简略的阐述。复旦记者：李开复博士您好，微软亚研院对应聘者提出三好——数学好、编程好、态度

Dart 层如何兼容 Android 和iOS平台特性_android 支持dart_一朵白山茶的博客-程序员宅基地

下面看看，打开微信应用的小例子：flutter 端代码class FlutterCallNativeDemo extends StatelessWidget {// 声明方法通道var platform = MethodChannel(“samples.chenhang/utils”);//处理点击事件openWeChat() async {int result;try {// 通过方法调用，调用原生方法result = (await platform.invokeListMethod(

C# 创建虚拟盘_c# 新建硬盘并设置大小_中洲少年的博客-程序员宅基地

一、介绍虚拟盘有点类似于文件的快捷方式，但是又有不同。本文介绍的虚拟盘，是通过网络路径或者自己本地计算机的某个文件夹来创建一个虚拟盘，可能表述不清楚，具体您先看一下效果图：该L盘，实际是本地路径 E:\test 的文件夹映射。双击进去L盘后，看到的东西，跟E:\test下看到的东西是一样的。二、C#如何实体虚拟盘创建虚拟盘的指令是使用cmd命令程序来执行subst命令，那么C#代码，就要模拟这个过程，具体代码如下： static void Main(string[

junit5 入门系列教程-03-junit5 测试类和方法_老马啸西风的博客-程序员宅基地

目录目录测试类和方法标准案例系列导航测试类和方法测试方法是使用@Test、@RepeatedTest、@ParameterizedTest、@TestFactory或@TestTemplate直接或元注释的任何实例方法。测试类是包含至少一个测试方法的任何顶层或静态成员类。标准案例注意测试类和测试方法都可以不设置为 public。...

Halcon算子--图像、区域、轮廓、测量、拟合、垂足、夹角_halcon点到线的垂足_冯相文要加油呀的博客-程序员宅基地

Halcon算子–图像、区域、轮廓、测量、拟合、垂足、夹角read_image (Image,‘fabrik’)画矩形draw_rectangle1 (3600, Row1, Column1, Row2, Column2)gen_rectangle1 (Rectangle, Row1, Column1, Row2, Column2)缩减图像定义域reduce_domain (Image, Rectangle, ImageReduced)阈值分割出感兴趣的部分threshold (ImageR

CS188-Pacman P1 Search Q1 DFS_cs188 project1_YYGQYRW的博客-程序员宅基地

CS188 | Introduction to Artificial Intelligence

Spring 2020

Project 1 Search

Q1: Finding a Fixed Food Dot using Depth First Search

智能推荐

介绍关于IBM MQSeries的使用指南_iteye_20954的博客-程序员宅基地

Google谷歌需要什么样的员工？_Hustudent20080101的博客-程序员宅基地

Dart 层如何兼容 Android 和iOS平台特性_android 支持dart_一朵白山茶的博客-程序员宅基地

C# 创建虚拟盘_c# 新建硬盘并设置大小_中洲少年的博客-程序员宅基地

junit5 入门系列教程-03-junit5 测试类和方法_老马啸西风的博客-程序员宅基地

Halcon算子--图像、区域、轮廓、测量、拟合、垂足、夹角_halcon点到线的垂足_冯相文要加油呀的博客-程序员宅基地

随便推点

mysql cve-2015-3152_The BACKRONYM MySQL Vulnerability （CVE-2015-3152）_quer li的博客-程序员宅基地

模拟电磁炮国一设计资料【2019电赛H题国一作品】_电赛国一作品_DLC913875329的博客-程序员宅基地

Pycharm项目使用pyinstalle打包过程中问题及解决方案_消灭BUG鸭的博客-程序员宅基地

开课吧里的python学习是真的吗-明星为开课吧直播带货：人人都要学，人人都可以学的Python..._编程大乐趣的博客-程序员宅基地

OpenFire源码学习之十三：消息处理_openfire的room chat实现_莫然的博客-程序员宅基地

blink渲染知识9-chromium webview硬件渲染的演进_csshell2002的博客-程序员宅基地

推荐文章

热门文章

相关标签