Самый короткий путь путем прокатки кубиков

Question

У меня есть трудная проблема для решения (по крайней мере, так я ее вижу). У меня есть die (лица с 1 по 6) с разными значениями (другие, чем [1-6]) и доски (n-by-m). У меня начальная позиция и финишная позиция. Я могу перейти от квадрата к другому, прокатив кубик. Делая это, я должен добавить верхнюю грань к сумме/стоимости.

Теперь я должен рассчитать, как добраться из стартового положения в конечное положение с минимальной суммой . Я пробовал почти все, но я не могу найти правильный алгоритм.

Я попробовал 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])); 
      } 

     } 
    } 

} 

Answer 1

Вы должны также рассмотреть положение штампа в ваших состояниях Дейкстра.

I.e. вы не можете просто иметь 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), что указывает до и тот, который находится на слева. Это означает, что у вашей матрицы меньше 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 возможных положений, потому что некоторые из них невозможны, например, две изначально противоположные стороны не смогут смещаться вверх/влево. На самом деле существует только 24 действительных позиции, но простая кодировка, которую я использовал выше, фактически будет использовать индексы до ~ 34 в зависимости от того, как вы кодируете свою матрицу.