0

我必须使用迭代深化搜索来解决高峰时间问题,我正在为每一步生成新节点,一切正常,除了计算所有内容需要太多时间,原因是我正在生成重复节点。任何想法如何检查重复?

首先我从根开始,然后有一种方法检查每辆车是否可以移动它,如果是,则从当前节点创建新节点,但是具有有效移动的一辆车替换为具有新坐标的新车.

问题是算法越深,重复的动作就越多。

我试图不更换汽车,但使用了与根节点中使用的相同的集合,但随后汽车仅朝一个方向移动。

我认为我需要以某种方式绑定汽车收藏,但不知道如何。

编码

任何想法如何停止重复?

题外话:我是 C# 新手(阅读了几个教程,然后已经使用了 2 天)所以你能告诉我我做错了什么或者我不应该做什么?

4

1 回答 1

1

如果你想坚持迭代深化,那么最简单的解决方案可能是构建一个哈希表。然后你需要对每个新节点做的就是

NewNode = GenerateNextNode
if not InHashTable(NewNode) then
  AddToHashTable(NewNode)
  Process(NewNode) 

或者,RushHour 中可能的位置(节点)数量相当少(假设您使用标准板尺寸),并且可以相当容易地生成所有可能(和不可能!)的板。然后,您可以从“解决方案”状态开始并向后工作(勾选所有可能的“父”状态),直到达到开始状态,而不是迭代深化。通过处理可能的状态表,您永远不会生成重复,并且通过在访问每个状态后标记每个状态,您永远不会重新访问状态。

于 2013-03-24T22:47:49.730 回答