Как создать алгоритм быстрого поиска, который может выполнять 2 или более целей на Python? ⇐ Python

[Гость]

У меня есть сетка с 7 столбцами и 8 строками, самая нижняя строка — это 0–6 слева направо, строка над ней — 7–13 слева направо, шаблон продолжается до самой верхней строки. с 49-55 слева направо. Есть 5 белых блоков в 1–5, белый шар в 3, пять черных блоков в 50–54 и черный шар в 52. Движение блока похоже на коня в шахматах, движение шара похоже на движение ферзя в шахматах, и это можно переместить только в тот же цветовой блок. Во время каждого хода игрок должен выбрать, переместить блок или мяч. Игрок с белыми фигурами ходит первым. Игрок может перемещать мяч из одного блока в другой неограниченное количество раз в течение каждого хода (например, он может перемещаться из 3->2->5, ему не нужно ждать следующего хода, чтобы перейти из 2- >5).

Чтобы протестировать реализацию логики, мы упоминаем нашу цель. Например, мы хотим переместить белый блок с 1 на 23. Итак, наш initial_state = [1,2,3,4,5,3,50,51,52,53,54,52] , goal_state = [23,2,3,4,5,3,50,51,52,53,54,52].

Вот ожидаемый результат наших ходов последовательности:

[(((1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), (0, 14)), (((14, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 1), (6, 37)), (((14, 2, 3, 4, 5, 3, 37, 51, 52, 53, 54, 52), 0), (0, 23)), (((23, 2, 3, 4, 5, 3, 37, 51, 52, 53, 54, 52), 1), (6, 50)), (((23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), Нет)] Мы перемещаем черный блок с 50 на 37 только ради правила, согласно которому каждый игрок должен двигаться во время своего хода (например, не имеет значения, какой черный блок вы перемещаете и куда двигаться, потому что это не указано в нашей цели). ), но нам придется вернуть его в исходное положение, поскольку в нашей цели он не указан. Когда мы достигаем нашей цели и другие части, которые не упомянуты в нашей цели, находятся в исходном положении, мы ничего не делаем, следовательно, последняя часть — «Нет».

Я реализовал свой алгоритм, ниже приведен код:

из очереди импорта коллекций Защиту find_sequence_with_restore (начальное_состояние, конечное_состояние): последовательность = find_sequence(начальное_состояние, конечное_состояние) если последовательность: Final_state = последовательность[-1][0][0] восстановления_последовательности = восстановления_начальных_позиций(конечное_состояние, окончательное_состояние, начальное_состояние) последовательность.расширить(восстановить_последовательность) if all(pos в исходном_состоянии или позиция в конечном_состоянии для позиции в последовательности[-1][0][0]): последовательность.append(((последовательность[-1][0][0], 1 - последовательность[-1][0][1]), нет)) еще: последовательность.append(((последовательность[-1][0][0], последовательность[-1][0][1]), нет)) обратная последовательность защита get_next_states (current_state, player_turn): next_states = [] если player_turn == 0: штук = текущее_состояние[:5] мяч = текущее_состояние[5] для i, кусок в перечислении(штуки): ходы = рыцарь_ходы(кусок) для хода ходами: если перемещение не в current_state: новое_состояние = список (текущее_состояние) new_state = переместить next_states.append(кортеж(new_state)) ball_moves = queen_moves(шар, фигуры, текущее_состояние) для хода в ball_moves: новое_состояние = список (текущее_состояние) new_state[5] = переместить next_states.append(кортеж(new_state)) еще: штук = текущее_состояние[6:11] мяч = текущее_состояние[11] для i, кусок в перечислении(штуки): ходы = рыцарь_ходы(кусок) для хода ходами: если перемещение не в current_state: новое_состояние = список (текущее_состояние) new_state[i + 6] = переместить next_states.append(кортеж(new_state)) ball_moves = queen_moves(шар, фигуры, текущее_состояние) для хода в ball_moves: новое_состояние = список (текущее_состояние) new_state[11] = переместить next_states.append(кортеж(new_state)) вернуть следующие_состояния Защиту find_sequence (начальное_состояние, конечное_состояние): очередь = deque([(начальное_состояние, Нет, Нет, 0)]) посетил = set([начальное_состояние]) родители = {} пока очередь: состояние, prev_state, ход, player_turn = очередь.popleft() если состояние[:5] == end_state[:5] и состояние[5] == end_state[5]: путь = [] пока состояние не None: path.append((состояние, player_turn, ход)) состояние, ход, player_turn = родители.get(состояние, (Нет, Нет, Нет)) последовательность = список(обратный(путь[1:])) последовательность_без_поворота = [(состояние, ход) для состояния, _, перемещение последовательно] formatted_sequence = [((state, move[0]), move[1]) для состояния, двигаться в последовательности_без_поворота] вернуть форматированную_последовательность для next_state в get_next_states(state, player_turn): если next_state не посещен: посетил.add(next_state) родители[next_state] = (state, (player_turn, find_move(state, next_state)), 1 - player_turn) очередь.append((next_state, state, (player_turn, find_move(state, next_state)), 1 - player_turn)) возврат Нет защита рыцарь_moves (позиция): строка, столбец = divmod (позиция, 7) движется = [ (строка + 2, столбец + 1), (строка + 2, столбец - 1), (строка – 2, столбец + 1), (строка – 2, столбец – 1), (строка + 1, столбец + 2), (строка + 1, столбец - 2), (строка – 1, столбец + 2), (строка – 1, столбец – 2) ] valid_moves = [r * 7 + c для r, c в ходах, если 0