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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Было получено задание, написать программу на языке программирования Visual Prolog, который был дан в качестве исходных данных. Программа на тему “Маршрутизация", а именно, поиск оптимального пути на маршрутном такси в Нижнем Новгороде. Назначение разработки - это изучение языка программирования Prolog. Эта программа должна быть полезной для навигации по нашему городу.

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

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

КР-НГТУ-071900-(03-КТ-1)-12-05

Набор понятий:

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

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

принадлежит и принадлежит_симв - предикаты определяют принадлежность элемента списку, только в первом предикате список целочисленный, а во втором - строковый.

принадлежит (элемент, список).

min, max - возвращают соответственно минимальное и максимальное значения из двух.

min (первое, второе, минимальное).

max (первое, второе, максимальное).

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

коридор (остановка1, остановка2, списокХ, списокУ).

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

добавить_в_дипазон (минимальное, максимальное, список).

мин_сумма1, мин_сумма2 - в совокупности определяют минимальный элемент в списке.

мин_сумма (минимальный, список).

путь - в общем-то, этот предикат самый основной. С помощью него происходит отыскание пути от остановки1 до остановки2 и суммы времени, которое необходимо затратить на преодоление данного пути.

список - список остановок. путь - список остановок и номеров маршрутных таски.

start -предикат, запускающий программу. Ему пользователь передаёт два значения (две остановки), а он возвращает путь и время. В ответе путь как переменная будет содержать не только остановки, но и маршрутные такси (их номера).

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

В качестве математической модели я выбрал ненаправленный граф, у которого 19 вершин и 29 дуг. Где вершины графа - это остановки, а ветви - участки маршрутки, которые она может проехать не останавливаясь. Аббревиатура, например, м4-10 означает, номер маршрутного такси “4", время прохождения между вершинами десять минут. Как было сказано раньше полный перебор здесь не подходит, поэтому я определил понятие “коридор", который определяет диапазон дуг. (Суть “коридора" описывается ниже в алгоритмах). Граф, конечно, может и не только неориентированным, но и смешанным, т.е. маршрутка может проезжать по ветви только в одном направлении, а возвращаться по иной ветви. Мой граф имеет циклы, смежные вершины, а не только перекрёстки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10Kb свободного пространства на HDD (для исходника)

15Mb RAM

Монитор

Клавиатура

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

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

Visual Prolog 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

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

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

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

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

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