algorithm - 掷骰子的最短路径

Question

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

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

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

算法概述:
dijkstra : 优先队列
如果(我可以到达一个总和较小的节点)
,将其从队列中移除,
我改变了它的成本和模具位置
, 将其加入队列。

这是代码:

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]));
            } 

        }
    }

}

Answer 1

您还需要考虑骰子在 Dijkstra 状态中的位置。

即你不能只有sums[lines][column] ，您必须执行类似 sums[lines][column][die_config] 的操作, 其中die_config是您创建的将骰子位置转换为整数的某种方式。

例如，如果您的骰子最初看起来像这样:

^1 <4 v2 >9 f5 b7 (^ = top face, < = left... down, right, front and back)

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

您可以通过简单地考虑指向向上和指向左侧的面的索引(从 0 到 5)将其转换为整数.这意味着您的骰子的可能旋转位置少于 36 个(见底部注释)，您可以通过诸如(基于 0) (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 个可能的位置，因为有些是不可能的，例如两个最初相对的边将无法在上/左上相邻。实际上只有 24 个有效位置，但我在上面使用的简单编码实际上会使用最多约 34 个索引，具体取决于您对骰子的编码方式。