48081 (Поиск оптимального пути в графе), страница 2
Описание файла
Документ из архива "Поиск оптимального пути в графе", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48081"
Текст 2 страницы из документа "48081"
мин_сумма2 (М, Список).
В данном случае конкретизирован Cписок, необходимо найти М. Присваиваем М значение первого элемента и сравниваем с остольными элементами списка. Если М является минимумом, то искомое значение найдено, отсечение не позволяет перейти ко второму условию этого правила. Иначе сравниваем с значения второго элемента списка с оставшимися. Цикл прекращается, если очередное значение М является минимальным.
г) коридор (Нач, Кон, СписокХ, СписокУ): -
участок (Нач, Х1, У1,_,_,_,_,_),!,
участок (_,_,_, Кон, Х2, У2,_,_),!,
min (Х1, Х2, МИН1),
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","пл_сенная"]
Сумма_времени=33yes
В решении используются факты, принадлежащие базе фактов, - факт24,26,21,31,34, также все факты и правила расположенные ниже базы фактов, кроме факта 60, который определяет путь, состоящий из одной остановки. Если, например, убрать факт21, то данного решения не будет, может, будет иное решение или решения вообще не будет. Проверив, я убедился, что решения нет. Убрав какое-нибудь из правил, вся программа “рухнет".
б) start (кузнечиха_2, кузнечиха_2).
Решение:
Путь: ["кузнечиха_2"]
Сумма_времени=0Yes
При решении затрагиваются: стартовое правило12 и факт 60, который и определяет это решение. Если его заремить, то решения не будет найдено.
в) Также ответ на запрос может быть “no" см. п.2.5
Используемая литература
1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. - М.: Мир, 1990. - 560 с., ил.
2. СТП 1-У-НГТУ-98 “Проекты (работы) дипломные и курсовые. Общие требования к оформлению пояснительных записок и чертежей"
