Список как график в прологе - PullRequest
Новая
       10

Список как график в прологе

0 голосов
/ 20 марта 2012

Я пытаюсь сгенерировать все возможные «пути» от одного элемента в матрице к другому. Условие Main говорит, что элемент в матрице может быть связан с другим, только если элементы имеют хотя бы один угол, поэтому в этой матрице 

[[1,2,3]
 [5,4,6]
 [8,9,7]]

1 можно связать только с 2,4,5, а 4 - со всеми элементами. Можно ли представить этот список в виде графа без использования привлечения? Или, может быть, я могу найти более простой способ сделать это

Спасибо за все ответы. Хорошо, я изложил :-) Теперь с помощью предикатов я сгенерировал все «ребра», но я нигде не могу их использовать, я не мог понять, как добавить в накопитель (список) данные каждой ячейки с таким шаблоном ([row:R1,column:C1,value:V1], [row:R2,column:C2,value:V2]).

Ответы [ 2 ]

2 голосов
/ 21 марта 2012

Вот (длинное, но простое) решение для рассмотрения.

Во-первых, полезно иметь вспомогательный предикат для извлечения элемента из позиции Row,Col в матрице в виде списка списков, например: 

get_matrix_entry_nth0(RowInd, ColInd, Matrix, Entry) :-
    nth0(RowInd, Matrix, Row),
    nth0(ColInd, Row, Entry).

Во-вторых, это также может помочь использовать этот предикат для определения записей, относящихся к индексированным Row и Col в терминах направлений, таких как: 

up_left_entry(R-C, Matrix, E) :-
    PrevR is R - 1,
    PrevC is C - 1,
    get_matrix_entry_nth0(PrevR, PrevC, Matrix, E).

up_entry(R-C, Matrix, E) :-
    PrevR is R - 1,
    get_matrix_entry_nth0(PrevR, C, Matrix, E).

up_right_entry(R-C, Matrix, E) :-
    PrevR is R - 1,
    NextC is C + 1,
    get_matrix_entry_nth0(PrevR, NextC, Matrix, E).

right_entry(R-C, Matrix, E) :-
    NextC is C + 1,
    get_matrix_entry_nth0(R, NextC, Matrix, E).

down_right_entry(R-C, Matrix, E) :-    
    NextR is R + 1,
    NextC is C + 1,
    get_matrix_entry_nth0(NextR, NextC, Matrix, E).

down_entry(R-C, Matrix, E) :-
    NextR is R + 1,
    get_matrix_entry_nth0(NextR, C, Matrix, E).

down_left_entry(R-C, Matrix, E) :-    
    NextR is R + 1,
    PrevC is C - 1,
    get_matrix_entry_nth0(NextR, PrevC, Matrix, E).

left_entry(R-C, Matrix, E) :-
    PrevC is C - 1,
    get_matrix_entry_nth0(R, PrevC, Matrix, E).

С этими вспомогательными предикатами решение довольно простое: 

matrix_path([R|Rs], P) :-
    % determine rows, cols
    length([R|Rs], Rows),
    length(R, Cols),
    % defer to matrix_path/4 to compute all paths starting with 0,0
    matrix_path(0-0, Rows-Cols, [R|Rs], P).

matrix_path/2 является точкой входа в программу. Этот предикат с одним предложением заранее определяет количество строк и столбцов в данной матрице и откладывает обработку до matrix_path/4, который начинает вычисление с элемента 0,0 (верхний левый). 

matrix_path(R-C, Rows-Cols, Matrix, P) :-
    C >= Cols, !,
    % end of column, proceed to next row
    NextRow is R + 1,
    NextRow < Rows,
    matrix_path(NextRow-0, Rows-Cols, Matrix, P).

В первом пункте matrix_path/4 проверяется, превышено ли количество столбцов; если это так, сокращение (!) используется для исключения приведенных ниже предложений, и перезапускает вычисление в следующей строке и сбрасывает индекс столбца на 0. 

matrix_path(R-C, _, Matrix, adj(S, T)) :-
    % get this entry
    get_matrix_entry_nth0(R, C, Matrix, S),
    % get each adjacent entry
    (   up_left_entry(R-C, Matrix, T)
    ;   up_entry(R-C, Matrix, T)
    ;   up_right_entry(R-C, Matrix, T)
    ;   right_entry(R-C, Matrix, T)
    ;   down_right_entry(R-C, Matrix, T)
    ;   down_entry(R-C, Matrix, T)
    ;   down_left_entry(R-C, Matrix, T)
    ;   left_entry(R-C, Matrix, T)
    ).

Второе предложение matrix_path/4 просто пытается извлечь все возможные «пути» из данной записи. Некоторые могут потерпеть неудачу (например, поиск в верхнем ряду), но Prolog откатится назад, чтобы найти все работающие решения. 

matrix_path(R-C, Rows-Cols, Matrix, P) :-
    % get the entry for the next column in this row
    NextC is C + 1,
    matrix_path(R-NextC, Rows-Cols, Matrix, P).

Последнее предложение matrix_path/4 просто переносит обработку относительно элемента в следующем столбце в той же строке.

Запуск простого примера: 

?- matrix_path([[1,2],[3,4]], P).
P = adj(1, 2) ;
P = adj(1, 4) ;
P = adj(1, 3) ;
P = adj(2, 4) ;
P = adj(2, 3) ;
P = adj(2, 1) ;
P = adj(3, 1) ;
P = adj(3, 2) ;
P = adj(3, 4) ;
P = adj(4, 1) ;
P = adj(4, 2) ;
P = adj(4, 3) ;
false.

Обратите внимание, что если вы хотите, чтобы все соседние пары были сразу же без возврата, оберните вызов в findall/2, например: 

?- findall(P, matrix_path([[1,2],[3,4]], P), Ps).
Ps = [adj(1, 2), adj(1, 4), adj(1, 3), adj(2, 4), adj(2, 3), adj(2, 1), adj(3, 1), adj(3, 2), adj(..., ...)|...].
1 голос
/ 21 марта 2012

Перечисление конечного множества можно легко выполнить с помощью обратного отслеживания Prolog: 

adjacent_pos((R,C), (Ra,Ca)) :-
     (R > 1, Ra is R-1 ; Ra is R ; Ra is R+1),
     (C > 1, Ca is C-1 ; Ca is C ; Ca is C+1),
     once(Ra \= R ; Ca \= C).

Используя парные nth1 / 3, мы можем получить доступ к ячейке: 

cell(Mat, (R,C), Cell) :-
     nth1(R, Mat, Row),
     nth1(C, Row, Cell).

Итак, в матрицеNxM различных элементов: 

adjacent(Mat, Elem, Adj) :-
     cell(Mat, Pe, Elem),
     adjacent_pos(Pe, Pa),
     cell(Mat, Pa, Adj).

простой тест: 

test :-
   M = [[1,2,3],
        [5,4,6],
        [8,9,7]],
   findall(A, adjacent(M,1,A), L1), writeln(L1),
   findall(A, adjacent(M,4,A), L4), writeln(L4).

выход: 

?- test.
[2,5,4]
[1,2,3,5,6,8,9,7]
true.

Обратите внимание, что тест R > 1 и C > 1 может бытьизбегать, требуя до nth1 / 3 провала теста «вне диапазона».То же самое верно для верхнего предела, опущенного действительно, с дополнительным преимуществом, что мы не ограничены предопределенным размером матрицы.

...