Floyd和Warshall在Prolog中的算法

我想在Prolog中编写这些算法，首先我需要从图表列表中创建一个矩阵。我之前已经做到了这一点（同时在你们中的一些人的帮助下），但现在我不知道如何将它存储在列表列表中（我认为这是prolog最好的方法）。我想我可以从那里继续（在每个算法中使用三重for循环）。程序的逻辑对我来说并不困难，但是如何处理数据。对不起，先打扰一下，谢谢！Floyd和Warshall在Prolog中的算法

我的矩阵生成：

graph(a,b). 
graph(a,a). 
graph(b,c). 
graph(b,d). 
graph(c,d). 
graph(a,e). 
graph(e,f). 

matrix :- allnodes(X),printmatrix(X). 

node(X) :- graph(X,_). 
node(X) :- graph(_,X). 
allnodes(Nodes) :- setof(X, node(X), Nodes). 

printedge(X,Y) :- graph(Y,X), write('1 '). 
printedge(X,Y) :- \+ graph(Y,X), write('0 '). 

printmatrix(List):- member(Y, List),nl,member(X, List),printedge(X,Y),fail.

来源

2011-04-21 Kirby

看来你想要的是图的[邻接矩阵]（http://en.wikipedia.org/wiki/Adjacency_matrix）。我提到这是因为在图表示中常常使用另一个矩阵，称为关联矩阵。邻接矩阵告诉两个节点何时共享边，而关联矩阵表明哪些节点由哪些边满足。简单图的邻接矩阵是对称的，对角线上只有零点（节点不与它们相邻）。我可以帮你解决这个问题，但我不确定实施弗洛伊德 - 沃沙尔会有多么重要。 – hardmath 2011-05-03 15:42:00

邻接矩阵正是我所需要的; __ ;! – Kirby 2011-05-04 02:42:08

你

前面的问题Adjacency Matrix in prolog处理的曲线图的邻接矩阵的可视显示（排过行）。这里我们解释如何将Prolog术语表示为邻接矩阵。具体而言，我们将采用如上所示的所有谓词作为获取所有节点列表的手段。 Prolog没有任何本地“矩阵”数据类型，因此这里采用的方法是使用列表列表来表示邻接矩阵。条目由0和1中的“行”组织，表示与具有对应于列的节点的行对应的节点的邻接。

看看你的例子graph/2的事实，我看到你已经包含了一个自我边缘（从a到a）。我不确定你是否打算将图形定向或不定向，所以我会假设有向图是有意图的，并且注意，如果不需要无向图，那么需要进行小的更改。

这里有一个“设计模式”，它通过对列表中的每个项目应用规则来定义一个列表。在这里，我们通过一种方法来构造“矩阵”的每一行，并且（以此作为我们的规则）来构造列表的整个列表。

/* construct adjacency matrix for directed graph (allow self-edges) */ 
adjacency(AdjM) :- 
    allnodes(L), 
    adjMatrix(L,L,AdjM). 

adjMatrix([ ],_,[ ]). 
adjMatrix([H|T],L,[Row|Rows]) :- 
    row_AdjM(H,L,Row), 
    adjMatrix(T,L,Rows). 

row_AdjM(_,[ ],[ ]). 
row_AdjM(X,[Y|Ys],[C|Cs]) :- 
    ( graph(X,Y) 
    -> C = 1 
    ; C = 0 
    ), 
    row_AdjM(X,Ys,Cs).

如果无向图中的意思，那么调用graph(X,Y)应当具有替代(graph(X,Y); graph(Y,X))，其允许边缘在任一方向被认为是替代。

来源

2011-05-06 12:44:42 hardmath

明天我会试试，谢谢！ – Kirby 2011-05-07 04:07:40

Floyd和Warshall在Prolog中的算法

回答

相关问题