新乡企业网站建设公司,长安网站建设多少钱,建设执业资格注册管理中心网站,爱前端WordPress主题一、问题描述“旅行商问题”常被称为“旅行推销员问题”#xff0c;是指一名推销员要拜访多个地点时#xff0c;如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单#xff0c;但在地点数目增多后求解却极为复杂。旅行商问题在本实验中的具体化#xff1a;从…一、问题描述“旅行商问题”常被称为“旅行推销员问题”是指一名推销员要拜访多个地点时如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单但在地点数目增多后求解却极为复杂。旅行商问题在本实验中的具体化从A城市出发到达每个城市并且一个城市只允许访问一次最后又回到原来的城市寻找一条最短距离的路径。二、知识表示1、A*算法概述A* 算法是N.Nillson于1971年提出的一种有序搜索算法, 该算法被认为是求解人工智能问题的最成功的技术理论之一。Nillson指出对于某一已到达的现行状态, 如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s 到任意一个节点n 的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n 到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s通过某一指定的n 到达目标节点ti的一条最佳路径的实际耗散值并有f*(n)g*(n)h*(n)。假设f 函数是对f* 函数的一种估计, 并有f(n)g(n)h(n)其中g 函数是对g*的估计h 函数是对h* 的一种估计。f( n) 包括两个部分其中g(n)表示到达n节点时已付出代价的估计而h(n)表示从n节点到达目标节点ti将要付出代价的估计。按f(n)g*(n)h*(n)的值来排序OPEN 表的节点f 值小者优先。通常称这种算法为A算法。在A算法的基础上进一步限制h(n)函数使得搜索图中的每一个节点n能满足h(n)h*(n)、称h 函数取h* 的下界。这种算法叫A* 算法。2、A*算法的状态所谓状态,是指在一定的时空范围内问题所涉及的人、物、时间等的布局关系。通常把问题的初始布局关系称为初始状态问题解决时到达的状态叫目标状态。这两个状态之间存在差异如何从初始状态到达目标状态就是对问题求解。在状态空间法中问题的求解通常是从初始状态到达目标状态的一条最佳路径这条路径依靠搜索算法在状态空间中寻找这就是状态空间法的核心所在。在旅行商问题中初始状态就是旅行商在A城市准备出发送货目标状态就是旅行商将所有的货送出归来到A城市。状态空间就是旅行商可以走的所有路径本实验的解就是最短距离的路径。3、估计函数的意义对于某一已到达的现行状态, 假设现在的现行状态是从A走到C(一共五个城市需走过B、C、D、E)那么下面可以走B、D、E如果继续走B就表示为A-C-B那么在OPEN表里即可选定活路径就有六种选择(1)A-C-B’(2)A-C-D’ (3)A-C-E’(4)A-B;(5)A-D;(6)A-E。为什么有的是B、B’在这里B的层数是2层就是第二步走的是B;而B’的层数是3层就是第三步走的是B。在OPEN表了的一个节点代表一条路径而非简单的代表一个城市结点所以在里面你会看到不同B的表现形式。对OPEN里的每一个节点做评估函数F分为两部分G和HG 未走的城市数×目前的最小距离未走的的城市数(总城市数1)-目前城市的层数。为什得加1因为最后得走回初始城市所以总路径的城市数为总城市数1。假设从A城市走到X城市又走到Y城市所以H可表示为H A到X的距离 X到Y的距离F G H ;计算OPEN表里每个节点的F值F值最小的节点作为活路径从OPEN表中删除放到CLOSE表里。三、算法实现1、数据结构typedef struct _node {int f;//f值int g;//g值int h;//h值int level;//第几次走到这个点(important)int parent;//父城市;int city;//city num;} node;使用node结构体表述每一个城市。typedef struct _list {struct _list *next;struct _list *pre;struct _list *parent; //父城市节点指针node city_node;} nodelist, *nodeptr;使用nodelist, *nodeptr描述路径城市结点与城市结点的关系。typedef struct _ttable {struct _ttable *_this;//this 指针nodelist open;//open表,nodelist close;//close表,(仓库)//一些操作nodeptr(*add_to_open)(int);nodeptr(*find_least_f)(void);void (*move_to_close) (nodeptr ptr);void (*print_path) (nodeptr ptr);} ttable;Ttable相当一个总表相当于面向对象的一个类成员变量有OPEN表和CLOSE表成员函数有nodeptr(*add_to_open) (int)、nodeptr(*find_least_f) (void)、void(*move_to_close) (nodeptr ptr)、void(*print_path) (nodeptr ptr)。2、程序流程(1)读取输入的城市距离的临界矩阵。(2)构造ttable,初始化调用ttable*table_constructor()函数申请空间将OPEN、CLOSE表设为NULL;(3)默认第一个城市A放到OPEN表将A城市标识设为-1表示在当前最短路径里A的层数设为1A的FHG值初始化为0更新最优路径临时指针指向A节点。(4)OPEN表F值最小的节点作为新的最优节点城市。搜索与最优节点相邻且不在当前最短路径里的城市放到OPEN表并将其父指针指向最优节点把此时的最优节点城市放到CLOSE表里。(5)判断最优路径临时指针是否指向前最优路径节点如果不同将最优路径临时指针指向当前最优节点并撤销旧的最优路径根据新的最优临时指针新建最优路径。(6)循环第四部直到最优路径上的节点数为城市数1。(7)输出最短路径析构ttable。四、实验结果分析(1)(2)(3)经过多种测试结果为最优解。五、程序清单#include #include#include#include#define MAX_INT 99999999typedef struct _node {int f;//f值int g;//g值int h;//h值int level;//第几次走到这个点(important)int parent;//父城市;int city;//city num;}node;typedef struct _list {struct _list *next;struct _list *pre;struct _list *parent;//父城市节点指针node city_node;}nodelist, *nodeptr;nodeptr _add_to_open(int);nodeptr _find_least_f();void_print_path(nodeptr ptr);void_move_to_close(nodeptr ptr);nodeptr _remove_from_open(nodeptr ptr);void_add_to_close(nodeptr ptr);typedef struct _ttable {struct _ttable *_this;//this 指针nodelist open;//open表,nodelist close;//close表,(仓库)//一些的操作nodeptr(*add_to_open)(int);nodeptr(*find_least_f)(void);void (*move_to_close) (nodeptr ptr);void (*print_path) (nodeptr ptr);}ttable;intmap[100][100];intb_path[100];//best_path;ttable *table NULL;ttable *table_constructor(){//构造一个table实体table (ttable *) malloc(sizeof(ttable));memset(table, 0, sizeof(ttable));table-open.next NULL;table-close.next NULL;table-open.city_node.parent -1;table-open.city_node.city -1;table-close.city_node.parent -1;table-close.city_node.city -1;table-add_to_open _add_to_open;table-find_least_f _find_least_f;table-move_to_close _move_to_close;table-print_path _print_path;table-_this table;return table;}void*table_destructor(ttable * table){//析构一个类if (table ! NULL) {nodeptr p table-_this-open.next;nodeptr q NULL;while (p) {q p-next;free(p);p q;}p table-_this-close.next;while (p) {q p-next;free(p);p q;}free(table);table NULL;}}nodeptr _add_to_open(int i){//添加到OPEN表//放在第一个位置nodeptr p NULL;p (nodeptr) malloc(sizeof(nodelist));memset(p, 0, sizeof(nodelist));if (p NULL) {return p;}p-next NULL;p-parent NULL;p-city_node.parent -1;p-city_node.city i;p-city_node.level 0;p-city_node.f 0;p-city_node.g 0;p-city_node.h 0;p-next table-_this-open.next;p-pre table-_this-open;if (table-_this-open.next){table-_this-open.next-pre p;}table-_this-open.next p;return p;}void_add_to_close(nodeptr ptr){//添加到close表ptr-next table-_this-close.next;ptr-pre table-_this-close;if (table-_this-close.next){table-_this-close.next-pre ptr;}table-_this-close.next ptr;}nodeptr _remove_from_open(nodeptr ptr){//从OPEN表中移除不删除ptr-pre-next ptr-next;if (ptr-next)ptr-next-pre ptr-pre;return ptr;}nodeptr _find_least_f(){//在OPEN表中找出最小的F节点int least MAX_INT;nodeptr p, q NULL;p table-_this-open.next;q p;while (p) {if (p-city_node.f least){q p;least p-city_node.f;}p p-next;}return q;}void_move_to_close(nodeptr ptr){//从OPEN移到CLOSE_remove_from_open(ptr);_add_to_close(ptr);}void_print_path(nodeptr ptr){//打印路径int least;if (ptr NULL)return;least ptr-city_node.f;printf(the best path is :);printf(A );ptr ptr-parent;while (ptr) {printf(%c , ptr-city_node.city 65);ptr ptr-parent;}printf(\nthe shortest length is %d\n, least);}intmain(){int num, min MAX_INT;int i, j, k, count;int tmpf, tmph, tmpg;ttable *table (ttable *) table_constructor();// 构造nodeptr ptr NULL, ptr_p NULL, ptr_c NULL;nodeptr l_ptr NULL; //the pointer of last best path;//input citydo {printf(请输入城市节点个数2scanf(%d, num);} while (num 99 || num 1);printf(\请输入节点之间的距离矩阵\n);for (i 0; i num; i) {for (j 0; j num; j) {scanf(%d, map[i][j]);if (i ! j min map[i][j]) {min map[i][j];}}}//最后回到Amap[num][num] map[0][0];for (i 0; i num; i) {map[num][i] map[0][i];map[i][num] map[i][0];}table-add_to_open(0);while (1) {ptr_p table-find_least_f();//当前最好节点,从最好节点回退肯定是最好路径table-move_to_close(ptr_p);//move to close table and save it;if (l_ptr l_ptr ! ptr_p) {//更新最好路径while (l_ptr ! NULL) {b_path[l_ptr-city_node.city] 0;l_ptr l_ptr-parent;}l_ptr ptr_p;while (l_ptr ! NULL) {b_path[l_ptr-city_node.city] 1;l_ptr l_ptr-parent;}}l_ptr ptr_p;for (i 0, count 0; i num; i) {if (b_path[i])count;}if (count num 1) {//all city in best path,A in twice:First And Last.break;}if (count num) {//left one,which ? Last A.Because we have never changed the valueof b_path[num].ptr_c table-add_to_open(num); //把它添加进开启列表中ptr_c-city_node.parent ptr_p-city_node.city;//把当前作为这的父节点ptr_c-city_node.level ptr_p-city_node.level 1; //他是父节点的下一层。ptr_c-parent ptr_p;ptr_c-city_node.g ptr_p-city_node.g map[num][ptr_p-city_node.city];//gptr_c-city_node.h min * (num -ptr_c-city_node.level);//hptr_c-city_node.f ptr_c-city_node.g ptr_c-city_node.h;//f} else {for (i 0; i num; i) {//对邻近的路径计算if (i ! ptr_p-city_node.city map[i][j] ! -1 ) {if (!b_path[i]) {//如果它不在最短路径中ptr_c table-add_to_open(i);//把它添加进开启列表中ptr_c-city_node.parent ptr_p-city_node.city;//把当前作为这的父节点ptr_c-city_node.level ptr_p-city_node.level 1; //他是父节点的下一层。ptr_c-parent ptr_p;ptr_c-city_node.g ptr_p-city_node.g map[i][ptr_p-city_node.city];//gptr_c-city_node.h min * (num -ptr_c-city_node.level);//hptr_c-city_node.f ptr_c-city_node.g ptr_c-city_node.h;//f}}}}}table-print_path(l_ptr);table_destructor(table);return 0;}
