Ответ в теме: Поиск пути в лабините (задан матрицей) на 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 в вершину с.