Добавлен: 03.12.2023
Просмотров: 47
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство науки и высшего образования Российской ФедерацииФедеральное государственное бюджетное образовательное учреждениевысшего образованияТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТСИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ(ТУСУР)Кафедра компьютерных систем в управлении и проектировании (КСУП)Отчёт по контрольной работе № 2по дисциплине«Искусственный интеллект»Вариант 3Томск – 2021Вариант 3 "Миссионеры и людоеды". Поиск в глубинуМиссионеры и людоеды:Три миссионера и три людоеда находятся по одну сторону реки, черезкоторую они хотят переправиться. В их распоряжении имеется лодка, котораяможет выдержать вес только двух человек. Кроме того, если в какой-то мо-мент число людоедов станет больше числа миссионеров, миссионеры будутсъедены независимо от того, на каком берегу реки это случится.Указания к решению:Различные состояния этой задачи однозначно задаютсяинформацией, на каком берегу находятся лодка и сколько миссионеров и лю-доедов на этом же берегу.Поэтому структураstate(ЛокализацияЛодки, ЧислоМиссионеровНаТомБерегуГдеЛодка, ЧислоЛюдоедовНаТомБерегуГдеЛодка)полностью описывает состояние. Допустимые состояния для решения задачи - это те, когда людоеды не могут съесть миссионеров ни на том берегу, где лодка, ни на противоположном,Возможные значение первого аргумента: атомы west (западный берег) и east (восточный берег). Возможные значения остальных аргументов: 0, 1, 2 или 3.Начальное состояние: state(east,3, 3).Конечное состояние: state(west,3,3).Решение:По приведенным тут указаниям решить задачу не удалось, так как мало знать сколько людоедов и миссионеров, на берегу - надо знать еще сколько находится в лодке - иначе как знать сколько из них высадить?
Поэтому было взято такое состояние:state(БерегЛодки,берег(Миссионеров, Людоедов),лодка(МиссионеровЛодка, ЛюдоедовЛодка)).Однако, допустим мы попали в состояние когда на восточном берегу 2 миссионера и 1 людоед, а также в лодке 2 людоеда. Надо определить возможное следующее состояние. Чтобы сделать это надо сначала рассчитать "а что там, на втором берегу", вычислить можно так:МиссионеровНаДругом = 3 - Миссионеров - МиссионеровЛодка,ЛюдоедовНаДругом = 3 - Людоедов - ЛюдоедовЛодка.Так как такой расчет надо выполнять часто - для этого написан предикат:другой_берег(west, east).другой_берег(east, west).расчет_друго_берега(берег(Миссионеров, Людоедов),лодка(МиссионеровЛодка, ЛюдоедовЛодка),берег(МиссионеровНаДругом, ЛюдоедовНаДругом)):-МиссионеровНаДругом is 3 - Миссионеров - МиссионеровЛодка,ЛюдоедовНаДругом is 3 - Людоедов - ЛюдоедовЛодка.Тут виден также вспомогательный предикат, возвращающий противоположный берег (west->east и наоборот).В ходе поиска решения программа будет перебирать состояния, для каждого из которых надо проверять допустимо ли оно. Допустимость - это не только Миссионеров >= Людоедов, ведь если миссионеров нет - то людоедов на берегу можно оставить сколько угодно. Это также оформлено в виде отдельного правила:можно_оставить(берег(Миссионеров, Людоедов)):-% если миссионеров большеМиссионеров >= Людоедов;% или если некого естьМиссионеров is 0.Сама по себе смена состояний - это не так просто ведь:
state(БерегЛодки,берег(МиссионеровБерегПосле, ЛюдоедовБерегПосле),лодка(МиссионеровЛодкаПосле, ЛюдоедовЛодкаПосле))):-% выгрузка (всех сложить):ВсегоМиссионеров is МиссионеровБерег + МиссионеровЛодка,ВсегоЛюдоедов is ЛюдоедовБерег + ЛюдоедовЛодка,% выбрать кто плывет назад:between(0, 2, МиссионеровЛодкаПосле),МиссионеровЛодкаПосле =< ВсегоМиссионеров,between(0, 2, ЛюдоедовЛодкаПосле),ЛюдоедовЛодкаПосле =< ВсегоЛюдоедов,% проверка емкости лодкиЛюдейВЛодке is ЛюдоедовЛодкаПосле + МиссионеровЛодкаПосле,ЛюдейВЛодке > 0, ЛюдейВЛодке =< 2,% расчет кто остался на берегуМиссионеровБерегПосле is ВсегоМиссионеров - МиссионеровЛодкаПосле,ЛюдоедовБерегПосле is ВсегоЛюдоедов - ЛюдоедовЛодкаПосле,% проверка что на берегу не съедят миссонеров:можно_оставить(берег(МиссионеровБерегПосле, ЛюдоедовБерегПосле)).Назад поплывет 0, 1 или 2 миссионера, а также 0, 1 или 2 людоеда. Для перебора их количества используется встроенная функция between. Она работает так:% Вызов:?- between(3, 7, X).% Результаты:X = 3;X = 4;X = 5;X = 6;X = 7.То есть она перебирает все числа в диапазоне.После того как выбрано не более двух людоедов и не более двух миссионеров - программа считает их сумму (сколько человек поплывет в лодке) и проверяет ограничение вместимости лодки.Исходя из того, кто оказался в лодке - программа определяет кто остался на берегу.При выполнении переправы содержимое лодки оказывается на другом берегу, однако чтобы узнать "кто там" - выполняется расчет другого берега, как было показано выше:переправа(state(БерегЛодки,берег(МиссионеровБерег, ЛюдоедовБерег),лодка(МиссионеровЛодка, ЛюдоедовЛодка)),state(ДругойБерегЛодки,берег(МиссионеровДругойБерег, ЛюдоедовДругойБерег),лодка(МиссионеровЛодка, ЛюдоедовЛодка))):-другой_берег(БерегЛодки, ДругойБерегЛодки),расчет_друго_берега(берег(МиссионеровБерег, ЛюдоедовБерег),лодка(МиссионеровЛодка, ЛюдоедовЛодка),берег(МиссионеровДругойБерег, ЛюдоедовДругойБерег)).Теперь, когда описано правило смены состояний, остается лишь добавить правило поиска в глубину:% поиск в глубинуdfs(Состояние, _, Path):-Состояние = state(west,берег(МиссионеровБерег, ЛюдоедовБерег),лодка(МиссионеровЛодка, ЛюдоедовЛодка)),ВсегоМиссионеров is МиссионеровБерег + МиссионеровЛодка,ВсегоЛюдоедов is ЛюдоедовБерег + ЛюдоедовЛодка,
ВсегоМиссионеров is 3, ВсегоЛюдоедов is 3,Path = [Состояние, state(west, берег(3, 3), лодка(0, 0))].dfs(Состояние, Старые, Path):-следующее_состояние(Состояние, Следующее),not(member(Следующее, Старые)),dfs(Следующее, [Состояние|Старые], ПутьИзСледующего),Path = [Состояние|ПутьИзСледующего].Это правило состоит из двух частей. Первая часть проверяет окончание переправы. Такое случится если ложка окажется на правом берегу west и если собрать лодку и текущий берег - то на них окажутся все 3 людоеда и все 3 миссионера.Такой случай описан отдельно, так как если из этого состояния выполнить генерацию следующих - то программа обязательно сформирует назад НЕПУСТУЮ лодку, а значит - на берегу будут не все люди.Если же текущее состояние не конечное - то на его основе формируется следующее состояние и программа ищет из него.Чтобы один людоед не плавал вечно с одного берега на другой - программа хранит список уже посещенных состояний (передается в dfs в виде второго аргумента - списка).Вызывать функцию надо так:CurrentState = state(east, берег(3, 3), лодка(0, 0)),dfs(CurrentState, [], Path).Результат ее работы:
Поэтому было взято такое состояние:state(БерегЛодки,берег(Миссионеров, Людоедов),лодка(МиссионеровЛодка, ЛюдоедовЛодка)).Однако, допустим мы попали в состояние когда на восточном берегу 2 миссионера и 1 людоед, а также в лодке 2 людоеда. Надо определить возможное следующее состояние. Чтобы сделать это надо сначала рассчитать "а что там, на втором берегу", вычислить можно так:МиссионеровНаДругом = 3 - Миссионеров - МиссионеровЛодка,ЛюдоедовНаДругом = 3 - Людоедов - ЛюдоедовЛодка.Так как такой расчет надо выполнять часто - для этого написан предикат:другой_берег(west, east).другой_берег(east, west).расчет_друго_берега(берег(Миссионеров, Людоедов),лодка(МиссионеровЛодка, ЛюдоедовЛодка),берег(МиссионеровНаДругом, ЛюдоедовНаДругом)):-МиссионеровНаДругом is 3 - Миссионеров - МиссионеровЛодка,ЛюдоедовНаДругом is 3 - Людоедов - ЛюдоедовЛодка.Тут виден также вспомогательный предикат, возвращающий противоположный берег (west->east и наоборот).В ходе поиска решения программа будет перебирать состояния, для каждого из которых надо проверять допустимо ли оно. Допустимость - это не только Миссионеров >= Людоедов, ведь если миссионеров нет - то людоедов на берегу можно оставить сколько угодно. Это также оформлено в виде отдельного правила:можно_оставить(берег(Миссионеров, Людоедов)):-% если миссионеров большеМиссионеров >= Людоедов;% или если некого естьМиссионеров is 0.Сама по себе смена состояний - это не так просто ведь:
-
исходя из состояния лодки и берега надо понять кто поплывет назад; -
исходя из состояния лодки и берега надо определить кто там на противоположном берегу.
state(БерегЛодки,берег(МиссионеровБерегПосле, ЛюдоедовБерегПосле),лодка(МиссионеровЛодкаПосле, ЛюдоедовЛодкаПосле))):-% выгрузка (всех сложить):ВсегоМиссионеров is МиссионеровБерег + МиссионеровЛодка,ВсегоЛюдоедов is ЛюдоедовБерег + ЛюдоедовЛодка,% выбрать кто плывет назад:between(0, 2, МиссионеровЛодкаПосле),МиссионеровЛодкаПосле =< ВсегоМиссионеров,between(0, 2, ЛюдоедовЛодкаПосле),ЛюдоедовЛодкаПосле =< ВсегоЛюдоедов,% проверка емкости лодкиЛюдейВЛодке is ЛюдоедовЛодкаПосле + МиссионеровЛодкаПосле,ЛюдейВЛодке > 0, ЛюдейВЛодке =< 2,% расчет кто остался на берегуМиссионеровБерегПосле is ВсегоМиссионеров - МиссионеровЛодкаПосле,ЛюдоедовБерегПосле is ВсегоЛюдоедов - ЛюдоедовЛодкаПосле,% проверка что на берегу не съедят миссонеров:можно_оставить(берег(МиссионеровБерегПосле, ЛюдоедовБерегПосле)).Назад поплывет 0, 1 или 2 миссионера, а также 0, 1 или 2 людоеда. Для перебора их количества используется встроенная функция between. Она работает так:% Вызов:?- between(3, 7, X).% Результаты:X = 3;X = 4;X = 5;X = 6;X = 7.То есть она перебирает все числа в диапазоне.После того как выбрано не более двух людоедов и не более двух миссионеров - программа считает их сумму (сколько человек поплывет в лодке) и проверяет ограничение вместимости лодки.Исходя из того, кто оказался в лодке - программа определяет кто остался на берегу.При выполнении переправы содержимое лодки оказывается на другом берегу, однако чтобы узнать "кто там" - выполняется расчет другого берега, как было показано выше:переправа(state(БерегЛодки,берег(МиссионеровБерег, ЛюдоедовБерег),лодка(МиссионеровЛодка, ЛюдоедовЛодка)),state(ДругойБерегЛодки,берег(МиссионеровДругойБерег, ЛюдоедовДругойБерег),лодка(МиссионеровЛодка, ЛюдоедовЛодка))):-другой_берег(БерегЛодки, ДругойБерегЛодки),расчет_друго_берега(берег(МиссионеровБерег, ЛюдоедовБерег),лодка(МиссионеровЛодка, ЛюдоедовЛодка),берег(МиссионеровДругойБерег, ЛюдоедовДругойБерег)).Теперь, когда описано правило смены состояний, остается лишь добавить правило поиска в глубину:% поиск в глубинуdfs(Состояние, _, Path):-Состояние = state(west,берег(МиссионеровБерег, ЛюдоедовБерег),лодка(МиссионеровЛодка, ЛюдоедовЛодка)),ВсегоМиссионеров is МиссионеровБерег + МиссионеровЛодка,ВсегоЛюдоедов is ЛюдоедовБерег + ЛюдоедовЛодка,
ВсегоМиссионеров is 3, ВсегоЛюдоедов is 3,Path = [Состояние, state(west, берег(3, 3), лодка(0, 0))].dfs(Состояние, Старые, Path):-следующее_состояние(Состояние, Следующее),not(member(Следующее, Старые)),dfs(Следующее, [Состояние|Старые], ПутьИзСледующего),Path = [Состояние|ПутьИзСледующего].Это правило состоит из двух частей. Первая часть проверяет окончание переправы. Такое случится если ложка окажется на правом берегу west и если собрать лодку и текущий берег - то на них окажутся все 3 людоеда и все 3 миссионера.Такой случай описан отдельно, так как если из этого состояния выполнить генерацию следующих - то программа обязательно сформирует назад НЕПУСТУЮ лодку, а значит - на берегу будут не все люди.Если же текущее состояние не конечное - то на его основе формируется следующее состояние и программа ищет из него.Чтобы один людоед не плавал вечно с одного берега на другой - программа хранит список уже посещенных состояний (передается в dfs в виде второго аргумента - списка).Вызывать функцию надо так:CurrentState = state(east, берег(3, 3), лодка(0, 0)),dfs(CurrentState, [], Path).Результат ее работы: