知识卡片

普通读书笔记卡 · 9956 · 生成模型:未记录

先进先出保证先扩展浅层

理解等级:中级

广度优先搜索把新发现状态加到队尾,从队首取待处理状态。一步可达的状态因此都排在两步状态前。若每条边代价相同,第一次抵达目标时步数最少。分支多且目标深时,同层状态大量累积,队列和去重集合会耗用大量内存。可与[[栈决定深度优先扩展]]对照。

这张卡片看不懂?

已有反馈 · 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是十分重要的。根据这个步骤,会从树中比较浅的节点开始一一尝试。