1

输出序言列表路径并避免用户在序言中输入的某些路线。

嗨,我正在做一个项目,一个建筑物包含区域,每个区域都有一个出口,我们想通过区域疏散人员到出口,用户输入两个参数,第一个是“感染区”,另一个是参数是“我们要疏散的人的区域”。输出应该是从“我们要撤离的人员区域”到避开感染区的出口的所有安全路线。

例如:用户输入(z11, z12) //这意味着z11被感染,我们要撤离的人在z12。

输出 :z12->z22->exit3. and z12->z21->exit2. and z12->elevators

事实是:

 path(z11,z12).
 path(z12,z11).
 path(z12,z22).
 path(z12,z21).
 path(z22,z12).
 path(z22,z21).
 path(z21,z22).
 path(z11,exit1).
 path(z12,elevators).
 path(z21,exit2).
 path(z22,exit3).

请帮我写代码。

4

1 回答 1

1

您选择命名谓词很不方便,path/2因为我们可能希望使用该名称调用生成出口路径的事物。所以首先我会把你所有的事实从 重命名path/2connected/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/2in用于防止循环返回,并且是使路径集有限所必需的。在基本情况下使用也有助于提高性能,因为我们没有生成中间路径。很高兴在您的特殊情况下您可以摆脱这种情况。path/3Seenexit/1path/3

最后进行回避是最后筛选出谷壳。一代不知道要避开这些节点,因此所有受污染的路径都将通过测试生成和删除。如果这种方式性能不够,您可以path/2直接将该代码移入,对列表进行类似的检查Seen

于 2013-07-18T14:22:24.833 回答