西电 人工智能上机报告2.docVIP

人工智能 实验上机报告二 班级：130811 学号 姓名：潘 圣 志 上机实验（二） 图有哪些信誉好的足球投注网站推理 定义题目 旅行商问题（Traveling-Salesman-Problem,TSP）。设有n个互相可直达的城市，某推销商准备从其中的A城出发，周游各城市一遍，最后又回到A城。要求为该推销商规划一条最短的旅行路线。 图2-1. 旅行商状态空间图 定义算符与状态转换 该问题的状态为以A打头的已访问过的城市序列：A… S0 ：A。 Sg : A, …,A。其中“…”为其余n – 1个城市的一个序列。 状态转换的规则： 规则1 如果当前城市的下一个城市还未去过，则去该城市，并把该城市名排在已去过的城市名序列后端。 规则2 如果所有城市都去过一次，则从当前城市返回A城，把A也添在去过的城市名序列后端。 代价树和各类表 字母定义 A：北京 B：武汉 C：南京 D：上海 E：广州 A B1 C1 D1 E1 D2 C2 E2 B2 D6 E7 B C E B C D C3 E3 D3 E6 C5 D6 D7 E9 B3 B4 B D C E B E B C C D B D B C E4 C4 E5 D4 D5 C6 E8 D8 E 10 D9D B E C E B C B D C D B C B 图2-2. 旅行商问题代价树 EPEN表和CLOSED的结构如图： OPEN表 CLOSED表 节点 父节点编号 A WU B1 A C1 A D1 A E1 A … … … … 编号 节点 父节点编号 … … … … … … … … … 5 E1 A 4 D1 A 3 C1 A 2 B1 A 1 A WU … … 图2-3. OPEN表与CLOSED表实例 程序代码 DOMAINS State=st(lists,integer) lists=symbol* Gx,Grule,Fx=integer city1,city2=symbol distance=integer StartingCity=symbol CitySum=integer DATABASE-mydatabase open(State,integer,Gx,Fx) closed(integer,State,integer,Gx) open1(State,integer,integer,integer) min(State,integer,integer,integer) mark(string,integer) minD(integer) fail_ PREDICATES road(city1,city2,distance) search(StartingCity,CitySum) searching step4(integer,State,Gx) step56(integer,State,Gx) calculator(integer,integer,integer,integer,integer) repeat sort p1 p12(State,integer,integer,integer) p2 rule(State,State,Grule) member(symbol,lists) append(lists,lists,lists) mindist(integer) mindist1 pa(integer) result GOAL clearwindow, write(Please