На этом шаге мы рассмотрим решение этой задачи.
Теперь у нас есть все необходимое для решения задачи. Напомню: когда мы решаем задачу, используя функции поиска bfs(), dfs() и astar(), то получаем узел, который с помощью node_to_path() преобразуем в список состояний, приводящий к решению. Еще нам потребуется способ преобразовать этот список в понятную наглядную последовательность шагов для решения задачи о миссионерах и людоедах.
Функция display_solution() преобразует путь решения в наглядный вывод - удобочитаемое решение задачи. Эта функция перебирает все состояния, вошедшие в готовый путь, а также отслеживает последнее состояние. Она анализирует разницу между последним состоянием и состоянием, которое отображается в настоящий момент, чтобы выяснить, сколько миссионеров и людоедов в каком направлении пересекло реку.
def display_solution(path: List[MCState]): if len(path) == 0: # санитарная проверка return old_state: MCState = path[0] print(old_state) for current_state in path[1:]: if current_state.boat: print("{} миссионеров и {} людоедов переехали с восточного на западный берег.\n" .format(old_state.em - current_state.em, old_state.ec - current_state.ec)) else: print("{} миссионеров и {} людоедов переехали с западного на восточный берег.\n" .format(old_state.wm - current_state.wm, old_state.wc - current_state.wc)) print(current_state) old_state = current_state
В функции display_solution() использовано преимущество, обусловленное тем, что MCState умеет вывести красивую сводку о своих данных с помощью __str__().
Последнее, что нам остается сделать, - на самом деле решить задачу о миссионерах и каннибалах. Для этого удобно будет повторно задействовать функцию поиска, которую мы уже написали, потому что она является параметризованной. Здесь применяется bfs(), потому что использование dfs() потребовало бы пометить ссылочно разные состояния с одинаковым значением как равные, a astar() требует эвристики.
if __name__ == "__main__": start: MCState = MCState(MAX_NUM, MAX_NUM, True) solution: Optional[Node[MCState]] = bfs(start, MCState.goal_test, MCState.successors) if solution is None: print("Решение не найдено!") else: path: List[MCState] = node_to_path(solution) display_solution(path)
Приятно видеть, насколько гибкими могут быть параметризованные функции поиска. Их можно легко адаптировать для решения разнообразных задач. Вы должны увидеть что-то вроде следующего списка:
На западном берегу есть 3 миссионеров и 3 людоедов. На восточном берегу есть 0 миссионеров и 0 людоедов. Лодка находится на западном берегу. 0 миссионеров и 2 людоедов переехали с западного на восточный берег. На западном берегу есть 3 миссионеров и 1 людоедов. На восточном берегу есть 0 миссионеров и 2 людоедов. Лодка находится на восточном берегу. 0 миссионеров и 1 людоедов переехали с восточного на западный берег. На западном берегу есть 3 миссионеров и 2 людоедов. На восточном берегу есть 0 миссионеров и 1 людоедов. Лодка находится на западном берегу. 0 миссионеров и 2 людоедов переехали с западного на восточный берег. На западном берегу есть 3 миссионеров и 0 людоедов. На восточном берегу есть 0 миссионеров и 3 людоедов. Лодка находится на восточном берегу. 0 миссионеров и 1 людоедов переехали с восточного на западный берег. На западном берегу есть 3 миссионеров и 1 людоедов. На восточном берегу есть 0 миссионеров и 2 людоедов. Лодка находится на западном берегу. 2 миссионеров и 0 людоедов переехали с западного на восточный берег. На западном берегу есть 1 миссионеров и 1 людоедов. На восточном берегу есть 2 миссионеров и 2 людоедов. Лодка находится на восточном берегу. 1 миссионеров и 1 людоедов переехали с восточного на западный берег. На западном берегу есть 2 миссионеров и 2 людоедов. На восточном берегу есть 1 миссионеров и 1 людоедов. Лодка находится на западном берегу. 2 миссионеров и 0 людоедов переехали с западного на восточный берег. На западном берегу есть 0 миссионеров и 2 людоедов. На восточном берегу есть 3 миссионеров и 1 людоедов. Лодка находится на восточном берегу. 0 миссионеров и 1 людоедов переехали с восточного на западный берег. На западном берегу есть 0 миссионеров и 3 людоедов. На восточном берегу есть 3 миссионеров и 0 людоедов. Лодка находится на западном берегу. 0 миссионеров и 2 людоедов переехали с западного на восточный берег. На западном берегу есть 0 миссионеров и 1 людоедов. На восточном берегу есть 3 миссионеров и 2 людоедов. Лодка находится на восточном берегу. 1 миссионеров и 0 людоедов переехали с восточного на западный берег. На западном берегу есть 1 миссионеров и 1 людоедов. На восточном берегу есть 2 миссионеров и 2 людоедов. Лодка находится на западном берегу. 1 миссионеров и 1 людоедов переехали с западного на восточный берег. На западном берегу есть 0 миссионеров и 0 людоедов. На восточном берегу есть 3 миссионеров и 3 людоедов. Лодка находится на восточном берегу.
На следующем шаге мы подведем некоторые итоги.
