Каннибалы и Миссионеры с Силой

Question

Мне нужна помощь с математическим заданием, которое наш профессор дал нам. Любые предложения помогут. Проблема в:

Есть N каннибалов и M миссинаров. Все миссионеры имеют атрибут прочности, который может быть 1 или любым положительным целым числом. Сила указывает, сколько каннибалов он может отбить.

В основном: есть две стороны реки, есть двухслотовая лодка, и вам нужно перевести всех парней на другую сторону, не позволяя людоедам съесть миссионеров.

Как бы вы написали программу для этого? Каков будет алгоритм переноса-группировки?

Спасибо в ожидании,

Отметка.

Answer 1

Смоделируйте вашу проблему как граф состояний.

Здесь состояние ({L, R}ⁿ, {L, R}^m, {L, R}), где:

• Первый n записи: по одной на каждого миссионера - где он находится: левый / правый берег реки
• следующий,m записи: одна для каждого canibal- где он: левый / правый берег реки
• Последняя запись для лодки

Это ваши вершины - вы также должны урезать недопустимые состояния - где сила миссионеров недостаточна в одну (или более) сторону. Это легко рассчитать для каждого состояния.

Ваши края:

E = { (S1,S2) | Can move in one boat ride from S1 to S2 }

Все осталось сделать - используйте алгоритм кратчайшего пути, чтобы найти кратчайший путь из: (L,L,....,L) в (R,R,...,R),

Вы можете использовать BFS для этой задачи, или даже двунаправленный поиск - или информированный алгоритм (с допустимой эвристикой), такой как алгоритм A*.

PS. "График" является просто концептуальным, на практике у вас будет функция next:S->2^S, что задано состояние - возвращает все действительные наследники этого состояния (утверждает, что вы можете получить к ним, используя одно ребро на графике из S). Это позволит вам "генерировать график" на лету.

Ваш next(S) функция должна выглядеть примерно так (высокоуровневый псевдокод без оптимизации):

next(S):
   let x be the bank where the boat is, and y the other bank
   for each person p1 on bank x:
      S' = S where boat and p1 moved from x to y
      if S' is valid according to strength limitations, yield S'
      for each p2 != p1 on bank x:
         S' = S where boat and p1 and p2 moved from x to y
         if S' is valid according to strength limitations, yield S'