1

1. Анализ исходных данных и разработка ТЗ

1.1 Основание и назначение разработки

Основанием для разработки данного проекта послужило выполнение курсовой работы по курсу «Представление знаний в информационных системах». Назначение разработки - это изучение языка программирования Prolog. Также эта программа должна быть полезной для навигации по нашему городу.

Данная разработка предназначена для выбора маршрута передвижения по городу Нижнему Новгороду на социальных автобусах.

Потенциальные пользователи программы - сотрудники и пассажиры Нижегородпассажиравтотранса. Данная работа облегчит поиск маршрута в по городу с заданными особенностями для людей, плохо ориентирующихся в Нижнем Новгороде или совсем не знакомых с его системой. Данные, которые являются результатом работы приведенной здесь программы, четко описывают путь движения автобусов, пересадки, и дают сведения о времени необходимом на преодоление данного пути.

1.2 Постановка задачи в предметной области. Разработка математической модели задачи

Суть задачи заключается в отыскании оптимального пути от одной остановки до другой по Нижнему Новгороду на социальном автобусе. Исходя из того, что маршрутов в городе более пятидесяти, а остановки, исчисляются сотнями, то размерность задачи можно считать средней. При решении полным перебором, может возникнуть проблема, а именно, время отыскания пути может занять неопределённое время. Поэтому полный перебор здесь не подойдёт.

Далее я выбрал геометрическую интерпретацию.

В данной задаче вершинам графа соответствуют остановки города с указанием координат их расположения, а ребрам - пути между соседними остановками.

Для решения данной задачи вводятся следующие понятия:

Остановка - один из узлов графа. Определяет параметры ветки, в которые входит: начальная остановка, её координаты, следующая остановка, её координаты.

Расстояние - расстояние между остановками, точками, принадлежащими коридору.

остановка(остановка1,остановка2,х1,у1,х2,у2).

Смежные - определяет соседние остановки, делает граф ненаправленным и рассчитывает расстояние между остановками.

Путь - осуществляет поиск ветвей и заносит найденные ветви в маршрут.

Принадлежит - определяет принадлежность элемента к списку. В нашем случае - остановки к маршруту.

Карта - то, что отображается графом.

Координаты остановок - пара значений Х и У, которые имеет каждый город карты.

Расстояние - вычисляет расстояние между точкой и прямой для подсчета коридора и расстояния от начальной точки до конечной. Вычисления производятся по формуле:

Оптимальный путь (в программе «путь») - это путь, имеющий наименьшее значение по сравнению с остальными.

Модуль (в программе «аbs»).

Корень числа (в программе«sqrt») - вычисляет квадратный корень из числа.

Коридор (в программе переменная «Коридор») - пояснение: Коридор<10 - невозможность выхода за пределы коридора. Коридор - полоса от начальной до конечной точки движения, в области которой определяются вершины - кандидаты для нахождения оптимального пути. Ширина коридора - максимальное расстояние от рассматриваемой вершины до прямой, соединяющей начальную и конечную точки.

Маршрут - содержит номер автобуса и остановки через которые он едет.

В качестве математической модели я выбрал ненаправленный граф. Где вершины графа - это остановки, а ветви - участки, которые автобус может проехать не останавливаясь. Как было сказано раньше полный перебор здесь не подходит, поэтому я определил понятие “коридор”, который определяет диапазон дуг. (Суть “коридора” описывается ниже в алгоритмах). Граф, конечно, может и не только неориентированным, но и смешанным, т.е. маршрутка может проезжать по ветви только в одном направлении, а возвращаться по иной ветви.

1.3 Выбор и обоснование основного алгоритма решения задачи

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

1. Суть первого алгоритма заключается в следующем: сначала поиск производится всех путей, а за тем в найденных путях по критерию наименьшей стоимости отбирается самый дешёвый. В таком алгоритме есть большой минус. Если граф будет состоять из большого числа ветвей, а в нашем случае предполагается что город большой, значит и граф должен быть большой, то поиск необходимого пути может занять неопределённое количество времени и в некоторых случаях персональный компьютер может просто зависнуть. Я считаю, что этот алгоритм оптимален сточки зрения результата. Потому что по этому алгоритму проверяются все возможные пути. Но в таком случае он не оптимален с точки зрения процедуры поиска самого пути.

Значит, поиск оптимального пути должен производиться не по всевозможным путям, а по путям, которые входят в некоторое подмножество. Отсюда следует следующий алгоритм.

2. По данному алгоритму вся карта делится на квадраты:

Каждый квадрат имеет пару координат. А в каждый квадрат могут попадать остановки, которые будут иметь координаты. В таком случае можно попробовать построить “коридор” от начальной остановки до конечной остановки. Этот “коридор” будет состоять из пары диапазонов: по вертикали и горизонтали. Диапазоны будут определяться из введённых пользователем данных: начальной и конечной остановок, которые в свою очередь имеют координаты. Теперь в полученном “коридоре” будет производиться поиск оптимального пути по предыдущему алгоритму. Недостаток этого алгоритма заключается в следующем: “коридор”, который мы сформировали, может не иметь ветвей, и в таком случае решения мы не получим. Поэтому не стоит делать коридор узким. Наверное, стоит его сделать искусственно шире, т.е. расширить диапазоны. Конечно вероятность получить ответ увеличивается, но остается вероятность также не получить оптимального результата или не получить ответа вообще. Достоинство этого алгоритма перед предыдущим заключается в том, что поиск производится по ограниченному “коридором” - числу ветвей. Он оптимален с точки зрения процедуры поиска пути. В отличие от первого алгоритма мы можем, получит здесь путь по времени дольше, так как перебор ветвей ограничен.

3. Еще один алгоритм. Сохраним систему координат и понятие из предыдущего алгоритма. Будем двигаться от начальной остановки к конечной остановке, выбирая ветвь наименьшей длинны. Этот алгоритм ещё называется градиентным. В таком алгоритме есть недостаток: полученный путь может получиться далеко не оптимальным.

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

5. Сохраняем стратегию второго алгоритма и добавляем ограничение на прохождение по ветви в обратном направлении. Тем самым мы отбрасываем не нужные нам решения.

Для решения поставленной задачи был выбран пятый алгоритм. Я считаю, что этот алгоритм в своём функционале имеет “золотую середину”. Так как процедура поиска пути получается не очень объёмная, потому что ограничено количество ветвей “коридором”, и происходит выбор пути из некоторого подмножества, а не сразу по некоторой эвристике. Объём этого подмножества, конечно, зависит не от объёма базы данных, а от того, на сколько удалены начальная и конечная остановки.

1.4 Требования к функциональным характеристикам

Программа должна выполнять следующие функции:

ь Ввод исходных данных

ь Решение задачи - нахождение оптимального пути

ь Вывод найденного решения

2. Руководство Пользователя

2.1 Назначение программы

Программа предназначена для поиска оптимального пути в Нижнем Новгороде на социальном автобусе. Или поиск пути в графе, где вершины графа - это остановки, а ветви - участки пути автобуса. С помощью этой программы можно отыскать путь за минимальное время проезда от одной остановки до заданной. Результатом программы является список остановок и номеров автобусов, которые расположены между остановками, и сумма времени. Из списка будет видно, что делать пользователю, а именно, пересаживаться на другое маршрутное такси или ехать дальше.

2.2 Минимальные требования к составу и параметрам технических средств

ь IBM совместимый персональный компьютер с CPU, начиная с 486 и выше

ь 100Kb свободного пространства на HDD

ь 15Mb RAM

ь Монитор

ь Клавиатура

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

ь Windows 95 или выше (Visual Prolog 5.1 требует ОС типа Windows)

ь Visual Prolog 5.1 или выше

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

2.4 Входные данные

Входными данными в программе являются:

Схема проезда.

Программа принимает базу фактов языка Prolog, описывающих все возможные перемещения между остановками.

б) Начальный и конечный пункт движения.

Начальным и конечным пунктом маршрута являются введенные пользователем остановки.

2.5 Выходные данные

В качестве выходных данных программа выдает минимальный путь в виде списка Prolog'a между начальной и конечной остановкой, и время пути.

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

После запуска программы программа просит пользователя ввести начальную и конечную остановки, после чего начинается поиск оптимального пути. После завершения поиска пути пользователь просматривает найденные решения. Если решение не найдено, следует увеличить ширину коридора.

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

При запуске программы пользователю предлагается ввести с клавиатуры название начальной и конечной остановки. Также можно выйти из программы нажатием кнопки Esc.

Следует вводить полное название станции. Вместо пробелов и дефисов используется знак подчеркивания "_".

Результатом работы программы будет время, которое необходимо затратить на преодоление данного маршрута и соответственно сам маршрут с указанием автобусов на которых следует его проходить.

Также результатом работы программы может быть и “no”, это означает, что остановка была введена некорректно, либо задан слишком узкий коридор.

Увеличивать коридор лучше со значения 1, с любым шагом до тех пор, пока программа не найдет оптимальный путь.

Пользователь должен учесть, что программа может рассмотреть всего один или несколько существующих путей в коридоре, среди которых будет найден оптимальный, но на самом деле таковым не является, так как может существовать точка за пределами коридора, после включения которой путь окажется меньшим. Для этого после первого появления оптимального пути, нужно повторить процедуру увеличения ширины коридора, после чего вероятность правильности результата будет стремиться к 100%.

- Изменение структуры:

У пользователя есть возможность изменить структуру сети маршрута (менять обозначения остановок, добавлять новые остановки, удалять остановки).

Изменяя данные факты, пользователь вносит желаемые изменения в структуру сети маршрута. Необходимо помнить, что для успешной работы с текстом программы, пользователь должен обладать знаниями синтаксиса языка Пролог.

2.8 Основной алгоритм программы

Результатом работы программы является конечное множество путей. Два пути мы будем считать различными, если они отличаются, хотя бы координатой одной остановки. Каждый последующий найденный путь сравнивается с предыдущим, если его длина оказывается меньше, то оптимальное значение пути, хранящееся во внутренней базе обновляется найденным и поиск продолжается, если нет, то ищется следующий путь.

Метод решения - метод последовательных испытаний. Поиск решений будет осуществляться рекурсивно, причем максимальная глубина рекурсии будет равна максимальному количеству переходов между пунктами движения.

Для решения поставленной задачи необходимы внутренние данные.

Внутренними данными в программе являются:

- переменные;

- факты;

- правила;

- константы.

Поиск оптимального пути построен также на алгоритме рекурсии, потому что при этом подходе легче передаются полученные в результате поиска данные (ответы). Также можно сказать, что в случае отыскания оптимального пути в БД (с удалением неоптимальных путей) гораздо легче использовать рекурсию, чем алгоритм полного перебора.

После запуска программы происходит проверка истинности запроса (GOAL). Истинность или ложность данного запроса определяется правильным введением размерности коридора и необходимых точек. Если база данных оказывается не пустой, то запрос оказывается истинным и выводится найденное решение и сообщение о том, что решение найдено. Иначе запрос оказывается ложным и выдается сообщение «no».

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

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

Пользователю позволено выбирать ширину коридора, в котором будут выбираться точки для поиска оптимально пути (разрешено менять обозначения остановок, добавлять новые остановки, удалять остановки).

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

3.1 Описание пользовательских типов данных

Для хранения и передачи данных из предложения в предложение использовались именованные переменные.

Для хранения и передачи данных между частями запроса использовалась база данных.

1. остановка(X,Y,A1,B1,A2,B2)

Описывает дугу графа, соединяющую две точки с координатами.

Аргументы: X-Y - ветвь графа; A1, B1 - координаты точки X; A2, B2 - координаты точки Y.

2. смежные(X,Y,Р)

Проверяет соединены ли точки X и Y, попадает ли смежная точка в коридор и находит расстояние между ними с помощью выражения Р=sqrt((A2-A1)*(A2-A1)+(B2-B1)*(B2-B1))

3. расст(A,B).

Используется для подсчета расстояния между точкой и прямой, соединяющей начальную и конечную точку, включает в себя проверку на принадлежность коридору.

Аргументы: A, В - координаты точки,

4. путь(Нач,Кон,П,Р)

Используется для формирования начальных данных и отсечения промежуточных результатов.

Аргументы: Нач - начальная вершина, Кон - конечная вершина, П - ациклический путь из начальной вершины в конечную в графе. Р - длина пути.

5. путь1(X,Y,П0,П,Р0,Р)

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

Аргументы: X - текущая точка, Y - начальная точка, П0 - текущий путь, П - путь от начальной точки до конечной, Р0 - текущая длина пути, длина всего найденного пути П.

6. принадл(Y, П0)

Устанавливает принадлежность вершины Y списку П0. Служит ограничением на повторной прохождение ветви.

7. мин (Путь,Тек)

Сохраняет значения текущих минимального пути Путь и его длины Тек.

8. узнать(real,real,real,real) - определяет координаты начальной и конечной остановки для построения коридора.

9. направление(symbol, symbol) - сохраняет названия начальной и конечной остановок.

Для работы с внутренней базой правил используются следующие встроенные предикаты:

assert(the fact) - добавляет указанный в скобках предикат во внутреннюю базу фактов.

retract(the fact) - унифицирует факт и удаляет его из внутренней базы фактов.

10. abs(X).

Вычисляет модуль X.

11. sqrt(Х)

Вычисляет квадратный корень из числа Х.

Путь в графе отыскивается вызовом предиката путь1(Z,Y,[Z|П0],П,Р2,Р) при выполнении следующих условий:

1. not(мин(_,_)) - проверка есть ли во внутренней базе предикат мин(_,_).

2. смежные(X,Z,P1) - поиск смежных точек с данной.

3. not(принадл(Z,П0)) - найденная точка не должна присутствовать в текущем пути

4. маршрут(А,С) - конкретизация переменных значениям из маршрута

5. принадл(Х,С) - найденная точка должна принадлежать одному из маршрутов

6. Р2=Р0+Р1 - расстояние находится сложением длин пройденных ребер

Таким образом, при выполнении рекурсивного условия до него выполняются проверка на смежность и запрет на повторное прохождении ветвей. После - рекурсивное правило можно легко будет извлечь из правила, так как его значение будет четко известно после выполнения рекурсии.

Примеры использующихся в задаче логических моделей:

1. Факт. Обращение к факту.

Простейшим примеров факта является следующее выражение

остановка(a,b,6.0,5.0,4.0,5.0).

При обращении к этому факту идет конкретизация именованных переменных, например при сопоставлении остановка(X,Y,A1,B1,A2,B2) переменная Х примет значение а, переменная Y примет значение b, переменная A1 примет значение 6.0, и т.д.

В программе:

Правую часть правила0 сопоставляем с фактом1 (+)

Х V a (+)

(X,Y,A1,B1,A2,B2 ) V (a,b,6.0,5.0,4.0,5.0) (+)

2. Правило без рекурсии.

Между путь и путь1 имеется следующее соотношение:

путь(Нач,Кон,_,_):- путь1(Кон,Нач,[Кон],_,0.0,_), fail.

Здесь в путь заносится начальный узел Нач, конечный узел Кон. Встроенный предикат fail означает возвращение с неудачей, то есть после каждого выполнения первого условия путь1(Кон,Нач,[Кон],_,0.0,_) проверка второго условия дает ложь и компилятор ищет другой решение условия №1

Без предиката fail

3. Рекурсивное правило.

А) Без дополнительных условий

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

Аргументы: Y - вершина , Список

Принадлежность элемента вершина Списку.

1

Б) Дополнительное условие стоит до рекурсивного или после него

Например, поиск первого пути.

Приложение А

DOMAINS

sl=symbol*

FACTS

determ мин(sl,real)

determ направление(symbol, symbol)

PREDICATES

nondeterm остановка(symbol,symbol,real,real,real,real)

nondeterm смежные(symbol,symbol,real)

nondeterm узнать(real,real,real,real)

nondeterm путь(symbol,symbol,sl,real)

nondeterm путь1(symbol,symbol,sl,sl,real,real)

nondeterm принадл(symbol,sl)

nondeterm расст(real,real)

nondeterm маршрут(symbol,sl)

nondeterm старт

CLAUSES

%факты описывающие граф дорог (первая остановка,вторая остановка,коодинаты первой остановки,координаты второй остановки)

остановка(печеры,касьянова,91.0,47.0,91.0,46.5). остановка(касьянова,верхнепечерская,91.0,46.5,91.0,46.0). остановка(верхнепечерская,лопатина,91.0,46.0,90.0,45.0).

остановка(лопатина,казанское_шоссе,90.0,45.0,91.0,44.0).остановка(казанское_шоссе,родионова,91.0,44.0,91.0,41.0).остановка(родионова,сенная,91.0,41.0,84.0,37.0).

остановка(сенная,белинского,84.0,37.0,83.0,38.0).остановка(белинского,лядова,83.0,38.0,77.0,41.0).остановка(лядова,гагарина,77.0,41.0,76.0,48.0).

остановка(гагарина,акад_сахарова,76.0,48.0,72.0,62.0).остановка(акад_сахарова,щербинки,72.0,62.0,70.0,65.0).остановка(красное_сормово,ул_свободы,59.0,27.0,59.0,29.0).

остановка(ул_свободы,коминтерна,59.0,29.0,59.0,30.0).остановка(коминтерна,культуры,59.0,30.0,58.0,30.0).остановка(культуры,циолковского,58.0,30.0,55.0,31.0).

остановка(циолковского,мирошникова,55.0,31.0,55.0,35.0).остановка(мирошникова,чаадаева,55.0,35.0,55.5,35.0).остановка(чаадаева,ярошенко,55.5,35.0,58.0,35.0).

остановка(ярошенко,рябцева,58.0,35.0,59.0,39.0).остановка(рябцева,московское_шоссе,59.0,39.0,59.5,35.5).остановка(московское_шоссе,ул_советская,59.5,35.5,72.0,36.0).

остановка(ул_советская,пл_ленина,72.0,36.0,72.0,36.5).остановка(пл_ленина,нижневолжская_наб,72.0,36.5,76.0,36.0).остановка(нижневолжская_наб,широкая,76.0,36.0,78.0,35.0).

остановка(широкая,зеленский_съезд,78.0,35.0,79.0,36.5).остановка(зеленский_съезд,пл_минина,79.0,36.5,80.0,36.0).остановка(пл_минина,варварская,80.0,36.0,81.0,37.5).

остановка(варварская,пл_свободы,81.0,37.5,81.5,38.5).остановка(мещерское_оз,к_маркса,69.0,31.0,67.0,32.0). остановка(к_маркса,акимова,67.0,32.0,70.0,35.0).

остановка(акимова,мурашкинская,70.0,35.0,71.5,36.0).остановка(мурашкинская,должанская,71.5,36.0,72.0,36.0).остановка(должанская,ул_советская,72.0,35.5,72.0,35.0).

остановка(ул_советская,пл_революции,72.0,35.0,71.0,38.0).остановка(пл_революции,прокофьева,71.0,38.0,71.0,39.0).остановка(прокофьева,долгополова,71.0,39.0,70.5,40.0).

остановка(долгополова,июльских_дней,70.5,40.0,70.0,41.0).остановка(июльских_дней,прт_ленина,70.0,41.0,69.0,45.0).остановка(прт_ленина,комсомольское_шоссе,69.0,45.0,70.0,45.5).

остановка(комсомольское_шоссе,пл_комсомольская,70.0,45.5,71.0,44.0).остановка(пл_комсомольская,молитовская,71.0,44.0,72.0,45.0).остановка(молитовская,голубева,72.0,45.0,72.0,46.5).

остановка(голубева,вайгач,72.0,46.5,72.0,48.5).остановка(вайгач,баумана,72.0,48.5,71.5,50.0).остановка(баумана,попова,71.5,50.0,70.5,52.0).

остановка(попова,п_приокский,70.5,52.0,68.0,56.0).остановка(зкпд4,прт_кораблестроителей,48.0,25.0,50.0,26.5).остановка(прт_кораблестроителей,стрелковая,50.0,26.5,51.0,26.0).

остановка(стрелковая,баренца,51.0,26.0,51.5,24.5).остановка(баренца,новосельская,51.5,24.5,53.5,25.5).остановка(новосельская,сутырина,53.5,25.5,56.0,27.5).

остановка(сутырина,пер_союзный,56.0,27.5,58.0,26.5).остановка(пер_союзный,коминтерна,58.0,26.5,59.0,30.0).остановка(коминтерна,сормовское_шоссе,59.0,30.0,63.0,34.5).

остановка(сормовское_шоссе,куйбышева,63.0,34.5,66.0,36.0).остановка(куйбышева,акмолинская,66.0,36.0,67.0,34.0).остановка(акмолинская,акимова,67.0,34.0,70.0,35.0).

остановка(дружаева,львовская,60.0,52.5,61.5,51.5).остановка(львовская,прт_бусыгина,61.5,51.5,62.5,52.0).остановка(прт_бусыгина,дьяконова,62.5,52.0,62.0,53.0).

остановка(дьяконова,прт_октября,62.0,53.0,59.0,56.0).остановка(прт_октября,веденяпина,59.0,56.0,60.0,62.0).остановка(веденяпина,южное_шоссе,60.0,62.0,56.5,65.0).

остановка(южное_шоссе,гайдара,56.5,65.0,54.0,66.5).остановка(гайдара,ореховская,54.0,66.5,51.0,68.5).остановка(ореховская,безводная,51.0,68.5,49.5,69.0).

остановка(безводная,аэропорт,49.5,69.0,47.5,66.0).остановка(высоково,выс_проезд,85.5,41.0,84.5,40.0).остановка(выс_проезд,республиканская,84.5,40.0,83.5,40.0).

остановка(республиканская,полтавская,83.5,40.0,82.5,38.5).остановка(полтавская,белинского,82.5,38.5,83.0,38.0).остановка(сенная,ул_минина,84.0,37.0,81.0,36.5).

остановка(ул_минина,пл_минина,81.0,36.5,80.0,36.0).остановка(ул_советская,коммунистическая,72.0,36.0,72.0,38.0).остановка(коммунистическая,приокская,72.0,38.0,72.0,39.0).

остановка(приокская,интернациональная,72.0,39.0,72.0,40.0).остановка(интернациональная,июльских_дней,72.0,40.0,70.0,41.0).остановка(прт_ленина,самочкина,69.0,45.0,67.0,46.5).

остановка(самочкина,кировская,67.0,46.5,66.5,46.5).остановка(кировская,премудрова,66.5,46.5,66.0,45.5).остановка(премудрова,порт_артурская,66.0,45.5,66.0,44.0).

остановка(порт_артурская,дачный,66.0,44.0,66.0,43.0).остановка(кузнечиха,ивлева,87.0,48.5,87.5,47.0). остановка(ивлева,козицкого,87.5,47.0,87.0,46.5).

остановка(козицкого,шишкова,87.0,46.5,86.0,45.5).остановка(шишкова,богородского,86.0,45.5,85.0,45.0).остановка(богородского,пл_советская,85.0,45.0,84.0,44.5).

остановка(пл_советская,ванеева,84.0,44.5,83.0,42.0).остановка(ванеева,пл_свободы,83.0,42.0,81.5,38.5). остановка(прт_ленина,веденяпина,72.0,36.0,60.0,62.0).

остановка(прт_гагарина,артельная,76.0,48.0,77.5,44.0).остановка(артельная,сады,77.5,44.0,81.0,43.5).остановка(усилова,сенная,87.5,39.0,84.0,37.0).

остановка(прт_гагарина,бекетова,76.0,48.0,80.5,45.5).остановка(бекетова,нартова,80.5,45.5,78.5,46.5).остановка(нартова,медицинская,78.5,46.5,78.5,48.0).

остановка(медицинская,игнатовых,78.5,48.0,78.5,49.0).остановка(игнатовых,горбатовская,78.5,49.0,79.5,50.5). остановка(горбатовская,щелоковский_хутор,79.5,50.5,81.0,51.0).

остановка(пл_горького,покровская,78.0,39.50,77.5,40.5).остановка(покровская,лядова,77.5,40.5,77.0,41.0).остановка(гагарина,кемеровская,76.0,48.0,75.0,58.5).

остановка(кемеровская,кащенко,75.0,58.5,77.0,57.5).остановка(кащенко,шапошникова,77.0,57.5,79.5,58.0). остановка(шапошникова,керамик,79.5,58.0,80.5,59.0).

остановка(веденяпина,лескова,60.0,62.0,59.0,60.5).остановка(лескова,коломенская,59.0,60.5,55.0,63.0).остановка(коломенская,мончегорская,55.0,63.0,54.0,62.0).

остановка(мончегорская,космическая,54.0,62.0,61.5,62.0).остановка(пл_советская,бекетова,84.0,44.5,80.5,45.5). остановка(нартова,гагарина,78.5,46.5,76.0,48.0).

остановка(гагарина,ларина,76.0,48.0,75.0,59.0).остановка(ларина,полевая,75.0,59.0,78.5,60.0).остановка(полевая,ближнеконстантиново,78.5,60.0,79.5,61.5).

остановка(прт_кораблестроителей,октября_70_лет,48.0,25.0,51.5,27.0).остановка(октября_70_лет,светлоярская,51.5,27.0,53.5,28.5).остановка(светлоярская,кузьмина,53.5,28.5,54.0,30.0).

остановка(кузьмина,циолковского,54.0,30.0,55.0,31.0).остановка(московское_шоссе,лесной_городок,59.5,35.5,54.5,40.0). остановка(лесной_городок,ухтомского,54.5,40.0,55.5,42.5).

остановка(ухтомского,электровозная,55.5,42.5,56.5,45.0).остановка(электровозная,движенцев,56.5,45.0,56.0,46.5).остановка(движенцев,гороховецкая,56.0,46.5,58.0,46.0).

остановка(гороховецкая,сортировочный,58.0,46.0,60.0,45.0).остановка(прт_кораблестроителей,ул_свободы,50.0,26.5,59.0,29.0). остановка(коминтерна,страж_революции,59.0,30.0,61.0,35.0).

остановка(страж_революции,прт_героев,61.0,35.0,62.0,38.0).остановка(прт_героев,комсомольское_шоссе,61.0,35.0,70.0,45.5).остановка(пл_комсомольская,окский_съезд,71.0,44.0,76.0,42.0).

остановка(окский_съезд,пл_лядова,76.0,42.0,77.0,41.0).остановка(прт_ленина,прт_ильича,69.0,45.0,58.5,58.5).остановка(прт_ильича,красноуральская,58.5,58.5,53.0,58.0).

остановка(красноуральская,прт_молодежный,53.0,58.0,51.5,58.5).остановка(прт_молодежный,петряевка,51.5,58.5,49.5,57.5). остановка(ванеева,сусловой,83.0,42.0,84.5,43.0).

остановка(сусловой,бринского,84.5,43.0,90.0,44.0).остановка(бринского,казанское_шоссе,90.0,44.0,91.0,44.0).остановка(нартова,корейская,78.5,46.5,78.0,51.0).

остановка(корейская,анкудиновское_шоссе,78.0,51.0,79.5,54.0).остановка(анкудиновское_шоссе,полярная,79.5,54.0,79.0,55.0). остановка(полярная,шатковская,79.0,55.0,78.0,54.5).

остановка(шатковская,октября_40_лет,78.0,54.5,76.5,54.5).остановка(октября_40_лет,гагарина,76.5,54.5,76.0,48.0). остановка(прт_ленина,грекова,69.0,45.0,68.0,54.0).

остановка(грекова,акад_сахарова,68.0,54.0,72.0,62.0).остановка(соцгород2,сов_армии,57.5,55.0,55.5,54.5).остановка(сов_армии,раевского,55.5,54.5,59.0,54.5).

остановка(раевского,дьяконова,59.0,54.5,62.0,53.0).остановка(прт_бусыгина,грекова,62.5,52.0,68.0,54.0). остановка(грекова,ларина,68.0,54.0,75.0,59.0).

%150 фактов

%Факты описывающие маршруты движения автобусов (имя маршрута автобуса, список остановок автобуса)

маршрут(a2,[печеры,касьянова,верхнепечерская,лопатина,казанское_шоссе,родионова,сенная,белинского,лядова,гагарина,акад_сахарова,щербинки]).

маршрут(a3,[красное_сормово,ул_свободы,коминтерна,культуры,циолковского,мирошникова,чаадаева,ярошенко,рябцева,московское_шоссе,ул_советская,пл_ленина,нижневолжская_наб,широкая,зеленский_съезд,пл_минина,варварская,пл_свободы]).

маршрут(a11,[дружаева,львовская,прт_бусыгина,дьяконова,прт_октября,веденяпина,южное_шоссе,гайдара,ореховская,безводная,аэропорт]).

маршрут(a20,[кузнечиха,ивлева,козицкого,шишкова,богородского,пл_советская,ванеева,пл_свободы,варварская,пл_минина,зеленский_съезд,нижневолжская_наб,пл_ленина,ул_советская,пл_революции,прокофьева,долгополова,июльских_дней,прт_ленина,веденяпина,южное_шоссе,гайдара,ореховская,безводная,аэропорт]).

маршрут(a27,[сенная,белинского,лядова,гагарина,артельная,сады]).

маршрут(a45,[зкпд4,прт_кораблестроителей,октября_70_лет,светлоярская,кузьмина,циолковского,мирошникова,чаадаева,ярошенко,рябцева,московское_шоссе,ул_советская,пл_ленина,нижневолжская_наб,широкая,зеленский_съезд,пл_минина,ул_минина,сенная,родионова,казанское_шоссе,лопатина,верхнепечерская,касьянова,печеры]).

маршрут(a66,[мещерское_оз,к_маркса,акимова,мурашкинская,должанская,ул_советская,пл_революции,прокофьева,долгополова,июльских_дней,прт_ленина,грекова,акад_сахарова,щербинки]).

% +7 фактов

%Правило определяет принадлежность ребра графу дорог, при определении проверяет принадлежность остановок

%P конкретизируется расстоянием между остановками

смежные(Х,У,Р):- остановка(Х,У,A1,B1,A2,B2), расст(A2,B2),Р=sqrt((A2-A1)*(A2-A1)+(B2-B1)*(B2-B1));

остановка(У,Х,A1,B1,A2,B2), расст(A1,B1),Р=sqrt((A2-A1)*(A2-A1)+(B2-B1)*(B2-B1)). %правило №1

%Проверяет попадание точки внутрь коридора.

%Ширина коридора 20. Длина 1.2*otr.

расст(A,B):-узнать(Н,Ч,Н1,Ч1),Коридор=abs((Ч1*A-Н1*B+Ч*Н1-Н*Ч1)/sqrt(Н1*Н1+Ч1*Ч1)),Коридор<2,

N=sqrt((A-Н)*(A-Н)+(B-Ч)*(B-Ч)),N<1.2*(sqrt(Н1*Н1+Ч1*Ч1)). %правило №2

%Правило проверяет принадлежность элемента списку

принадл(X,[X|_]):- !. %правило №3

принадл(X,[_|T]):- принадл(X,T). %правило №4

%Для поиска оптимального маршрута

путь(Нач,Кон,_,_):- путь1(Кон,Нач,[Кон],_,0.0,_),fail. %правило №5

путь(_,_,П,Р):- мин(П,Р).

%направление(Нач,Кон):-assert(напр(Нач,Кон)). %правило №6

узнать(Н,Ч,Н1,Ч1):-направление(Нач,Кон),

остановка(Нач,_,Н,Ч,_,_),

остановка(_,Кон,_,_,Н1,Ч1);

направление(Нач,Кон),

остановка(_,Нач,_,_,Н,Ч),

остановка(_,Кон,_,_,Н1,Ч1);

направление(Нач,Кон),

остановка(Нач,_,Н,Ч,_,_),

остановка(Кон,_,Н1,Ч1,_,_);

направление(Нач,Кон),

остановка(_,Нач,_,_,Н,Ч),

остановка(Кон,_,Н1,Ч1,_,_).

путь1(X,Y,П0,П,Р0,Р):- мин(_,Тек),смежные(X,Z,Р1),

Р2=Р0+Р1,Р2<=Тек,

not(принадл(Z,П0)),

маршрут(Ц,Ъ),

принадл(X,Ъ),

принадл(Z,Ъ),

путь1(Z,Y,[Ц,Z|П0],П,Р2,Р). %правило №7

путь1(X,Y,П0,П,Р0,Р):- not(мин(_,_)),смежные(X,Z,Р1),

not(принадл(Z,П0)),Р2=Р0+Р1,

маршрут(Ц,Ъ),

принадл(X,Ъ),

принадл(Z,Ъ),

путь1(Z,Y,[Ц,Z|П0],П,Р2,Р). %правило №8

путь1(Y,Y,П,П,Р,Р):- мин(Путь,Тек),Р<Тек,

retract(мин(Путь,Тек)),

assert(мин(П,Р));

not(мин(_,_)),assert(мин(П,Р)). %правило №9

%Обеспечивает работу пользователя с консолью

старт:- write("Поиск оптимального автобусного маршрута"), nl,

write("Для выхода нажмите Esc"), nl,

write("--------------------------------------------------------------------"), nl,

write("Введите начальную остановку -> "), readln(Нач_ост),

write("Введите конечную остановку -> "), readln(Кон_ост),nl,

assert(направление(Нач_ост,Кон_ост)),

путь(Нач_ост,Кон_ост,Путь,Расстояние),

Время=Расстояние,

write("Путь займет:",Время,"минут"), nl,

write(Путь), nl. %правило №10

GOAL

старт.

Список используемой литературы

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

2. Стерлинг Л, Шапиро Э. «Искусство программирования на языке Пролог» : Пер. с англ. Сопрунова С.Ф. Под ред. Соболева В.Н.Г. - М.: Мир,1990. -324 с.: ил

3. У. Клоксин, К. Меллишь «Программирование на языке Пролог»

4. Материалы с сайта www.transp.nnov.ru