我有一个难题要解决(至少我是这么看的)。我有一个具有不同值([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]));
}
}
}
}