85749 (612563)

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

Текст из файла

Содержание

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 Функциональная схема программы

Открыть в Viual Prolog файл маршрут.pro

Ввод нач., кон. и промежут. станций.

Поиск оптимального маршрута

Вывод результата

Вывод

Рис. 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,список)

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов курсовой работы