List as graph in prolog

Question

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

[[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]).

Answer 1

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

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 a nd C > 1 можно было бы избежать, требуя nth1/3 сбой теста «вне диапазона». То же самое можно сказать и о верхнем пределе, опустившись, с дополнительным преимуществом, что мы не ограничены предопределенным размером матрицы.

Answer 2

Это долгое, но простое решение.

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

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

Во-вторых, она также может помочь использовать этот предикат для определения записей относительно них проиндексированных и 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(..., ...)|...].