Неизвестно - Prolog

допускается( Состояние, Цепочка, Макс_переходов)

Посмотреть ответ

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

4. 4. Планирование поездки

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

По каким дням недели есть прямые рейсы из Лондона в Любляну?

Как в четверг можно добраться из Любляны в Эдинбург?

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

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

расписание( Пункт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) Маршрут с пересадками: маршрут между пунктами Р1и Р2состоит из первого перелета из P1в некоторый промежуточный пункт Р3и маршрута между Р3и Р2. Кроме того, между окончанием первого перелета и отправлением во второй необходимо оставить достаточно времени для пересадки.

маршрут( Р1, Р2, День, [Р1-Р3 : Nр1 : Отпр1 | Маршрут]) :-

маршрут( Р3, Р2, День, Маршрут ),