1. Анализ исходных данных и разработка ТЗ
2. Руководство пользователя
2.1.1 Минимальные требования к составу и параметрам технических средств IBM совместимый персональный компьютер с CPU, начиная с 486 и выше
Было получено задание, написать программу на языке программирования VisualProlog, который был дан в качестве исходных данных. Программа на тему “Маршрутизация", а именно, поиск оптимального пути на маршрутном такси в Нижнем Новгороде. Назначение разработки - это изучение языка программирования Prolog. Эта программа должна быть полезной для навигации по нашему городу.
Суть моей задачи заключается в отыскании оптимального пути от одной остановки до другой по Нижнему Новгороду на маршрутном такси. Исходя из того, что маршрутов в городе порядка пятидесяти, а остановки, я думаю что, исчисляются сотнями, то размерность задачи можно считать средней. При решении полным перебором, может возникнуть проблема, а именно, время отыскания пути может занять неопределённое время. Поэтому полный перебор здесь не подойдёт. Далее я выбрал геометрическую интерпретацию.
Набор понятий:
участок - определяет параметры ветки, в которые входит: начальная остановка, координаты её, следующая остановка, координаты её, номер маршрутного такси, на котором можно добраться от этих остановок, а также время прохождения.
участок (остановка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. Суть алгоритма, который мне пришёл на ум первым заключается в следующем: сначала поиск производится всех путей, а за тем в найденных путях по критерию наименьшей стоимости отбирается самый дешёвый. Стоимость складывается из цен каждой ветви. В таком алгоритме есть большой минус. Если граф будет состоять из большого числа ветвей, а в моём случае предполагается что город большой, значит и граф должен быть гутой, то поиск необходимого пути может занять неопределённое количество времени и в некоторых случаях персональный компьютер может просто зависнуть. Я считаю, что этот алгоритм оптимален сточки зрения результата. Потому что по этому алгоритму проверяются всевозможные пути. Но в таком случае он не оптимален с точки зрения процедуры поиска самого пути.
Значит, поиск оптимального пути должен производится не по всевозможным путям, а по путям, которые входят в некоторое подмножество. Отсюда следует следующий алгоритм.
2. По данному алгоритму вся карта делится на квадраты:
Каждый квадрат имеет пару координат. А в каждый квадрат могут попадать остановки, которые будут иметь координаты. В таком случае можно попробовать построить “коридор” от начальной остановки до конечной остановки. Этот “коридор” будет состоять из пары диапазонов: по вертикали и горизонтали. Диапазоны будут определяться из введённых пользователем данных: начальной и конечной остановок, которые в свою очередь имеют координаты. Теперь в полученном “коридоре" будет производиться поиск оптимального пути по предыдущему алгоритму. Недостаток этого алгоритма заключается в следующем: “коридор", который мы сформировали, может не иметь ветвей, и в таком случае решения мы не получим. Поэтому не стоит делать коридор узким. Наверное, стоит его сделать искусственно шире, т.е. расширить диапазоны. Конечно вероятность получить ответ увеличивается, но остается вероятность также не получить оптимального результата или не получить ответа вообще. Достоинство этого алгоритма перед предыдущим заключается в том, что поиск производится по ограниченному “коридором” - числу ветвей. Он оптимален с точки зрения процедуры поиска пути. В отличие от первого алгоритма мы можем, получит здесь путь по стоимости дороже, так как перебор ветвей ограничен.
3. Еще один алгоритм. Сохраним систему координат и понятие из предыдущего алгоритма. Будем двигаться от начальной остановки к конечной остановке, выбирая ветвь наименьшей цены. Этот алгоритм ещё называется градиентным. В таком алгоритме есть недостаток: полученный путь может получиться далеко не оптимальным.
4. Модифицируя предыдущий алгоритм: поиск пути от конечной остановки к начальной остановке. То есть берётся конечная остановка и ищется ветвь, примыкающая к ней с наименьшей ценой.
5. Сохраняем стратегию второго алгоритма и добавляем ограничение на прохождение по ветви в обратном направлении. Тем самым мы отбрасываем не нужные нам решения.
Для решения поставленной задачи я выбрал пятый алгоритм. Я считаю, что этот алгоритм в своём функционале имеет “золотую середину". Так как процедура поиска пути получается не очень объёмная, потому что ограничено количество ветвей “коридором", и происходит выбор пути из некоторого подмножества, а не сразу по некоторой эвристике. Объём этого подмножества, конечно, зависит не от объёма базы данных, а от того, на сколько удалены начальная и конечная остановки.
Программа должна выполнять следующие функции:
Ввод исходных данных
Решение задачи - нахождение оптимального пути
Вывод найденного решения
Программа предназначена для поиска оптимального пути в Нижнем Новгороде на маршрутном такси. Или поиск пути в графе, где вершины графа - это остановки, а ветви - участки пути маршрутного такси. С помощью этой программы можно отыскать путь за минимальное время проезда от одной остановки до заданной. Результатом программы является список остановок и номеров маршрутных такси, которые расположены между остановками, и сумма времени. Из списка будет видно, что делать пользователю, а именно, пересаживаться на другое маршрутное такси или ехать дальше.
10Kb свободного пространства на HDD (для исходника)
