巡回售货员

巡回售货员问题问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。一个状态用三元素表（L,N,C)，其中L是按倒序列出的已访问的城市名表，N已访问的城市数目，C为状态的估值。domainsList=symbol*status=status(List,integer,integer)statusList=status*储存路径：path1(symbol,symbol,integer)path(a,b,7).path(a,c,6).path(a,d,10).path(a,e,13).path(b,c,7).path(b,d,10).path(b,e,10).path(c,d,5).path(c,e,9).path(d,e,6).一个状态用三元素表（L,N,C)，其中L是按倒序列出的已访问的城市名表，N已访问的城市数目，C为状态的估值。astar(T,T,_).astar(X,Y,Open):-findall(Z,rule(X,Z),L),enter(L,Open,[A|T]),nl,write(A),astar(A,Y,T).首先，findall是找出x的后继节点放到列表L中，enter是x的后继节点按估值大小排序，合并到open表中，然后把open表中的表头节点取出来，递归直到三元素表（L,N,C)N=5.rule(status([T1|L1],C,A),status(P,D,B)):-path1(T1,T2,E),not(member(T2,[T1|L1])),D=C+1,//访问城市数量P=[T2,T1|L1],B=A+E-5.//计算估值C值的计算：C=g+h'h'=(n+1)*5在城市列表L中取出表头（最近访问的结点）T1，找到T1后继结点，更新状态列表。path1(T1,T2,E):-path(T1,T2,E);path(T2,T1,E).enter([X],L,L1):-enter1(X,L,L1).enter([X|Y],L,L1):-enter1(X,L,L2),enter(Y,L2,L1).enter1(X,[],[X]):-!.enter1(X,[F|T],[X,F|T]):-le(X,F),!.enter1(X,[F|T],[F|T1]):-enter1(X,T,T1).le(status(_,_,A),status(_,_,B)):-AB.goalastar(status([a],1,25),status(L,5,X),[]).