如何在m x n表中找到路径 [英] How find path at the m x n table

问题描述

我有表m×n和点对。例如，我们可以有表格3 x 3和点对：

A =（1,3），（3,2）
B =（ 1,2），（3,1）

我必须找到所有将成对连接点的路径。这些路径不能相互交叉。我们可以左转，右转，上下。在前面的例子中，我们有followig路径：

A =（1,3） - >（2,3） - >（3,3） - >（3， 2）
B =（1,2） - >（2,2） - >（2,1） - >（3,1）

如果是更多的解决方案，我想所有）

有没有人有任何概念我怎么能在haskell做到这一点？

也许你可以用语言解释你的Prolog算法

好吧，我还有我的代码，所以：

我有四个谓词可以左，右，上和下。

  go（（I1，J1），（I2，J2），_，_）： -  
 J1是J2，
 I2> = 2，
 I1是I2  -  1. 
 
 go（（I1，J1），（I2，J2），_，N）： -  $ （I1，J1），（I2，J2）b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 b1 ，M $ _）： -  
 J1是J2，
 I2 =  I1是I2 + 1. 
 
 go（（I1， J1），（I2，J2），_，_）： -  
 I1是I2，
 J2> = 2，
 J1是J2  -  1. 
  
 
例如 go（（I，J），（3,3），5,5）（I，J）= code $ return $ 
 $ b $ pre $ （4,3）
（I，J）=（3,2）
（I，J）=（3,4）
  

当然，参数5是表的大小 - 在这里我们有表5x5。

我必须知道，是路径的结尾，所以我写道：

$ $ p $ 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）），！ 
  

如果不是路径的结尾，我们必须递归地生成路径。

pre $ generatePath（（I1，J1），（I2，J2），Acc，T，M，N，Input，Bufor， NewBufor）：
go（（I3，J3），（I2，J2），M，N），
\ + member（（I3，J3），Bufor），
\\ （I3，J3），Acc），
\ + member（（I3，J3），Input），
generatePath（（I1，J1），（I3，J3），[ （I3，J3）|度Acc]，T，M，N，输入，[（I3，J3）| Bufor]，NewBufor）。因此，首先我们找到紧邻（I2，J2）的点，然后我们检查几个点条件（例如，如果（I3，J3）属于任何其他路径 - 这是错误的一点）。然后我们递归地生成从（I1，J1）到（I3，J3）的路径。我们有问题，当（I3，J3）是路径结束时，因为（I3，J3）属于Input且条件+成员（（I3，J3），Input）未满足。



因此，我写了最后一个谓词：



  generatePath（（I1，J1），（I2，J2 ），
去（（I3，J3），（I2，J2），M，N），
 \ + member（（）），Acc，T，M，N，Input，Bufor，NewBufor （I3，J3），Acc），
 I3 == I1，J3 == J1，
 generatePath（（I1，J1），（I3，J3），[（I3，J3）| Acc] ，T，M，N，输入，[（I3，J3）| Bufor]，NewBufor）。 
  

这很容易，而且效果很好，但我不知道如何在Haskell中做到这一点。真的，我有很大的问题，请帮助我。

您的代码翻译为

go mn（i，j）=
[（i + 1，j）| i< m] ++
[（i-1，j）| i> 1] ++
[（i，j + 1）| j< n] ++
[（i，j-1）| j> 1]

- isEndOfPath pq = p == q

genPath pq acc mn input buf = head $ - 因为您在那里有一个
gpq acc buf
其中
gpq acc buf | p == q = [（acc，buf）] - return acc，buf
g p q acc buf = [s |
r < - go mnq，notElem r buf，notElem r acc，
notElem r input，
s < - gpr（r：acc）（r：buf）] ++
[s |
r < - go mnq，notElem r acc，
r == p，
s < - gpr（r：acc）（r：buf）]


i have table m x n and pairs of points. For example, we can have table 3 x 3 and pairs of points:

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

I must find all paths which will be connect points in pairs.This paths can't intersect each other. We can go in left, right, down and up. In preceding example, we have followig paths:

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

(if is more solve, i would like have all)

Have anyone any concept how can i do it in haskell?

---

Perhaps you could explain in words your Prolog algorithm

Ok, furthermore i have my code, so:

I have four predicate to go on left, right, up and down.

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.

For example go((I,J),(3,3),5,5) returns

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

Of course, arguments 5 is size of table - here we have table 5x5.

I must knew, when is end of path, so i wrote:

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

Then I could make predicate which will generate paths from point (I1,J1) to (I2,J2). First we must check if it is end of path:

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

If it isn't end of path we must generate paths recursively.

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

Thus, first we find point which is directly next to (I2,J2), then we check several conditions (for example, if (I3,J3) belong to any other path - it's wrong point). And then we generate path from (I1,J1) to (I3,J3) recursively. We have problem, when (I3,J3) is end of path, because (I3,J3) belong to Input and condition + member((I3,J3),Input) is not fulfilled.

Hence, I wrote the last predicate:

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

It was quite easy and gives good results but I don't know how can I make it in Haskell. Really, I have very big problem and please help me.

解决方案

your code translates as

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

这篇关于如何在m x n表中找到路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！