我程序用最临近算法无法实现其功能,有没有善良的大佬帮我解决一下。非常感谢!!!
public static List sortPoint(char result[], int k){
String s = "";
if(k==result.length){
for(int i=0;i<result.length;i++){
s += result[i];
}
list.add(s);
return list;
}
for(int i=k;i<result.length;i++){
//交换
{char t = result[k];result[k] = result[i];result[i] = t;}
//递归,下一个数去排列
sortPoint(result,k+1);
//再归位数据
{char t = result[k];result[k] = result[i];result[i] = t;}
}
return list;
}
这是链接 https://blog.csdn.net/Naide_S/article/details/103714447
#include "stdafx.h"
int cn, tt, start; // 要经过的城市个数,,起点
double arry1[Max][Max]; // 邻接矩阵,存放两两城市间的距离
double fn = 0, gn = 0, hn = 0; // 启发函数
double f1 = 0, g1 = 0, h1 = 0;
int arry3[Max]; // 存放已历经的城市名
int arry4[Max]; // 标志位数组,cn个城市中已历经的置,未历经的置
// 定义顶点数据类型
struct Vertex
{
int x;
int y;
}City[Max];
///////////////////////////////////////////////////////////////////////////////////////////
// 主函数
void main()
{
void RandNum(int);
void CityCoordinate();
double CityCost(int, int);
void TSP();
double MaxLengh();
int i, j;
CityCoordinate(); // 随机生成并显示个城市及其坐标
printf("\n");
printf("\n");
for (i = 1; i<Max; i++) // 随机生成并显示表示两城市间距离的邻接矩阵
{
tt = 0;
for (j = i; j<Max; j++, tt++)
{
if (i == j) arry1[i][j] = 0;
else arry1[i][j] = CityCost(i, j);
}
}
TSP(); // 用最小生成树查找最短路径
printf("\n从%d出发的最佳路径为:%d→", start, start);
for (i = 2; i <= cn; i++) printf("%d→", arry3[i]);
printf("%d\n", arry3[cn + 1]);
printf("总路径长度为:%f\n", fn);
}
///////////////////////////////////////////////////////////////////////////////////////////
// 随机数产生器
int RandNum(int max)
{
int m;
m = rand() % (max - 1) + 1; // 产生一个~20的随机数
return m;
}
// 生成并显示城市坐标
void CityCoordinate()
{
int i, j, hh = 0;
srand((unsigned)time(NULL)); // 使用当前时间作为种子
City[1].x = RandNum(Max); // 生成并显示第个城市的坐标
City[1].y = RandNum(Max);
printf("City[1]的坐标: (%d,%d); ", City[1].x, City[1].y);
for (i = 2; i<Max; i++) // 生成第~10个城市的坐标
{
City[i].x = RandNum(Max);
City[i].y = RandNum(Max);
for (j = 1; j<i; j++) // 检查重合坐标,有重合时重新生成
if (City[i].x == City[j].x&& City[i].y == City[j].y)
i = i - 1;
hh++; // 换行
if (0 != i % 2) hh = 0;
if (0 == hh) printf("\n");
printf("City[%d]的坐标: (%d,%d); ", i, City[i].x, City[i].y);// 显示第i个城市的坐标
}
}
// 计算并显示城市间的欧式距离
double CityCost(int i, int j)
{
int x1, x2, y1, y2, hh = 0;
double Distance, t;
x1 = City[i].x;
x2 = City[j].x;
y1 = City[i].y;
y2 = City[j].y;
t = (x1 - x2)* (x1 - x2) + (y1 - y2)* (y1 - y2);
Distance = sqrt(t);
arry1[i][j] = Distance;
hh++;
if (0 != tt % 2) hh = 0; // 换行
if (0 == hh) printf("\n");
printf("%d与%d的距离:%3.2f ", i, j, Distance);
return arry1[i][j];
}
// 用最邻近法找最短路径
void TSP(){
int Mnode; // 起点,当前搜索层的父节点
int h, i, k, l, m, j;
double min;
int x, y = 0;
int arry2[Max] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };;// 标志位数组,已历经的置0,未历经的置1
double temp1 = 100, temp2 = 100;
printf("\n请输入要经过的城市个数:");
scanf_s("%d", &cn);
printf("\n");
printf("请输入要历经的城市:\n");
for (h = 1; h <= cn; h++) // 输入历经节点
{
scanf_s("%d", &x);
if (0 == arry2[x]) arry2[x] = 1; // 避免重复
else if (1 == arry2[x]) h = h - 1;
}
printf("\n");
for (i = 1; i<Max; i++) // 显示历经节点
if (1 == arry2[i])
printf("%d ", i);
printf("\n");
printf("请输入出发城市:"); // 输入出发点
scanf_s("%d", &start);
printf("\n");
arry2[start] = 0; // 初始化
arry3[1] = start;
arry3[cn + 1] = start; //首尾端点一致
Mnode = arry3[1];
////////////////////////////////////////寻找最近的点
for (k = 1, l = 1; k < Max&&arry2[k] == 1; k = m){
for (j = 1; j < Max; j++){
if (arry2[j] == 1 && j != k) {
min = arry1[k][j];
if (arry1[k][j] <= min){
min = arry1[k][j];
m = j;
arry3[++l] = j;
}
}
}
fn += min;
}
}
程序如上,希望各位大佬能帮忙解决!