Содержание

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

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

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

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

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

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

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

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

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

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

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

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

3.1 Логические модели. Блок-схемы алгоритмов

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

Использованные источники

Приложение

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

 

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

 

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

•        закрепить и углубить теоретические знания и практические навыки, связанные с программированием в среде Visual Prolog Personal Edition 5.2;

•        получить навыки в составлении текстовой конструкторской документации в соответствии с существующими стандартами.

 

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

 

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

1.Начальная станция – заданная вершина графа;

2.Конечная станция – одна из вершин графа;

3.Промежуточная станция – одна из вершин графа;

4.Кольцевая линия – замкнутая линия метро;

5.Пересадка – вершина графа из которой выходят более двух ребер;

6.Линия метро–ребро графа.

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

 

Существуют следующие алгоритмы нахождения пути в неориентированном графе:

А)Полный нециклический перебор:

Алгоритмом нахождения пути в данной курсовой работе является метод полного нециклического перебора.

Маршрут S(l0, l1, l2,…, ln) имеет не определенное число вершин. Каждый элемент liV, где V множество вершин графа. Множество кандидатов в li т.е. Si есть множество вершин соединенных ребрами с вершиной li-1. Было бы не целесообразно искать путь из одной точки в другую, как маршрут возможно содержащий циклы. Кроме практической непригодности данного решения, возникает проблема не ограниченности числа вершин в маршруте. Поэтому, для исключения циклов, на кандидатов в li вводится дополнительное ограничение: li. l1, li. l2,…, li. li-1 т.е. ни одна вершина не должна встречаться в маршруте более одного раза.

Описанный выше алгоритм нахождения пути наиболее прост в реализации на языке Prolog, так как он наиболее близок к процедуре доказательства истинности целей, которая осуществляется путем полного перебора по базе фактов и правил. (см. Математические модели информационных процессов и управления)

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

Б) Последовательный перебор(Метод полного перебора):

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