求助：将旅行商问题（TSP）递归解法转换为迭代形式

首先咱们先明确原递归代码的核心逻辑，这是理解问题的基础：

// 原递归TSP实现
int tsp(int mask, int pos, int n) {
    if (mask == VISITED_ALL) {
        return dist[pos][0]; // 回到起点的距离
    }
    int result = 2147483647;
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) == 0) { // i未被访问
            int new_result = dist[pos][i] + tsp(mask | (1 << i), i, n);
            result = min(result, new_result);
        }
    }
    return result;
}

这个递归的核心是每个状态(mask, pos)独立计算最短路径：当所有城市都访问过（mask全1），就返回当前城市回起点的距离；否则遍历所有未访问的城市，递归计算从该城市出发的最短路径，加上当前到该城市的距离，取最小值作为当前状态的结果。

你的迭代代码的核心问题 #

你尝试用栈模拟递归，但几个关键逻辑错了：

1. 用全局retVal存储所有子调用的返回值：递归中每个子调用的返回值是独立的，父调用需要收集每个子调用的结果来更新自己的result，但你用单个retVal会被后续子调用覆盖，导致结果混乱。
2. stage 1的遍历逻辑错误：你在stage 1重新遍历所有未访问的i，但无法对应到每个子调用的返回值，因为栈弹出的顺序是逆序的，你不知道当前retVal对应哪个i。
3. 终止条件的处理错误：当mask == VISITED_ALL时，你直接给retVal赋值，但这个结果需要返回给对应的父调用，而不是覆盖全局变量。
4. 没有跟踪当前处理的i索引：递归是逐个处理每个未访问的i，迭代时需要记录当前处理到哪个i，避免重复处理或遗漏。

修复后的迭代实现 #

我们需要修改结构体，让每个栈元素能跟踪自己的状态（当前处理的i、已计算的result、是否已处理子调用），同时让每个调用的结果能正确传递给父调用：

#include <stack>
#include <climits>
#include <algorithm>

// 定义全局的距离矩阵（和递归版一致）
int dist[100][100];
const int VISITED_ALL = (1 << 10) - 1; // 假设最多10个城市，可根据实际调整

struct TSPState {
    int mask;          // 已访问城市的掩码
    int pos;           // 当前所在城市
    int n;             // 城市总数
    int result;        // 当前状态的最短路径结果
    int current_i;     // 当前正在处理的未访问城市索引
    bool is_processed; // 是否已经处理过子调用（标记是第一次进入还是子调用返回后）
};

int tspIterative(int initial_mask, int initial_pos, int n) {
    std::stack<TSPState> stk;
    // 初始化初始状态：第一次进入，还没处理任何子调用，result设为最大值
    stk.push({initial_mask, initial_pos, n, INT_MAX, 0, false});
    
    // 用一个栈来存储每个调用的返回结果，栈顶对应当前子调用的返回值
    std::stack<int> result_stack;

    while (!stk.empty()) {
        TSPState curr = stk.top();
        stk.pop();

        if (!curr.is_processed) {
            // 情况1：第一次进入这个状态，先处理终止条件
            if (curr.mask == VISITED_ALL) {
                // 终止状态，计算返回值并压入结果栈
                int return_val = dist[curr.pos][0];
                result_stack.push(return_val);
                continue;
            }

            // 标记当前状态为已准备处理子调用，先压回栈
            curr.is_processed = true;
            stk.push(curr);

            // 逆序压入所有未访问的城市（因为栈是后进先出，逆序保证处理顺序和递归一致）
            for (int i = curr.n - 1; i >= 0; i--) {
                if (!(curr.mask & (1 << i))) {
                    int new_mask = curr.mask | (1 << i);
                    // 压入子调用状态：第一次进入，current_i从0开始，result设为最大值
                    stk.push({new_mask, i, curr.n, INT_MAX, 0, false});
                }
            }
        } else {
            // 情况2：子调用返回后，处理当前状态的result更新
            int sub_result = result_stack.top();
            result_stack.pop();

            // 计算当前i对应的路径长度
            int current_path = dist[curr.pos][curr.current_i] + sub_result;
            curr.result = std::min(curr.result, current_path);

            // 移动到下一个未访问的城市
            curr.current_i++;
            while (curr.current_i < curr.n) {
                if (!(curr.mask & (1 << curr.current_i))) {
                    // 还有未处理的子调用，压回当前状态，再压入下一个子调用
                    stk.push(curr);
                    int new_mask = curr.mask | (1 << curr.current_i);
                    stk.push({new_mask, curr.current_i, curr.n, INT_MAX, 0, false});
                    break;
                }
                curr.current_i++;
            }

            // 如果所有未访问城市都处理完了，把当前result压入结果栈，返回给父调用
            if (curr.current_i >= curr.n) {
                result_stack.push(curr.result);
            }
        }
    }

    // 最后结果栈的栈顶就是初始调用的返回值
    return result_stack.top();
}

修复逻辑的关键点 #

1. 双栈设计：用stk存储递归调用的状态，result_stack存储每个调用的返回结果，保证子调用的结果能正确传递给父调用。
2. 状态标记is_processed：区分第一次进入调用（需要触发子调用）和子调用返回后（需要更新当前结果）。
3. 跟踪current_i：记录当前处理到哪个未访问城市，避免重复遍历，确保每个子调用的结果都能对应到正确的i。
4. 逆序压入子调用：因为栈是后进先出，逆序压入未访问城市，保证处理顺序和递归的顺序一致，结果不会出错。

你可以用和递归版相同的测试用例来验证这个迭代版，比如3个城市的距离矩阵，应该能得到和递归版一致的结果。

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