贪婪算法求解TSP问题：

贪婪算法求解TSP问题：

贪婪算法（greedy algorithm）

贪心法，又称贪心算法、贪婪算法、或称贪婪法，是一种在每一步选择中都采起在当前状态下最好或最优（即最有利）的选择，从而但愿致使结果是最好或最优的算法。
贪心算法在有最优子结构的问题中尤其有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题可以分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 ios

TSP问题

旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中很是重要。c++

• 为了简化问题，这里使用数字来代替各点
• A——1
• B——2
• C——3
• D——4
• E——5

代码块

#include <iostream>
using namespace std;
#define n 5

int main()
{
    int dis[n][n];
    int i;
    //int k = 1;
    int index = 1;
    int l = 1;
    int max = 1000;
    int disSum = 0;
    int flag = 0;
    int c[n];
    int N = 4; 
    c[0] = 0;
    dis[0][1] = 2; dis[0][2] = 10; dis[0][3] = 5; dis[0][4] = 1;
    dis[1][0] = 2; dis[1][2] = 7; dis[1][3] = 8; dis[1][4] = 4;
    dis[2][0] = 10; dis[2][1] = 7; dis[2][3] = 3; dis[2][4] = 6;
    dis[3][0] = 5; dis[3][1] = 8; dis[3][2] = 3; dis[3][4] = 9;
    dis[4][0] = 1; dis[4][1] = 4;dis[4][2] = 6; dis[4][3] = 9;
    while(index < n)
    { 
        int k = 1;
        while(k < n && N >=0)
        {
            i = 0;
            while(i < l)
            {
                if(k == c[i])
                  { 
                      k = k+1;
                      flag = 1;
                      i = 0;
                  }
                else
                  { 
                      i = i+1;  
                      flag = 0;       
                  }
            }  
            if(flag == 0 && dis[c[index-1]][k] < max )  
            {
                max = dis[c[index-1]][k];
                c[index] = k;
                k = k+1;
                l = index+1;
            } 
            else// if(flag == 1 || dis[c[index-1]][k] > max)
            { 
                k = k+1;
            }    
        }        
    cout << "the distance between "<< c[index-1] << " and " << c[index] << " is " << max << "\n";  
    disSum = disSum + max;    
    index = index + 1;
    //k = 1;
    max = 1000;
    N = N-1;
    }    
    cout << "the first city is " << c[0] << "\n"; 
    for(int x = 1; x < n; x++)
    {
        printf("the next city is %d \n",c[x]);//cout << c[x] << " ";
    }
    cout << "the shortest diastance is " << disSum << "\n" ;
    system("pause");    
}