知识卡片
分支上界低于现解就剪枝
最大化摆放数量时,可用当前棋子数加合法空位数作为最乐观的上界。即使空位彼此也冲突,这个数仍不会低估能达到的数量。上界低于已经找到的最大值就能剪枝。若还要枚举并列最优布局,要保留等于现有最大值的分支。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
当前放置的棋子数+接下来可以放置棋子位置的数量<到目前为止找到的最大棋子数
参考来源
- 位置:《AI游戏开发和深度学习进阶》第3章 3.5.1 尽可能放置多个棋子(book-source,`extracted/AI游戏开发和深度学习进阶/_epub-src/OEBPS/Text/0028.xhtml`)
- 结论依据:原文式 3.9 把当前棋子数、剩余位置及已知最大值连在一起。
- 原始内容:当前放置的棋子数+接下来可以放置棋子位置的数量<到目前为止找到的最大棋子数