人工智能 图搜索的实现方式?
发布网友
发布时间：2022-04-23 13:13
共1个回答
热心网友
时间：2023-07-01 02:00
不论是使用目标驱动搜索还是数据驱动搜索来求解问题，问题求解器都必须在状态空间图中找到一条从起始状态到目标的路径。这条路径的弧序列对应了有序的求解步骤。如果问题求解器被赋予了神谕或其他确实可靠的机制来选取解路径，那么就不再需要搜索，问题求解器会不犯任何错误地穿越空间到达预期目标，而且一边行进一边就建立了解路径。因为对于感兴趣的问题来说神谕是不存在的，所以问题求解器必须考虑穿越空间的不同路径直到找到目标。回溯( backtracking）是系统地尝试穿越状态空间的所有路径的一种技术。我们从回溯开始讨论搜索方法的原因是，回溯技术是计算机科学家最早研究的搜索算法之一，而且它可以在面向堆栈的递归环境中自然地实现。
回溯搜索从起始状态出发沿一条路径前进直到要么到达目标，要么到达一个“死端"。如果发现了目标，它退出搜索并返回解路径。如果到达的是一个死端，那么它便回溯到路径上含有未分析过最近兄弟结点，并沿这个分支继续下去，如下面的递归规则所述:如果当前状态S不满足目标描述的要求，那么便产生它的第一个后代Scas，并对这个结点递归地应用回溯过程。如果回溯没有在以Sae为根的子图上发现目标结点，那么便对它的兄弟hnz应用递归过程。继续上面的过程直到一个孩子的某个后代是目标结点或已经搜索了所有的孩子。如果S的孩子没有一个可以通向目标，那么回溯便“无功而返”到S的双亲，并在那里对S的兄弟应用以上过程,依此类推。这种算法不断搜索直到找到--个目标或穷举了状态空间。
