【人工智能实验】蚁群算法解决TSP问题_蚁群算法解决tsp问题是人工智能的-程序员宅基地
定义了Point类忘了用了结果代码变成了粪山
其中涉及贪婪算法，轮盘赌法，以及看不懂自己写的什么了
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <time.h>
#include<fstream>
#include<sstream>
using namespace std;
//created by jzyghsh
#define MAXPATH 9999999
struct Point {
//city class
string name;
double x, y;
int num;
};
void init();
double distance(Point a, Point b);
double greedyPath(vector<Point> v);
bool isIn(string str, vector<string> list);
void nextCity();
int findNumOfCity(string name);
string RWS(vector<string> visitList);
void update();
int n;//city number
int m;//ant number
int alpha = 1, beta = 2;
double rou = 0.5;
vector<Point> cities;//city group (unchaged)
vector<vector<double>> dist;//distance list (unchaged)
vector<vector<double>> message;//message level on every road
vector<vector<string>> visitedCities;//abandon list
vector<double> p;
vector<double> C;
double minPath = FLT_MAX;
vector<string> bestPath;
int nextCityNum;
int main() {
#ifndef ONLINE_JUDGE
freopen("E:\\txts\\wi29.txt", "r", stdin);
#endif
int times = 0;
int i;
double difference = 0.0;
vector<int> count;
init();
while (times<=100) {
nextCity();
update();
times++;
}
nextCity();
cout << "共生成" << times * m << "只蚂蚁" << endl;
cout << "最终路径为：";
for (i = 0; i < bestPath.size(); i++) {
cout << bestPath[i] << "->";
}
cout << "最终路径长度为：" << minPath << endl;
return 0;
}
void nextCity() {
int i, j, k, begin, first;
string nextVisit;
int notVisit,nowVisit;
double up, pi, totalUp = 0, ci = 0;
C.clear();
for (i = 0; i < m; i++) {
notVisit = n - visitedCities[i].size();
ci = 0;
C.push_back(ci);
vector<string> visitList;
first = 0;
while (notVisit > 0) {
visitList.clear();//available visit list
totalUp = 0;
p.clear();
for (j = 0; j < n; j++) {
if (visitedCities[i].back() == cities[j].name) {
nowVisit = j;
if (first == 0) {
begin = j;
first = 1;
}
break;
}
}
for (j = 0; j < n; j++) {
if (!isIn(cities[j].name, visitedCities[i])) {
//cout << cities[j].name << "not in" << endl;
up = pow(message[nowVisit][j], alpha) * pow((1 / dist[nowVisit][j]), beta);//i有问题
totalUp += up;
p.push_back(up);
visitList.push_back(cities[j].name);
//cout << visitList.back() << " ";
}
}
//cout << endl;
//created by jzyghsh
//cout << p.size() << endl;
for (j = 0; j < p.size(); j++) {
p[j] /= totalUp;
}
nextVisit = RWS(visitList);
visitedCities[i].push_back(nextVisit);
//cout << "add" << visitList[nextVisit] << endl;
for (k = 0; k < n; k++) {
if (nextVisit == cities[k].name) {
nextCityNum = k;
}
}
C[i] += dist[nowVisit][nextCityNum];
//cout << cities[nowVisit].name << " " << cities[nextCityNum].name << endl;
notVisit--;
}
//cout << endl;
C[i] += dist[nextCityNum][begin];
//cout << cities[nextCityNum].name << " " << cities[begin].name << endl;
}
for (i = 0; i < m; i++) {
cout << "蚂蚁" << i << "爬过的路径为：";
visitedCities[i].push_back(visitedCities[i][0]);
for (j = 0; j < visitedCities[i].size(); j++) {
cout << visitedCities[i][j] << "->";
}
cout << "路径长度为：" << C[i] << endl;
if (C[i] < minPath) {
minPath = C[i];
bestPath = visitedCities[i];
}
}
}
string RWS(vector<string> visitList) {
//select a city
double q, area = 0, temp;
string t;
int i, j;
q = rand()/double(RAND_MAX);//0~1 double number
//cout << "q=" << q;
for (i = 0; i < visitList.size()-1; i++) {
for (j = i; j < visitList.size() - 1; j++) {
if (p[i] > p[i + 1]) {
temp = p[i];
p[i] = p[i + 1];
p[i + 1] = temp;
t = visitList[i];
visitList[i] = visitList[i + 1];
visitList[i + 1] = t;
}
}
}
for (i = 0; i < p.size(); i++) {
area += p[i];
if (q < area) {
//cout << "choose" << i << endl;
nextCityNum = i;
return visitList[i];
}
}
return visitList[0];
}
void update() {
int i, j;
int cityA = 0, cityB = 0;
for (i = 0; i < n; i++) {
// message fade
for (j = 0; j < n; j++) {
message[i][j] *= (1 - rou);
}
}
for (i = 0; i < m; i++) {
//message adding
for (j = 0; j < visitedCities[i].size()-1; j++) {
cityA = findNumOfCity(visitedCities[i][j]);
cityB = findNumOfCity(visitedCities[i][j + 1]);
message[cityA][cityB] += 1 / C[i];
//cout << cities[cityA].name << "to" << cities[cityB].name << endl;
}
//cout << endl;
}
for (i = 0; i < m; i++) {
//randomly put ants again
int ran;
visitedCities[i].clear();
ran = rand() % n;
visitedCities[i].push_back(cities[ran].name);
cout << "蚂蚁" << i << "初始在城市" << visitedCities[i].back() << endl;
}
}
int findNumOfCity(string name) {
int i;
for (i = 0; i < cities.size(); i++) {
if (name == cities[i].name) {
return i;
}
}
return NULL;
}
void init() {
int i = 0, j = 0;
double Cnn,t0;
cin >> n >> m;
for (i = 0; i < n; i++) {
Point p;
cin >> p.name >> p.x >> p.y;
p.num = i;
cities.push_back(p);
}
for (i = 0; i < n; i++) {
//init distance list
vector<double> v;
dist.push_back(v);
for (j = 0; j < n; j++) {
dist[i].push_back(distance(cities[i], cities[j]));
}
}
Cnn = greedyPath(cities);
t0 = m / Cnn;
cout << "用贪婪算法得到的初始路径长度为：" << Cnn << endl;
for (i = 0; i < n; i++) {
//init message list
vector<double> v;
message.push_back(v);
for (j = 0; j < n; j++) {
if (i != j) {
message[i].push_back(t0);
}
else {
message[i].push_back(0);
}
}
}
for (i = 0; i < m; i++) {
//randomly put ants
int ran;
vector<string> str;
ran = rand() % n;
str.push_back(cities[ran].name);
visitedCities.push_back(str);
str.clear();
cout << "蚂蚁" << i << "初始在城市" << visitedCities[i].back() << endl;
}
}
double distance(Point a,Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool isIn(string str,vector<string> list) {
int i = 0, length = list.size();
for (i = 0; i < length; i++) {
if (str == list[i]) {
return true;
}
}
return false;
}
double greedyPath(vector<Point> v) {
//greedy method get Cnn
double res = 0, nowPath, minPath;
int count = 0, begin, end;
int i = 0, j = 0;
vector<string> checked;
string choseCity;
int choseCityNum;
srand((unsigned)time(NULL));
begin = rand() % n;
end = begin;
checked.push_back(v[begin].name);
choseCityNum = begin;
while (count < v.size()-1) {
minPath = MAXPATH;
for (i = 0; i < n; i++) {
if (i != begin) {
nowPath = distance(v[begin], v[i]);
if (nowPath < minPath && !isIn(v[i].name,checked)) {
minPath = nowPath;
choseCity = v[i].name;
choseCityNum = i;
}
}
}
checked.push_back(choseCity);
begin = choseCityNum;
res += minPath;
count++;
}
checked.push_back(checked[0]);
cout << "贪婪算法路径为：";
for (i = 0; i < checked.size(); i++) {
cout << checked[i] << "->";
}
cout << endl;
res += dist[begin][end];
//cout << begin << " " << end;
return res;
}
智能推荐
Spring Security2的COOKIE的保存时间设置_springsecurity 设置cookie失效时间-程序员宅基地
文章浏览阅读1.3k次。http auto-config="true" access-denied-page="/common/403.htm"> intercept-url pattern="/login.**" access="IS_AUTHENTICATED_ANONYMOUSLY"/> form-login login-page="/login.jsp" defau_springsecurity 设置cookie失效时间
view滑动冲突解决实战篇2（外部拦截法）_viewpage2外部拦截事件-程序员宅基地
文章浏览阅读1.1k次。继上篇内部拦截法需求还是跟上篇一样。只不过这次用外部拦截法来解决；只要在父容器添加如下代码就可以解决了滑动冲突，很简单，套模板就行 // 分别记录上次滑动的坐标(onInterceptTouchEvent) private int mLastXIntercept = 0; private int mLastYIntercept = 0; @Override public bo_viewpage2外部拦截事件
汇编 堆栈 变量存储 指针_汇编语言栈指针-程序员宅基地
文章浏览阅读2.5k次，点赞7次，收藏9次。本文章系作者原创，未经许可，不得转载。汇编 堆栈 变量存储 指针先说栈的概念，栈其实也是一种。。。。。先说内存的概念吧。。。。。额 先说计算机吧，简单来说的话，可以把计算机理解成由CPU，内存，硬盘组成，而CPU内部又包括一种叫做内部寄存器的东西，包括 数据寄存器： AX,BX,CX,DX； 段寄存器： CS,DS,ES,SS； 指针与变址寄存器SP,BP,SI,DI； ..._汇编语言栈指针
架构师之路：从码农到架构师你差了哪些_web架构师-程序员宅基地
文章浏览阅读1w次，点赞14次，收藏56次。转载自 架构师之路：从码农到架构师你差了哪些 Web应用，最常见的研发语言是Java和PHP。 后端服务，最常见的研发语言是Java和C/C++。 大数据，最常见的研发语言是Java和Python。 可以说，Java是现阶段中国互联网公司中，覆盖度最广的研发语言，掌握了Java技术体系，不管在成熟的大公司，快速发展的公司，还是创业阶段的公司，都能有立足之地。有..._web架构师
js sort排序_sort a<b-程序员宅基地
文章浏览阅读103次。/* 排序 >号 从小到大排序 <从大到小排序 */ list.sort(function(a, b) { return a.date < b.date ? 1 : -1; })如果是简单的list就直接 return a < b ? 1 : -1;即可，如果是list里面套的map，可让list按map里面的指定字段进行排揎。..._sort a
前端设置条件限制form表单提交到后端解决方案_jsp前端页面将表单是否提交成功作为限制条件-程序员宅基地
文章浏览阅读375次。<script src="js/jquery-1.8.3.min.js" type="text/javascript"></script> <script type="text/javascript"> function checkName() { var name = document.getElementB..._jsp前端页面将表单是否提交成功作为限制条件
随便推点
生成随机数_<math.h>随机数-程序员宅基地
文章浏览阅读1.5k次。C语言中有可以产生随机数据的函数，需要添加 stdlib. h头文件与time.h头文件。首先在main函数开头加上“ srand(unsigned)time(NULL));"，这个语句将生成随机数的种子(不懂也没关系，只要记住这个语句，并且知道 srand是初始化随机种子用的即可)。然后，在需要使用随机数的地方使用 rand()函数。下面是一段生成十个随机数的代码：程序代码：#incl..._随机数
Z-Blog编辑器支持ppt导入-程序员宅基地
文章浏览阅读47次。图片的复制无非有两种方法，一种是图片直接上传到服务器，另外一种转换成二进制流的base64码目前限chrome浏览器使用首先以um-editor的二进制流保存为例：打开umeditor.js，找到UM.plugins['autoupload']，然后找到autoUploadHandler方法，注释掉其中的代码。加入下面的代码：//判断剪贴板的内容是否包含文本//首先解释一下为什么要判断文本是不是为空//在ctrl+c word中的文字或者图片之后会返回1种(image/png)或者4种t
基于Unity3D的相机功能的实现（六）—— 上帝视角（王者荣耀视角）_unity overlook-程序员宅基地
文章浏览阅读4k次，点赞2次，收藏15次。在MOBA游戏中，上帝视角是一个很实用的功能。_unity overlook
用mac的chrome浏览器调试Android手机的网页-程序员宅基地
文章浏览阅读2.5k次，点赞2次，收藏2次。一、参考链接read chrome remote debugging documentation调出开发者选项二、设置android在安卓4.2及更新的版本中，默认情况下，【开发者选项】是隐藏的。要启用【开发者选项】，设置 -> 关于手机 -> 版本号，对着版本号点击7次。设置 -> 开发者选项 -> USB调试三、连接手机和电脑..._小米13链接mac chrome inspect
树莓派GPIO简单操作_树莓派怎么读取gpio口上的信息-程序员宅基地
文章浏览阅读637次。树莓派的GPIO操作被抽象为文件读写，下面以一个例子来说明GPIO操作。_树莓派怎么读取gpio口上的信息
【汽车电子】浅谈车载系统QNX_车机qnx虚拟化软件系统架构-程序员宅基地
文章浏览阅读1.7k次。QNX是一种商用的遵从POSIX规范的类Unix实时操作系统，目标市场主要是面向嵌入式系统。它可能是最成功的微内核操作系统之一。QNX是一种商用的类Unix实时操作系统，遵从POSⅨ规范，目标市场主要是嵌入式系统[1]。QNX成立于1980年，是加拿大一家知名的嵌入式系统开发商。QNX的应用范围极广，包含了：控制保时捷跑车的音乐和媒体功能、核电站和美国陆军无人驾驶Crusher坦克的控制系统[2]，还有RIM公司的BlackBerry PlayBook平板电脑。_车机qnx虚拟化软件系统架构