Учитывая набор стеков NXP, где N - количество стеков, а P - емкость стеков, как я могу рассчитать минимальное количество перестановок, необходимое для перейти от некоторого узла в местоположении A к некоторому произвольному местоположению B? Я разрабатываю игру, и конечная цель состоит в том, чтобы отсортировать все стеки так, чтобы они все были одного цвета.
# Let "-" represent blank spaces, and assume the stacks are
stacks = [
['R', 'R', 'R', 'R'],
['Y', 'Y', 'Y', 'Y'],
['G', 'G', 'G', 'G'],
['-', '-', '-', 'B'],
['-', 'B', 'B', 'B']
]
Если я хочу вставить букву B в stacks[1][1], например, что stacks[1] = ["-", "B", "Y", "Y"]. Как я могу определить минимальное количество ходов, необходимое для этого?
Я рассматривал несколько подходов, я пробовал генерировать алгоритмы c, которые генерируют все возможные движения из состояния, оценивают их, и затем продолжаем идти по лучшим путям подсчета очков, я также попытался запустить алгоритм Djikstra для поиска пути к проблеме. Это кажется невероятно простым, но я не могу придумать, как заставить его работать за исключением экспоненциального времени. Есть ли алгоритм, который мне не хватает, который применим здесь?
Редактировать
Я написал эту функцию для вычисления минимального необходимого количества ходов: stacks: Список списка символов, представляющих штук в стеке, stacks [0] [0] является вершиной стека [0] stack_ind: индекс стека, к которому этот кусок будет добавлен в needs_piece: кусок, который должен быть добавлен в стек needs_index: индекс, где кусок должен быть расположен
def calculate_min_moves(stacks, stack_ind, needs_piece, needs_index):
# Minimum moves needed to empty the stack that will receive the piece so that it can hold the piece
num_removals = 0
for s in stacks[stack_ind][:needs_index+1]:
if item != "-":
num_removals += 1
min_to_unlock = 1000
unlock_from = -1
for i, stack in enumerate(stacks):
if i != stack_ind:
for k, piece in enumerate(stack):
if piece == needs_piece:
if k < min_to_unlock:
min_to_unlock = k
unlock_from = i
num_free_spaces = 0
free_space_map = {}
for i, stack in enumerate(stacks):
if i != stack_ind and i != unlock_from:
c = stack.count("-")
num_free_spaces += c
free_space_map[i] = c
if num_removals + min_to_unlock <= num_free_spaces:
print("No shuffling needed, there's enough free space to move all the extra nodes out of the way")
else:
# HERE
print("case 2, things need shuffled")
Редактировать: Тестовые случаи в стеках:
stacks = [
['R', 'R', 'R', 'R'],
['Y', 'Y', 'Y', 'Y'],
['G', 'G', 'G', 'G'],
['-', '-', '-', 'B'],
['-', 'B', 'B', 'B']
]
Case 1: stacks[4][1] should be 'G'
Move 'B' from stacks[4][1] to stacks[3][2]
Move 'G' from stacks[2][0] to stacks[4][1]
num_removals = 0 # 'G' is directly accessible as the top of stack 2
min_to_unlock = 1 # stack 4 has 1 piece that needs removed
free_spaces = 3 # stack 3 has free spaces and no pieces need moved to or from it
moves = [[4, 3], [2, 4]]
min_moves = 2
# This is easy to calculate
Case 2: stacks[0][3] should be 'B'
Move 'B' from stacks[3][3] to stack[4][0]
Move 'R' from stacks[0][0] to stacks[3][3]
Move 'R' from stacks[0][1] to stacks[3][2]
Move 'R' from stacks[0][2] to stacks[3][1]
Move 'R' from stacks[0][3] to stacks[3][0]
Move 'B' from stacks[4][0] to stacks[0][3]
num_removals = 0 # 'B' is directly accessible
min_to_unlock = 4 # stack 0 has 4 pieces that need removed
free_spaces = 3 # If stack 3 and 4 were switched this would be 1
moves = [[3, 4], [0, 3], [0, 3], [0, 3], [0, 3], [4, 0]]
min_moves = 6
#This is hard to calculate
Реальная реализация кода не та сложная часть, она определяет, как реализовать алгоритм, который решает проблему, с которой я борюсь.
По запросу @ YonIif я создал для задачи gist .
При запуске генерирует случайный массив стеков и выбирает случайный кусок, который нужно вставить в случайный стек в случайном месте.
При запуске он печатает что-то из этого формата на консоль.
All Stacks: [['-', '-', 'O', 'Y'], ['-', 'P', 'P', 'O'], ['-', 'P', 'O', 'Y'], ['Y', 'Y', 'O', 'P']]
Stack 0 is currently ['-', '-', 'O', 'Y']
Stack 0 should be ['-', '-', '-', 'P']
Обновление статуса
I Я полон решимости решить эту проблему каким-то образом .
Имейте в виду, что есть способы минимизировать количество случаев, таких как @Hans Olsson, упомянутые в комментариях. Мой самый последний подход к этой проблеме - разработать набор правил, аналогичных упомянутым выше, и использовать их в алгоритме поколений.
Правила, такие как:
Никогда не изменяться движение. Go из 1-> 0, затем 0-> 1 (не имеет смысла)
Никогда не перемещайте фигуру дважды подряд. Никогда не двигайтесь от 0 -> 1, затем 1 -> 3
Учитывая некоторый переход от стеков [X] к стекам [Y], затем некоторое количество ходов, затем переход от стеков [Y] к стекам [Z] ], если стеки [Z] находятся в том же состоянии, в котором они находились при переходе от стеков [X] к стекам [Y], перемещение можно было бы исключить, если перейти из стеков [X] непосредственно в стеки [Z]
В настоящее время я подхожу к этой проблеме, пытаясь создать достаточно правил, чтобы минимизировать количество «допустимых» ходов, достаточно, чтобы можно было рассчитать ответ с использованием алгоритма генерации. Если кто-то может придумать дополнительные правила, мне было бы интересно услышать их в комментариях.
Обновление
Благодаря ответу @RootTwo у меня был небольшой прорыв, который я здесь опишу.
На прорыв
Определите высоту цели как глубину, которую должен быть помещен в целевую стопку.
Всякий раз, когда какая-либо цель попадает в индекс <= stack_height - высота цели, всегда будет кратчайший путь к победе с помощью метода clear_path (). </p>
Let S represent some solid Piece.
IE
Stacks = [ [R, R, G], [G, G, R], [-, -, -] ]
Goal = Stacks[0][2] = R
Goal Height = 2.
Stack Height - Goal Height = 0
С учетом некоторого стека, такого, что stack[0] = R, игра выиграна.
GOAL
[ [ (S | -), (S | -), (S | -) ], [R, S, S], [(S | - ), (S | -), (S | -)] ]
Поскольку известно, что у них всегда есть хотя бы свободные пробелы stack_height, наихудший возможный случай будет:
[ [ S, S, !Goal ], [R, S, S], [-, -, -]
Так как мы знаем, что цель не может быть в пункте назначения цели, или игра выиграна. В этом случае минимальное количество необходимых ходов будет:
(0, 2), (0, 2), (0, 2), (1, 0)
Stacks = [ [R, G, G], [-, R, R], [-, -, G] ]
Goal = Stack[0][1] = R
Stack Height - Goal Height = 1
Учитывая некоторый стек, такой, что stack[1] = R, игра выиграна.
GOAL
[ [ (S | -), (S | -), S], [ (S | -), R, S], [(S | -), (S | -), (S | -)]
Мы знаем, что доступно как минимум 3 пробела, поэтому наихудший возможный случай будет:
[ [ S, !Goal, S], [S, R, S], [ -, -, - ]
В этом случае минимальное количество ходов будет равно ходам:
(1, 2), (0, 2), (0, 2), (1, 0)
Это будет выполняться для всех случаев.
Таким образом, проблема была уменьшена до проблема определения минимального количества ходов, необходимого для размещения цели на уровне или выше на высоте цели.
Это разбивает задачу на ряд подзадач:
-
Когда в стеке назначения есть доступная фигура! = Цель, определяющая, есть ли для этой фигуры правильное место, или же эта фигура должна оставаться там во время замены другой фигуры.
Когда у стека назначения есть доступная часть == цель, определение, может ли она быть удалена и помещена на требуемую высоту цели, или должна ли часть оставаться, пока другой поменялся местами.
Когда В двух вышеупомянутых случаях требуется обменять другую часть, определяя, какие части следует поменять местами для увеличения, чтобы позволить целевой части достичь высоты цели.
Стек назначения должен всегда сначала оцените свои случаи.
IE
stacks = [ [-, R, G], [-, R, G], [-, R, G] ]
Goal = stacks[0][1] = G
Проверка стека целей сначала приводит к:
(0, 1), (0, 2), (1, 0), (2, 0) = 4 Moves
Игнорирование стека целей:
(1, 0), (1, 2), (0, 1), (0, 1), (2, 0) = 5 Moves