2

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

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

我将我的电路板存储为汽车列表 + 宽度、高度和目标点（您的汽车应该结束的位置）。a Car 存储为完全描述汽车的 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。（见下文）

4

2 回答 2

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 次移动的高峰时间板，并且内存使用量合理。

于 2013-11-02T16:40:24.587 回答
0

这个效率很低，但它对我有用，因为我的 RushHour 总体上非常快。 

public string HashCode()
{
    StringBuilder str = new StringBuilder();
    foreach (Car car in this.Positions)
    {
        //#yolo
        str.Append(string.Format("#{0}({1},{2})#", car.Original, car.Vector.X, car.Vector.Y));
    }
    return str.ToString();
}
于 2014-11-07T20:25:23.870 回答