导航:首页 > 计算方法 > tsp问题限界函数计算方法

tsp问题限界函数计算方法

 发布时间：2022-02-21 04:34:47

① TSP（旅行商问题）用分支限界法。用c语言写

#include <bits/stdc++.h>
using namespace std;
double graph[25][25];
int vis[25];
double a[25];
double ub;
double ans;
struct point {
int x;
int y;
}p[25];
double dis(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void dfs(int n, int x, double temp, int cnt)
{
// printf("%.2lf\n", temp);
if(cnt == n-2)
{
ub = min(ub, temp+graph[x][n-1]);
return ;
}
vis[x]=1;
for(int i=0; i<n-1; i++)
{
if(graph[x][i] && !vis[i])
{
temp += graph[x][i];
if(temp < ub)
dfs(n, i, temp, cnt+1);
temp -= graph[x][i];
vis[i]=0;

}
}

}
int main()
{
int t, n, x, y;
scanf("%d", &t);
while(t--)
{
int cnt=0;
ub=0x3f3f3f3f;
double temp=0;
memset(graph, 0, sizeof(graph));
memset(vis, 0, sizeof(vis));

scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
graph[i][j] = dis(p[i], p[j]);

vis[0]=1;
dfs(n,0,temp,0);
printf("%.2lf\n", ub);
}
return 0;
}

② 贪心算法TSP问题，有代码但是看不懂，求注释

int[] part = new int[3];//这里定义了3个int数组空间 { 0，1，2}

pat[1]=2;//数据的第二位设置为2

③ 急求tsp问题算法的源代码（c++）

将k=0,lb,x[1:n]=0存入PT
while(PT不为空)
{ 从PT中取出lb值最小元素
k=k+1;
for(i=1; i<=n; i++)
{ x[k]=i;
if(c[i][x[k-1]<+∞)
{ die=0;计算 lb ;
for(j=1; j<k; j++)
if (x[j]=x[k]) {die=1; break; }
if(die=0 and lb<up) 将k,lb,x[1:n]存入PT
}
}
if(k=n) { lb=c[x[1]][x[2]]+…+c[x[n-1]][x[n]]+c[x[1]][x[n]]
if (lb 是PT中最小值) 输出解,结束
else{ up=lb;删除 PT中lb>=up元素 }
}
}
哈哈，楼上对了

④ . 粒子群算法解决TSP问题的目标函数是什么

求得的路径长度。。越短越好

⑤ 遗传算法求解tsp问题的适应度值问题求城市间最短距离

把距离矩阵中每个值都缩小一定倍数

⑥ 粒子群算法解决TSP问题的目标函数是什么

function main()clc;clear all;close all;tic; %程序运行计时E0=0.001; %允许误差MaxNum=100; %粒子最大迭代次数narvs=1; %目标函数的自变量个数particlesize=30; %粒子群规模c1=2; %每个粒子的个体学习因子，也称为加速常数c2=2; %每个粒子

⑦ 用分支限界法求解TSP问题的C++代码（C的也可以），要完整的可以运行的源代码！！！

分支就用switch 要么就 用 if else if else if，，，，，

⑧ java人工蜂群算法求解TSP问题

一、人工蜂群算法的介绍

人工蜂群算法(Artificial Bee Colony, ABC)是由Karaboga于2005年提出的一种新颖的基于群智能的全局优化算法，其直观背景来源于蜂群的采蜜行为，蜜蜂根据各自的分工进行不同的活动，并实现蜂群信息的共享和交流，从而找到问题的最优解。人工蜂群算法属于群智能算法的一种。

二、人工蜂群算法的原理

1、原理

标准的ABC算法通过模拟实际蜜蜂的采蜜机制将人工蜂群分为3类: 采蜜蜂、观察蜂和侦察蜂。整个蜂群的目标是寻找花蜜量最大的蜜源。在标准的ABC算法中，采蜜蜂利用先前的蜜源信息寻找新的蜜源并与观察蜂分享蜜源信息；观察蜂在蜂房中等待并依据采蜜蜂分享的信息寻找新的蜜源；侦查蜂的任务是寻找一个新的有价值的蜜源，它们在蜂房附近随机地寻找蜜源。

假设问题的解空间是。

代码：

[cpp]view plain

  • #include<iostream>

  • #include<time.h>

  • #include<stdlib.h>

  • #include<cmath>

  • #include<fstream>

  • #include<iomanip>

  • usingnamespacestd;

  • constintNP=40;//种群的规模，采蜜蜂+观察蜂

  • constintFoodNumber=NP/2;//食物的数量，为采蜜蜂的数量

  • constintlimit=20;//限度，超过这个限度没有更新采蜜蜂变成侦查蜂

  • constintmaxCycle=10000;//停止条件

  • /*****函数的特定参数*****/

  • constintD=2;//函数的参数个数

  • constdoublelb=-100;//函数的下界

  • constdoubleub=100;//函数的上界

  • doubleresult[maxCycle]={0};

  • /*****种群的定义****/

  • structBeeGroup

  • {

  • doublecode[D];//函数的维数

  • doubletrueFit;//记录真实的最小值

  • doublefitness;

  • doublerfitness;//相对适应值比例

  • inttrail;//表示实验的次数，用于与limit作比较

  • }Bee[FoodNumber];

  • BeeGroupNectarSource[FoodNumber];//蜜源，注意：一切的修改都是针对蜜源而言的

  • BeeGroupEmployedBee[FoodNumber];//采蜜蜂

  • BeeGroupOnLooker[FoodNumber];//观察蜂

  • BeeGroupBestSource;//记录最好蜜源

  • /*****函数的声明*****/

  • doublerandom(double,double);//产生区间上的随机数

  • voidinitilize();//初始化参数

  • doublecalculationTruefit(BeeGroup);//计算真实的函数值

  • doublecalculationFitness(double);//计算适应值

  • voidCalculateProbabilities();//计算轮盘赌的概率

  • voidevalueSource();//评价蜜源

  • voidsendEmployedBees();

  • voidsendOnlookerBees();

  • voidsendScoutBees();

  • voidMemorizeBestSource();

  • /*******主函数*******/

  • intmain()

  • {

  • ofstreamoutput;

  • output.open("dataABC.txt");

  • srand((unsigned)time(NULL));

  • initilize();//初始化

  • MemorizeBestSource();//保存最好的蜜源

  • //主要的循环

  • intgen=0;

  • while(gen<maxCycle)

  • {

  • sendEmployedBees();

  • CalculateProbabilities();

  • sendOnlookerBees();

  • MemorizeBestSource();

  • sendScoutBees();

  • MemorizeBestSource();

  • output<<setprecision(30)<<BestSource.trueFit<<endl;

  • gen++;

  • }

  • output.close();

  • cout<<"运行结束!!"<<endl;

  • return0;

  • }

  • /*****函数的实现****/

  • doublerandom(doublestart,doubleend)//随机产生区间内的随机数

  • {

  • returnstart+(end-start)*rand()/(RAND_MAX+1.0);

  • }

  • voidinitilize()//初始化参数

  • {

  • inti,j;

  • for(i=0;i<FoodNumber;i++)

  • {

  • for(j=0;j<D;j++)

  • {

  • NectarSource[i].code[j]=random(lb,ub);

  • EmployedBee[i].code[j]=NectarSource[i].code[j];

  • OnLooker[i].code[j]=NectarSource[i].code[j];

  • BestSource.code[j]=NectarSource[0].code[j];

  • }

  • /****蜜源的初始化*****/

  • NectarSource[i].trueFit=calculationTruefit(NectarSource[i]);

  • NectarSource[i].fitness=calculationFitness(NectarSource[i].trueFit);

  • NectarSource[i].rfitness=0;

  • NectarSource[i].trail=0;

  • /****采蜜蜂的初始化*****/

  • EmployedBee[i].trueFit=NectarSource[i].trueFit;

  • EmployedBee[i].fitness=NectarSource[i].fitness;

  • EmployedBee[i].rfitness=NectarSource[i].rfitness;

  • EmployedBee[i].trail=NectarSource[i].trail;

  • /****观察蜂的初始化****/

  • OnLooker[i].trueFit=NectarSource[i].trueFit;

  • OnLooker[i].fitness=NectarSource[i].fitness;

  • OnLooker[i].rfitness=NectarSource[i].rfitness;

  • OnLooker[i].trail=NectarSource[i].trail;

  • }

  • /*****最优蜜源的初始化*****/

  • BestSource.trueFit=NectarSource[0].trueFit;

  • BestSource.fitness=NectarSource[0].fitness;

  • BestSource.rfitness=NectarSource[0].rfitness;

  • BestSource.trail=NectarSource[0].trail;

  • }

  • doublecalculationTruefit(BeeGroupbee)//计算真实的函数值

  • {

  • doubletruefit=0;

  • /******测试函数1******/

  • truefit=0.5+(sin(sqrt(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))*sin(sqrt(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))-0.5)

  • /((1+0.001*(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))*(1+0.001*(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1])));

  • returntruefit;

  • }

  • doublecalculationFitness(doubletruefit)//计算适应值

  • {

  • doublefitnessResult=0;

  • if(truefit>=0)

  • {

  • fitnessResult=1/(truefit+1);

  • }else

  • {

  • fitnessResult=1+abs(truefit);

  • }

  • returnfitnessResult;

  • }

  • voidsendEmployedBees()//修改采蜜蜂的函数

  • {

  • inti,j,k;

  • intparam2change;//需要改变的维数

  • doubleRij;//[-1,1]之间的随机数

  • for(i=0;i<FoodNumber;i++)

  • {

  • param2change=(int)random(0,D);//随机选取需要改变的维数

  • /******选取不等于i的k********/

  • while(1)

  • {

  • k=(int)random(0,FoodNumber);

  • if(k!=i)

  • {

  • break;

  • }

  • }

  • for(j=0;j<D;j++)

  • {

  • EmployedBee[i].code[j]=NectarSource[i].code[j];

  • }

  • /*******采蜜蜂去更新信息*******/

  • Rij=random(-1,1);

  • EmployedBee[i].code[param2change]=NectarSource[i].code[param2change]+Rij*(NectarSource[i].code[param2change]-NectarSource[k].code[param2change]);

  • /*******判断是否越界********/

  • if(EmployedBee[i].code[param2change]>ub)

  • {

  • EmployedBee[i].code[param2change]=ub;

  • }

  • if(EmployedBee[i].code[param2change]<lb)

  • {

  • EmployedBee[i].code[param2change]=lb;

  • }

  • EmployedBee[i].trueFit=calculationTruefit(EmployedBee[i]);

  • EmployedBee[i].fitness=calculationFitness(EmployedBee[i].trueFit);

  • /******贪婪选择策略*******/

  • if(EmployedBee[i].trueFit<NectarSource[i].trueFit)

  • {

  • for(j=0;j<D;j++)

  • {

  • NectarSource[i].code[j]=EmployedBee[i].code[j];

  • }

  • NectarSource[i].trail=0;

  • NectarSource[i].trueFit=EmployedBee[i].trueFit;

  • NectarSource[i].fitness=EmployedBee[i].fitness;

  • }else

  • {

  • NectarSource[i].trail++;

  • }

  • }

  • }

  • voidCalculateProbabilities()//计算轮盘赌的选择概率

  • {

  • inti;

  • doublemaxfit;

  • maxfit=NectarSource[0].fitness;

  • for(i=1;i<FoodNumber;i++)

  • {

  • if(NectarSource[i].fitness>maxfit)

  • maxfit=NectarSource[i].fitness;

  • }

  • for(i=0;i<FoodNumber;i++)

  • {

  • NectarSource[i].rfitness=(0.9*(NectarSource[i].fitness/maxfit))+0.1;

  • }

  • }

  • voidsendOnlookerBees()//采蜜蜂与观察蜂交流信息，观察蜂更改信息

  • {

  • inti,j,t,k;

  • doubleR_choosed;//被选中的概率

  • intparam2change;//需要被改变的维数

  • doubleRij;//[-1,1]之间的随机数

  • i=0;

  • t=0;

  • while(t<FoodNumber)

  • {

  • R_choosed=random(0,1);

  • if(R_choosed<NectarSource[i].rfitness)//根据被选择的概率选择

  • {

  • t++;

  • param2change=(int)random(0,D);

  • /******选取不等于i的k********/

  • while(1)

  • {

  • k=(int)random(0,FoodNumber);

  • if(k!=i)

  • {

  • break;

  • }

  • }

  • for(j=0;j<D;j++)

  • {

  • OnLooker[i].code[j]=NectarSource[i].code[j];

  • }

  • /****更新******/

  • Rij=random(-1,1);

  • OnLooker[i].code[param2change]=NectarSource[i].code[param2change]+Rij*(NectarSource[i].code[param2change]-NectarSource[k].code[param2change]);

  • /*******判断是否越界*******/

  • if(OnLooker[i].code[param2change]<lb)

  • {

  • OnLooker[i].code[param2change]=lb;

  • }

  • if(OnLooker[i].code[param2change]>ub)

  • {

  • OnLooker[i].code[param2change]=ub;

  • }

  • OnLooker[i].trueFit=calculationTruefit(OnLooker[i]);

  • OnLooker[i].fitness=calculationFitness(OnLooker[i].trueFit);

  • /****贪婪选择策略******/

  • if(OnLooker[i].trueFit<NectarSource[i].trueFit)

  • {

  • for(j=0;j<D;j++)

  • {

  • NectarSource[i].code[j]=OnLooker[i].code[j];

  • }

  • NectarSource[i].trail=0;

  • NectarSource[i].trueFit=OnLooker[i].trueFit;

  • NectarSource[i].fitness=OnLooker[i].fitness;

  • }else

  • {

  • NectarSource[i].trail++;

  • }

  • }

  • i++;

  • if(i==FoodNumber)

  • {

  • i=0;

  • }

  • }

  • }

  • 阅读全文

    与tsp问题限界函数计算方法相关的资料

    热点内容
    召唤电脑灵魂的方法 浏览：111
    马拉松训练方法讲解 浏览：421
    中国现代文学研究方法论集 浏览：416
    情感渗透的方法有哪些 浏览：749
    用牛尿洗头的正确方法 浏览：893
    抓羽毛球拍子正确方法 浏览：766
    三星显示器感应开关在哪里设置方法 浏览：938
    吸入硝酸怎么处理方法 浏览：618
    如何撩帅哥最有效的方法 浏览：768
    小型投资者最佳方法 浏览：500
    国内罗西尼自动手表如何调试方法 浏览：786
    装修支线的连接方法 浏览：747
    经常爱放屁有什么方法可以治疗吗 浏览：781
    浙江应变测量系统方法指南 浏览：172
    简单的折纸信封的方法 浏览：678
    可暖使用方法 浏览：444
    物理最基本的研究方法 浏览：85
    双元音最简单的方法 浏览：80
    素麻花的制作方法视频 浏览：566
    旅游失温的解决方法 浏览：345