知识卡片
先进先出保证先扩展浅层
广度优先搜索把新发现状态加到队尾,从队首取待处理状态。一步可达的状态因此都排在两步状态前。若每条边代价相同,第一次抵达目标时步数最少。分支多且目标深时,同层状态大量累积,队列和去重集合会耗用大量内存。可与[[栈决定深度优先扩展]]对照。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
在Step4中向OPEN的末端追加了新的状态,然后从Step3的首端取出k是十分重要的。根据这个步骤,会从树中比较浅的节点开始一一尝试。
参考来源
- 位置:《AI游戏开发和深度学习进阶》第2章 2.1.3 宽度优先搜索(book-source,`extracted/AI游戏开发和深度学习进阶/_epub-src/OEBPS/Text/0015.xhtml`)
- 结论依据:原文给出队首出队、队尾入队的规则,并用渡河和八数码示范逐层扩展。
- 原始内容:在Step4中向OPEN的末端追加了新的状态,然后从Step3的首端取出k是十分重要的。根据这个步骤,会从树中比较浅的节点开始一一尝试。