Программирование на языке Пролог для искусственного интеллекта
Шрифт:
Рис. 4.5. Планировщик воздушных маршрутов и база данных о рейсах
Вот некоторые примеры вопросов к планировщику:
• По каким дням недели существуют прямые рейсы из Лондона в Люблину?
• Как мне добраться из Любляны в Эдинбург в четверг?
• Как мне посетить Милан, Любляну и Цюрих, вылетев из Лондона во вторник и вернувшись в него в пятницу, совершая в день не более одного перелета? Этот вопрос сложнее, чем предыдущие. Его можно сформулировать, использовав отношение
4.5. Задача о восьми ферзях
Эта задача состоит в отыскании такой расстановки восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого. Решение мы запрограммируем в виде унарного отношения:
которое истинно тогда и только тогда, когда
4.5.1. Программа 1
Вначале нужно выбрать способ представления позиции на доске. Один из наиболее естественных способов — представить позицию в виде списка из восьми элементов, каждый из которых соответствует одному из ферзей. Каждый такой элемент будет описывать то поле доски, на которой стоит соответствующий ферзь. Далее, каждое поле доски можно описать с помощью пары координат (X и Y), где каждая координата - целое число от 1 до 8. В программе мы будем записывать такую пару в виде
где оператор "
После того, как мы выбрали такое представление, задача свелась к нахождению списка вида:
удовлетворяющего требованию отсутствия нападений. Наша процедура
Рис. 4.6. Решение задачи о восьми ферзях. Эта позиция может быть представлена в виде списка
Нас интересует решение для доске размером 8×8. Однако, как это часто бывает в программировании, ключ к решению легче найти, рассмотрев более общую постановку задачи. Как это ни парадоксально, но часто оказывается, что решение более общей задачи легче сформулировать, чем решение более частной, исходной задачи; после этого исходная задача решается просто как частный случай общей задачи.
Основная часть работы при таком подходе ложится на нахождение правильного обобщения исходной задачи. В нашем случае хорошей является идея обобщать задачу в отношении количества ферзей (количества вертикалей в списке), разрешив количеству ферзей принимать любое значение, включая нуль. Тогда отношение решение можно сформулировать, рассмотрев два случая:
Случай 1. Список ферзей пуст. Пустой список без сомнения является решением, поскольку нападений в этом случае нет.