Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
4.4. Почему не могло возникнуть зацикливание модели исходного автомата на рис. 4.3, когда в его графе переходов не было "спонтанного цикла"?
4.5. Зацикливание при вычислении допускается можно предотвратить, например, таким способом: подсчитывать число переходов, сделанных к настоящему моменту. При этом модель должна будет искать пути только некоторой ограниченной длины. Модифицируйте так отношение допускается. Указание: добавьте третий аргумент — максимально допустимое число переходов:
допускается(Состояние, Цепочка, Макс_переходов)
Планирование поездки
В данном разделе мы создадим программу, которая дает советы по планированию воздушного путешествия. Эта программа будет довольно примитивным советчиком, тем не менее она сможет отвечать на некоторые полезные вопросы, такие как:
• По каким дням недели есть прямые рейсы из Лондона в Любляну?
• Как в четверг можно добраться из Любляны в Эдинбург?
• Мне нужно посетить Милан, Любляну и Цюрих; вылетать нужно из Лондона во вторник и вернуться обратно в Лондон в пятницу. В какой последовательности мне следует посещать эти города, чтобы ни разу на протяжении поездки не пришлось совершать более одного перелета в день.
Центральной частью программы будет база данных, содержащая информацию о рейсах. Эта информация будет представлена в виде трехаргументного отношения:
расписание(Пункт1, Пункт2, Список_рейсов)
где Список_рейсов — это список, состоящий из структурированных объектов вида:
Время_отправления / Время_прибытия / Номер_рейса
/ Список_дней_вылета
Список_дней_вылета — это либо список дней недели, либо атом "ежедневно". Одно из предложений, входящих в расписание могло бы быть, например, таким:
расписание(лондон, эдинбург,
[ 9:40 / 10:50 / bа4733/ ежедневно,
19:40 / 20:50 / bа4833 / [пн, вт, ср, чт, пт, сб]]).
Время представлено в виде структурированных объектов, состоящих из двух компонент — часов и минут, объединенных оператором ":".
Главная задача состоит в отыскании точных маршрутов между двумя заданными городами в определенные дни недели. Ее решение мы будем программировать в виде четырехаргументного отношения:
маршрут(Пункт1, Пункт2, День, Маршрут)
Здесь Маршрут — это последовательность перелетов, удовлетворяющих следующим критериям:
(1) начальная точка маршрута находится в Пункт1;
(2) конечная точка — в Пункт2;
(3) все перелеты совершаются в один и тот же день недели — День;
(4) все перелеты, входящие в Маршрут, содержатся в определении отношения расписание;
(5) остается достаточно времени для пересадки с рейса на рейс.
Маршрут представляется в виде списка структурированных объектов вида
Откуда - Куда: Номер_рейса: Время_отправления
Мы еще будем пользоваться следующими вспомогательными предикатами:
(1) рейс(Пункт1, Пункт2, День, N_рейса, Вр_отпр, Вр_приб)
Здесь сказано, что существует рейс N_рейса между Пункт1 и Пункт2 в день недели День с указанными временами отправления и прибытия.
(2) вр_отпр(Маршрут, Время)
Время — это время отправления по маршруту Маршрут.
(3) пересадка(Время1, Время2)
Между Время1 и Время2 должен существовать промежуток не менее 40 минут для пересадки с одного рейса на другой.
Задача нахождения маршрута напоминает моделирование недетерминированного автомата из предыдущего раздела:
• Состояния автомата соответствуют городам.
• Переход из состояния в состояние соответствует перелету из одного города в другой.
• Отношение переход автомата соответствует отношению расписание.
• Модель автомата находит путь в графе переходов между исходным и конечным состояниями; планировщик поездки находит маршрут между начальным н конечным пунктами поездки.
Неудивительно поэтому, что отношение маршрут можно определить аналогично отношению допускает, с той разницей, что теперь нет "спонтанных переходов". Существуют два случая:
(1) Прямой рейс: если существует прямой рейс между пунктами Пункт1 и Пункт2, то весь маршрут состоит только из одного перелета:
маршрут(Пункт1, Пункт2, День, [Пункт1-Пункт2: Nр: Отпр]):-
рейс(Пункт1, Пункт2, День, Np, Отпр, Приб).
(2) Маршрут с пересадками: маршрут между пунктами P1 и Р2 состоит из первого перелета из P1 в некоторый промежуточный пункт Р3 и маршрута между Р3 и Р2. Кроме того, между окончанием первого перелета и отправлением во второй необходимо оставить достаточно времени для пересадки.
маршрут(P1, Р2, День, [P1-Р3: Nр1: Отпр1 | Маршрут]):-
маршрут(Р3, Р2, День, Маршрут),
рейс(P1, Р3, День, Npl, Oтпpl, Приб1),
вр_отпр(Маршрут, Отпр2),
пересадка(Приб1, Отпр2).
Вспомогательные отношения рейс, пересадка и вр_отпр запрограммировать легко; мы включили их в полный текст программы планировщика поездки на рис. 4.5. Там же приводится и пример базы данных расписания.
Наш планировщик исключительно прост и может рассматривать пути, очевидно ведущие в никуда. Тем не менее его оказывается вполне достаточно, если база данных о рейсах самолетов невелика. Для больших баз данных потребовалось бы разработать более интеллектуальный планировщик, который мог бы справиться с большим количеством путей, участвующих в перебора при нахождении нужного пути.
% ПЛАНИРОВЩИК ВОЗДУШНЫХ МАРШРУТОВ
:- op(50, xfy,:).
рейс(Пункт1, Пункт2, День, Np, ВрОтпр, ВрПриб):-
расписание(Пункт1, Пункт2, СписРейсов),
принадлежит(ВрОтпр / ВрПриб / Nр / СписДней, СписРейсов),
день_выл(День, СписДней).
принадлежит(X, [X | L]).
принадлежит(X, [Y | L]):-
принадлежит(X, L).
день_выл(День, СписДней):-
принадлежит(День, СписДней).
день_выл(День, ежедневно):-
принадлежит(День, [пн, вт, ср, чт, пт, сб, вс]).
маршрут(P1, P2, День, [P1-Р2: Np: ВрОтпр]):-
% прямой рейс
рейс(P1, P2, День, Np, ВрОтпр, _).
маршрут(P1, Р2, День, [Pl-P3: Np1: Oтпp1 | Маршрут]):-
% маршрут с пересадками
маршрут(Р3, P2, День, Маршрут),
рейс(P1, Р3, День, Npl, Oтпp1, Приб1),
вр_отпр(Маршрут, Отпр2),
пересадка(Приб1, Отпр2).
вр_отпр([P1-Р2: Np: Отпр | _ ], Отпр).
пересадка(Часы1: Минуты1, Часы2: Минуты2):-
60 * (Часы2-Часы1) + Минуты2 - Минуты1 >= 40
% БАЗА ДАННЫХ О РЕЙСАХ САМОЛЕТОВ
расписание(эдинбург, лондон,
[ 9:40 / 10:50 / bа4733 / ежедневно,
13:40 / 14:50 / ba4773 / ежедневно,
19:40 / 20:50 / bа4833 / [пн, вт, ср, чт, пт, вс] ]).
расписание(лондон, эдинбург,
[ 9:40 / 10:50 / bа4732 / ежедневно,
11:40 / 12:50 / bа4752 / ежедневно,
18:40 / 19:50 / bа4822 / [пн, вт, ср, чт, пт] ]),
расписание(лондон, любляна,
[13:20 / 16:20 / ju201 / [пт],
13:20 / 16:20 / ju213 / [вс] ]).
расписание(лондон, цюрих,
[ 9:10 / 11:45 / bа614 / ежедневно,
14:45 / 17:20 / sr805 / ежедневно ]).
расписание(лондон, милан,
[ 8:30 / 11:20 / bа510 / ежедневно,
11:00 / 13:50 / az459 / ежедневно ]).
расписание(любляна, цюрих,
[11:30 / 12:40 / ju322 / [вт,чт] ]).
расписание(любляна, лондон,
[11:10 / 12:20 / yu200 / [пт],
11:25 / 12:20 / yu212 / [вс] ]).
расписание(милан, лондон,
[ 9:10 / 10:00 / az458 / ежедневно,
12:20 / 13:10 / bа511 / ежедневно ]).
расписание(милан, цюрих,
[ 9:25 / 10:15 / sr621 / ежедневно,
12:45 / 13:35 / sr623 / ежедневно ]).
расписание(цюрих, любляна,
[13:30 / 14:40 / yu323 / [вт, чт] ]).
расписание(цюрих, лондон,
9:00 / 9:40 / bа613 /
[ пн, вт, ср, чт, пт, сб],
16:10 / 16:55 / sr806 / [пн, вт, ср, чт, пт, сб] ]).
расписание(цюрих, милан,
[ 7:55 / 8:45 / sr620 / ежедневно ]).
Рис. 4.5. Планировщик воздушных маршрутов и база данных о рейсах самолетов.
Вот некоторые примеры вопросов к планировщику:
• По каким дням недели существуют прямые рейсы из Лондона в Люблину?
?- рейс(лондон, любляна, День, _, _, _).
День = пт;
День = сб;
no (нет)
• Как мне добраться из Любляны в Эдинбург в четверг?
?- маршрут(любляна, эдинбург, чт, R).
R = [любляна-цюрих: уu322: 11:30, цюрих-лондон:
sr806: 16:10,
лондон-эдинбург: bа4822: 18:40 ]
• Как мне посетить Милан, Любляну и Цюрих, вылетев из Лондона во вторник и вернувшись в него в пятницу, совершая в день не более одного перелета? Этот вопрос сложнее, чем предыдущие. Его можно сформулировать, использовав отношение перестановка, запрограммированное в гл. 3. Мы попросим найти такую перестановку городов Милан, Любляна и Цюрих, чтобы соответствующие перелеты можно было осуществить в несколько последовательных дней недели:
?- перестановка([милан, любляна, цюрих],
[Город1, Город2, Город3]),
рейс(лондон, Город1, вт, Np1, Oтпp1, Пpиб1),
peйc(Город1, Город2, ср, Np2, Отпр2, Приб2),
рейс(Город2, Город3, чт, Np3, Отпp3, Приб3),
рейс(Город3, лондон, пт, Np4, Отпр4, Приб4).
Город1 = милан
Город2 = цюрих
Город3 = любляна
Np1 = ba510
Отпр1 = 8:30
Приб1 = 11:20
Np2 =sr621
Отпр2 = 9:25
Приб2 = 10:15
Np3 = yu323
Отпр3 = 13:30
Приб3 = 14:40
Np4 = yu200
Отпр4 = 11:10
Приб4 = 12:20
Задача о восьми ферзях
Эта задача состоит в отыскании такой расстановки восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого. Решение мы запрограммируем в виде унарного отношения:
решение(Поз)
которое истинно тогда и только тогда, когда Поз изображает позицию, в которой восемь ферзей не бьют друг друга. Будет интересно сравнить различные идеи, лежащие в основе программирования этой задачи. Поэтому мы приведем три программы, основанные на слегка различающихся ее представлениях.
Дата публикования: 2015-10-09; Прочитано: 170 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!