对于“人工智能导论”中的作业,我需要解决以下问题:
Let f(n) = c1*g(n) + c2*h(n) be an evaluation function, where c1,c2 be constants.
1. Define c1,c2,h(.),g(.) such that A* with this evaluation function is bfs.
2. Define c1,c2,h(.),g(.) such that A* with this evaluation function is dfs.
对于 BFS,我有以下想法:
设 g(n)
是从起始节点到当前节点的成本,h(n)
是从当前节点到目标的估计成本。
如果我设置 c2 = 0
它实际上应该是广度优先搜索。
对于 DFS,我想到了设置 c2 = 0
和 c1 = (-1)
有什么想法、提示或反馈可以给我吗?
最佳答案
我认为您的回答符合预期。但是我认为这个问题有点错误,因为我发现不可能制作 BFS 和 DFS(以我理解的方式)。
问题是 DFS 和 BFS 都不关心路径长度。他们只关心节点顺序。
您的 BFS 解决方案实际上是统一成本搜索(或 dijkstra 算法),这是对基本 BFS 的改进。
您的 DFS 解决方案扩展了最远的节点,这不是实际 DFS(带堆栈)的工作方式。
如果某处声明弧成本始终相同,那么答案就是正确的。
关于algorithm - 将 A* 搜索实现为广度优先搜索/深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15998905/