搜索图的所有路径和最短路径

本文介绍了搜索图的所有路径和最短路径 - Prolog的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我在turbo prolog的代码中遇到问题，它在2个节点之间的图中搜索所有路径和最短路径。 我遇到的问题是测试节点是否在列表中（正好在成员的子句中）

1 ---- b ---- 3 --- | --- --- | ----- a | 5 d --- | ----- --- | --- 2 --- | --- 4 - c - 例如我们有b ---> c （[b，c]，5），（[b ，a，c]，3）和（[b，d，c]，7）：可能的路径。 （[b，a，c]，3）：最短路径。

这是我的代码： <$ p $ path $（符号，符号，列表，整数）路径（符号，符号，列表，列表，整数）距离（符号，列表，整数）成员（符号，列表）最短（符号，符号，列表） ，整数） CLAUSES 距离（a，b，1）。 距离（a，c，2）。 距离（b，d，3）。 距离（c，d，4）。 距离（b，c，5）。 距离（b，a，1）。 距离（c，a，2）。 距离（d，b，3）。 距离（d，c，4）。 距离（c，b，5）。 成员（X，[X | T]）。 成员（X，[Y | T]）： - 成员（X，T）。 缺席（X，L）： - 会员（X，L），！，失败。 缺席（_，_）。 $ b $ *找到所有路径* / path1（X，Y，L，C）： - 路径（X，Y，L，I，C）。 path（X，X，[X]，I，C）： - 缺席（X，I）。 path（X，Y，[X | R]，I，C）： - distance（X，Z，A）， absent（Z，I），路径（Z，Y，R，[X | I]，C1）， C = C1 + A 。 $ b $ *找出最短路径* / 最短（X，Y，L，C）： - 路径（X，Y，L，C），路径（X，Y，L1，C1）， C< C1。

解决方案

这显示最短路径和重量： p>

edge（a，b，6）。 edge（a，c，1）。 edge（b，d，5）。 edge（c，e，4）。 edge（c，f，1）。 edge（d，h，3）。 edge（e，h，7）。 edge（f，g，2）。 edge（g，h，1）。 路径（X，Y，M，[Y]）： - 边（X，Y，M）。 path（X，Y，P，[Z | T]）： - 边（X，Z，M），路径（Z，Y，N，T）， P是M + N。 pravilo（X，Y，Z）：assert（min（100）），assert（minpath（[]）），！， path（X，Y，K，PATH1 ），（min（Z），K

I have a problem in my code with turbo prolog which searches all paths and the shortest path in a graph between 2 nodes. The problem that i have is to test if the node is in the list or not (exactly in the clause of member)

1 ---- b ---- 3 --- | --- --- | ----- a |5 d --- | ----- --- | --- 2 --- | --- 4 -- c -- for example we have for b--->c ([b,c],5) , ([b,a,c],3) and ([b,d,c],7) : possible paths. ([b,a,c],3) : the shortest path.

and this is my code :

DOMAINS list=Symbol * PREDICATES distance(Symbol, Symbol) path1(Symbol, Symbol, list, integer) path(Symbol, Symbol,list, list, integer) distance(Symbol, list, integer) member(Symbol, list) shortest(Symbol, Symbol, list, integer) CLAUSES distance(a, b, 1). distance(a, c, 2). distance(b, d, 3). distance(c, d, 4). distance(b, c, 5). distance(b, a, 1). distance(c, a, 2). distance(d, b, 3). distance(d, c, 4). distance(c, b, 5). member(X, [X|T]). member(X, [Y|T]) :- member(X, T). absent(X, L) :- member(X, L), !, fail. absent(_, _). /* find all paths */ path1(X, Y, L, C) :- path(X, Y, L, I, C). path(X, X, [X], I, C) :- absent(X, I). path(X, Y, [X|R], I, C) :- distance(X, Z, A), absent(Z, I), path(Z, Y, R, [X|I], C1), C = C1 + A . /* to find the shortest path */ shortest(X, Y, L, C) :- path(X, Y, L, C), path(X, Y, L1, C1), C < C1.

解决方案

This shows the shortest path and it's weight:

edge(a,b,6). edge(a,c,1). edge(b,d,5). edge(c,e,4). edge(c,f,1). edge(d,h,3). edge(e,h,7). edge(f,g,2). edge(g,h,1). path(X,Y,M,[Y]) :- edge(X,Y,M). path(X,Y,P,[Z|T]) :- edge(X,Z,M),path(Z,Y,N,T), P is M+N. pravilo(X,Y,Z) :- assert(min(100)),assert(minpath([])),!, path(X,Y,K,PATH1), (min(Z),K<Z, retract(min(Z));assert(min(K))), minpath(Q),retract(minpath(Q)), assert(minpath([X|PATH1])), fail. ?- pravilo(a,h,X); write("Minimal Path:"), minpath(PATH), write(PATH), nl, write("Path weight:"), min(Z), write(Z).