[프로그래밍 연습] TSP 문제와 최단 경로

TSP 폭력 매거법: 이 방법은 도시 개수 >8에 적합하지 않습니다.시간 복잡도 승급 상승

#include 
#include 
#include 
using namespace std;
#define maxx 9999
int l[maxx][maxx];//           
int n;//    
int min_l = maxx;//    
int sum[maxx];//            
int go_city;//    go_city     
int visited[maxx]; // i       ：visited[i]=1;    visited[i]=0;
int path_index = 1; //         。
int path[maxx][maxx];//         
int route = 0;//       
int recursion(int index)
{
    if(path_index != n)
    {
        for(int i=1;i <= n;i++)
        {
            if(visited[i] == 0)
            {
                visited[i] = 1;
                path[route][path_index] = index;
                path_index++;
                recursion(i);
                //  
                path_index--;
                visited[i] = 0;
            }
        }
    }
    else
    {
        //                 （          ）
        path[route][path_index] = index;
        path[route][path_index + 1] = go_city;
        //            ,     
        printf("  %d ：
",route+1);
        sum[route] = 0;
        for(int i=1;i<=n;i++)
        {
            sum[route] += l[ path[route][i] ][ path[route][i+1] ];
            cout << path[route][i] << " --> ";
            // route+1 ，path[route][i]       ，    。
            path[route+1][i] = path[route][i];
        }
        if(min_l > sum[route])
        {
            min_l = sum[route];
        }
        cout << path[route][n+1] << endl;
        cout << "       ： " << sum[route] << endl;
        route++;
    }
    return 0;
}

int main()
{
    memset(visited,0,sizeof(visited));
    cout << "       ：";
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            printf("   %d    %d        :",i,j);
            cin >> l[i][j];
            l[j][i] = l[i][j];
        }
    }
    cout << "               ：";
    cin >> go_city;
    visited[go_city] = 1;
    recursion(go_city);
    cout << "       : ";
    cout << min_l << endl;
    return 0;
}

동적 기획법

#include 
#include 
#include 
#define maxx 10000
using namespace std;
int n;//    
int l[maxx][maxx];//       
int dp[maxx][maxx];//dp 
int menthod()
{
	//      
	for (int i = 0; i < n; i++)
	{
		dp[i][0] = l[i][0];
	}
	//      
	for (int j = 1; j < 1 << (n - 1); j++)
	{
		for (int i = 0; i < n; i++)
		{
			dp[i][j] = 0x7ffff; //     
			//         j，     ， continue
			if (j >> (i - 1) & 1)
			{
				continue;
			}
			for (int k = 1; k < n; k++)
			{
				//             k  ，    k   continue
				if ((j >> (k - 1) & 1) == 0)
				{
					continue;
				}
				//  dp[i][j]    ，(l[i][k] + dp[k][j ^ (1 << (k - 1))         
				if (dp[i][j] > (l[i][k] + dp[k][j ^ (1 << (k - 1))]))
				{
					dp[i][j] = l[i][k] + dp[k][j ^ (1 << (k - 1))];
				}
			}
		}
	}
	return 0;
}

int main()
{
	memset(dp, 0, sizeof(dp));
	cout << "       ：";
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			printf("     %d       %d         ：", i, j);
			cin >> l[i][j];
			l[j][i] = l[i][j];
		}
	}
	menthod();
	cout << "     ： " << dp[0][(1 << (n - 1))-1] << endl;
	return 0;
}

TSP 문제를 해결하는 유전 알고리즘도 있습니다. 자세한 내용은 이 블로그를 참조하십시오.https://blog.csdn.net/weixin_44611644/article/details/95016984
최단 경로 문제 (1) 모든 점에서 점까지의 원리: 가장자리를 느슨하게 하고 v1에서 v3까지의 거리가 v1에서 v2+v2에서 v3보다 크면 v1-v3의 최소값을 업데이트합니다.즉, v1에서 v3까지의 거리는 v2라는 점을 통해 업데이트할 수 있다.Floyd:

int i,j,k;
for(k=0;k

o (n^3) 모든 결점 사이의 가장 짧은 경로 길이를 얻을 수 있습니다.핵심 코드는 위와 같습니다. 인접 행렬의 초기화와 초기 값의 대수 문제를 주의하십시오.
단원 최단로 - 디제스트라는 모두 n개의 점을 가정하면 점 x에서 나머지 n-1개의 최단로를 구할 수 있다.원리가 유사하다.현재 점에서 가장 가까운 점을 꺼낼 때마다 인접점을 이용하여 디스 그룹을 업데이트합니다.최종적으로 디스 그룹이 저장한 값은 결점 0에서 나머지 결점까지의 가장 짧은 거리를 대표한다.

#include
#include
#include
using namespace std;
const int MAX=0x3f3f3f3f;
int map[110][110];
int dis[110];
int visit[110];
/*
      ：map          ，  map[1][2]=3，  1   2      3
dis                 ，  dis[3]=5，      3       5
visit     0  1，1         。
*/
int n,m;
int dijkstra()
{
    int i,j,pos=1,min,sum=0;
    memset(visit,0,sizeof(visit));//    0，        
    for(i=1; i<=n; i++)
    {
        dis[i]=map[1][i];
    }
    visit[1]=1;
    dis[1]=0;
    int T=n-1;
    while(T--)
    {
        min=MAX;
        for(j=1; j<=n; j++)
        {
            if(visit[j]==0&&min>dis[j])
            {
                min=dis[j];
                pos=j;
            }
        }
        visit[pos]=1;//         
        for(j=1; j<=n; j++)
        {
            if(visit[j]==0&&dis[j]>min+map[pos][j])//  dis  
                dis[j]=map[pos][j]+min;
        }
    }
    return dis[n];
}
int main()
{
    int i,j;
    while(cin>>n>>m)//n  n  ，m  m  
    {
        memset(map,MAX,sizeof(map));
        int a,b,c;
        for(i=1; i<=m; i++)
        {
            cin>>a>>b>>c;
            if(c