Поиск оптимального пути в графе (стр. 2 из 2)

15MbRAM

Монитор

Клавиатура

2.2 Минимальные требования к информационной и программной совместимости

Windows 9х/NT/2000/ME (Visual Prolog 5.2 требует ОС типа Windows)

VisualProlog 5.2

Поддержка операционной системой национальных шрифтов (кириллица)

2.3 Интерфейс пользователя

Для получения решения пользователь должен ввести запрос в формате: start (остановка1, остановка2). Где остановка1 - начальная остановка, а остановка2 - конечная. Результат решения:

Путь: ["остановка1","мi","остановкаQ",...,"мj"," остановка 2"]

Сумма_времени=Kyes

Так же результата решения может и не быть: “no", если нет таких пути, остановок, введённых в запрос пользователем. Поэтому требование к входным данным такое: остановки, введённые в запрос должны быть базе фактов.

Если пользователь захотел добавить ветвь, то ему необходимо добавить в базу фактов ещё один или два, один из которых обеспечивает не направленность ветки в формате:

участок (остановка1, х1, у1, остановка2, х2, у2, номер_маршрутки, время).

(участок (остановка2, х2, у2, остановка1, х1, у1, номер_маршрутки, время)) Для закрытии какой-нибудь линии необходимо сделать обратное -.

Для добавления новой остановки между двумя соединенными остановками надо отредактировать один факта и добавить новый и плюс два факта, описывающие обратные участки для всё той же не направленности веток и графа в целом:

участок (остановка1, х1, у1, остановкаNew, хN, уN, номер_маршрутки, время1).

NEW-участок (остановкаNew, хN, уN, остановка2, х2, у2, номер_маршрутки, время2).

(участок (остановкаNew, хN, уN, остановка1ew, х1, у1, номер_маршрутки, время1).

NEW-участок (остановка2, х2, у2, остановкаNew, хN, уN, номер_маршрутки, время2))

Для добавления новой остановки, не врезающейся в ветвь надо добавить факты, описывающие соединения этой остановки с другими.

3. Руководство программиста

3.1 Функциональная схема

Логические модели. Блок-схемы алгоритма.

а) принадлежит (Х, [Х|_]).

принадлежит (Х, [_|Хвост]): - принадлежит (Х, Хвост).

см. Братко И. Программирование на языке Пролог для искусственного интеллекта.

б) max (X,Y,X): - X>Y.

max (X,Y,Y): - X<=Y.

min (X,Y,X): - X<Y.

min (X,Y,Y): - X>=Y.

см. Братко И. Программирование на языке Пролог для искусственного интеллекта.

в) мин_сумма1 (_, []).

мин_сумма1 (М, [Х|Список]): - М<=Х, мин_сумма1 (М, Список).

мин_сумма2 (М, [Х|Список]): - мин_сумма1 (М, Список),!;

мин_сумма2 (М, Список).

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

г) коридор (Нач, Кон, СписокХ, СписокУ): -

участок (Нач, Х1, У1,_,_,_,_,_),!,

участок (_,_,_, Кон, Х2, У2,_,_),!,

min (Х1, Х2, МИН1),

max (Х1, Х2, МАКС1),

добавить_в_дипазон (МИН1, МАКС1, СписокХ),

min (У1, У2, МИН2),

max (У1, У2, МАКС2),

добавить_в_дипазон (МИН2, МАКС2, СписокУ).

Определяет координаты начальной и конечной остановки, минимальное и максимальное значения среди Х1, Х2 и У1, У2, затем уходит на правило, описанное в пункте д). Отсечение (зелёное) позволяет находить первое единсвенное решение, а остальные отбрасываютя, из-за идентичности.

д) добавить_в_дипазон (А, В, []): - А=В+1.

добавить_в_дипазон (А, В, [А|Список]): - А<=В, А1=А+1,добавить_в_дипазон (А1, В, Список).

А - минимальное значение, а В - максимальное. Список - дискретный набор целых чисел от А до В включительно с шагом в единицу. Пока А не равно В+1, А увеличивается на единицу и добавляется в голову Списка. Хвост в списке остаётся пустым.

е) путь (С, С,_, [С],_,_,0).

Путь с любой остановки в туже занимает время равное нолю, а список пути имеет только один элемент - начальная остановка. Так же этот предикат служит “заглушкой” для следующего правила, т.е. путь, найден, когда следующая остановка равна конечной. Конечная остановка добавляется в переменную Путь в виде списка. Время затраченное на прохождение ветви из конечной в начальную равняется нолю.

участок (Нач, След, Х2, У2, М, Время),

not (принадлежит_симв (След, Список)),

принадлежит (Х2, СписокХ),

принадлежит (У2, СписокУ), путь (След, Кон, [След|Список], Путь, СписокХ, СписокУ, Сумма1),

Сумма=Сумма1+Время.

Ветвь существует, если:

существует участок с первой начальной (последующей) остановкой и существующей следующей;

следующая остановка не принадлежит списку из предшествующих её остановок;

координаты следующей остановки принадлежат соответственным спискам, которые определяют “коридор".

Общая схема поиска пути (правило stsrt)

Блок-схема поиска отдельного пути (правило путь)

3.2 Тестовый пример

Выполним запросы:

а) start (кузнечиха_2, пл_сенная).

Решение:

Путь:

["кузнечиха_2","м43","кардиоцентр","м43","пл_советская","м39","в_печеры","м2","семашко","м2","пл_сенная"]

Сумма_времени=33yes

В решении используются факты, принадлежащие базе фактов, - факт24,26,21,31,34, также все факты и правила расположенные ниже базы фактов, кроме факта 60, который определяет путь, состоящий из одной остановки. Если, например, убрать факт21, то данного решения не будет, может, будет иное решение или решения вообще не будет. Проверив, я убедился, что решения нет. Убрав какое-нибудь из правил, вся программа “рухнет".

б) start (кузнечиха_2, кузнечиха_2).

Решение:

Путь: ["кузнечиха_2"]

Сумма_времени=0Yes

При решении затрагиваются: стартовое правило12 и факт 60, который и определяет это решение. Если его заремить, то решения не будет найдено.

в) Также ответ на запрос может быть “no" см. п.2.5

Используемая литература

1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. - М.: Мир, 1990. - 560 с., ил.

2. СТП 1-У-НГТУ-98 “Проекты (работы) дипломные и курсовые. Общие требования к оформлению пояснительных записок и чертежей"