您选择命名谓词很不方便,path/2
因为我们可能希望使用该名称调用生成出口路径的事物。所以首先我会把你所有的事实从 重命名path/2
为connected/2
。然后你会想要注释出口:
exit(exit1). exit(exit2).
exit(elevators).
否则,您必须在其他地方对它们进行硬编码。
一个简单的方法是解决一般路径问题,然后检查以确保路径不包含受感染的站点。看起来像这样:
path(Start, Path) :- path(Start, Path, []).
path(Start, [Exit], Seen) :-
exit(Exit),
connected(Start, Exit),
\+ memberchk(Exit, Seen).
path(Start, [Next|Rest], Seen) :-
connected(Start, Next),
\+ memberchk(Next, Seen),
path(Next, Rest, [Next|Seen]).
safe_path(Start, Avoid, Path) :-
path(Start, Path),
\+ memberchk(Avoid, Path).
这很容易概括为处理一组避免区域:
safe_path(Start, AvoidList, Path) :-
path(Start, Path),
forall(member(Avoid, AvoidList), \+ memberchk(Avoid, Path)).
Prolog 中大部分有趣和有趣的事情都是通过生成/测试范式完成的。最简单和最直接的公式通常是您生成太多(您可能会说太笼统)并将所有限制放在测试中的公式。一般来说,您可以通过使生成器更智能地生成可能性来获得更好的性能——将代码从“测试”部分移动到“生成和测试”的“生成”部分。
通常,您面临的第一个问题是生成无限树。对于图表尤其如此。带有列表的memberchk/2
in用于防止循环返回,并且是使路径集有限所必需的。在基本情况下使用也有助于提高性能,因为我们没有生成中间路径。很高兴在您的特殊情况下您可以摆脱这种情况。path/3
Seen
exit/1
path/3
最后进行回避是最后筛选出谷壳。一代不知道要避开这些节点,因此所有受污染的路径都将通过测试生成和删除。如果这种方式性能不够,您可以path/2
直接将该代码移入,对列表进行类似的检查Seen
。