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

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

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 9 мес., 1 неделя назад.

  • Автор
    Сообщения
  • #3064

    questioner
    Участник

    Лабиринт задан матрицей соединений, в которой для каждой пары комнат указано, соединены ли они коридором. Программа должна строить путь перехода из одной комнаты в другую.
    labirinth
    Эта лабораторная должна решаться на Visual Prolog 5.2.

  • #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 в вершину с.

Для ответа в этой теме необходимо авторизоваться.