旅行商问题动态规划递归代码可计算最小成本，如何获取对应最优路径

你已经定义了类成员path数组，不需要新增额外数组，仅需要在递归函数的两个逻辑节点补充路径写入逻辑即可，同时先修复你现有代码的一个越界bug：你初始化cities数组时申请了size长度的空间，但循环条件写了i<size+1，会发生数组越界，先修正这部分。

核心修改逻辑 #

• 递归终止（level == 0）时，已经遍历完所有待访问城市，当前city是最后一个到访的城市，直接在这个分支写入路径的最后两段：最后一个访问城市 + 起点
• 每次遍历子路径得到更小的总成本时，除了更新最小成本，同时把当前选择的下一站城市写入path对应层级的位置，递归返回时深层路径已经由子调用写入完成，无需额外操作

修改后完整代码 #

void Dynamic::dynamic(Array array)
{
    int start;
    size = array.getSize();
    s = size;
    path = new int[size+1]; // 路径长度是size+1，最后回到起点
    
    cout << "Which city we start from?" << endl;
    cin >> start;
    int* cities = new int[size];
    // 修复原代码越界问题：数组长度为size，i最大到size-1
    for (int i=0; i<size; i++)
    {
        cities[i] = i;
    }
    
    int cost = g(array, size-1, cities, start, start, s);
    
    cout<<"Minimum cost: " << cost << endl;
    cout << "Path:" <<endl;
    
    // 原逻辑是倒序输出，和我们写入的顺序匹配
    for (int i=size; i>=0; i--)
    {
        cout << path[i] << "\t";
    }
    // 补充内存释放逻辑，避免泄漏
    delete[] cities;
    cout << "\n";
}

int Dynamic::g(Array & array, int level, int* tab, int city, int start, int z)
{
    if (level>0)
    {
        int minimum = INF;
        int position;
        bool exists = false;
        int k = z;
        int best_next = -1; // 记录当前最优的下一站城市
    
        for (int i=0; i<z; i++)
        {
            if (tab[i] == city)
            {
                position = i;
                exists = true;
            }
        }
        
        int* tmp;
        if (exists == true)
        {
            k = z-1;
            tmp = new int [k];
            for (int i=0; i<position; i++)
            {
                tmp[i] = tab[i];
            }
            for (int i=position; i<k; i++)
            {
                tmp[i] = tab[i+1];
            }
        }
        else
        {
            tmp = new int [k];
            for (int i=0; i<k; i++)
            {
                tmp[i] = tab[i];
            }
        }
    
        for (int i=0; i<k; i++)
        {
            int c = array[city][tmp[i]];
            int* t = new int [k-1];
            for(int j=0; j<i; j++)
            {
                t[j] = tmp[j];
            }           
            for (int j=i; j<k-1; j++)
            {
                t[j] = tmp[j+1];
            }
            
            int a = g(array, level-1, t, tmp[i], start, k-1);
            int result = c + a;
            
            if (minimum > result)
            {
                minimum = result;
                best_next = tmp[i]; // 记录当前最优下一站
            }
            // 释放临时数组内存，避免泄漏
            delete[] t;
        }
        // 找到最优下一站后写入path对应位置
        if (best_next != -1)
        {
            path[level + 1] = best_next;
        }
        // 释放临时数组内存
        delete[] tmp;
        return minimum;
    }
    if (level == 0)
    {
        // 最后一个访问城市写入path[1]，起点写入path[0]
        path[1] = city;
        path[0] = start;
        return array[city][start];
    }
    return INF; // 异常分支返回极大值
}

额外优化建议 #

你现有代码中多次申请的临时数组tmp、t都没有释放，会产生内存泄漏，上述修改代码中已经补充了对应的delete[]释放逻辑。

内容的提问来源于stack exchange，提问作者czesiek