Как найти путь в таблице m x n

Question

У меня есть таблица m x n и пары точек. Например, мы можем иметь таблицу 3 х 3 и пары точек:

A = (1,3), (3,2) В = (1,2), (3,1)

Я должен найти все пути, которые будут соединяться точками в парах. Эти пути не могут пересекаться друг с другом. Мы можем идти влево, вправо, вниз и вверх. В предыдущем примере мы имеем следующие пути:

A = (1,3) -> (2,3) -> (3,3) -> (3,2) B = (1,2) - > (2,2) -> (2,1) -> (3,1)

(если больше решать, я хотел бы иметь все)

у кого-либо концепции, как я могу это сделать в Haskell?

---

Может быть, вы могли бы объяснить словами, ваш алгоритм Пролог

Хорошо, кроме того, у меня есть свой код, так:

У меня есть четыре предиката идти по левой стороне, вправо, вверх и вниз.

go((I1,J1),(I2,J2),_,_) :- 
    J1 is J2, 
    I2>=2, 
    I1 is I2 - 1. 

go((I1,J1),(I2,J2),_,N) :- 
    I1 is I2, 
    J2=<N-1, 
    J1 is J2 + 1. 

go((I1,J1),(I2,J2),M,_) :- 
    J1 is J2, 
    I2=<M-1, 
    I1 is I2 + 1. 

go((I1,J1),(I2,J2),_,_) :- 
    I1 is I2, 
    J2>=2, 
    J1 is J2 - 1. 

Например go((I,J),(3,3),5,5) возвращает

(I,J) = (2,3) 
(I,J) = (4,3) 
(I,J) = (3,2) 
(I,J) = (3,4) 

Конечно, аргументы 5 является размер таблицы - здесь мы имеем таблицу 5х5.

я должен знал, когда это конец пути, так что я писал:

endOfPath((I1,J1),(I2,J2)) :- 
    I1 == I2, 
    J1 == J2. 

Тогда я мог бы сделать предикат, который будет генерировать пути от точки (I1, J1) к (I2, J2). Во-первых, мы должны проверить, если это конец пути:

generatePath((I1,J1),(I2,J2),T,T,_,_,_,B,B) :- 
    endOfPath((I1,J1),(I2,J2)),!. 

Если это не конец пути, мы должны генерировать пути рекурсивно.

generatePath((I1,J1),(I2,J2), Acc,T,M,N,Input,Bufor,NewBufor) :- 
    go((I3,J3),(I2,J2),M,N), 
    \+ member((I3,J3),Bufor), 
    \+ member((I3,J3),Acc), 
    \+ member((I3,J3),Input), 
    generatePath((I1,J1),(I3,J3),[(I3,J3)|Acc],T,M,N,Input,[(I3,J3)|Bufor],NewBufor). 

Таким образом, сначала мы находим точку, которая находится непосредственно рядом с (I2, J2), то мы проверяем несколько условий (например, если (I3, J3) принадлежит к какому-либо другому пути - это неправильно пункт). Затем мы возвращаем путь от (I1, J1) до (I3, J3) рекурсивно. У нас есть проблема, когда (I3, J3) является концом пути, потому что (I3, J3) принадлежат Input и условие + member ((I3, J3), Input) не выполняется.

Поэтому я написал последний предикат:

generatePath((I1,J1),(I2,J2), Acc,T,M,N,Input,Bufor,NewBufor) :- 
    go((I3,J3),(I2,J2),M,N), 
    \+ member((I3,J3),Acc), 
    I3 == I1, J3 == J1, 
    generatePath((I1,J1),(I3,J3),[(I3,J3)|Acc],T,M,N,Input,[(I3,J3)|Bufor],NewBufor). 

Это было довольно легко и дает хорошие результаты, но я не знаю, как я могу это сделать в Haskell. На самом деле, у меня очень большая проблема, и, пожалуйста, помогите мне.

Answer 1

код переводится как

go m n (i,j) = 
    [ (i+1,j) | i<m ] ++ 
    [ (i-1,j) | i>1 ] ++ 
    [ (i,j+1) | j<n ] ++ 
    [ (i,j-1) | j>1 ] 

-- isEndOfPath p q = p == q 

genPath p q acc m n input buf = head $  -- since you have a cut there 
            g p q acc buf 
    where 
    g p q acc buf | p==q = [(acc,buf)] -- return acc, buf 
    g p q acc buf = [s | 
         r <- go m n q, notElem r buf, notElem r acc, 
         notElem r input, 
         s <- g p r (r:acc) (r:buf)] ++ 
        [s | 
         r <- go m n q, notElem r acc, 
         r==p, 
         s <- g p r (r:acc) (r:buf)]