Шрифт:
Посмотреть ответ
4. 5. Зацикливание при вычислении допускается можно предотвратить, например, таким способом: подсчитывать число переходов, сделанных к настоящему моменту. При этом модель должна будет искать пути только некоторой ограниченной длины. Модифицируйте так отношение допускается. Указание: добавьте третий аргумент - максимально допустимое число переходов:
допускается( Состояние, Цепочка, Макс_переходов)
Посмотреть ответ
Назад | Содержание | Вперёд
Назад | Содержание | Вперёд
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 минут для пересадки с одного рейса на другой.
Задача нахождения маршрута напоминает моделирование недетерминированного автомата из предыдущего раздела:
Состояния автомата соответствуют городам.