Решение логических задач на Prolog

Заказать решение задачи на Prolog или попросить помощь

Язык пролог начал зарождаться в далеком 1879 году, точнее в этом году известный ученый Людвиг Фреге предложил исчисление предикатов, которое лежит в основе логического программирования. Фреге был не только математиком, но и философом (как и большинство других известных ученых своего времени). В то время еще не начала рушиться классическая картина мира, популярным философским учением являлся позитивизм Конта, и Фреге разделял эти взгляды, относясь к школе аналитической философии. Одной из своих задач философы видели формализацию знаний, т.е. пытались выразить знания на более точном, научном языке, например так, как делают математики. Работы по исчислению предикатов лаконично вписались в это направление.

Позже по этой теме работали другие известные философы, такие как Бертран Рассел и Людвиг Витгенштейн, представители более новой школы логического позитивизма. Исследования ведутся до сих пор, но позитивисты несколько отошли от исчисления предикатов в сторону темпоральной логики.

В 1980х годах уже появились эффективные реализации Пролога и он рассматривался как универсальный язык, при этом использовался для реализации реляционных СУБД, автоматического доказательства теорем, разработки компиляторов, САПР и других областях [1]. В начале 1990х годов пролог продвигался, в большей мере, как удобное средство разработки графического интерфейса (лучших инструментов тогда не было) [4]. В 1992 году провалился японский национальный проект компьютера пятого поколения, одной из целей которого было исследование искусственного интеллекта. В качестве языка программирования этого компьютера был выбран пролог, популярность которого резко упала [5]. В настоящее время, пролог используется , в основном, при разработке трансляторов и в задачах искусственного интеллекта [6].

Более подробно про историю языка Пролог можно почитать в толстых книгах [1, 2, 3], но а я привел эти факты чтобы чуть-чуть отразить особенности развития этого языка и решаемых на нем задач. Традиционно в российских ВУЗах на предметах «логическое и функциональное программирование», «искусственный интеллект» выдаются задания связанные с решением логических задач. Ноги у этих задач растут из автоматического доказательства теорем.

В статье рассматривается 2 типа логических задач — задачи на установление соответствия и задачи поиска в пространстве состояний.

Логические задачи

Задачи на установление соответствия

Задачи на установление соответствия очень похожи на работу Шерлок Холмса, в них дается набор фактов, которые надо увязать между собой чтобы найти решение. Машина логического вывода решает такие задачи полным перебором, никакого пути поиска решения при этом нет.

Примером такой головоломки может быть задача про купе:

Как то раз случай свёл в купе астронома, поэта , прозаика и драматурга. Это были Алексеев, Борисов, Константинов и Дмитриев. Оказалось, что каждый из них взял с собой книгу написанную одним из пассажиров этого купе. Алексеев и Борисов углубились в чтение предварительно обменявшись книгами. Поэт читал пьесу, прозаик — очень молодой человек, выпустивший свою книгу, говорил что он никогда и ни чего не читал по астрономии. Борисов купил одно из произведений Дмитриева. Никто из пассажиров не читал свои книги. Что читал каждый из них, кто кем был?

Перед тем, как запросить у машины логического вывода решение задачи, необходимо формализовать имеющиеся факты. В этой задаче даны 4 имени, 4 профессии и 4 вида книг. Профессии задавать не обязательно, т.к. профессию можно вывести из книги.

man(alekseev).
man(borisov).
man(konstantinov).
man(dmitriev).

writebook(astronomy).
writebook(poetry).
writebook(prose).
writebook(piece).

Пассажир купе будет описываться фактом passenger:

passenger(Name, Read, Buy, Write)

Чтобы получить решение, надо попросить машину логического вывода найти четырех таких пассажиров с разными именами, читающих, написавших и купивших разные книги. Вспомогательный предикат unique, следящий за тем, чтобы элементы в списке не повторялись, описан в соседней статье: Задачи на списки [Prolog].

solve(Solve):-
  Solve = [passenger(X, XRead, XBuy, XWrite), passenger(Y, YRead, YBuy, YWrite),
          passenger(Z, ZRead, ZBuy, ZWrite), passenger(W, WRead, WBuy, WWrite)],

  % 4 разных пасажира
  man(X), man(Y), man(Z), man(W), unique([X, Y, Z, W]),

  % каждый написал книгу
  writebook(XWrite), writebook(YWrite),
  writebook(ZWrite), writebook(WWrite),
  unique([XWrite, YWrite, ZWrite, WWrite]),

  % каждый купил книгу
  writebook(XBuy), writebook(YBuy),
  writebook(ZBuy), writebook(WBuy),
  unique([XBuy, YBuy, ZBuy, WBuy]),

  % каждый читает книгу
  writebook(XRead), writebook(YRead),
  writebook(ZRead), writebook(WRead),
  unique([XRead, YRead, ZRead, WRead]).

Если запустить такое правило — мы получим все варианты решения без учета ограничений, описанных в задаче. Для проверки того, что никто не читает и не покупал свою книгу потребуется вспомогательное правило:

check([]):-!.
check([passenger(_, XRead, XBuy, XWrite)|T]):-
  !, not(XRead = XWrite), not(XBuy = XWrite), check(T).

Остальные ограничения можно описать следующим образом:

  % поэт читает пьесу
  member(passenger(_, piece, _, poetry), Solve),

  % прозаик читает не астрономию
  not(member(passenger(_, astronomy, _, prose), Solve)),
  % прозаик не покупал астрономию
  not(member(passenger(_, _, astronomy, prose), Solve)),

  % никто не читает и не покупал свою книгу
  check(Solve),

  % алексеев и борисов обменялись книгами
  member(passenger(alekseev, AlekseevRead, AlekseevBuy, _), Solve),
  member(passenger(borisov, AlekseevBuy, AlekseevRead, _), Solve),

  % Борисов купил произведение Дмитриева
  member(passenger(dmitriev, _, _, DmitrievWrite), Solve),
  member(passenger(borisov, DmitrievWrite, _, _), Solve)

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

рис. 1 результат решения логической задачи про купе

рис. 1 результат решения логической задачи про купе

Рассмотрим еще одну задачу на поиск соответствия:

Три друга заняли первое, второе и третье места в соревнованиях универсиады. Друзья — разной национальности, зовут их по-разному и любят они разные виды спорта.

Майкл предпочитает баскетбол и играет лучше чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крикет занял первое место.

Кто является австралийцем? Каким видом спорта занимается Ричард?

Решение задачи опять начинается с формализации фактов. Пролог не знает что теннис — это спорт, а Саймон — имя. Сообщим ему об этом:

nation(austrian).
nation(american).
nation(israeli).

sport(basketball).
sport(tennis).
sport(cricket).

name(mikl).
name(saimon).
name(richard).

prize(1).
prize(2).
prize(3).

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

solve(Mans):-
  Mans = [man(X, XNat, XSp, XP), man(Y, YNat, YSp, YP), man(Z, ZNat, ZSp, ZP)],

  name(X), name(Y), name(Z), unique([X, Y, Z]),
  nation(XNat), nation(YNat), nation(ZNat), unique([XNat, YNat, ZNat]),
  sport(XSp), sport(YSp), sport(ZSp), unique([XSp, YSp, ZSp]),
  prize(XP), prize(YP), prize(ZP), unique([XP, YP, ZP]),

  % Майкл играет в баскетбол
  member(man(mikl, _, basketball, MiklPos), Mans),

  % Майкл играет лучше чем американец
  member(man(_, american, _, AmerPos), Mans), MiklPos < AmerPos,

  % Саймон - израильтянин
  member(man(saimon, israeli, _, SaimonPos), Mans),

  % Саймон играет лучше теннисиста
  member(man(_, _, tennis, TennPos), Mans), SaimonPos < TennPos,

  % игрок в крикет занят первое место
  member(man(_, _, cricket, 1), Mans).

start(Solve):-
  solve(Solve), Solve = [man(_, _, _, 1), man(_, _, _, 2), man(_, _, _, 3)].

рис. 2 результат решения логической задачи про спортсменов

рис. 2 результат решения логической задачи про спортсменов

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

Задачи поиска в пространстве состояний

Во многих логических задачах заданы начальное и конечное условия (состояния), и какие-либо правила поведения. Требуется найти последовательность действий, которая переведет из начального состояния в конечное. Условно, такие задачи можно разделить на 3 типа, которые мы рассмотрим на примерах.

Фиксированное число состояний

Если множество возможных состояний программы очень мало — то их можно задать руками в виде графа, где вершины — состояния, а дуги отражают возможность перехода между ними. Для решения задачи достаточно запустить поиск пути из начального состояния в конечное. Если требуется найти оптимальный путь, то к графу применяют алгоритм обхода в ширину, если же требуется найти все варианты решения — то обходят в глубину.

В качестве примера рассмотрим следующую задачу:

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

  1. Найди путь в лабиринте от входа до входа,не посещая дважды одной и той же комнаты;
  2. Найти путь с посещением золотой комнаты;
  3. Найти путь,избегающий запрещенных к посещению комнат.

Как именно выглядит лабиринт в задаче не сказано (нет информации о расположении переходов). Предположим, возможны следующие переходы:

edge(in, out).
edge(in, gold).
edge(in, monster).
edge(in, robber).

edge(gold, out).
edge(gold, monster).
edge(gold, robber).

edge(monster, out).
edge(monster, gold).
edge(monster, robber).

edge(robber, out).
edge(robber, gold).
edge(robber, monster).

Собственно, но этом решение закончилось, осталось написать 3 запроса (по запросу на каждый пункт задания):

?- dfs(in, out, [], Path). %1

?- dfs(in, out, [], Path), member((_, gold), Path). %2

?- dfs(in, out, [], Path), not(member((_, robber), Path)), not(member((_, monster), Path)). %3

Результаты выполнения запросов приведены на рисунках 3-5.

рис. 3 писк всех путей в лабиринте

рис. 3 писк всех путей в лабиринте

рис. 4 поиск путей через золотую комнату

рис. 4 поиск путей через золотую комнату

рис. 5 поиск путей без запрещенных комнат

рис. 5 поиск путей без запрещенных комнат

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

У фермера есть волк, коза и капуста. Все они находятся на левом берегу реки. Необходимо перевезти это «трио» на правый берег, но в лодку может поместиться что-то одно — волк, коза или капуста. Нельзя оставлять на одном берегу волка с козой и козу с капустой.

Фермер может перевозить зверей как с левого берега на правый, так и с правого на левый, а может и проехать порожняком. Требуется соблюдать, чтобы в его отсутствие звери не угрожали друг другу, т.е. состояние должно включать не только информацию о животных каждом берегу, но и положение фермера. Зверей на каждом берегу удобно представить списком.

Программа должна начать работать из состояния, в котором волк, коза и капуста находятся на левом берегу, возле них сидит фермер. Чтобы получить решение, программа достраивает граф (добавляя новые состояния и дуги) и одновременно выполняет его обход, до тех пор, пока вся живность не будет перевезена на правый берег.

Схематично, начало процесса работы программы показано на рис. 6. Состояния изображены цветными овалами, возможность перехода отражают дуги. Зеленым цветом выделены «правильные» состояния, которые обрабатывается программой, красным — «неверные» состояния (в которых коза съест капусту или волк — козу), желтым — уже обработанные состояния. Программа должна рассматривать все состояния, выполнять проверку и добавлять в граф только зеленые.

рис. 6 дерево решения задачи о волке, козе и капусте

рис. 6 дерево решения задачи о волке, козе и капусте

Для генерации новых состояний будем использовать правило permutation_length, которое выдаст нам все варианты подсписков заданной величины. В этой задаче, предел длины — 1, т.к. в лодке одно место. Когда подсписок будет получен, его нужно будет отнять от одного берега (правило subtraction) и прибавить к другому (стандартный предикат append).

Проверка корректности списка (правило check) и генерация новых состояний (правило generate) могут быть выражены следующим образом:

check(L):-
  member(wolf, L), !, not(member(goat, L));
  member(goat, L), !, not(member(cabbage, L));
  !.

generate((Left, Right, left)):-
  permutation_length(Left, 1, LeftPart),
  subtraction(Left, LeftPart, NewLeft),
  append(LeftPart, Right, NewRight),
  check(NewLeft),
  not(edge(_, (NewLeft, NewRight, right))),
  assert(edge((Left, Right, left), (NewLeft, NewRight, right))),
  fail;!.

generate((Left, Right, right)):-
  permutation_length(Right, 1, RightPart),
  subtraction(Right, RightPart, NewRight),
  append(RightPart, Left, NewLeft),
  check(NewRight),
  not(edge(_, (NewLeft, NewRight, left))),
  assert(edge((Left, Right, right), (NewLeft, NewRight, left))),
  fail;!.

Разберем по строчкам правило генерации из состояния фермера на левом берегу:

  • в 7 строке из списка зверей левого берега (Left) выделяется подсписок (LeftPart), длина которого не превышает 1;
  • в 8 строке LeftPart вычитается из Left, чтобы получить список зверей, остающихся на левом берегу (NewLeft);
  • в 9 строке список LeftPart присоединяется к правому берегу (Right), в результате получается список NewRight;
  • в следующем состоянии фермер переедет на правый берег и звери на левом берегу останутся совсем одни. Их безопасность проверяется в 10 строке;
  • нет смысла обрабатывать состояния, которые уже были обработаны (на рис. 6 выделены желтым цветом), в 11 строке выполняется соответствующая фильтрация;
  • 12 строка добавляет в граф новую дугу, которая идет из старого состояния (Left, Right, left) в новое — (NewLeft, NewRight, right);
  • чтобы программа добавила не одно, а все возможные новые состояния, 13 строка завершает правило неудачей. В результате, процесс вычисления откатывается до 7 строки, генерируется новый подсписок (LeftPart) и процесс повторяется.

Генерация новых состояний при переходе с правого берега выполняется аналогично. Теперь, когда мы можем порождать новые состояния, осталось лишь слегка модифицировать правило обхода графа в ширину, чтобы получить решение задачи:

path(Finish, [[Finish | PathPart] | _], [Finish | PathPart]):-!.
path(Finish, [[X | PathPart] | ProcList], Path):-
  generate(X),
  findall(Y, step(X, PathPart, Y), AdjNodes),
  append(ProcList, AdjNodes, NewProcList), !,
  path(Finish, NewProcList, Path).

step(X,T,[Y,X|T]):-
  edge(X,Y),
  not(member(Y,T)).

path(Start, Finish):-
    path(Finish, [[Start]], RPath), !,
    reverse(RPath,Path), write(Path).

Видно, что в обычный обход графа в ширину, описанный ранее, была добавлена лишь третья строчка. Перед тем, как искать смежные вершины (вызов findall в 4 строке) надо их сгененировать, чем и занимается наш generate.

Запрос для машины логического вывода и решение, найденное прологом, приведены на рис. 7.

рис. 7 решение задачи о волке, козе и капусте

рис. 7 решение задачи о волке, козе и капусте

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

Во время наводнения пять супружеских пар оказались отрезанными от суши водой. В их распоряжении была одна лодка, которая могла одновременно вместить только трех человек. Каждый супруг был настолько ревнив, что не мог позволить своей супруге находиться в лодке или на другом берегу с другим мужчиной (или мужчинами) в его отсутствие. Найти способ переправить на сушу этих мужчин и жен в целости и сохранности.

Если мы попытались бы решить эту задачу также как предыдущую — нас ждала бы неудача, т.к. даже на первом шаге есть 120 вариантов посадить в лодку 3 человека, а можно ведь заполнить лодку не полностью (т.е. в дереве, подобном тому, что приведено на рис. 6 из начальной вершины выходило бы более 100 дуг). И это только на первом шаге. Очевидно, поиск в ширину (по крайней мере, обычный) не сработает в этой ситуации. Задачу можно решить поиском в глубину.

Для начала, опишем пары и правила проверки списка на правильность (пары в списке не должны быть разрушены):

pair(ma, fa). % ma - муж, fa - женщина
pair(mb, fb).
pair(mc, fc).
pair(md, fd).
pair(me, fe).

check(L):- onlyfemale(L); check(L, L).

onlyfemale([]):-!.
onlyfemale([H|T]):-
  pair(_, H), !, onlyfemale(T).

check([], _):-!.
check([H|T], L):-
  pair(X, H), !, member(X, L), check(T, L).
check([_|T], L):-
  check(T, L).

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

proliferate((Left, Boat, Right, left), (Left_1, Boat_1, Right, right)):-
  length(Boat, LenBoat), LenLeftPart is 3 - LenBoat,
  permutation_length(Left, LenLeftPart, LeftPart),

 subtraction(Left, LeftPart, Left_1),
 append(Boat, LeftPart, Boat_1),

 check(Boat_1), check(Left_1).

proliferate((Left, Boat, Right, right), (Left, Boat_1, Right_1, left)):-
 length(Boat, LenBoat),
 permutation_length(Boat, LenBoat, BoatPart),

 subtraction(Boat, BoatPart, Boat_1),
 append(Right, BoatPart, Right_1),

 check(Boat_1), check(Right_1).

Правило proliferate, приведенное выше перегоняет лодку с одного берега на другой. При перегоне лодки с левого берега на правый, с берега в лодку набираются люди (строка 3). При перегоне с правого берега на левый, часть людей высаживаются с лодки (строка 12). В принципе, можно научить пролог набирать людей на обоих берегах, но тогда он будет искать решение слишком долго.

Как и в предыдущей задачи, обход графа лишь незначительно изменится (но на этот раз, обход в ширину):

dfs(([], [], L, Dir), _, [([], [], L, Dir)]):-!.
dfs(A, VN, [A|TR]):-
  proliferate(A, X),
  not(member(X, VN)),
  dfs(X, [A|VN], TR).

В первой строке описано условие, отражающее конечное состояние — берег и лодка пусты. В третьей строке вместо выбора дуги из вершины А в вершину X выполняется генерация этой дуги правилом proliferate.

рис. 8 решение логической задачи о супружеских парах

рис. 8 решение логической задачи о супружеских парах

Решение логических задач — обширная тема, по которой написаны толстые (и даже современные) книги [7,8], которые явно стоит посмотреть всем небезразличным. Безразличные тоже могут почитать для расширения кругозора.

Список использованных источников

  1. Агафонов В.Н. Логическое программирование — сборник статей. М.: Мир, 1988. — 368 с., ил.
  2. Хоггер К. Введение в логическое программирование: Пер. с англ. — М.: Мир, 1988. — 348 с.
  3. Доорс Дж., Рейблейн А.Р., Вадера С. Пролог язык программирования будущего. — М.: ФиС, 1990. — 144 С.
  4. Visual Prolog, http://www.visual-prolog.com/
  5. Кто убил пролог? / https://geektimes.ru/post/106224/
  6. Сергиевский Г.М., Волченков Н.Г. Функциональное и логическое программирование. М.: Академия, 2010
  7. Джордж Ф. Люгер, «Искусственный интеллект, Стратегии и методы решения сложных проблем», М.: Издательский дом «Вильямс», 2003
  8. John Stobo, Problem Solving With Prolog, Taylor & Francis, 2007.

13 thoughts on “Решение логических задач на Prolog

  1. Danny

    В задаче про ревнивых мужей лодка один раз ходит пустая. Разве такое допустимо по условию задачи? Если ставить в предикате перевозки проверку наличия людей в лодке, то не выходит перевезти.
    Видимо, надо будет всё таки добавить возможность забора людей с правого берега, или даже высадки их на левом берегу.
    Попробовал это сделать, теперь вечно false получаю.

    proliferate((Left, Boat, Right, left), (Left_2, Boat_2, Right, right)):-
      length(Boat, LenBoat), %количество людей в лодке
    
      sublist(Boat, [], BoatPart, LenBoat), %берем несколько людей
      subtraction(Boat, BoatPart, Boat_1), %высаживаем с лодки
      append(Left, BoatPart, Left_1), %пихаем на берег
    
      length(Boat_1, LenBoat_1),%новое количество людей в лодке
    
      LenLeftPart is 2 - LenBoat_1, %сколько можем посадить в лодку
      sublist(Left_1, [], LeftPart, LenLeftPart), %берем несколько людей
      subtraction(Left_1, LeftPart, Left_2),%убираем с берега
      append(Boat_1, LeftPart, Boat_2), %сажаем в лодку
    
      check(Boat_2), check(Left_2).
    
    1. admin Post author

      Отличное замечание. В задании не оговорены операции над лодкой, я решил упростить задачу чтобы не усложнять код, но переборщил.

      Я не сильно вникал, но исправил правило следующим образом:

      proliferate((Left, Boat, Right, left), (Left_1, Boat_1, Right, right)):-
        length(Boat, LenBoat), LenLeftPart is 3 - LenBoat,
        sublist(Left, [], LeftPart, LenLeftPart),
       
        subtraction(Left, LeftPart, Left_1),
        append(Boat, LeftPart, Boat_1), Boat_1 \= [], 
       
        check(Boat_1), check(Left_1).
       
      proliferate((Left, Boat, Right, right), (Left, Boat_1, Right_1, left)):-
        length(Boat, LenBoat),
        sublist(Boat, [], BoatPart, LenBoat),
       
        subtraction(Boat, BoatPart, Boat_1), 
        append(Right, BoatPart, Right_1), 
      
        length(Boat_1, LenBoat_1), LenRightPart is 3 - LenBoat_1,
        sublist(Right_1, [], Right_1Part, LenRightPart),
      
        subtraction(Right_1, Right_1Part, Right_2), 
        append(Boat_1, Right_1Part, Boat_2), Boat_2 \= [],
       
        check(Boat_2), check(Right_2).
      

      Тут добавлены проверка пустоты лодки во время отплытия и возможность посадки в лодку людей с правого берега. Высадку людей с лодки на левый берег я добавлять не стал, чтобы не усложнять код :). Решение сейчас выглядит примерно так:

      ?- dfs(([ma,mb,mc,md,me,fa,fb,fc,fd,fe],[],[],left),[],Path), 
         printpath(Path), !, fail.
      [ma,mb,mc,md,me,fa,fb,fc,fd,fe],[],[],left
      [mb,mc,md,me,fb,fc,fd,fe],[ma,fa],[],right
      [mb,mc,md,me,fb,fc,fd,fe],[fa],[ma],left
      [mb,mc,md,me,fc,fd,fe],[fa,fb],[ma],right
      [mb,mc,md,me,fc,fd,fe],[fb],[ma,fa],left
      [mc,md,me,fc,fd,fe],[fb,mb],[ma,fa],right
      [mc,md,me,fc,fd,fe],[mb],[ma,fa,fb],left
      [md,me,fd,fe],[mb,mc,fc],[ma,fa,fb],right
      [md,me,fd,fe],[mc,fc],[ma,fa,fb,mb],left
      [md,me,fd,fe],[mc,fc],[ma,fa,fb,mb],right
      [md,me,fd,fe],[fc],[ma,fa,fb,mb,mc],left
      [md,me,fe],[fc,fd],[ma,fa,fb,mb,mc],right
      [md,me,fe],[fd],[ma,fa,fb,mb,mc,fc],left
      [me,fe],[fd,md],[ma,fa,fb,mb,mc,fc],right
      [me,fe],[md],[ma,fa,fb,mb,mc,fc,fd],left
      [fe],[md,me],[ma,fa,fb,mb,mc,fc,fd],right
      [fe],[me],[ma,fa,fb,mb,mc,fc,fd,md],left
      [],[me,fe],[ma,fa,fb,mb,mc,fc,fd,md],right
      [],[fe],[ma,fa,fb,mb,mc,fc,fd,md,me],left
      [],[fe],[ma,fa,fb,mb,mc,fc,fd,md,me],right
      [],[],[ma,fa,fb,mb,mc,fc,fd,md,me,fe],left
      
      1. Danny

        Всё отлично работает, спасибо за ответ.
        Теперь стало интересно, как можно избежать бессмысленной переправы fe туда обратно перед конечным состоянием.

        1. admin Post author

          Чтобы бессмысленную переправу fe устранить, надо высадить его сразу с me. Высаживается он отдельно, потому что правило sublist написано так, как написано. Можно переписать sublist так, чтобы первым делом оно возвращало исходный список (ведь он является собственным подсписком), однако в этом случае постоянно одни и те же люди будут кататься туда-обратно на лодке.
          Поэтому sublist лучше не трогать, мне кажется что без этого можно обойтись.

          (Left = [], BoatPart = Boat; sublist(Boat, [], BoatPart, LenBoat)),
          % вместо sublist(Boat, [], BoatPart, LenBoat)
          

          Я не проверял этот код, но не вижу причин, по которым он может не работать.

          1. Аня

            Здравствуйте, спасибо большое за ответ, но мне кажется, или если убрать отсечение оно будет выдавать бесконечное число одинаковых решений? Я согласна, что выдавать все решения это не очень хорошая затея, но это упражнение, чтобы продемонстрировать работу поиска по графу, что решения ветвятся, пока не получается это понять.
            И еще мне даже стало интересно, не могли бы вы подробнее рассказать также и про поезда, пожалуйста, как можно реализовать поиск и генерацию состояний.

            1. admin Post author

              Здравствуйте.

              Я не совсем уверен, что количество решений будет бесконечным, но абсолютно уверен, что не все решения будут одинаковыми.

              Чтобы продемонстрировать (читаю как «наглядно показать») работу поиска по графу не нужно выводить все решения. Поиск одного решения — это тоже поиск в графе. Чтобы показать процесс поиска решения можно вставить куда-нибудь отладочную печать.

              Я уже привел фрагмент кода генерации состояний к задаче о поездах и рассказал как его можно дописать. Что конкретно не получается?

        2. ПРОЛОЖЕ

          Всё, чего Вы добились таким изменением кода — избавились от проверок лодки у правого берега и самого берега. Т.е. просто были убраны ограничения, что превращает задачу в тривиальную. Нет никаких сомнений, что она должна выполняться при таком коде. Значения Boat_2, Right_2 — пустышки (на результат никак не влияют). Простите за отсутствие конструктива, сам нахожусь в поиске корректного решения.
          С уважением.

          1. admin Post author

            Отличное замечание. Я ошибся, но вот исправился:

            proliferate((Left, Boat, Right, left), (Left_1, Boat_1, Right, right)):-
              length(Boat, LenBoat), LenLeftPart is 3 - LenBoat,
              sublist(Left, [], LeftPart, LenLeftPart),
             
              subtraction(Left, LeftPart, Left_1),
              append(Boat, LeftPart, Boat_1),
             
              check(Boat_1), check(Left_1).
            proliferate(([], Boat, Right1, right), ([], [], Right2, left)):-
            	!, append(Boat, Right1, Right2).
            proliferate((Left, Boat, Right, right), (Left, Boat_1, Right_1, left)):-
              length(Boat, LenBoat),
              sublist(Boat, [], BoatPart, LenBoat),
             
              subtraction(Boat, BoatPart, Boat_1),
              append(Right, BoatPart, Right_1),
             
              check(Boat_1), check(Right_1).
            

            Добавлена проверка того, что если на левом берегу уже пусто — то из лодки всегда стоит высадить всех людей.
            Хотя нет смысла в такой проверке, я думаю. Как использовался поиск в глубину, так и используется. Оптимальность решения не гарантируется.
            Если нужно избежать всех бессмысленных переправ — надо писать поиск в ширину. Но вопрос стоял так:

            избежать бессмысленной переправы fe туда обратно перед конечным состоянием.

            Для такой формулировки решение подходит как нельзя лучше.

        1. admin Post author

          Спасибо за замечание. Тут использовалась нестандартная реализация предиката permutation, генерирующая перестановки, длина которых не превышает заданного значения, однако в SWI Prolog встроена функция, генерирующая перестановки заданной длины. В связи с этим я заменил свою реализацию и эта задача перестала работать. Решить проблему можно заменой вызова permutation на permutation_length. Я поправил статью, проверил корректность работы решения.

Добавить комментарий