Ответ в теме: Поиск пути в лабините (задан матрицей) на Prolog

      Комментарии к записи Ответ в теме: Поиск пути в лабините (задан матрицей) на Prolog отключены
#3066

В Visual Prolog нет матриц для представления поля, но лабиринт можно представить списком списков:

 
Matrix = [
%A  B  C  D  E  F  G
[0, 1, 0, 0, 0, 0, 0], % A
[1, 0, 1, 0, 1, 0, 0], % B
[0, 1, 0, 1, 0, 0, 0], % C
[0, 0, 1, 0, 1, 0, 0], % D
[0, 1, 0, 1, 0, 0, 0], % E
[0, 0, 0, 0, 1, 0, 0], % F
[0, 0, 0, 0, 1, 0, 0] % G
]

Можно рассматривать эту матрицу как матрицу смежности, а лабиринт тогда — как граф. Нам нужно запустить поиск по этому графу, пусть это будет поиск в глубину.

На вход нашей функции поиска должна передаваться матрица, начальная и конечная вершины, а также буфер для накопления искомого пути (изначально инициализированный пустым списком). Если начальная и конечная вершины совпадают (совпали на каком-то шаге алгоритма), то функции достаточно вернуть накопленный результат (значение из буфера, в котором копился путь переписать в аргумент, соответствующий результату). Если же поиск еще нельзя закончить, то нужно выбрать строчку матрицы, соответствующую начальной вершине. В этой строчке нужно последовательно перебирать элементы, не равные нулю (комнаты, в которые можно попасть) и запускать для них поиск рекурсивно:

path(From, From, _Matrix, Path, Path):-!.
path(From, To, Matrix, PathPart, Path):-
get_element_by_pos(Matrix, From, Line),
get_pos(Line, NewFrom, 1),
NOT(member(NewFrom, PathPart)),
path(NewFrom, TO, Matrix, [NewFrom|PathPart], Path).

В данном случае, функция get_element_by_pos выполняет поиск элемента списка с заданным индексом, а функция get_pos определяет позицию элемента в списке. Если бы мы писали на SWI Prolog, то вместо них можно было бы использовать стандартную функцию nth0, которая решает сразу две эти задачи. Функция member в SWI Prolog также является встроенной, но в Visual Prolog ее нужно писать самому.

get_pos([H|_T], 0, H).
get_pos([_H|T], Pos, E):-
get_pos(T, TPos, E),
Pos = TPos + 1.
get_element_by_pos([H|_T], 0, H):-!.
get_element_by_pos([_H|T], N, E):-
NextN = N - 1,
get_element_by_pos(T, NextN, E).

Также, в Visual/Turbo Prolog нужно описать типы данных и прототипы функций в разделах domains и predicates:

domains 
element = integer
list_d = element*
matrix_d = list_d*
predicates
nondeterm get_pos(list_d, integer, element)
get_element_by_pos(matrix_d, integer, list_d)
nondeterm member(element, list_d)
nondeterm path(element, element, matrix_d, list_d, list_d)

Вызов path(0, 2, Matrix, [], Path). выполнит поиск пути из вершины a в вершину с.