Наша взаимовыгодная связь https://banwar.org/
Анотація: Вивчаються основні методи пошуку шляхів на графах - пошук в глибину і пошук в ширину. Розглядається ставлення досяжності на графі. Розбираються деякі способи пошуку найкоротших шляхів. Генерується випадковий лабіринт, візуалізується прохід по ньому. Версія Visual Prolog 7.5, ще не опублікована. Її публікація планується в 2014 році, але точна дата поки не відома. Зараз всім доступна версія Visual Prolog 7.4.
У цій главі вивчаються основні методи пошуку шляхів на графах - пошук в глибину і пошук в ширину. Розглядається ставлення досяжності на графі. Розбираються деякі способи пошуку найкоротших шляхів. Генерується випадковий лабіринт, візуалізується прохід по ньому.
Для представлення графа в мові Пролог зазвичай використовуються факти. Наприклад, нехай в окремих фактах зберігаються вершини і ребра графа:
node ( "a"). node ( "b"). node ( "c"). arc (1, "a", "b"). % Номер ребра, його початок і кінець arc (2, "b", "c").Тоді предикат, який повертає елементи матриці інцидентності, можна визначити наступним чином:
incidenceMatrix (Node, Edge, Elem): - node (Node), arc (Edge, Node1, Node2), getElem (Node, Node1, Node2, Elem). getElem (Node, Node, _, 1): -!. getElem (Node, _, Node, -1): -!. % 1 для неоріент. графа getElem (_, _, _, 0). ? - incidenceMatrix (Node, Edge, Elem).В якості основного прикладу в цьому розділі використовується система доріг, яка пов'язує деякі міста. Цю систему можна зобразити у вигляді навантаженого графа, вершини якого відповідають містам, а ребра - з'єднує їм дорогах ( Мал. 8.1 ).
Мал. 8.1. Граф системи доріг
Граф представляється у вигляді безлічі ребер, для зберігання яких використовуються факти:
clauses arc ( "Москва", "Нижній Новгород", 400). arc ( "Нижній Новгород", "Перм", 950). arc ( "Єкатеринбург", "Перм", 350). arc ( "Єкатеринбург", "Новосибірськ", 1550). arc ( "Нижній Новгород", "Єкатеринбург" 1300). arc ( "Москва", "Самара", 1050). arc ( "Самара", "Єкатеринбург", 950). arc ( "Самара", "Новосибірськ", 2300). arc ( "Санкт-Петербург", "Петрозаводськ", 450). arc ( "Санкт-Петербург", "Псков", 300).В директорії Exe проекту слід створити текстовий файл graph .txt і помістити в нього дані факти.
8.1. Пошук в глибину
Пошук в глибину є природним для мови Пролог, він використовується машиною виведення Прологу для обчислення цілей. Тому пошук в глибину шляхів на графах реалізується в мові Пролог найбільш просто.
Пояснимо ідею пошуку в глибину на наступному прикладі. Розглянемо граф, зображений на Мал. 8.2 (A).
Мал. 8.2. (A) Зв'язковий граф; (B) обхід графа в глибину
Нехай ребра графа зберігаються в наступному порядку: 
. Зробимо обхід графа з вершини 
. Будемо рухатися вперед по ребрах і позначати пройдені вершини до тих пір, поки будуть зустрічатися непомічені вершини. Коли це стане неможливим, повернемося в останню пройдену вершину 
, Для якої існує Непомічені суміжна з нею вершина. Далі обхід буде відбуватися з вершини . Обхід триває до тих пір, поки залишаються непомічені вершини. Схематично обхід графа можна представити таким чином ( Мал. 8.2 (B)):
Мал. 8.3. Схематичне зображення обходу графа
У наступних двох програмах для знаходження шляхів використовується пошук в глибину. У першій програмі використовується функціональний стиль, а в другій предикатний. У другій програмі разом з пошуком підраховується довжина шляху. Ставлення edge є симетричним замиканням відносини arc. Для зберігання пройденого шляху використовується список. В процесі обчислень вершини записуються в список, як в стек, тому до знайденого шляху застосовується операція звернення списку.
class facts - graph arc: (string Город1, string Город2, unsigned Відстань). class predicates depthFirst: (string, string) -> string * nondeterm. path: (string, string, string *) -> string * nondeterm. edge: (string, string, unsigned) nondeterm (i, o, o). clauses edge (X, Y, Dist): - arc (X, Y, Dist); arc (Y, X, Dist). depthFirst (Start, Goal) = list :: reverse (path (Start, Goal, [Start])). path (Goal, Goal, Path) = Path: -!. path (V, Goal, CurrPath) = path (NextV, Goal, [NextV | CurrPath]): - edge (V, NextV, _), not (list :: isMember (NextV, CurrPath)). run (): - file :: consult ( "graph.txt", graph), VertexList = depthFirst ( "Москва", "Новосибірськ"), write (string :: concatWithDelimiter (VertexList, "->")), nl, fail; _ = ReadLine (). Приклад 8.1. Пошук в глибинуПредикат concatWithDelimiter з'єднує список рядків в один рядок, вставляючи між ними поставлене роздільник.
Для поточної вершини можна не використовувати окремий аргумент (див. Вище визначення предиката path / 3):
depthFirst (Start, Goal) = list :: reverse (path ([Start], Goal)). path ([Goal | Path], Goal) = [Goal | Path]. path ([V | Path], Goal) = path ([NextV, V | Path], Goal): - edge (V, NextV, _), not (NextV in Path).Вправа 1. Знайдіть всі шляхи з Москви до Новосибірська, що проходять через Пермь1.
class facts - graph arc: (string, string, unsigned). class predicates depthFirst: (string, string, string * [out], unsigned [out]) nondeterm. path: (string, string, string *, string * [out], unsigned, unsigned [out]) nondeterm. edge: (string, string, unsigned) nondeterm (i, o, o). clauses edge (X, Y, Dist): - arc (X, Y, Dist); arc (Y, X, Dist). depthFirst (Start, Goal, list :: reverse (Path), Dist): - path (Start, Goal, [Start], Path, 0, Dist). path (Goal, Goal, Path, Path, Dist, Dist): -!. path (V, Goal, CurrPath, Path, CurrDist, Dist): - edge (V, NextV, D), not (NextV in CurrPath), path (NextV, Goal, [NextV | CurrPath], Path, CurrDist + D, Dist). run (): - file :: consult ( "graph.txt", graph), depthFirst ( "Москва", "Новосибірськ", Path, D), write (string :: concatWithDelimiter (Path, "->"), " : ", D), nl, fail; _ = ReadLine (). Приклад 8.2. Пошук в глибину з підрахунком довжини шляхуВправа 2.
- Знайдіть всі шляхи, не перевищують заданої довжини.
- Знайдіть всі шляхи від одного пункту до іншого, які містять не більше заданого числа пересадок.
