Курсовая работа: Поиск оптимального пути в графе
Содержание
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 Основание и назначение разработки
Было получено задание, написать программу на языке программирования VisualProlog, который был дан в качестве исходных данных. Программа на тему “Маршрутизация", а именно, поиск оптимального пути на маршрутном такси в Нижнем Новгороде. Назначение разработки - это изучение языка программирования Prolog. Эта программа должна быть полезной для навигации по нашему городу.
1.2 Постановка задачи в предметной области, разработка математической модели
Суть моей задачи заключается в отыскании оптимального пути от одной остановки до другой по Нижнему Новгороду на маршрутном такси. Исходя из того, что маршрутов в городе порядка пятидесяти, а остановки, я думаю что, исчисляются сотнями, то размерность задачи можно считать средней. При решении полным перебором, может возникнуть проблема, а именно, время отыскания пути может занять неопределённое время. Поэтому полный перебор здесь не подойдёт. Далее я выбрал геометрическую интерпретацию.
|
Набор понятий:
участок - определяет параметры ветки, в которые входит: начальная остановка, координаты её, следующая остановка, координаты её, номер маршрутного такси, на котором можно добраться от этих остановок, а также время прохождения.
участок (остановка1, х1, у1, остановка2, х2, у2, маршрутка, время).
принадлежит и принадлежит_симв - предикаты определяют принадлежность элемента списку, только в первом предикате список целочисленный, а во втором - строковый.
принадлежит (элемент, список).
min, max - возвращают соответственно минимальное и максимальное значения из двух.
min (первое, второе, минимальное).
max (первое, второе, максимальное).
коридор - принимает две остановки как входные данные и заполняет два списка, один по горизонтали (Х), а другой по вертикали (У). Эти два списка будут определять диапазон ветвей, которые будут участвовать в решении, а остальные просто-напросто отбрасываться, опираясь на то, что они все равно не дадут оптимального решения.
коридор (остановка1, остановка2, списокХ, списокУ).
добавить_в_диапазон - это предикат непосредственно заполняет список из целых цифр, лежащих в диапазоне от минимального до максимального значений с шагом равным единице.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--