Выбор оптимального маршрута авиаперелета с учетом расписания и времени перелета

Размещено на http://www.allbest.ru/

Содержание

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

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

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

1.3 Требования к функциональным характеристикам программы и алгоритму решения задачи

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

2.1 Минимальные требования к составу и параметрам технических средств, к информационной и программной совместимости

2.2Описание интерфейса. Шаблоны входных данных и результата

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

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

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

3.3 Разработка логических моделей и блок-схем типовых фрагментов программы

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

Список использованных источников

Приложение

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

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

Основанием для разработки стало задание на курсовой проект по дисциплине: «Представление знаний в информационных системах» по направлению «Логическое программирование на языке Visual Prolog».

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

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

Основная задача моделирования в данной программе - выбор оптимального маршрута авиаперелета с учетом расписания и времени перелета. В качестве математической модели выбран неориентированный граф (см.Приложение Б), вершины которого - города, а ребрам присвоены значения времени перелета (переход по ребру из одной вершины в другую возможен, как в прямом, так и в обратном направлении, вершины доступны в зависимости от расписания). Размерность задачи: для демонстрации работы алгоритма количество узлов взято равным 16, а связей между ними - 22, но для получения практической ценности, эти числа могут быть увеличены в десятки раз. Потенциально, эту программу можно, например, разместить на сайте авиакомпании, чтобы интернет-пользователи могли узнать маршрут оптимального перелета в нужные им точки.

Введем набор понятий, которыми будем оперировать:

1. Список - список символов (не является стандартным доменом Visual Prolog).

2. Откуда - города, от которого начинается движение.

3. Куда - города, которым заканчивается перелет.

4. Время - время перелета.

5. День - допускает вылет из города.

6. Расписание - набор дней.

7. Номер - число типа integer, указывающее желаемое число перелетов

8. Часть_пути - список, часть от общего пути, хранящая в себе перелеты, начиная с начального города, которые уже найдены, но не дошедшие до конечного результата (конечного города).

9. Путь - список всех переездов от первого города до конечного

10. Общее_время - суммарное время перелета между всеми городами из списка пути.

11. МинВремя - время перелета по городам, образующим минимальный путь.

12. Перелет (symbol, symbol, real, список) - определяет понятие «перелета» в данной задаче, включает в себя (слева направо): город вылета, город прилета, время перелета, расписание.

13. Принадлежит (symbol, список) определяет принадлежность элемента списку.

14. Смежные (symbol, symbol, real, symbol) - включает в себя (слева направо): город вылета, город прилета, время перелета, день. Определяет наличие ветви, ведущей из города вылета или в город вылета.

15. Путь (symbol, список, список, real, symbol, integer) - включает в себя (слева направо): город вылета, город прилета, путь, время, день, номер. Прокладывает маршрут из начального города в конечный.

16. Самый_быстрый_путь (symbol, symbol, real, symbol, integer) - включает в себя (слева направо): город вылета, город прилета, время, день,номер. Ищет маршрут с минимальным временем перелета.

17. Оптимальный_путь (symbol, symbol, список, real, symbol, integer) - включает в себя (слева направо): город вылета, город прилета, путь, время, день,номер. Прокладывает маршрут и выбирает из возможных оптимальный.

1.3 Требования к функциональным характеристикам программы и алгоритму решения задачи

Программа должна обеспечить:

· работу в режиме тестирования для представления возможностей программы;

· ввод данных пользователем;

· выбор оптимальных маршрутов перелетов с учетом расписания и времени перелета;

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

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

2.1 Минимальные требования к составу и параметрам технических средств, к информационной и программной совместимости

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

· IBM - совместимый персональный компьютер класса 486/66 или выше (желательно Pentium II или выше)

· Видеоадаптер SVGA , поддерживающий разрешение не менее 800x600 пикселей, для повышения качества изображения

Минимальные требования к внешним устройствам:

· Монитор с эффективным разрешением экрана 640480 или выше

· Клавиатура

· Мышь

Требования к информационной и программной совместимости:

· Операционная система MSWindows 95 и выше

· Поддержка операционной системой кириллицы

Для создания программы необходимо наличие Visual Prolog 5.2 Personal Edition.

Минимальные требования к выполнению программы:

· 16 МБ оперативной памяти (рекомендуется 32МБ)

2.2 Описание интерфейса. Шаблоны входных данных и результата

Открыв программу «Перелет.pro», нужно ввести запрос на поиск оптимального пути. Программа выдаст результат в виде набора городов и суммарное время перелетов между ними. Если она не нашла оптимального маршрута, то выводится ответ no Solution.

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

· Начальный город

· Конечный город

· День недели

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

· Последовательность городов (в виде списка), включающую в себя начальный город, конечный, промежуточные города (пересадки)

· Общее время перелета

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

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

авиаперелет время маршрут программа

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

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

1. Алгоритм полного перебора: производится поиск всех путей, с учетом критерия, а затем в найденных путях отбирается самый короткий. Длина пути складывается из длин каждой ветви.

2. Алгоритм поиска по «коридору»: Узлам графа присваиваются координаты. При поиске маршрута от начального пункта к конечному, создается сначала «коридор» - диапазон значений по оси Х и диапазон значений по оси Y, затем в пределах коридора прокладываются маршруты и перебором из них выбирается оптимальный.

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

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

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

Размещено на http://www.allbest.ru/

Рисунок 1

3.3 Разработка логических моделей и блок-схем типовых фрагментов программы

Факт:

перелет (рим,мадрид,2.00,[вторник,среда,четверг,суббота,воскресение])

% из рима в мадрид можно лететь во вт,ср,чт,сб и вск, потратив при этом 2 часа

Пример

GOAL

перелет (рим,мадрид,2.00,[вторник,среда,четверг,суббота,воскресение])

% истинно ли из рима в мадрид можно лететь во вт,ср,чт,сб и вск, потратив при этом 2?

%Решение:

%yes

Блок - схема фрагмента программы с применением факта перелет()

Размещено на http://www.allbest.ru/

Рисунок 2

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

путь(Откуда,[Откуда|Часть_пути],Часть_пути,0,_,0).

путь(Откуда,[Куда|Часть_пути],Путь,Общее_время,День,Номер):

Номер>0,Номер-1=Номер1,

перелет (След,Куда,Время1,Расписание),

not(принадлежит(След,Часть_пути)),

принадлежит (День,Расписание),

путь(Откуда,[След,След,Куда|Часть_пути],Путь,Время2,День,Номер1),

Общее_время=Время1+Время2.

Нахождение пути перелета основано на рекурсии.

Если начальный город совпадает с конечным, то путь - это начальный город, время равно нулю, число перелетов равно нулю, выводится путь и время перелета. Если конечный город не совпадает с начальным, то ищем следующий город, в который можно прилететь из текущего в заданный день. Затем проверяется, принадлежит ли найденный город частичному пути. Если принадлежит, то ищется другой, в который возможен перелет в заданный день. Если найденный город не принадлежит частичному пути, то записываем его в частичный путь. Все эти шаги выполняются снова для новых значений городов пока номер возможных перелетов не станет равным нулю. Когда путь найден, то при рекурсивном возвращении считается общее время перелета между всеми городами, входящих в путь. Искомый путь будет найден тогда, когда текущий город совпадает с конечным и счетчик перелетов равен 0.

Пример

GOAL

путь (берлин,[мадрид],Путь,Время,пятница,2).

%Решение

% путь (берлин,[мадрид],Путь,Время,пятница,2).

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

Выбираем город вылета и город прилета из представленных в приложении Б, выбираем день недели и число перелетов, заносим в запрос оптимальный_путь.

Например:

GOAL

оптимальный_путь(москва,берлин,Путь,Время,понедельник,3).

Результат:

Рисунок 4

Список использованных источников

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

2. Малпас Дж. Реляционный язык Prolog и его применение. - М.: Наука, 1990.

Приложение

Domains

список=symbol*

PREDICATES

nondeterm перелет (symbol,symbol,real,список)

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

nondeterm путь (symbol,список,список,real,symbol, integer)

nondeterm оптимальный_путь(symbol,symbol,список,real,symbol, integer)

nondeterm самый_быстрый_путь(symbol,symbol,real,symbol, integer)

nondeterm тестовый_пример

CLAUSES

/* СПИСОК ПЕРЕЛЕТОВ */

перелет (москва,минск,1.10,[понедельник,вторник,четверг,пятница,суббота]).

перелет (минск,киев,0.50,[вторник,среда,четверг,суббота,воскресение]).

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

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

перелет (будапешт,рига,1.00,[вторник,среда,пятница,суббота]).

перелет (будапешт,берлин,1.30,[понедельник,пятница,суббота,воскресение]).

перелет (будапешт,белград,0.30,[вторник,среда,четверг,пятница,воскресение]).

перелет (рига,берлин,2.30,[вторник,среда,четверг,пятница,суббота]).

перелет (рига,хельсинки,2.00,[среда,четверг,пятница,суббота,воскресение]).

перелет (хельсинки,осло,1.00,[вторник,среда,четверг,суббота,воскресение]).

перелет (хельсинки,берлин,2.30,[вторник,среда,четверг,пятница,воскресение]).

перелет (берлин,осло,2.45,[понедельник,среда,четверг,суббота,воскресение]).

перелет (берлин,белград,2.15,[вторник,среда,четверг,пятница,суббота,воскресение]).

перелет (берлин,мадрид,3.15,[пятница,суббота,воскресение]).

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

перелет (белград,прага,0.40,[понедельник,вторник,среда,четверг,пятница,суббота,воскресение]).

перелет (белград,софия,0.30,[понедельник,вторник,среда,четверг,суббота]).

перелет (прага,рим,1.40,[вторник,среда,четверг,пятница,суббота]).

перелет (софия,афины,0.30,[вторник,среда,четверг,суббота,воскресение]).

перелет (афины,рим,2.05,[понедельник,среда,четверг,пятница,воскресение]).

перелет (рим,мадрид,2.00,[вторник,среда,четверг,суббота,воскресение]).

перелет (мадрид,лондон,2.20,[понедельник,вторник,среда,четверг,пятница,суббота,воскресение]).

/* ПРИНАДЛЕЖНОСТЬ ЭЛЕМЕНТА СПИСКУ */

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

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

/* НАХОЖДЕНИЕ ПУТИ ОТ НАЧ К КОН */

путь(Откуда,[Откуда|Часть_пути],Часть_пути,0,_,0).

путь(Откуда,[Куда|Часть_пути],Путь,Общее_время,День,Номер):

Номер>0,Номер-1=Номер1,

перелет (След,Куда,Время1,Расписание),

not(принадлежит(След,Часть_пути)),

принадлежит (День,Расписание),

путь(Откуда,[След,След,Куда|Часть_пути],Путь,Время2,День,Номер1),

Общее_время=Время1+Время2.

самый_быстрый_путь(Откуда,Куда,МинВремя,День,Номер):-путь(Откуда,[Куда],_,Общее_время,День,Номер),

Общее_время < МинВремя.

/*ОПТИМАЛЬНЫЙ ПУТЬ */

оптимальный_путь(Откуда,Куда,Путь,Общее_время,День,Номер):

путь(Откуда,[Куда],Путь,Общее_время,День,Номер),

not(самый_быстрый_путь(Откуда,Куда,Общее_время,День,Номер)).

/*ПОСМОТРЕТЬ ТЕСТОВЫЙ ПРИМЕР */

тестовый_пример:-

write("Здравствуйте!\n Это программа рассчета оптимального маршрута авиапрелета\n Чтобы программа проложила маршрут,нужно ввести нач данные\nВылет из\nПрилет в\nДень недели (от 1 до 7)\nЧисло перелетов (>0)\nХотите посмотреть тестовый пример (да-1,нет-2)?: "), readint(Ответ),Ответ=1,

write("\nПунк вылета: москва\n"),

write("\nПунк прилета: берлин\n"),

write("\nДень недели: пятница\n"),

write("\nЧисло перелетов: 4 \n"),

оптимальный_путь (москва,берлин,Путь,Время_перелета,пятница,4),

write("\nОптимальный путь:\n"),

write(Путь),nl,write("\nВремя перелета: "),

write(Время_перелета),nl.

GOAL

%тестовый_пример.

оптимальный_путь(москва,берлин,Путь,Время,понедельник,3).

Размещено на Allbest.ru