0

我有一个难题要解决（至少我是这么看的）。我有一个具有不同值（[1-6] 除外）的骰子（面 1 到 6）和一块板（n×m）。我有一个起始位置和一个结束位置。我可以通过掷骰子从一个正方形移动到另一个正方形。通过这样做，我必须将顶面添加到总和/成本中。

现在我必须计算如何以最小的总和/成本从起始位置到达结束位置。我几乎尝试了所有方法，但找不到正确的算法。

我尝试了 Dijkstra，但它没用，因为在正确的路径中有一些中间节点，我可以从另一条路径获得更好的总和（最终证明是不正确的）。我应该如何改变我的算法？

算法概述：
dijkstra：PriorityQueue
如果（我可以到达一个总和较小的节点）
，将其从队列中删除，
我更改其成本和模具位置
，将其添加到队列中。

这是代码：

public void updateSums() {

    PriorityQueue<Pair> q = new PriorityQueue<>(1, new PairComparator());

    Help h = new Help();

    q.add(new Pair(startLine, startColumn, sums[startLine][startColumn]));

    while (!q.isEmpty()) {

        Pair current = q.poll();

        ArrayList<Pair> neigh = h.getNeighbours(current, table, lines, columns);

        table[current.line][current.column].visit(); //table ->matrix with Nodes

        for (Pair a : neigh) {

            int alt = sums[current.line][current.column] + table[current.line][current.column].die.roll(a.direction);

            if (sums[a.line][a.column] > alt) {

                q.remove(new Pair(a.line, a.column, sums[a.line][a.column]));

                sums[a.line][a.column] = alt; //sums -> matrix with costs

                table[a.line][a.column].die.setDie(table[current.line][current.column].die, a.direction);

                q.add(new Pair(a.line, a.column, sums[a.line][a.column]));
            } 

        }
    }

}
4

1 回答 1

3

您还需要考虑 Dijkstra 州中骰子的位置。

即你不能只拥有sums[lines][column]，你必须做一些事情，例如sums[lines][column][die_config]，die_config你创建的某种方式将骰子位置转换为整数。

例如，如果您有一个最初看起来像这样的模具：

^1 <4 v2 >9 f5 b7（^ = 顶面，< = 左...下、右、前和后）

int initial_die[6] = {1,4,2,9,5,7}

您可以将其转换为整数，只需考虑指向上方的面部索引（从 0 到 5）和左侧的面部索引。这意味着您的 die 有少于 36 个（见底部注释）可能的旋转位置，您可以通过诸如(0-based) 之类的 (up*6 + left)东西对其进行编码。我的意思是每个面都有一个你决定的从 0 到 5 的值，不管它们的成本相关值如何，所以按照上面的例子，我们将最初的顶面编码为索引0，左面编码为索引1， 等等。

因此，具有配置值的骰子30意味着left = 30%6 (=0)最初指向上方的面（initial_die[0]）当前指向左侧，而up = (30 - left)/6 (=5)当前指向上方的面是最初指向背面的面死（initial_die[5]）。因此，这意味着骰子当前的左侧面值为 1，顶部面值为 7，并且您可以从该信息中推导出骰子的其余面，因为您知道初始配置。（基本上，这告诉我们骰子向左滚动一次，然后向其前面滚动一次，与初始状态相比）

有了这些附加信息，您的 Dijkstra 将能够通过考虑到达最终节点的最便宜成本来找到您寻求的正确答案，因为您可能有多个具有不同最终模具位置的模具。

注意：它实际上并没有 36 个可能的位置，因为有些是不可能的，例如两个最初相对的边将无法在 Up/Left 上相邻。实际上只有 24 个有效位置，但我上面使用的简单编码实际上将使用高达 ~34 的索引，具体取决于您对骰子进行编码的方式。

于 2013-05-21T01:19:57.807 回答