如何使Prolog深度优先搜索算法更深地进入树？（应用于Sokoban游戏）

Question

如何使Prolog深度优先搜索算法更深地进入树？（应用于Sokoban游戏）

prologdepth-first-searchbacktracking

3

我正在尝试使用深度优先搜索算法在Prolog中解决Sokoban谜题，但是我无法深入搜索解决方案树。我只能探索第一层。

所有源代码都在Github（链接到提问时的修订版），所以请随意探索和测试它们。我将规则分成了几个文件：

board.pl：包含与棋盘相关的规则：方向、邻域等。
game.pl：此文件规定了有关移动、有效位置等的规则。
level1.pl：为示例游戏定义了棋盘、箱子位置和解决方案方块。
sokoban.pl：试图实现dfs: (

我知道当一个新状态被创建时，需要深入探索，而不是检查它是否为最终状态并回溯... 我需要继续移动，只有一个移动是不可能达到最终状态的。

任何帮助/建议都将不胜感激，我一直在尝试但没有改进。

谢谢！

PS.- 噢！我正在使用SWI-Prolog，以防有所不同。

PS.- 我真的很菜，在Prolog中可能会遇到一些明显的错误，但这就是我在这里询问的原因。

- jgsogo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mat · Accepted Answer

这很容易修复：在sokoban.pl文件中的solve_problem/2谓词中，您正在将解决方案限制为目标列表中只有一个元素的列表：

   solve_dfs(Problem, Initial, [Initial], [Solution])

相反，您可能想表达的是：

    solve_dfs(Problem, Initial, [Initial], Solution)

因为一个解决方案可能由多个步骤组成。

事实上，更好的搜索策略通常是迭代加深，可以通过以下方式实现:

    length(Solution, _),
    solve_dfs(Problem, Initial, [Initial], Solution)

迭代加深搜索是一种完备的搜索策略，在相当一般的假设下也是一种最优策略。

除此之外，我建议您减少程序中大量的不纯I/O调用。有太多谓词在屏幕上写东西。

相反，专注于清晰的声明性描述，并将输出与解决方案的描述清晰地分离。实际上，让toplevel为您打印：描述解决方案的外观（这已经是您正在做的），并让toplevel显示变量绑定的解决方案。另外，以声明性的方式思考，并使用更好的名称，如dfs_moves/4、problem_solution/2而不是solve_dfs/4、solve_problem/2等。

DCGs在代码的某些地方也可能帮助您更方便地描述列表。

+1，为了用Prolog解决一个美好而具有挑战性的搜索问题！