Зміст
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, тому що він найбільш близький до процедури докази істинності цілей, яка здійснюється шляхом повного перебору по базi фактів і правил. (Див. Математичні моделі інформаційних процесів та управління)
Якщо існує кілька оптимальних маршрутів, то вибирається тільки один з них.
Б) Послідовний перебір (Метод повного перебору):
У самому загальному випадку вважають, що рішення складається з вектора (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 *
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 пошук
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 (Кінець),
vvod 1 (_, 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, List 1): - N> 1, write ("Введіть проміжну станцію:"),
readln (Nomer),
not (належить (Nomer, List1)), N1 = N-1,
vvod (N1, List2, [Nomer | List1]), List = [Nomer | List2],!;
write ("Станція з такою назвою вже була введена"), nl, vvod (N, List, List 1).
digit (Str, Digit): - str_int (Str, Digit).
vvod 2 (N): - write ("Скільки ви хочете ввести проміжних станцій:"), nl,
readln (Str), digit (Str, N),!;
write ("Була введена не цифра. Повторіть введення"), nl, vvod 2 (N).
vvod1 (N, List):-vvod2 (N), vvod (N, List ,[]).
GOAL
пошук.