anjilabibi
2016-12-15 13:27
采纳率: 100%
浏览 1.9k
已采纳

tsp问题求解,最临近法出问题。

我程序用最临近算法无法实现其功能,有没有善良的大佬帮我解决一下。非常感谢!!!

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • nades 2019-12-26 15:53
    已采纳

    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
    
    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • anjilabibi 2016-12-15 13:31

    #include "stdafx.h"

    include

    include

    include

    include

    define Max 11

    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;
    }
    

    }

    评论
    解决 无用
    打赏 举报
  • anjilabibi 2016-12-15 13:31

    程序如上,希望各位大佬能帮忙解决!

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题