Курсовая работа: Поиск оптимального пути в графе
max (Х1, Х2, МАКС1),
добавить_в_дипазон (МИН1, МАКС1, СписокХ),
min (У1, У2, МИН2),
max (У1, У2, МАКС2),
добавить_в_дипазон (МИН2, МАКС2, СписокУ).
Определяет координаты начальной и конечной остановки, минимальное и максимальное значения среди Х1, Х2 и У1, У2, затем уходит на правило, описанное в пункте д). Отсечение (зелёное) позволяет находить первое единсвенное решение, а остальные отбрасываютя, из-за идентичности.
д) добавить_в_дипазон (А, В, []): - А=В+1.
добавить_в_дипазон (А, В, [А|Список]): - А<=В, А1=А+1,добавить_в_дипазон (А1, В, Список).
А - минимальное значение, а В - максимальное. Список - дискретный набор целых чисел от А до В включительно с шагом в единицу. Пока А не равно В+1, А увеличивается на единицу и добавляется в голову Списка. Хвост в списке остаётся пустым.
е) путь (С, С,_, [С],_,_,0).
Путь с любой остановки в туже занимает время равное нолю, а список пути имеет только один элемент - начальная остановка. Так же этот предикат служит “заглушкой” для следующего правила, т.е. путь, найден, когда следующая остановка равна конечной. Конечная остановка добавляется в переменную Путь в виде списка. Время затраченное на прохождение ветви из конечной в начальную равняется нолю.
участок (Нач, След, Х2, У2, М, Время),
not (принадлежит_симв (След, Список)),
принадлежит (Х2, СписокХ),
принадлежит (У2, СписокУ), путь (След, Кон, [След|Список], Путь, СписокХ, СписокУ, Сумма1),
Сумма=Сумма1+Время.
Ветвь существует, если:
существует участок с первой начальной (последующей) остановкой и существующей следующей;
следующая остановка не принадлежит списку из предшествующих её остановок;
координаты следующей остановки принадлежат соответственным спискам, которые определяют “коридор".
Общая схема поиска пути (правило stsrt)
Блок-схема поиска отдельного пути (правило путь)
3.2 Тестовый пример
Выполним запросы:
а) start (кузнечиха_2, пл_сенная).
Решение:
Путь:
["кузнечиха_2","м43","кардиоцентр","м43","пл_советская","м39","в_печеры","м2","семашко","м2","пл_сенная"]