Математические модели

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), конечной, но неопределенной длины, удовлетворяющего определенным ограничениям. Каждое аi? Ai, где Ai конечное упорядоченное множество. В качестве исходного частичного решения примем пустой вектор () и на основе имеющихся ограничений выясним, какие элементы из А1 являются кандидатами в а1. Обозначим это подмножество кандидатов через

S1?A1. В результате имеем частичное решение (a1). В общем случае для расширения частичного решения (a1,a2,…, ak-1) до (a1,a2,…, ak-1, ak) кандидаты на роль аk выбираются из Sk? Ak. Если частичное решение (a1, a2,…, ak-1) не позволяет выбрать аk то Sk =?;

возвращаемся и выбираем новый элемент ak-1.

В) Перебор на основе заданного количества элементов в комбинациях.

Аналогично полному перебору, только с ограничениями по количеству элементов.

Рассомтренную задачу можно решить с помощью двух алгоритмов:

1)Найти все возможные пути маршрута, составить список из количесва остановок и в этом списке выбрать минимальное значение;

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

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

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

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

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

Программа позволяет найти маршрут между двумя станциями в метро с проездом через заданные станции. При этом выбирается маршрут с минимальным числом остановок.

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

Минимальные требования программы к составу и параметрам технических средств в основном определяются требованиями операционной системы, а так как для работы программы необходима ОС Windows 95(или выше), то предъявляются следующие минимальные требования:

* Процессор 486/66;

* 16Мб оперативной памяти;

* Видеоадаптер SVGA;

* SVGA монитор;

* Дисковое пространство не менее 10 MB.

Мышь, клавиатура.

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

* На компьютере должна быть установлена операционная система Windows 95/ NT 4.0 или более поздняя версия;

* Для запуска программы на языке Prolog необходим Visual Prolog v. 5.2 Personal Edition или выше.

* Система должна поддерживать национальные шрифты (кириллицу).

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

Рис. 1

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

Открываем Visual Prolog в самой программе находим закладку «Open», через неё раскрываем файл маршрут.pro

После запуска маршрут.pro появится окно с вопросом:

`Введите начальную станцию =a'

Указываете начальный пункт (например, «a»). Нажимаете «Enter»

` Введите конечную станцию = g'

Указываете конечный пункт назначения («g»). Нажимаете «Enter»

`Сколько вы хотите ввести количество промежуточных станций=2'

Указываете промежуточные станции с и j. Нажимаете «Enter»

После обработки входных данных появится

`Путь: [" a" ," s" ," n" ," c" ," j" ," f" ," g" ]

Число остановок: 7

yes'

«Путь» показывает оптимальный маршрут с наименьшим количеством пересадок.

Если на экране появится надпись «no», значит неправильно введено название станции или невозможно найти оптимальный маршрут, не проезжая через какую-либо станцию дважды.

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

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

Описание станций линий метро

линия (линия₁,[a, s, d, f, g]).

линия (линия₂,[l, k, d, j, h]).

линия (линия₃,[z, x, d, c, v]).

линия (линия₄,[b, n, d, m, q]).

линия (линия₅,[c, j, f, m, x, k, s, n, c]).

Далее определяеться принадлежность станции к линии. Т. е. станция принадлежит списку (линии), если она являеться головой этого списка; станция принадлежит списку, если она находиться в хвосте.

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

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

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

соседние (Станция1,Станция2,[Станция1,Станция2|_]).

соседние (Станция1,Станция2,[_|Хвост]):;

соседние (Станция1,Станция2,Хвост).

Ненаправленность графа обеспечивается в поиске смежных станций, т. е. находим ветвь Станция1, Станция2 или Станция2, Станция1.

смежные_станции (Станция1,Станция2,Линия): — линия (Линия, Список), принадлежит (Станция1,Список),

принадлежит (Станция2,Список), соседние (Станция1,Станция2,Список);

линия (Линия, Список), принадлежит (Станция1,Список),

принадлежит (Станция2,Список), соседние (Станция2,Станция1,Список).

Пересадка с линии1 на линию 2 возможна, когда станция принадлежит обеим линиям.

пересадка (Станция, Линия1, Линия2): — линия (Линия1,Список1), линия (Линия2, Список2),

принадлежит (Станция, Список1), принадлежит (Станция, Список2), Линия1<>Линия2.

Осуществляем поиск возможного пути от начальной станции к конечной.

маршрут (Станция, Станция,[Станция], 1, Линия,_) : — линия (Линия, Список), принадлежит (Станция, Список).

% путь с пересадкой

маршрут (Начало, Конец,[Начало, Начало2|Хвост], Остановки1, Линия, История) :;

линия (Линия, Список), линия (Новая_Линия, Новый_Список),

принадлежит (Начало, Список), принадлежит (Начало2,Новый_Список),

пересадка (Начало, Линия, Новая_Линия), Линия<>Новая_Линия,

смежные_станции (Начало, Начало2,_),

not (принадлежит (Начало2,История)),

маршрут (Начало2,Конец,[Начало2|Хвост], Остановки2, Новая_Линия, [Начало2|История]),

Остановки1=Остановки2+1.

% путь без пересадки

маршрут (Начало, Конец,[Начало, Начало2|Хвост], Остановки1, Линия, История) :;

линия (Линия, Список), линия (Новая_Линия, Новый_Список),

принадлежит (Начало, Список), принадлежит (Начало2,Новый_Список),

Линия=Новая_Линия, смежные_станции (Начало, Начало2,_),

not (принадлежит (Начало2,История)),

маршрут (Начало2, Конец, [Начало2|Хвост], Остановки2, Линия, [Начало2|История]),

Остановки1 = Остановки2 + 1.

/* осуществляется поиск пути через заданную остановку*/

через_станцию (Начало, Конец, Пром, Ost, List):-маршрут (Начало, Конец, List, Ost,_,[Начало]), принадлежит (Пром, List).

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

Из схемы метро (см. приложение А) выбираем начальную и конечную станции, а так же вводим промежуточные через которые нам надо проехать. Запускаем программу. Вводим соответствующие названия станций Например: нач-a, кон-g, пром-с, j.

После обработки данных программа выводит на экран маршрут проезда, в виде списка станций, через которые следует ехать, и количество остановок в пути.

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

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

Мир — Москва, 1990.

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

3. Математические модели информационных процессов и управления

Сост.: С. И. Беляева и др. — Нижний Новгород, 1991.

Приложение

Код программы

/*ПРОЕЗД В МЕТРО ЧЕРЕЗ ЗАДАННЫЕ ОСТАНОВКИ*/

DOMAINS

список=symbol*

список1=integer*

PREDICATES

nondeterm линия (symbol, список)

nondeterm мин₁(integer, список1)

nondeterm минимальное (integer, список1)

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

nondeterm соседние (symbol, symbol, список)

nondeterm смежные_станции (symbol, symbol, symbol)

nondeterm пересадка (symbol, symbol, symbol)

nondeterm маршрут (symbol, symbol, список, integer, symbol, список)

nondeterm через_станцию (symbol, symbol, symbol, integer, список)

nondeterm поиск

nondeterm stations (symbol, symbol, список, integer, список)

nondeterm includ (список, список)

nondeterm vvod (integer, список, список)

nondeterm vvod1(integer, список)

nondeterm vvod2(integer)

nondeterm digit (string, integer)

CLAUSES

/* ОПИИСАНИЕ ЛИНИЙ */

линия (линия₁,[a, s, d, f, g]).

линия (линия₂,[l, k, d, j, h]).

линия (линия₃,[z, x, d, c, v]).

линия (линия₄,[b, n, d, m, q]).

линия (линия₅,[c, j, f, m, x, k, s, n, c]).

/* ПОИСК МИНИМАЛЬНОГО ЭЛЕМЕНТА В СПИСКЕ ЦЕЛЫХ ЧИСЕЛ */

мин₁(_,[]).

мин₁(Мин,[X|Хвост]): — Мин<=X, мин₁(Мин, Хвост).

минимальное (Мин,[X|Хвост]): — Мин=X, мин₁(Мин, Хвост); минимальное (Мин, Хвост).

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

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

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

/*ПРОВЕРКА ДВУХ СТАНЦИЙ НА СОСЕДСТВО В СПИСКЕ */

соседние (Станция1,Станция2,[Станция1,Станция2|_]).

соседние (Станция1,Станция2,[_|Хвост]): — соседние (Станция1,Станция2,Хвост).

/* СМЕЖНЫЕ СТАНЦИИ */

смежные_станции (Станция1,Станция2,Линия): — линия (Линия, Список), принадлежит (Станция1,Список),

принадлежит (Станция2,Список), соседние (Станция1,Станция2,Список);

линия (Линия, Список), принадлежит (Станция1,Список),

принадлежит (Станция2,Список), соседние (Станция2,Станция1,Список).

/* ВОЗМОЖНОСТЬ ПЕРЕСАДКИ */

пересадка (Станция, Линия1, Линия2): — линия (Линия1,Список1), линия (Линия2,Список2),

принадлежит (Станция, Список1), принадлежит (Станция, Список2), Линия1<>Линия2.

/* ОСУЩЕСТВЛЯЕТСЯ ПОИСК ПУТИ */

маршрут (Станция, Станция,[Станция], 1, Линия,_) : — линия (Линия, Список), принадлежит (Станция, Список).

% путь с пересадкой

маршрут (Начало, Конец,[Начало, Начало2|Хвост], Остановки1, Линия, История) :;

линия (Линия, Список), линия (Новая_Линия, Новый_Список),

принадлежит (Начало, Список), принадлежит (Начало2,Новый_Список),

пересадка (Начало, Линия, Новая_Линия), Линия<>Новая_Линия,

смежные_станции (Начало, Начало2,_),

not (принадлежит (Начало2,История)),

маршрут (Начало2,Конец,[Начало2|Хвост], Остановки2, Новая_Линия,[Начало2|История]),

Остановки1=Остановки2+1.

% путь без пересадки

маршрут (Начало, Конец,[Начало, Начало2|Хвост], Остановки1, Линия, История) :;

линия (Линия, Список), линия (Новая_Линия, Новый_Список),

принадлежит (Начало, Список), принадлежит (Начало2,Новый_Список),

Линия=Новая_Линия, смежные_станции (Начало, Начало2,_),

not (принадлежит (Начало2,История)),

маршрут (Начало2,Конец,[Начало2|Хвост], Остановки2, Линия,[Начало2|История]),

Остановки1 = Остановки2 + 1.

/* осуществляется поиск пути через заданную остановку*/

через_станцию (Начало, Конец, Пром, Ost, List):-маршрут (Начало, Конец, List, Ost,_,[Начало]), принадлежит (Пром, List).

поиск:-write («Выбор маршрута в метро c проездом через заданные остановки»), nl,

write («Схему метро смотрите в Приложении, А пояснительной записки»), nl, nl,

write («Введите начальнаую станцию = «), readln (Начало),

write («Введите конечную станцию = «), readln (Конец),

vvod1(_, Prom),

findall (Остановки, stations (Начало, Конец, Prom, Остановки, List), Ost_Список),

минимальное (Остановки, Ost_Список),

stations (Начало, Конец, Prom, Остановки, List),

%через_станцию (Начало, Конец, Пром, Остановки, List),

write («nПуть: «, List,» nЧисло остановок: «,

Остановки), nl.

stations (Начало, Конец, Пром, Ost, List):-маршрут (Начало, Конец, List, Ost,_,[Начало]),

includ (Пром, List).

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

includ ([X], List):-принадлежит (X, List).

includ ([X|List1], List):-принадлежит (X, List), includ (List1,List).

vvod (1,List, List1):-write («Введите последнюю промежуточную станцию: «),

readln (Str), not (принадлежит (Str, List1)), List=[Str],!.

vvod (N, List, List1):-N>1,write («Введите промежуточную станцию: «),

readln (Nomer),

not (принадлежит (Nomer, List1)), N1=N-1,

vvod (N1,List2,[Nomer|List1]), List=[Nomer|List2],!;

write («Станция с таким названием уже была введена»), nl, vvod (N, List, List1).

digit (Str, Digit): — str_int (Str, Digit).

vvod2(N):-write («Сколько вы хотите ввести промежуточных станций: «), nl,

readln (Str), digit (Str, N),!;

write («Была введена не цифра. Повторите ввод»), nl, vvod2(N).

vvod1(N, List):-vvod2(N), vvod (N, List,[]).

GOAL

поиск.