path - Prolog 未加权图距离减少 1
问题描述
所以我试图找到未加权图的路径及其长度。这是我的代码;你给它一个关系,一个开始和结束,以及长度。该代码有效,但是它返回的长度比需要的少 1。
:- use_module(library(lists)).
edge(1,2).
edge(1,4).
edge(1,3).
edge(2,3).
edge(2,5).
edge(3,4).
edge(3,5).
edge(4,5).
connected(X,Y) :-
edge(X,Y)
;
edge(Y,X).
path(Rel,A,B,Path,Len) :-
travel(Rel,A,B,[A],Q,Len),
reverse(Q,Path).
travel(Rel,A,B,P,[B|P],L) :-
call(Rel, A, B), L is 1 .
travel(Rel,A,B,Visited,Path,L) :-
call(Rel,A,C),
C \== B,
\+member(C,Visited),
travel(Rel,C,B,[C|Visited],Path,L1),
L is L1 + 1.
所有这些边的权重/距离都为 1,但是给定一个查询,例如
?- path(connected, 1, 5, Path, Length).
返回的每个长度都比应有的少 1。
任何有用的建议。
解决方案
我没有尝试根据经验修复计算谓词中路径长度的方式,travel
我知道在处理列表以计算另一个属性时重构 Prolog 代码并不难,而且通常是这样做的。
因此,这会重构 predicate reverse/2
。要重构reverse/2
,我们首先需要以下工作代码reverse/2
:
% Reverse using accumulator
rev(List,Rev) :-
rev(List,[],Rev) .
rev([],A,A).
rev([H|T],A,R) :-
rev(T,[H|A],R).
示例rev/2
?- rev([],L).
L = [].
?- rev([a],L).
L = [a].
?- rev([a,b],L).
L = [b, a].
?- rev([a,b,c],L).
L = [c, b, a].
现在重构rev/2
以计算长度。
rev_n(List,Rev,N) :-
rev_n(List,[],Rev,N) .
rev_n([],A,A,0).
rev_n([H|T],A,R,N) :-
rev_n(T,[H|A],R,N0),
N is N0 + 1.
示例rev_n/2
?- rev_n([],L,N).
L = [],
N = 0.
?- rev_n([a],L,N).
L = [a],
N = 1.
?- rev_n([a,b],L,N).
L = [b, a],
N = 2.
?- rev_n([a,b,c],L,N).
L = [c, b, a],
N = 3.
最后,只需修改您的代码以使用rev_n/2
和删除计算 N 的代码中不再需要的部分。
path_2(Rel,A,B,Path,Len) :-
travel_2(Rel,A,B,[A],Q),
rev_n(Q,Path,Len).
travel_2(Rel,A,B,P,[B|P]) :-
call(Rel, A, B).
travel_2(Rel,A,B,Visited,Path) :-
call(Rel,A,C),
C \== B,
\+member(C,Visited),
travel_2(Rel,C,B,[C|Visited],Path).
例子:
?- path_2(connected, 1, 5, Path, Length).
Path = [1, 2, 5],
Length = 3 ;
Path = [1, 2, 3, 5],
Length = 4 ;
Path = [1, 2, 3, 4, 5],
Length = 5 ;
Path = [1, 4, 5],
Length = 3 ;
Path = [1, 4, 3, 5],
Length = 4 ;
Path = [1, 4, 3, 2, 5],
Length = 5 ;
Path = [1, 3, 5],
Length = 3 ;
Path = [1, 3, 4, 5],
Length = 4 ;
Path = [1, 3, 2, 5],
Length = 4 ;
false.
一种更实用的方法也是只使用length/2
path_3(Rel,A,B,Path,Len) :-
travel_2(Rel,A,B,[A],Q),
reverse(Q,Path),
length(Path,Len).
?- path_3(connected, 1, 5, Path, Length).
Path = [1, 2, 5],
Length = 3 ;
Path = [1, 2, 3, 5],
Length = 4 ;
Path = [1, 2, 3, 4, 5],
Length = 5 ;
Path = [1, 4, 5],
Length = 3 ;
Path = [1, 4, 3, 5],
Length = 4 ;
Path = [1, 4, 3, 2, 5],
Length = 5 ;
Path = [1, 3, 5],
Length = 3 ;
Path = [1, 3, 4, 5],
Length = 4 ;
Path = [1, 3, 2, 5],
Length = 4 ;
false.
推荐阅读
- node.js - crypotjs - 使用 findOne() 解密值
- c++ - 当子类需要在 C++ 中相互包含时的有缺陷的继承
- ios - 如何使用拖动事件移动 UIImageView
- geometry - MySQL 5.6 查找距离内的点并按距离排序 ASC
- java - 在 ECLIPSE 中与 Windows Builder 不兼容的 java 版本
- swift - SwiftUI 在变量更改时调用函数
- arrays - 映射 redux 传奇结果
- python - 如何防止归一化公式产生 NaN 值?
- java - 我可以将 Spring JPA 与只读数据库一起使用吗?
- sql - PDO 内连接?