c# - 高峰期求解器禁忌表的数据结构

Question

我正在使用广度优先搜索来解决 rush hour game .它工作正常，但在困难的板上需要很长时间。我正在使用禁忌列表来避免我已经发现的状态，以避免疯狂的内存使用并提高运行时间。

我认为这个禁忌 list 是运行时间长的主要原因。与普通 BFS 相比，它确实大大缩短了时间，但仍然太慢。目前我使用的是普通列表(C# 的 List 和 List.Contains 方法)。我确信有更好的选择。

我将我的板存储为汽车列表 + 宽度、高度和目标点(您的汽车应该结束的位置)。一辆车存储为 2 个点(左上角和右下角)，可以完整描述汽车(因为它们只能水平或垂直放置)。

我能想到的一些事情:

• 尝试
• 带有哈希码的东西
• 庞大的词典 (?)

对于我的问题，什么是好的/最好的数据结构？感谢您的帮助。

编辑 1: 伪代码(X为禁忌列表类型):

void Solve(Board b)
    Queue q = {b};
    X taboo = {b};
    while (q not empty)
        Board next = q.Dequeue();
        foreach (Board succ in next.Successors)
            if (succ.IsSolved)
                PrintSolution();
                return;
            if (!taboo.Contains(succ))
                q.Enqueue(succ);
                taboo.Add(succ);
    WriteLine("No solution found");

编辑 2: 解决方案是使用 HashSet。 (见下文)

Answer 1

感谢其他人的评论，找到了答案(或至少找到了一个答案)。我将 C# 的 HashSet 数据结构与以下板的哈希函数一起使用:

public override int GetHashCode()
{
    int hash = 0;
    int mul = 1;
    foreach (Car c in Cars.Values)
    {
        hash += (c.P1.X + c.P1.Y * W) * mul;
        mul += W * H;
    }
    return hash;
}

这似乎工作正常并为每个板提供唯一的哈希码(如果我错了请纠正我)，假设汽车总是以相同的顺序存储并且 P1 代表汽车的左上角。

有了这个解决方案，我现在可以在不到 0.5 秒的时间内解决需要 50 次移动的尖峰时刻板，并且内存使用量合理。