回溯法解旅行商问题java,【算法作业】用回溯法求解旅行商问题

港控/mmm° 2023-01-13 06:13 190阅读 0赞

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼

\#include

\#include

\#define N 6

\#define MAX 10000

int bestc=MAX;

int cc=0;

int dis\[N+1\]\[N+1\]=\{0,0,0,0,0,0,0,

0,0,10,20,30,40,50,

0,12,0,18,30,25,21,

0,23,19,0,5,10,15,

0,34,32,4,0,8,16,

0,45,27,11,10,0,18,

0,56,22,16,20,12,0\};

int x\[N+1\];

int bestx\[N+1\];

void swap(int x\[N+1\],int i,int j)

\{

int a;

a=x\[i\];

x\[i\]=x\[j\];

x\[j\]=a;

\}

void backtrack(int i)

\{

int j;

if(i==N)

\{

if(dis\[x\[i-1\]\]\[x\[i\]\]

dis\[x\[i\]\]\[1\]

(bestc==MAX||cc+dis\[x\[i-1\]\]\[x\[i\]\]+dis\[x\[i\]\]\[6\]

\{

for(j=1;j<=i;j++)

bestx\[j\]=x\[j\];

bestc=cc+dis\[x\[i-1\]\]\[x\[i\]\]+dis\[x\[i\]\]\[6\];

\}

\}

else

\{

for(j=i;j<=N;j++)

if(dis\[x\[i-1\]\]\[x\[j\]\]

(bestc==MAX||cc+dis\[x\[i-1\]\]\[x\[j\]\]

\{

swap(x,i,j);

cc+=dis\[x\[i-1\]\]\[x\[i\]\];

backtrack(i+1);

cc-=dis\[x\[i-1\]\]\[x\[i\]\];

swap(x,i,j);

\}

\}

\}

int main()

\{

int i;

for(i=1;i<=N;i++)

\{

x\[i\]=i;

bestx\[i\]=i;

\}

backtrack(2);

printf("bestc=%d\\n",bestc);

for(i=1;i<=N;i++)

\{

printf("%d ",bestx\[i\]);

\}

getch();

return 0;

\}

/\*

int i,j;

for(i=0;i

\{

for(j=0;j

\{

printf("%3d ",dis\[i\]\[j\]);

\}

printf("\\n");

\}

\*/

发表评论取消回复

表情：

评论列表（有 0 条评论，190人围观）

还没有评论，来说两句吧...

相关阅读

相关实现旅行商问题算法（Java）

实现旅行商问题算法（Java）旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题，目标是找到一条最短路径，使得旅行商可以经过

淡淡的烟草味﹌/ 2023年10月15日 15:46/ 0 赞/ 67 阅读

相关算法__旅行商问题

1.问题定义 TSP问题（旅行商问题）是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。假设现在有四个城市，0,1,2,3

旧城等待，/ 2023年10月07日 12:33/ 0 赞/ 44 阅读

相关旅行商问题分析（分支限界法）

一、题目 ![1462891-20190923210503975-622218032.png][] 二、思路 1、dfs 实验要求用多种思路完

古城微笑少年丶/ 2023年08月17日 16:11/ 0 赞/ 136 阅读

相关旅行商问题 | 回溯：N排列（最小剪枝）

> 旅行推销员问题（TSP）：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。 > > 它是[组合优化][Link 1]中的一个[NP][

秒速五厘米/ 2023年03月13日 05:59/ 0 赞/ 2 阅读

相关回溯法解旅行商问题java,【算法作业】用回溯法求解旅行商问题

该楼层疑似违规已被系统折叠隐藏此楼查看此楼 \include \include \define N 6 \define MAX 10000 int bestc=MA

港控/mmm°/ 2023年01月13日 06:13/ 0 赞/ 191 阅读

相关粒子群算法求解旅行商问题

算法原理旅行商问题是一个经典的NP问题，假设有N个城市，需要确定一个访问顺序，使得每个城市都访问一面，最后回到起点城市，且保证行走的总距离最短。

客官°小女子只卖身不卖艺/ 2022年11月15日 06:25/ 0 赞/ 309 阅读

相关离散蚁群算法实例（求解旅行商问题）

蚁群算法蚁群算法原理 [万字长文带你了解蚁群算法及求解复杂约束问题【源码实现】][Link 1] 上面这篇博文的蚁群算法是实数编码。今天讲解

墨蓝/ 2022年10月16日 06:15/ 0 赞/ 273 阅读

相关算法设计与分析——回溯法——旅行售货员问题

include<iostream> include<bits/stdc++.h> using namespace std; const int

╰+攻爆jí腚メ/ 2022年10月15日 10:55/ 0 赞/ 433 阅读

相关模拟退火算法求解旅行商问题（python实现）

模拟退火算法求解旅行商问题 -------------------- 文章目录模拟退火算法求解旅行商问题一、模拟退火算法原理二、旅行商问题

刺骨的言语ヽ痛彻心扉/ 2022年10月08日 15:17/ 0 赞/ 290 阅读

相关 (C语言)分支界限法求解旅行商(TSP)问题

1.代码： include <stdio.h> include <malloc.h> define NoEdge 100

落日映苍穹つ/ 2022年09月17日 11:19/ 0 赞/ 252 阅读