解決するのが難しい問題があります (少なくとも私はそう見ています)。異なる値 ([1-6] 以外)のサイコロ(面 1 ～ 6) とボード(n-by-m) があります。開始位置と終了位置があります。サイコロを振って、あるマスから別のマスに移動できます。これを行うことで、上面を合計/コストに追加する必要があります。
ここで、最小の合計/コストで開始位置から終了位置に到達する方法を計算する必要があります。ほとんどすべてを試しましたが、正しいアルゴリズムが見つかりません。
ダイクストラを試しましたが、正しいパスには、別のパスからのより良い合計で到達できる中間ノードがいくつかあるため、役に立ちません(最終的には正しくないことがわかります)。アルゴリズムを変更するにはどうすればよいですか?
アルゴリズムの概要:
dijkstra : PriorityQueue
if(合計が小さいノードに到達できる)
、それをキューから削除し、
そのコストとサイコロの位置を変更し、
それをキューに追加します。
これはコードです：
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]));
}
}
}
}