Содержание
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) имеет не определенное число вершин. Каждый элемент liV, где Vмножество вершин графа. Множество кандидатов в li т.е. Si есть множество вершинсоединенных ребрами с вершиной li-1. Было бы не целесообразно искать путь изодной точки в другую, как маршрут возможно содержащий циклы. Кроме практическойнепригодности данного решения, возникает проблема не ограниченности числавершин в маршруте. Поэтому, для исключения циклов, на кандидатов в li вводитсядополнительное ограничение: li. l1, li. l2,…, li. li-1т.е. ни одна вершина не должна встречаться в маршруте более одного раза.
Описанный выше алгоритмнахождения пути наиболее прост в реализации на языке Prolog, так как оннаиболее близок к процедуре доказательства истинности целей, котораяосуществляется путем полного перебора по базе фактов и правил. (см.Математические модели информационных процессов и управления)
Если существует несколькооптимальных маршрутов, то выбирается только один из них.
Б) Последовательныйперебор(Метод полного перебора):
В самом общем случаеполагают, что решение состоит из вектора (a1, a2,…, an), конечной, нонеопределенной длины, удовлетворяющего определенным ограничениям. Каждое аiAi,где Ai конечное упорядоченное множество. В качестве исходного частичногорешения примем пустой вектор () и на основе имеющихся ограничений выясним,какие элементы из А1 являются кандидатами в а1. Обозначим это подмножествокандидатов через
S1A1. Врезультате имеем частичное решение (a1). В общем случае для расширениячастичного решения (a1,a2,…,ak-1) до (a1,a2,…, ak-1, ak) кандидаты на роль аkвыбираются из SkAk. Если частичное решение (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*
PREDICATES
nondetermлиния(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поиск
nondetermstations(symbol,symbol, список,integer, список)
nondeterminclud(список, список)
nondetermvvod(integer, список, список)
nondetermvvod1(integer, список)
nondetermvvod2(integer)
nondetermdigit(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|Хвост]):- Мин=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 входили в список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
поиск.