Беря во руки свои ноги
Мечтая протоптать дороги
Заветной цели на пороге
Сквозь лабиринты prolog-аем путь
По привычке подключения библиотек в начале кода сообщаю: будем использовать фантазию. Фантазия позволяет представить самые разнообразные структуры, представить как они меняются и что из этого получается.
Разнообразие всех возможностей воображения сложно как-то системно разделить, но один вариант разделения я, пожалуй, распишу. По возрастанию сложности можно расставить так: лабиринты, пути их прохождения, принципы поиска путей прохождения, принципы построения лабиринтов — для которых в свою очередь можно будет искать пути прохождения.
Лабиринты
Почему за основу я взял именно лабиринты? Потому что блуждание по лабиринту — это выраженное стремление пройти к цели через множество возможностей, путём выбора действия и повтора всего этого после того как пришёл результат действий, снова и снова. То есть, это кратко описывает решение любой задачи. А если затем ты переходишь пониманием с уровня прохождения на уровень построения лабиринтов, то задача состоит уже в том чтобы правильно понимать, что вообще происходит.
Ну, например, как правильно понимать, построение лабиринтов — это прохождение лабиринтов другого уровня или уже принципиально иное действие, в каком-то смысле противоположность? Вот, кто бы знал. До двух вариантов выбора описание тут может и не сойтись.
Первое и самое простое что в воображении можно осуществить — это что-то создать. Ну, или не создавать — на выбор.
Сначала надо представить образ как потенциал, а потом, раз уж мы решили вещь в своём воображении создать, то хлоп — и образ осуществлён. И теперь если кто-то спросит, а не существует ли вот это и покажет тот же образ, то ответ будет — да. И это всё что поменялось. Был образ, стал факт существования.
Ну а для такого образа, для которого не прошло создание, ответ будет тем который принят по умолчанию. С учётом того что наше воображение полностью наше, ответ «не знаю» не годится. Точный ответ: «Все осуществлённые образы помню, этого среди них нет».
С тем почему у существования только два варианта мы разобрались. Меньше просто некуда. Самое интересное тут — это то что после создания можно о чём-то спрашивать. Вопросы — важная часть воображения.
И вот, оказывается, любой вопрос можно свернуть к вопросу с двумя вариантами ответа. Точнее, если вопрос можно свернуть до вопроса о существовании — то есть, до «существует ли хороший путь прохождения вот так вот устроенного лабиринта?» и после положительного ответа будет возможность выслушать как именно лабиринт прошли за тебя — то вопрос был отлично свёрнут. Остаётся только разобраться, что здесь значит «хороший путь», кто и как это определяет. Бывает, что «существующий» — уже «хороший».
Когда кто-то проходит лабиринт за тебя, то время летит незаметно. Если не происходит зависания, то приходит ответ. А теперь стоит разобраться, как любые вопросы превращать в лабиринты.
В прологе используется два этапа: сначала описывается то что существует, а затем задаётся вопрос, на который в связи с этим надо ответить. Такой запрос это запуск программы, но от простого нажатия кнопки отличается тем что надо достроить описание результата, иначе описание желаемого не полно.
Сейчас будет показан самый минимальный лабиринт. Он состоит из одной стены между началом лабиринта и его концом и представляет собой образ проёма, сквозь который можно пройти.
проход.
Вот и всё. На языке пролога это утверждение о том что проход существует. Название факта со строчной буквы и за ним точка. Весь лабиринт.
?- проход
true
На втором этапе вопрос поставлен о существовании прохода. И пролог отвечает true, существование подтверждено.
Минимальный лабиринт пройден. Воображение рисует, что в конце пути нас ждал открытый сундук с монетами. Пора заказывать шампанское и на вечер салют.
Надеюсь, такой минимализм воспринимается приемлемой шуточкой.
Если бы это было всё что в прологе есть — то было бы скучновато. Это был бы список фактов, и на вопрос об интересующем факте нужно было бы просто пробежаться по списку и ничего больше.
Обегать список, между прочим, достаточно долго. Обычно поиск по списку оптимизируют. Например, сортировка по алфавиту позволяет составлять индексы, по которым слово будет находиться быстрее. Или можно из длинных слов составлять короткий хэш и искать соответствие по нему. Но это уже оптимизация, которая во время разработки может быть преждевременной. В прологе такого изначально нет. Наверняка, сделать потом возможно.
В простейшем виде поиск по списку можно представить как прохождение по лабиринту в виде коридора без ответвлений. Составление списка фактов — это построение такого лабиринта. Поиск по списку — прохождение. Как же хорош лабиринт, когда линейный: всегда ясно с чего начинать и всегда ясно какой следующий шаг, если на данном этапе совпадения с желаемым не произошло. А если произошло, то тем более ясно: лабиринт пройден.
Как бы не усложнялся пролог, он останется языком описания ситуации, где всегда ясно каков следующий шаг.
И тут можно вспомнить о том, чего в настоящих лабиринтах полным полно — о развилке. На развилке не всегда ясно куда идти.
Так и представляю: стоит поисковик посреди помещения, в котором два варианта дальнейшего прохода и вся задача состоит в выборе, по какому пути идти. Но на этот случай существует хороший алгоритм действий: нужно сначала обшарить весь лабиринт по одному направлению, а затем вернуться и обшарить всё по другому направлению. То есть, сами варианты направлений как будто создадут ещё один список. Список списков, всего делов.
И если бы в лабиринтах не было «сходящихся» развилок, то это было бы действительно хорошим решением.
Только вот, развилки не сообщают о том что они сходящиеся — и что часть вариантов прохождения будет ставить поисковика на путь возвращения обратно без результата, при этом ничем не выдавая, что возвращение началось. Не сообщая даже того какой по счёту круг здесь наматывается.
Вариантов решения можно подобрать как минимум два: либо составлять карту пройденных мест, на каждом шаге отслеживая возможное возвращение, либо требовать существования только таких лабиринтов, где возвратные шаги себя обозначают. Здесь вопрос в том кто, путешественник или лабиринт должен быть больше готов к прохождению. Пусть сейчас будет больше готов лабиринт, путешественник наберётся мастерства чуть позже.
Так что будем описывать проход так:
проход_вперёд(начало, первая_развилка).
проход_назад(первая_развилка, начало).
И тогда на вопрос о существовании прямого прохода для мест, указанных в обратном порядке:
?- проход_вперёд(первая_развилка, начало)
false
Ответ будет отрицательный.
Здесь мы использовали в качестве факта структуру.
Она выглядит как выписанный за названием структуры список её элементов — факты в скобках. Но, конечно, в скобках могут быть вписаны опять структуры. Главное в таком описании что общая структура создана и может подтвердить своё существование. Тут стоит отметить, что существование для структуры подтверждается только по результату проверки того что между заданным утверждением и вопросом совпадают все составляющие, и для такого подтверждения элементы структуры сами не обязаны существовать.
Выглядит просто: спросил, существует ли определённая структура, и в ответ после полного сравнения составных элементов получен желанный бит информации. Но вопросы о структурах могут быть составлены чуть шире. В них добавлена возможность после определения имени составляющие не определять. Указывать, что составляющая неизвестна.
Для описания неизвестных величин на этапе вопроса используются слова, которые начинаются с прописной буквы. Например, Место.
?- проход_вперёд(начало, Место)
Место = первая_развилка
Ответ будет подтверждением существования, но выражаться он будет в описании того чему должны быть равны неизвестные величины. Причём, так как неизвестная величина не обязана предоставлять только один вариант своего значения, то ответ может быть началом целого списка ответов.
И если построить лабиринт так:
проход_вперёд(развилка, помещение_справа).
проход_вперёд(развилка, помещение_слева).
То на вопрос
?- проход_вперёд(развилка, Место)
Ответ будет
Место = помещение_справа
Появится возможность продолжить и получить следующий ответ. «Дальше»:
Место = помещение_слева
Наш пролог-поисковик воспользовался тем что у него есть список существующих структур — и сам прошёлся по нему последовательно, отобрав те записи, у которых на месте известных элементов структуры они совпадают, то что оказывалось на месте неизвестных элементов он поместил в ответ.
Приём таких ответов можно организовать сразу в виде списка. Но можно и несколько иначе: тот кто получает ответ может сначала его использовать, а потом вернуться и запросить следующий вариант.
Кроме вопросов о существовании структур в вопросах к прологу можно использовать запятую — как описание того что для конечного ответа должна выполняться часть как до запятой так и после. То есть, союз «и».
Если мы опишем так:
проход_вперёд(развилка, помещение_справа).
проход_вперёд(развилка, помещение_слева).
проход_вперёд(помещение_справа, комната_с_сокровищем).
проход_вперёд(помещение_слева, комната_с_сокровищем).
проход_вперёд(помещение_справа, комната_с_сокровищем).
Вопрос о том как пройти к сокровищу будет таким:
?- проход_вперёд(развилка, X), проход_вперёд(X, комната_с_сокровищем)
И ответ будет в том что можно пройти как через правое, так и через левое помещение.
X = помещение_справа
X = помещение_справа
X = помещение_слева
Нечаянное дублирование прохода не вызвало ошибок, он просто упомянут в ответе два раза. Процесс стоит рассмотреть подробнее. После того как для первой части вопроса был получен ответ, поиск был продолжен для второй части вопроса, но при этом X обозначал уже не неизвестную величину, он был связан с конкретным значением, с правой комнатой. После того как были пройдены все варианты прохода через правую комнату, поиск немного отступил, и стал продолжать перебирать варианты для первой части. И дальше были получены варианты с проходом через левую комнату.
Интересно здесь то, что поисковик сохраняет в своей памяти то где он искал раньше, и эта память помогает ему отступать из тупиков, и затем просто перейти на следующий вариант, не особо-то переживая за то чтобы не сбиться с порядка. При такой организации всё последовательно, зависания невозможны, даже не смотря на присутствие неизвестных величин.
Ну а дальше будет представлено кое-что посерьёзней, чем обход списков, в которые превращены древообразные разветвления, и отсутствие зависания уже не гарантировано.
Идея в следующем: а что если указания на этапе описания будут не просто элементами списка для подтверждения? Что если кроме подтверждаемого варианта тут же будет описан дополнительный вопрос, который и определяет результат подтверждения?
Получается, очередной шаг при разрешении вопросов будет состоять в том чтобы задать новый вопрос — обычное дело при поиске ответов. Самое главное чтобы новые вопросы приближали к ответу, хотя бы на один шаг.
Подытоживая, на первом этапе программа на прологе состоит из перечисления отношений (clauses), каждое из которых может быть быть либо фактом, либо правилом.
Правило описывается через указание его головы и тела, соединяемых знаком шеи «:-». Тело пишется в формате вопроса. Но при этом неизвестные величины могут указываться как в теле так и в голове. Голова указывает на то что данное отношение подтверждает, но составляющие могут быть неизвестны, и всё что здесь требуется — чтобы могло произойти успешное связывание с вопросом, который задан к самому этому правилу.
Иногда пролог рассматривая вашу программу делает замечания. Например, если неизвестная величина в правиле использована только один раз, он сообщает, что будет лучше если имя будет прямо на это указывать. Для этого используется знак «_» - каждое использование его в качестве имени это отдельная неизвестная величина, которая ни с чем другим не связывается.
можно_в_пути_перекусить(_).
?- можно_в_пути_перекусить(когда_ещё_ничего_не_нашёл)
true
С точки зрения поиска здесь лучше сказать наоборот, связывание любой величины с этим знаком всегда удачное, потому что она ни на что не влияет, не имеет возможности получить потом дополнительных ограничений.
Ещё пролог говорит что факты и правила с одним названием должны идти подряд в одном месте, не перемежаясь с другими названиями. Это вполне естественно, ведь искать правила при чтении когда они идут одной группой легче, да и каким-нибудь намеренным чередованием разноимённых правил никакого преимущества в поиске не создать. Факты и правила с одинаковым названием можно понимать как один предикат.
Из чего состоит каждый вопрос, исходя их того что было уже рассказано? Из перечисления фактов или структур, с возможно неизвестными составляющими, связанными через запятые как указанием обязательности нескольких условий. И теперь можно дополнить, что такие группы в свою очередь могут связываться через знак «;», который обозначает, что для положительного ответа может подойти как группа до знака так и группа после знака. Связка «или».
Практически, правило со знаком «;» в теле может быть заменено двумя раздельными правилами с одинаковой головой и теми частями в теле, которые были справа и слева от знака, идущими в том же порядке. Или, наоборот, правила с одинаковой головой могут быть объединены в одно тело и «;» как разделителем. («Практически всегда» — значит не всегда. Существует оператор условного выполнения «->», который меняет работу оператора «;» изнутри его первого аргумента, в некоторых случаях отменяя обработку второго аргумента.)
Ещё можно для группировки условий использовать скобки.
Для полноты описания стоит сказать, что однострочный комментарий в прологе идёт после знака процента.
Использование правил очень сильно расширяют возможности пролога, и, пожалуй, пора это демонстрировать. Начну с простых, скромных примеров.
Представьте лабиринт из таких проходов, для которых уже известно в каком направлении шаг по нему прямой, а в каком обратный. С помощью дополнительных правил можно узнать ответ на вопрос, существует ли путь от одного места к другому, такой, который состоит только из шагов прохождения вперёд. Проще говоря, по двум пунктам найти путь.
При составлении правил такого определения для начала мы можем сказать, что прямой путь точно существует, если состоит из одного шага вперёд.
прямой_путь(От, До) :- проход_вперёд(От, До).
А затем это описание надо дополнить. Шаг, который мы уже поставили как условие существования пути должен быть первым шагом, при этом весь остальной путь должен быть тоже прямым путём.
прямой_путь(От, До) :-
проход_вперёд(От, Через_шаг),
прямой_путь(Через_шаг, До).
Правило задаёт два условия и использует себя же в качестве одного из них, и это работает.
Или, правило можно написать немного по-другому. Отдельный шаг может быть последним шагом пути, и тогда прямой путь должен существовать до того места откуда этот шаг сделан.
прямой_путь(От, До) :-
проход_вперёд(Остался_шаг, До),
прямой_путь(От, Остался_шаг).
В обоих случаях процесс подтверждения существования пути состоит из поиска одного шага, а затем тот путь который остался, подтверждается рекурсивно.
Интересно различие этих подходов. В первом новые вопросы о существовании пути задаются в порядке удаления от начала. Во втором вопросы задаются по порядку от пункта назначения в обратную сторону. При этом — оно работает, и выводит результат. По сути, для существования прохода не важно с какой стороны его последовательно выявлять, различие будет только в порядке перебора подходящих вариантов.
Второй подход достаточно необычен: формулируя правило можно представлять, что путь уже пройден, осталось только установить как это было. Выявлять путь можно в обратной к прохождению последовательности, пользуясь таким правилом, в котором описан самый важный последний шаг. И в момент выявления что это был за шаг последним важным шагом становится последний шаг предыдущего пути, конечно, если этот путь ещё остался. Декларативный подход фокусируется на описании цели как желаемого завершённого состояния, остальное делает контролируемый перебор.
Можно заметить одну особенность: при развороте границы прямого пути поменялись, а очерёдность того что сначала ищется одиночный шаг, а затем подбирается дополняющий его путь — осталась. И это действительно важно, потому что при составлении условий в другом порядке поиск вполне обосновано зависает. Беда.
Чтобы проверить существование пути поиск должен перебрать все возможные варианты для вложенного пути, а когда вариант, при котором вложенный путь совпадает с самим путём не отсеивается, поиск просто попробует найти этот же путь точно тем же способом. И получается непрерывное хождение по кругу.
А порядок, в котором сначала происходит поиск прямого шага, а только затем поиск уменьшенного пути — отсеивает вариант при котором вложенный путь такой же по длине как он сам. Здесь то что один прямой шаг обязан увеличивать путь использовано как полезное свойство уменьшения пути при отделении этого шага. И такой поиск после перебора всех вариантов успешно завершается, не зависнув.
В записи лабиринта через шаги вперёд сразу заложена схема что он разбивается на расходящиеся пути вперёд и получается древообразная структура. А если вспомнить про остальные проходы, то надо отметить, они хотя и были бы возвращением туда где уже, возможно, был, но только — нежелательным, и сами по себе для возвращения использоваться не могут. Так что, лучше их называть просто проходами, без указания направления.
Вот как выглядит поиск на данном этапе:
% Пара развилок, после которых будут две различных комнаты с сокровищами.
проход_вперёд(начало, первая_развилка).
проход_вперёд(первая_развилка, комната_слева).
проход_вперёд(первая_развилка, вторая_развилка).
проход_вперёд(вторая_развилка, комната_справа).
проход_вперёд(вторая_развилка, тупик).
проход_назад(Y, X) :-
проход_вперёд(X, Y).
% проходы между прямыми ветками пока не используются,
% но пусть лабиринт будет описан полностью
проход(вторая_развилка, комната_слева).
% по итогу у второй развилки проходы будто по четырём сторонам
% указания где сокровища могут быть найдены
есть_сокровище(комната_слева).
есть_сокровище(комната_справа).
есть_сокровище(комната_отдельная).
% правила определяют что значит путь
прямой_путь(От, До) :- проход_вперёд(От, До).
прямой_путь(От, До) :-
проход_вперёд(Остался_шаг, До),
прямой_путь(От, Остался_шаг).
% Кстати, если начинать сразу из комнаты с сокровищами, то и бродить не придётся
прямой_путь(Тут, Тут) :- true.
% факт записан в виде правила
?- есть_сокровище(X), прямой_путь(начало, X)
По такому запросы мы узнаем только то что смогли бы найти сокровища в паре комнат, но нам ничего не сообщают про путь, который для этого надо пройти. А именно это и было бы полезным.
В подтверждённом пути должна содержаться информация о всех промежуточных пунктах, так что нужны массивы. В прологе как массивы используются списки.
Список выглядит как линейный лабиринт, по которому можно пройтись и посмотреть что находится в каждой его комнате. Но в программе его можно представлять как один элемент, который либо пуст, либо предоставляет возможность на выбор: посмотреть его содержание или пройти дальше. А если описание упростить, то список это либо пустой список [], либо пара [голова|хвост], в котором хвост это опять список (но иногда и нет).
Хотя, конечно, проще вместо [A|[B|[C|[]]]] писать [A, B, C].
Самое интересное, что в правилах можно писать списки с неизвестными величинами как в теле так и в голове. И связывание переменных, или, уже можно говорить об общем случае, унификация предикатов, всё равно с этим работает.
Следующие примеры будут с использованием чисел. Так что, наверное, пора упомянуть, что величины могут быть и числами. Подтверждать существование чисел не требуется, а вот унифицировать с неизвестными величинами можно. Унификация в теле правила задаётся через функтор «is». Запрос «X is 3» подтверждается только если X и 3 унифицированы. Так как другие варианты унификации перебирать не приходится, то это работает как присваивание.
Можно написать в вопросе X is 1 + 2 и получить X = 3. В функторе is только второй аргумент является рассчитываемым выражением с точно определённым не перебираемым результатом, это совсем не похоже на симметричное «равно», обратный порядок «3 is X» не срабатывает.
Знак равно, конечно, проще. Это симметричная команда унификации. Но если написать X = 1 + 2 в запросе, то никакого расчёта структуры справа не будет, ответ так и будет X = 1 + 2.
одинаковые(X, X) :- true.
?- одинаковые(1 + 2, +(1, 2))
true
?- одинаковые(1 + 2, 3)
false
И теперь для освоения списков следует выполнить такое задание: написать правило, которое выдаёт как решение только такие списки, в которых элементы выражают прямой счёт. То есть, натуральные числа, идущие подряд, начиная с единицы. Различие между такими списками будет в том на каком числе этот счёт остановился.
У меня получилось составить вот такое правило:
пробный_список([X, Y | Z]) :-
пробный_список([Y | Z]),
X is Y + 1.
Которое означает, что когда уже есть список из таких чисел, то можно составить новый, добавив в начало элемент на единицу больше.
Перебор таких списков можно запустить, добавив в начало факт
пробный_список([1]).
?- пробный_список(X)
X = [1]
X = [2, 1]
X = [3, 2, 1]
И так далее.
Проблема в том, что пользуясь синтаксисом, в котором от списка есть только голова и хвост легко добраться только до первого элемента. А как добраться до последнего элемента, как добавить новый в конец?
Конечно, задача решается сразу, если уметь разворачивать список. Существует команда reverse
?- reverse([1, 2, 3], X)
X = [3, 2, 1]
Для работы со списками есть и встроенное определение длины списка и обращение к элементу по индексу, это практически массивы.
Но интересное испытание для программиста получается, если считать заданием развернуть список без использования этой команды, пользуясь только синтаксисом головы/хвоста списка. Это вполне осуществимо.
И разворот и добавление в конец списка это задачи одного уровня. Получилось ли у вас придумать самостоятельно?
Начать описание того что получилось у меня можно с рассмотрения правила, которое перекладывает элемент с одного списка в другой.
переложить([H|T], A) :- переложить(T, [H|A]).
Здесь во время поиска решения из первого списка элементы перекладываются во второй, поиск продолжается, и когда первый список опустошается, второй существует в обратном порядке.
Ну а как это заставить работать? Ведь в это правило нужно как-то вставить изначальный список и как-то забрать ответ.
Представьте что будет если добавить завершающий обработку факт
переложить([], _).
И запустить
?- переложить([1, 2, 3], X)
true
Надо представить подробно, каждый шаг.
(Здесь было подробное описание того как поисковик исполняет одно и то же правило по перекладыванию одного элемента с верхушки одного массива на верхушку другого, пока массив не опустеет, а потом натыкается на правило с пустым массивом, и только после этого возвращается по стеку с подтверждением к самому первому выполненному правилу. Но описание было нудным и я его убрал.)
Мы узнаем, что каким бы ни был X, к нему спереди добавится развёрнутый список и программа удовлетворённо сообщит, что всё что надо было сделать — сделано. И всё.
Это как если бы мы послали в лабиринт за сокровищем кого-то другого, а он возвращается и говорит: — Нашёл!
Только вот, принести забыл.
Что ж, исправим это. Чтобы посланник что-нибудь нам принёс, надо ему иметь карман. Такой, чтобы пока он там ходит всё что в нём лежит сохранялось.
Что будет с третьим аргументом, если его оформить так?
развернуть([H|T], A, Z) :- развернуть(T, [H|A], Z).
Всё что лежит в этом «кармане» сохраняется. Самое примечательное — что сохраняется и тогда когда поисковик идёт вперёд и когда уже возвращается.
Если добавить перед правилом факт
развернуть([], Z, Z).
То в момент когда первый список опустеет, факт будет в том что обращённый список и содержимое кармана имеют одинаковое значение. А карман унифицирован с неизвестной величиной из запроса. И по итогу развернуть заданный список получилось.
?- развернуть([1, 2, 3], [], X)
X = [3, 2, 1]
Вот решение целиком:
обратный_список([1]).
обратный_список([X, Y | Z]) :-
обратный_список([Y | Z]),
X is Y + 1.
развернуть([], Z, Z).
развернуть([H|T], A, Z) :-
развернуть(T, [H|A], Z).
список(Y) :-
обратный_список(X),
развернуть(X, [], Y).
?- список(X)
X = [1]
X = [1, 2]
X = [1, 2, 3]
X = [1, 2, 3, 4]
...
Теперь можно вернуться по стеку заданий и вспомнить, что списки нам были нужны для того чтобы вывести путь, который надо пройти в лабиринте.
% Когда-нибудь мы сможем не спрашивать у лабиринта, точно ли это шаг вперёд
проход_вперёд(начало, первая_развилка).
проход_вперёд(первая_развилка, комната_слева).
проход_вперёд(первая_развилка, вторая_развилка).
проход_вперёд(вторая_развилка, комната_справа).
проход_вперёд(вторая_развилка, тупик).
% тут пропущены неиспользуемые обратные пути
% а проход, сменяющий ветку, оставлен на память
проход(вторая_развилка, комната_слева).
% среди комнат с сокровищем есть
% отдельная комната - в которую не попасть
% это чтобы показать что пути до сокровища может ещё и не быть
есть_сокровище(комната_слева).
есть_сокровище(комната_справа).
есть_сокровище(комната_отдельная).
% путь
составить_путь(От, До, Путь) :-
проход_вперёд(От, До),
Путь = [До].
составить_путь(От, До, Путь) :-
проход_вперёд(Остался_шаг, До),
составить_путь(От, Остался_шаг, Часть_пути),
Путь = [До|Часть_пути].
развернуть([], Z, Z).
развернуть([H|T], A, Z) :-
развернуть(T, [H|A], Z).
путь_к_сокровищу(Путь) :-
есть_сокровище(X),
составить_путь(начало, X, Путь_оттуда),
развернуть(Путь_оттуда, [], Путь).
?- путь_к_сокровищу(Путь)
Путь = [первая_развилка, комната_слева]
Путь = [первая_развилка, вторая_развилка, комната_справа]
Получилось. Путь к каждому из сокровищ найден.
В правиле для вычисления пути приравнивание пути можно написать вместо тела правила сразу в головной части
составить_путь(От, До, [До]) :-
проход_вперёд(От, До).
Унификация в этом случае проходит точно так же.
Итак, у нас составляются пути. Теперь стоит организовать так чтобы во время поиска уже не спрашивать у лабиринта, вперёд ли это шаг.
Перед тем как попробовать это написать, ещё один полезный челендж, надо составить такую пару отношений (clauses) с помощью которых выяснить, есть ли в списке заданный элемент.
Первое правило указывает, что если список начинается на этот элемент, то он точно там есть.
в_списке(Элемент, [Элемент|_]).
А второе правило говорит что в начало списка можно добавить любой элемент, и, по логике, если выискиваемый элемент там был, то он там и остался.
в_списке(Элемент, [_|Список]) :-
в_списке(Элемент, Список).
И этого достаточно.
Обязательно стоит заметить, что такое определение присутствия в списке возвращает подтверждение не один раз, а столько сколько элемент в нём встретился. Если правило отработало, то при дальнейшем исполнении ситуация откатится до обхода всех правил с тем же именем и будет проверено следующее правило.
Чтобы результат в виде простого подтверждения возвращался только один раз можно использовать отсечение.
Если правило переписать в форме
в_списке(Элемент, [Элемент|_]) :- !.
Тогда первый же встретившийся совпадающий элемент вместе с подтверждением встречи прекратит дальнейший поиск. Зачем искать следующий если для подтверждения факта нахождения достаточно первого?
Отсечение «!» очищает вершину стека для всего прохода данного предиката. То есть, при встрече в конце правила подтверждает не только голову правила, а сразу весь предикат, и больше предикат в той же точке отката не проверяется. Знак «!» может стоять и не в самом конце правила. После него через запятую могут стоять ещё условия, но провал этих условий не заставит проверять условия идущие до отсечения ещё раз, результат переходит сразу на весь предикат.
Если до этого различный порядок правил в предикате влиял только на очерёдность обхода, то при использовании отсечения те правила которые идут раньше отсекают перебор с использованием последующих, и значит, при перестановке наверняка изменяется и состав перебираемых вариантов.
Кроме того, если правила, идущие после отсечения, учитывают его присутствие, то при его отмене результат тоже может измениться.
Отсечение - мощный оператор. Из подобных особых операторов можно привести оператор «\+», который подтверждается только если его аргумент не подтверждается, иначе не подтверждается он сам. Используется как not, понимать стоит как «ни один из вариантов не подтверждён» относительно внутреннего выражения. Аналог оператора может быть организован через отсечение.
Здесь можно дополнительно рассказать как работает оператор условия, аналог оператора if в других языках. Выражение A -> B; C; D означает что если верно A, то запрос подтверждения переходит на B, а иначе на (C; D). Причём, скобки (A -> B); (C; D) не меняют работу оператора, он остаётся первым аргументом у ; («или») и изнутри первого аргумента влияет на его работу. Альтернативные ветки заключены внутри второго аргумента, причём, D даже в варианте без скобок это часть альтернативной ветки. Поэтому для того чтобы их отделить от внешних альтернатив оператор условия стоит заключать в скобки целиком.
Продолжим поход.
Я в своём воображении представляю лабиринт смотря на него сверху, светлые прожилки проходов на тёмном фоне. Если в лабиринте пути разветвляются, а потом смыкаются и ведут к цели, то при указании лабиринта как древообразной структуры прямых шагов (в воображении эти шаги подсвечиваются) вместе с неиспользуемыми проходами для шагов смены ветки (в воображении эти пути чуть тусклее) из смыкающихся веток прямой путь будет проводить только одна.
Где-то раньше нам пришлось выбирать кто отвечает за отсутствие нежелательных возвратов. Мы собирались определение направление прохода повесить на поисковика. Для полного отделения прямых проходов от тех которые можно назвать побочными придётся обойти весь лабиринт, без этого никак.
Но как поисковику выбирать прямой путь, ведь результат любого выбора при отсутствии повторного прохождения мест по итогу всё равно гарантирует успех? Не начнёт ли он перебирать варианты и для этого выбора? Конечно, начнёт. И с этим надо разобраться.
Для того чтобы найти сокровище достаточно чтобы поисковик помнил комнаты пройденные от начала — чтобы не зацикливаться. С обычным выполнением отмены хранения пути при отступлении. И тогда, например, каждый путь из трёх сошедшихся вместе коридоров будет как будто отдельной частью лабиринта, схема обхода при этом останется древообразной, пусть и с повторяющимися ветками. Каждый сундук может быть найден огромное количество раз, зато каждый раз по другому, самонепересекающемуся пути.
Чтобы сокровище не встречалось несколько раз нужно держать в памяти все места где поисковик уже побывал, даже при отступлении. Но если все посещённые места просто складывать в карман, то, по логике, под конец прохода там будут все комнаты, а значит, и посреди прохода тоже. Может придти осознание вполне простого ограничения: одновременно складывать в карман и проверять что туда сложили не получится. Что же делать?
Для выбора самого короткого пути требуются оптимально расставленные возвраты. Я так понимаю, для этого следует прошаривать лабиринт по всем отходящим путям одновременно, определяя список посещённых комнат соответственно количеству шагов отхода от начала.
Если будут встречаться переходы, замыкающие путь в кольцо — они будут классифицированы как побочные переходы.
Вариант для переобозначения лабиринта тогда будет единственным, за исключением особенности, что если сходящиеся в комнату коридоры будут пройдены за одинаковое количество шагов, то один из последних проходов, всё же, должен быть прямым — и тут конфигурация не подскажет, какой именно. Остальные проходы к этому месту будут простыми (побочными).
Программу я уж не стану показывать, зачем портить удовольствие самостоятельной разработки.
Если оптимальность не сильно интересует, то лабиринт можно прошаривать так, чтобы перебрать все варианты прохождения один за другим. Для этого нужно хранить уже распределённую область, а расширять её в таком порядке, который зависит от варианта перебора, и когда разведанная область накроет весь лабиринт, фиксировать очередной результат.
На каждом шаге нерешительного обхода можно идти не только вперёд, но и отступить, точнее, произвольно сменить место по границе разведанной области. Самые оптимальные обходы можно попробовать расставить в таком переборе первыми, разница в шагах между местами на концах каждого побочного перехода в этом случае не больше единицы.
Что касается остальных вариантов, то вот что можно заметить: любой линейный коридор может иметь в середине замыкающий проход, но его место в разных вариантах перебора может различаться. Поисковик остановился где-то в середине, а закончил прохождение потом, зайдя в коридор с другой стороны. В общем, действительно, не торопился.
Если воображение хорошее, то можно представить все варианты, всё их разнообразие. И в целом, тоже не спешить.
Могут существовать задачи, для которых введение дополнительных условий приводит к тому, что решения, оптимальные в исходной постановке, становятся неоптимальными.
Прологи
То что мы на данном этапе в воображении имеем можно описать как бескрайнее пространство, которое заполнено точками, каждая из которых, для наглядности, либо светится, либо нет. Каждый образ, стоящий за точкой, либо осуществлён, либо нет.
Конкретное состояние точек зависит от дополнительных условностей — кроме одной пары точек. Одна из них точно светлая, а другая точно тёмная — их имена именно это и задают, true (ack, подтверждение) и false (nak, отказ). Все другие имена задают существование не напрямую, два простых варианта исчерпаны и приходится использовать более сложные принципы.
Определение существования других элементов придётся поделить на два этапа: установка правил и действие правил. Правило состоит в том чтобы задавать не просто существование, а передачу существования от одной точки к другой. Тогда передача существования есть, а было ли оно получено — зависит от того, было ли оно у источника. Если источник отличается от true, то это уже не обязательно. И чтобы выяснить результат придётся отследить всю цепочку передачи. Один элемент за другим. Такое вот «Спасибо Марио, но твоя принцесса в другом замке».
В прологе описываемая передача выглядит так: получатель :- источник. Логически всё что происходит при установке этой связи это исключается сочетание, в котором источник существует, а получатель нет.
Сначала было обыкновенное пространство точек, а теперь всё усложнилось. В целом это даже интересно: простое пространство состояний существования преобразуется в пространство отношений, где по каждым двум именам в заданном порядке определено, есть ли между ними передача существования, либо её нет.
Либо «наука ещё пока не в курсе дела». Оказывается вдруг, такой вариант состояния связи тоже есть. Да, третий вариант. Уместен вопрос: а с чего бы вдруг оказалось больше двух?
Так ведь у расстановки две формы: одна форма, в которой собраны как расставленные связи так и неизвестные, которые условно отсутствуют. И вторая, в которой все ответы о существовании каждой связи уже получены и варианта существования «неизвестно» нет. Их различие в том что во второй каждые две идущие подряд передачи преобразованы одну прямую передачу, из условно отсутствующей она стала существующей. И только по завершении преобразования становится ясно, какое состояние у каждой точки, существует ли передача до неё от true, или её нет.
«Условное отсутствие» в точном понимании это «статус существования неизвестен».
Так что, два состояния на первом этапе и два на втором не имеют парного соответствия.
Переход от первой формы ко второй, выявление неизвестных данных исходя из известных, на основе общей согласованности — можно считать обобщённым вычислением. Это как поиск ответа сразу на все вопросы, которые возможны в данной ситуации.
При указании каждой связи чётко определено направление, и его различие очень важно. Например, передача существования от false к true бессмысленна, и полностью безразлично, существует она или нет. А вот передача существования от true к false это противоречие, её в полезной расстановке быть не может.
Для других точек одновременно получать существование от true и передавать его к false тоже нельзя, это ошибка, которая приводит к противоречивой расстановке.
Несуществование как будто тоже распространяется по связи, только в обратную сторону. И тогда всё симметрично, и не только у true есть своя пара, а всё пространство может быть сдвоено: у каждой точки есть дубль, связи у которого повторяют по своему существованию исходные связи, но направлены в противоположную сторону.
В полностью рассчитанной форме каждая точка либо связана с true, либо нет. Есть интересная возможность отсутствие связи от true считать наличием связи к false. Тогда возможны противоположности, которые обе ведут к false, когда обе не получают связь от true. Обратно в связь от true такие связи уже не дублируются.
Можно устанавливать связи между точками исходного пространства и дублирующего, это обыкновенные связи, стен между пространствами нет.
Только вот, связывать точку со своей противоположностью можно исключительно в направлении от отсутствующей к существующей, а в обратном направлении это создаёт связь через эти точки от true к false, и возникнет противоречие. У непротиворечивой связи внутри пары особого смысла нет: она свой собственный дубль, и ничего через себя ни в какую сторону передать не может.
Остальные связи полезны для ответов на вопросы. Вопрос в прологе это как попытка вывести связь от true к заданной точке путём рекурсивного поиска таких связей у всех точек, которые ведут к ней.
Выражение с точкой с запятой
результат :- условие1; условие2.
Означает что к точке «результат» есть две связи, сначала нужно проверить, есть ли связь от true до условие1, и затем есть ли связь до точки условие2. В любом из этих случаев будет установлено существование связи от true до результата.
В таком простом виде если первое условие выполняется, то для экономии времени второе можно было бы не проверять. Но пролог обходит все возможности и проверяет второе даже при верности первого. Правильно делает. Если в качестве результата и в качестве условий использованы структуры с неизвестными величинами в параметрах, то второе условие надо проверять наравне, варианты такой связи параметров когда оба условия выполняются — не должны исключаться. Ну а если оба условия просто true и подтверждение результата пройдёт два раза, то это совсем небольшие издержки.
Поиск на прологе, получается, — это поиск связей, идущих к некоторой заданной области, с выявлением формы той части этой области, к которой связь от true есть.
В воображении при размышлениях представляются точки, стрелки. Но всю описываемую связность можно представить в виде таблицы, в которой колонки и строки соответствуют отдельным точкам, а на пересечении нужно поставить одно из двух значений — связь (от точки колонки к точке строки) установлена/связь неизвестна — на первом этапе, или, после расчёта: связь есть/связи нет.
Вычислительное преобразование таблицы такое: если на пересечении колонки для первой точки и строки для второй точки есть отметка об установке, тогда все установленные связи в строке для первой точки устанавливают связь в строке для второй точки, в той же колонке. Простая операция.
Причём, ни добавление в таблицу к каждой точке её логической противоположности, ни оперирование неограниченным количеством точек в этой схеме не может привести к возникновению противоречий или парадоксов. (кроме пробоя true на false)
Впрочем, тонкий эффект возникает когда эти две особенности совмещаются.
Сначала касательно противоположностей: если у двух точек есть связность к третьей через «или», то у их противоположностей подобная связь в том же направлении будет через «и». Но такое «и» не срабатывает как «совмещённое зажигание». Объяснение этого в том что группа «или» в процессе вычисления вполне допускает последующие дополнения, и соответствующее ей «и» дожидается соответствующих этим дополнениям связей.
То есть, у связки «и» без фиксации группы аргументов устанавливающие связи идут от результата к аргументам, а в обратную сторону нет, и совместной установки результата при установленных аргументах не происходит. Как-то уже не так симметрично.
Конечно, операцию «и» можно внести, сделав учёт групп, дополнительными относительно обработки таблицы способами.
Но это ещё не эффект, только первая особенность. Вторая особенность что связь «и» может использоваться для превращения информации о существовании связи в утверждение (стрелка между точками будто сама становится точкой). Приведу соответствующий пример, в нём одно из условий это утверждение о существовании связи.
утверждение_получатель :- связь_существует, источник_этой_связи.
Описать можно так: если связь существует, то её результат будет зависеть от утверждения, которое является у этой связи источником. При этом само существование связи это отдельное утверждение.
Казалось бы, утверждение и связь единообразны, у обоих два варианта существования. Только вот, если не учитывать, что связей всегда больше чем утверждений — то есть, если скинуть связи и утверждения в одну кучу — то при использовании такой бесконечности открывается дорога к парадоксам и противоречиям — по сути, к непониманию собственных утверждений. Такая таблица, в которой для каждого пересечения строки и колонки есть своя собственная строка и колонка — всё же, не простая таблица. И что же может пойти не так?
Каждая связь интерпретируется сама как получатель связи. Если мы установим, что подтверждение B устанавливает связь от A к B, то на вопрос при подтверждённом A подтверждается ли B нельзя ответить однозначно. Ведь сброс условно отсутствующей связи при завершении расчёта должен учитывать и её собственные связи. И сброс может не выполняться из-за одного только наличия этих связей.
Конечно, такое исключение из списка сбрасываемых можно не делать, отсутствующая связь сама не возникнет. Но ведь можно и сделать, сброс вовсе не обязан сбрасывать всё! И тогда состояние остаётся неопределённым даже после завершения расчёта. По итогу, использование связей как утверждений позволяет привнести недосказанность как таковую. Такая связь уже не вписывается в три варианта состояния.
Ещё можно вспомнить, что в прологе различие порядка аргументов у конъюнкции влияет на зависание. Есть о чём задуматься.
Как вывод, абсолютно прозрачное совмещение фактов и их связей делать не стоит. Возможность есть, но это ведь только начало осознания всех возможностей.
Следующее на что нужно обратить внимание это то что связность утверждений зависит от их содержания, это можно рассматривать как существование у каждого утверждения такого имени, по которому его можно отличить от остальных, и которое раскрывает его суть. Можно расставлять связи исходя из имён объектов. И здесь можно заметить ещё один эффект.
Если между тремя утверждениями есть связи от первого ко второму, а от второго к третьему, то при выявлении других связей образуется и связь от первого к третьему. Это тривиально. А вот если уже существовала связь от третьего к первому, то по тем же принципам появятся связи от второго к первому и от третьего ко второму. Получится круговая связь в обе стороны.
Но если между любыми двумя утверждениями есть связь в обе стороны, то связь от true у них будет одинаковая — какой бы она ни была. И значит, кроме своего описания эти утверждения ничем не отличаются. Практически, такие два утверждения схлапываются до одного. И в примере для всех трёх утверждений — то же самое.
Замкнутая связь любой длины в результате схлапывается до одного утверждения, пусть и с разными описаниями. Это как разные имена у одного объекта, а количество имён не ограничено. После цепочки выводов любой длины достаточно одного шага замыкания чтобы различия на всём пути стали бы символическими и мы бы оказались там же откуда и вышли.
Это в воображении производит разделение: пространство связности утверждений и пространство их описаний. Эти пространства имеют связь, но совсем разные. Пространство имён шире. Да и в целом, стоит обратить внимание, что именование не менее важная часть работы с утверждениями, чем связность.
Пролог с множественными именами не справляется — встретив безусловные циклические связи он провалит весь поиск, просто зависнет. Пролог рассчитан на то что его не обманывают, описывая разными способами одно и то же утверждение.
Немного о программировании в ограничениях (Constraint Logic Programming, CLP).
Что в прологе во время расчёта происходит? Просто перебираются варианты, в ситуации когда подходящий обязательно о себе сообщит. Вполне действенно, если затраченное время не важно. Но если хочется побыстрей, то можно ускориться.
Есть хорошо подходящий для объяснения пример: с помощью пролога решают судоку. В нём демонстрируются дополнительные возможности, так как без них перебор происходил бы слишком долго. «Судоку» — это квадрат девять на девять, в каждой клетке которого находится цифра от одного до девяти, но так чтобы в каждой строке был весь набор, в каждой строке тоже был весь набор, и если общий квадрат разделить на девять квадратов, составленных вместе три на три, то и в каждом таком квадрате тоже был бы весь набор. Изначально заданы только некоторые числа, а «решить судоку» — значит подобрать остальные. Чаще всего вариант решения только один. Пока решаешь, то учишься что-то прикидывать в уме, а программа легко решает за тебя.
Я видел текст программы — там просто описываются все эти правила, наглядно показано декларативное программирование — просто опиши задачу, которую хочешь решить. Но есть в тексте и дополнения.
Как вручную решется судоку? Я решал так: в каждой клетке, в которой значение неизвестно, подписывал все значения, которые там могут быть (сначала весь набор), а потом их постепенно вычёркивал. Если бы пролог учитывал не только точно известное значение, но и знание о возможных значениях, то решение было бы быстрым, будто проходится сразу несколько веток решения одновременно. Ну так, он с помощью дополнительных библиотек и учитывает.
Для значений учитывается «домен» — возможные варианты, количество которых ограничено.
Подключаемое расширение работает прямо с доменами, появляются дополнительные операторы, которые их используют в качестве переменных, при решении сужают возможные значения до одного.
Если в клетке при решении судоку из возможных значений останется только одно, то оно фиксируется, и дальше просчитывается влияние на остальные клетки, одна клетка запрещает повторяться другим 8 + 8 + 4 = 20 клеткам. Расчёт влияния на домен — хороший приём, вот только его одного недостаточно для решения всех судоку.
Иногда встречаются ситуации, требующие более глубокого анализа. Например, такая в которой в двух клетках одной группы остаются только по два варианта. Тогда расставить в них значения можно только двумя способами, а особенность в том что влияние на другие клетки в любом случае будет одинаковым — оба варианта в других клетках группы исключаются.
Бывает, встречается и три клетки, в которых только по три повторяющихся значения. С ними произойдёт то же самое, в других клетках эти три значения будут исключены. Причём, если в одной клетке из трёх вариантов осталось только два (1, 2, 3) - (1, 2, 3) - (1, 2), это всё равно подходит под шаблон.
С этим уменьшением домена можно разобраться чуть глубже: влияние также останется если и в других клетках некоторые значения будут исключены, например, во второй один, а в первой два. Ведь тогда будет как будто замкнутая цепочка из (2, 3) - (3, 1) - (1, 2). Алгоритм, обрабатывающий предикат all_different, ищет именно такие цепочки максимальной длины и учитывает их влияние на возможные значения.
К чему мы пришли? Пространство в воображении занимают точки-объекты трёх типов: true, false, и утверждения, связность с указанными двумя объектами зависит от того, как связность заданная переходит в связанность рассчитанную. Их количество не ограниченно, а результат использования зависит от навыков именования. Включая некоторые оптимизации.
Заканчивая статью, можно построить наглядную модель пролога. Это такой прибор, в которой собраны мелкие однонаправленные провода, каждый такой проводок это либо контакт снаружи от плюса — это в прологе «факт», либо контакт, ведущий от другого контакта, в прологе это действие правил.
К этой области подразумевается некоторая противоположность, в ней контакты либо ведут к земле, либо точно так же от одного контакта к другому, только, в обратную сторону относительно отражения в другой области.
Самое главное в схеме — ни один проводок не должен замыкать плюс на землю.
И третья область, характеризуется тем что плюс не подведён ни к элементу, ни к его противопложности. Можно считать, что в прологе области противоположности и нет, есть только области с подведённым плюсом, и эта, третья, с не подведённым. Каждый проводок к какой-нибудь из них принадлежит, сразу не разберёшь. Так что, к этому узлу подключают щуп с минусом — вводят вопрос.
Если сделать ток переменный, то вместо «+» будет фаза, а вместо «-» ноль. Вся работа заключается в поиске всех вариантов замыкания фазы на ноль, а если контакта не будет, то до места куда подсоединили щуп фаза не добирается, и значит, можно замыкать на ⏚. Недавно подключал стиральную машинку, так там точно так же три провода.