Prolog中的简化旅行推销员 [英] Simplified Travelling Salesman in Prolog

查看:135
本文介绍了Prolog中的简化旅行推销员的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我已经浏览了类似的问题,但是找不到与我的问题相关的任何内容.我正在努力寻找一个算法或一组循环",使用数据库

I've looked through the similar questions but can't find anything that's relevant to my problem. I'm struggling to find an algorithm or set of 'loops' that will find a path from CityA to CityB, using a database of

distance(City1,City2,Distance)

事实.到目前为止,我设法做到的是,但是它总是在write(X),处回溯,然后完成最终的迭代,这是我希望它执行的操作,但仅在一定程度上进行.

facts. What I've managed to do so far is below, but it always backtracks at write(X), and then completes with the final iteration, which is what I want it to do but only to a certain extent.

例如,我不希望它打印出任何死胡同的城市名称,或使用最终迭代.我希望它基本上建立从CityACityB的路径,并在路径上写下它要去的城市的名称.

For example, I don't want it to print out any city names that are dead ends, or to use the final iteration. I want it to basically make a path from CityA to CityB, writing the name of the cities it goes to on the path.

我希望有人能帮助我!

all_possible_paths(CityA, CityB) :-
    write(CityA),
    nl,
    loop_process(CityA, CityB).

loop_process(CityA, CityB) :- 
    CityA == CityB.
loop_process(CityA, CityB) :-
    CityA \== CityB,
    distance(CityA, X, _),
    write(X),
    nl,
    loop_process(X, CityB).

推荐答案

我试图演示如何实现您正在从事的工作,以便您可以更好地了解其工作方式.因此,由于您的OP并不是很完整,所以我享有一些自由!这是我正在使用的事实:

I tried to demonstrate how you can achieve what you're working on so that you can understand better how it works. So since your OP wasn't very complete, I took some liberties ! Here are the facts I'm working with :

road(birmingham,bristol, 9).
road(london,birmingham, 3).
road(london,bristol, 6).
road(london,plymouth, 5).
road(plymouth,london, 5).
road(portsmouth,london, 4).
road(portsmouth,plymouth, 8).

这是我们将调用以查找路径的谓词, get_road/4 .它基本上称为工作谓词,它有两个累加器(一个累加点,一个累加的距离).

Here is the predicate we will call to find our paths, get_road/4. It basically calls the working predicate, that has two accumulators (one for the points already visited and one for the distance we went through).

get_road(Start, End, Visited, Result) :-
    get_road(Start, End, [Start], 0, Visited, Result).

这是工作谓词,
get_road/6 :get_road(+开始,+结束,+航点,+ DistanceAcc,-Visited,-TotalDistance):
第一条说明如果我们的第一个点和最后一个点之间有一条路,我们可以在这里结束.

Here is the working predicate,
get_road/6 : get_road(+Start, +End, +Waypoints, +DistanceAcc, -Visited, -TotalDistance) :
The first clause tells that if there is a road between our first point and our last point, we can end here.

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, End, Distance),
    reverse([End|Waypoints], Visited),
    TotalDistance is DistanceAcc + Distance.

第二个子句告诉我们,如果在我们的第一个点和一个中间点之间有一条路,我们可以走这条路,然后求解get_road(intermediate,end).

The second clause tells that if there is a road between our first point and an intermediate point, we can take it and then solve get_road(intermediate, end).

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, Waypoint, Distance),
    \+ member(Waypoint, Waypoints),
    NewDistanceAcc is DistanceAcc + Distance,
    get_road(Waypoint, End, [Waypoint|Waypoints], NewDistanceAcc, Visited, TotalDistance).

用法如下:

?- get_road(portsmouth, plymouth, Visited, Distance).

产生:

Visited = [portsmouth, plymouth],
Distance = 8 ;
Visited = [portsmouth, london, plymouth],
Distance = 9 ;
Visited = [portsmouth, plymouth, london, plymouth],
Distance = 18 ;
false.

希望对您有所帮助.

这篇关于Prolog中的简化旅行推销员的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆