На этом шаге мы приведем описание класса, предназначенного для решения указанной задачи.
Представим задачу с помощью структуры, которая отслеживает ситуацию на западном берегу. Сколько миссионеров и людоедов здесь находятся? Причалена ли к западному берегу лодка? Получив эти знания, мы можем выяснить, кто находится на восточном берегу, потому что все, кто не на западном берегу, находятся на восточном.
Прежде всего создадим небольшую вспомогательную переменную для отслеживания максимального количества миссионеров или людоедов. Затем определим основной класс.
from __future__ import annotations from typing import List, Optional from generic_search import bfs, Node, node_to_path MAX_NUM: int = 3 class MCState: def __init__(self, missionaries: int, cannibals: int, boat: bool) -> None: self.wm: int = missionaries # миссионеры с западного берега self.wc: int = cannibals # людоеды с западного берега self.em: int = MAX_NUM - self.wm # миссионеры с восточного берега self.ec: int = MAX_NUM - self.wc # людоеды с восточного берега self.boat: bool = boat def __str__(self) -> str: return ("На западном берегу есть {} миссионеров и {} людоедов.\n" "На восточном берегу есть {} миссионеров и {} людоедов.\n" "Лодка находится на {} берегу.").format(self.wm, self.wc, self.em, self.ec, ("западном" if self.boat else "восточном"))
Класс MCState инициализируется в зависимости от количества миссионеров и людоедов, находящихся на западном берегу, а также от местоположения лодки. Он умеет красиво выводить свои данные, что окажется полезным позже, при отображении решения задачи.
Действуя в рамках существующих функций поиска, мы должны определить функцию проверки того, является ли состояние целевым, и функцию для поиска преемников для любого состояния. Функция проверки целевого состояния, как и в задаче прохода по лабиринту, довольно проста. Наша цель состоит в том, чтобы просто достичь разрешенного состояния, при котором все миссионеры и людоеды оказываются на восточном берегу. Мы добавим это в MCState в качестве метода.
def goal_test(self) -> bool:
return self.is_legal and self.em == MAX_NUM and self.ec == MAX_NUM
Чтобы создать функцию преемников, необходимо перебрать все возможные шаги, которые могут быть сделаны для перевозки с одного берега на другой, и затем проверить, приводит ли каждый из них к разрешенному состоянию. Напомним, что разрешенное состояние - такое, при котором на каждом берегу количество людоедов не превышает количества миссионеров. Чтобы определить это, мы можем создать вспомогательное свойство (как метод в MCState), проверяющее, допустимо ли данное состояние.
@property
def is_legal(self) -> bool:
if self.wm < self.wc and self.wm > 0:
return False
if self.em < self.ec and self.em > 0:
return False
return True
Реальная функция преемников немного многословна. Это сделано для того, чтобы она была понятной. Функция пытается добавить каждую возможную комбинацию из одного или двух человек, пересекающих реку с того берега, на котором в настоящий момент находится каноэ. Когда все возможные ходы будут добавлены, функция отфильтровывает те, что действительно допустимы, используя списковое включение (или генератор списков, list comprehension). Эта функция также является методом MCState.
def successors(self) -> List[MCState]:
sucs: List[MCState] = []
if self.boat: # лодка на западном берегу
if self.wm > 1:
sucs.append(MCState(self.wm - 2, self.wc, not self.boat))
if self.wm > 0:
sucs.append(MCState(self.wm - 1, self.wc, not self.boat))
if self.wc > 1:
sucs.append(MCState(self.wm, self.wc - 2, not self.boat))
if self.wc > 0:
sucs.append(MCState(self.wm, self.wc - 1, not self.boat))
if (self.wc > 0) and (self.wm > 0):
sucs.append(MCState(self.wm - 1, self.wc - 1, not self.boat))
else: # лодка на восточном берегу
if self.em > 1:
sucs.append(MCState(self.wm + 2, self.wc, not self.boat))
if self.em > 0:
sucs.append(MCState(self.wm + 1, self.wc, not self.boat))
if self.ec > 1:
sucs.append(MCState(self.wm, self.wc + 2, not self.boat))
if self.ec > 0:
sucs.append(MCState(self.wm, self.wc + 1, not self.boat))
if (self.ec > 0) and (self.em > 0):
sucs.append(MCState(self.wm + 1, self.wc + 1, not self.boat))
return [x for x in sucs if x.is_legal]
На следующем шаге мы рассмотрим решение этой задачи.
