Математические модели
Содержание
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 Логические модели. Блок-схемы алгоритмовОписание станций линий метро линия(линия_1,[a,s,d,f,g]). линия(линия_2,[l,k,d,j,h]). линия(линия_3,[z,x,d,c,v]). линия(линия_4,[b,n,d,m,q]). линия(линия_5,[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*PREDICATESnondeterm линия(symbol,список)nondeterm мин_1(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/* ОПИИСАНИЕ ЛИНИЙ */линия(линия_1,[a,s,d,f,g]).линия(линия_2,[l,k,d,j,h]). линия(линия_3,[z,x,d,c,v]).линия(линия_4,[b,n,d,m,q]).линия(линия_5,[c,j,f,m,x,k,s,n,c])./* ПОИСК МИНИМАЛЬНОГО ЭЛЕМЕНТА В СПИСКЕ ЦЕЛЫХ ЧИСЕЛ */мин_1(_,[]).мин_1(Мин,[X|Хвост]):- Мин<=X, мин_1(Мин,Хвост).минимальное(Мин,[X|Хвост]):- Мин=X,мин_1(Мин,Хвост); минимальное(Мин,Хвост)./* ПРОВЕРКА НА ПРИНАДЛЕЖНОСТЬ СТАНЦИИ СПИСКУ */принадлежит(Станция,[Станция|_]).принадлежит(Станция,[_|Хвост]):- принадлежит(Станция,Хвост)./*ПРОВЕРКА ДВУХ СТАНЦИЙ НА СОСЕДСТВО В СПИСКЕ */соседние(Станция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 входили в список2includ([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поиск.