一、

問題描述

“旅行商問題”常被稱為“旅行推銷員問題”，是指一名推銷員要拜訪多個地點時，如何找到在拜訪每個地點一次后再回到起點的最短路徑。規則雖然簡單，但在地點數目增多后求解卻極為復雜。

旅行商問題在本實驗中的具體化：從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

#include

#include

#include

#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=

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;

}

總結

以上是生活随笔為你收集整理的a算法TSP旅行商java_A*算法实现旅行商问题（人工智能报告，付代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。