我正在尝试创建一个社交图,我必须编写一些Prolog才能获得最小和最强的路径 .
我的知识库只有以下声明:
边缘(来源,目的地,重量)
例如:(john,mary,2) .
权重现在只能为3:
1 - 朋友2-亲密的朋友3 - 家庭
这是我的最小路径代码(加权较少) .
findapath(X, Y, W, [X,Y], _) :- edge(X, Y, W).
findapath(X, Y, W, [X|P], V) :- \+ member(X, V),
edge(X, Z, W1),
findapath(Z, Y, W2, P, [X|V]),
W is W1 + W2.
:-dynamic(solution/2).
findminpath(X, Y, W, P) :- \+ solution(_, _),
findapath(X, Y, W1, P1, []),
assertz(solution(W1, P1)),
!,
findminpath(X,Y,W,P).
findminpath(X, Y, _, _) :- findapath(X, Y, W1, P1, []),
solution(W2, P2),
W1 < W2,
retract(solution(W2, P2)),
asserta(solution(W1, P1)),
fail.
findminpath(_, _, W, P) :- solution(W,P), retract(solution(W,P)).
如何包含一个变量来计算行进路径的数量,然后用它来获得最强的路径?
最强的路径是路径重量/行进路径的数量 .
例如,
重量= 8 N行进路径= 3
8/3 = 2.67强度
这意味着我和我的目的地之间有3个人(这是社交图),他们的加权和是8 .
但在这种情况下
重量= 7 N行进路径= 7
这将是最小的路径,对吗?是的,因为它是7和7 <8 . 但是,它不是最强的路径,因为7/7 = 1,这意味着我和我的目的地之间可能有很多人没有和我一样接近我路径 .
我该怎么办?
1 回答
如果您的Prolog系统具有
keysort/2
和findall/3
,则可以避免断言/撤消 . 也就是说,您可以先根据体重来定义力量我是如何理解的:然后用它们的强度枚举所有路径列表,并键入它 . 我将力量定义为负值,因此keysort给了我最高的力量:
我猜以上在某些图表的实践中不起作用,当有组合爆炸时,
path_list_and_neg_strength/4
将有太多的重做 . 在这种情况下,基于表格的解决方案可能更好 .再见