一、 问题描述
“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。
旅行商问题在本实验中的具体化：从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和H：
G = 未走的城市数×目前的最小距离；
未走的的城市数=（总城市数+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的层数设为1，A的F，H，G值初始化为0，更新最优路径临时指针指向A节点。
（4）OPEN表F值最小的节点作为新的最优节点城市。搜索与最优节点相邻且不在当前最短路径里的城市放到OPEN表，并将其父指针指向最优节点，把此时的最优节点城市放到CLOSE表里。
（5）判断最优路径临时指针是否指向前最优路径节点，如果不同，将最优路径临时指针指向当前最优节点，并撤销旧的最优路径，根据新的最优临时指针新建最优路径。
（6）循环第四部，直到最优路径上的节点数为城市数+1。
（7）输出最短路径，析构ttable。
四、 实验结果分析
（1）
（2）
（3）
经过多种测试，结果为最优解。
五、 程序清单
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <memory.h>
#define MAX_INT 99999999
typedef 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;
int map[100][100];
int b_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);
}
int main()
{
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 city
do {
printf("请输入城市节点个数：2=<节点个数<99\n");
scanf("%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];
}
}
}
//最后回到A
map[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 value of 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]; //g
ptr_c->city_node.h = min * (num - ptr_c->city_node.level); //h
ptr_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]; //g
ptr_c->city_node.h = min * (num - ptr_c->city_node.level); //h
ptr_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;
}
http://blog.sina.com.cn/s/blog_7587e3630100ptqx.html
评论