Нахождение эвристического миссионера и людоедов

Question

Я пытаюсь построить * алгоритм, который решит проблему миссионеров и людоедов.Я не уверен в эвристике, которую я должен использовать, и в том, что я должен искать, чтобы попытаться решить эту проблему.

Это требования и способ, которым вы можете двигаться.

Четыре миссионераи четыре людоеда находятся на Западном берегу (W) реки, вместе с лодкой, которая может вместить до трех человек: 0 <вместимость лодки ≤ 3. Найдите способ доставить всех на Восточный берег (E), не покидаягруппа миссионеров в одном месте превосходила каннибалов в этом месте.Эта проблема известна в ИИ, потому что она была предметом первой статьи, которая подошла к постановке проблемы с аналитической точки зрения (Amerel, 1968). </p>

Answer 1

Это конкретное пространство состояний достаточно мало, чтобы вы могли исследовать его при первом поиске в ширину.

В целом, однако, один плодотворный источник эвристики - отбросить одно или несколько ограничений, которые усложняют проблему.тем самым «расслабляя» проблему (это технический термин).Выяснить, какие из них - искусство, к сожалению.Для этой конкретной проблемы вы можете отменить ограничение, заключающееся в том, что каннибалы не превосходят численностью миссионеров, что делает эвристическую ценность простой функцией того, где находится лодка и сколько людей на каждой стороне реки.