Добавлен: 05.12.2023
Просмотров: 52
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ
(ТУСУР)
Кафедра компьютерных систем в управлении и проектировании
(КСУП)
Отчёт по контрольной работе № 2
по дисциплине
«Искусственный интеллект»
Вариант 3
Выполнили: ст. гр.з589П8-4
____________Игумнов Ф.С.
«___»__________2021 г.
Проверил:
_________ Зюзьков В.М.
«___»__________2021 г.
Томск – 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).
Тутвидентакжевспомогательныйпредикат,возвращающийпротивоположныйберег(west->eastинаоборот).Входепоискарешенияпрограммабудетперебиратьсостояния,длякаждогоизкоторыхнадопроверять допустимо ли оно. Допустимость - это не только Миссионеров >= Людоедов, ведьесли миссионеров нет - то людоедов на берегу можно оставить сколько угодно. Это такжеоформлено ввидеотдельногоправила:
можно_оставить(берег(Миссионеров, Людоедов)):-
% если миссионеров больше Миссионеров >= Людоедов;
% или если некого есть Миссионеров is 0.
Самапосебесменасостояний-этонетакпростоведь:
-
исходя из состояния лодки и берега надо понять кто поплывет назад; -
исходя из состояния лодки и берега надо определить кто там на противоположном берегу.
следующее_состояние(Состояние, Следующее):- разгрузка_загрузка(Состояние, СостояниеПослеПерегрузки), переправа(СостояниеПослеПерегрузки, Следующее).
Цельразгрузкиизагрузки-сформироватьлодкудляотплытияназадизтехлюдей,чтоестьвлодкеинатекущемберегу:
разгрузка_загрузка( state(БерегЛодки,
берег(МиссионеровБерег, ЛюдоедовБерег), лодка(МиссионеровЛодка, ЛюдоедовЛодка)),
state(БерегЛодки,
берег(МиссионеровБерегПосле, ЛюдоедовБерегПосле), лодка(МиссионеровЛодкаПосле, ЛюдоедовЛодкаПосле))):-
% выгрузка (всех сложить):
ВсегоМиссионеров is МиссионеровБерег + МиссионеровЛодка, ВсегоЛюдоедов is ЛюдоедовБерег + ЛюдоедовЛодка,
% выбрать кто плывет назад: between(0, 2, МиссионеровЛодкаПосле),
МиссионеровЛодкаПосле =< ВсегоМиссионеров,
between(0, 2, ЛюдоедовЛодкаПосле), ЛюдоедовЛодкаПосле =< ВсегоЛюдоедов,
% проверка емкости лодки
Назадпоплывет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 ЛюдоедовБерег + ЛюдоедовЛодка,
Это правило состоит из двух частей. Первая часть проверяет окончание переправы. Такоеслучитсяеслиложкаокажетсянаправомберегуwestиеслисобратьлодкуитекущийберег-тонанихокажутсявсе3людоедаивсе3 миссионера.Такой случай описан отдельно, так как если из этого состояния выполнить генерациюследующих-топрограммаобязательносформируетназадНЕПУСТУЮлодку,азначит-наберегу будут невселюди.Еслижетекущеесостояниенеконечное-тонаегоосновеформируетсяследующеесостояниеипрограммаищетиз него.Чтобыодинлюдоеднеплавалвечносодногобереганадругой-программахранитсписокужепосещенныхсостояний(передаетсяв dfsввидевторогоаргумента-списка).Вызыватьфункциюнадотак:
CurrentState = state(east, берег(3, 3), лодка(0, 0)), dfs(CurrentState, [], Path).
Результатееработы: