动态规划求tsp最短路径matlab

TSP最短路径问题是一个经典的组合优化问题，可以用动态规划算法解决。下面是Matlab代码示例：

% 初始化
n = 4; % 城市数量
dist = [0, 2, 9, 10; 1, 0, 6, 4; 15, 7, 0, 8; 6, 3, 12, 0]; % 城市间距离矩阵
dp = zeros(2^n, n); % 动态规划数组
path = zeros(2^n, n); % 记录路径

% 初始化dp数组
for i = 1:2^n
    for j = 1:n
        dp(i, j) = Inf;
    end
end
dp(1, 1) = 0;

% 动态规划
for i = 1:2^n-1
    for j = 1:n
        if bitand(i, bitshift(1, j-1)) == 0 % 检查状态是否包含城市j
            for k = 1:n
                if bitand(i, bitshift(1, k-1)) ~= 0 % 检查状态是否包含城市k
                    if dp(i+2^(j-1), j) > dp(i+2^(k-1), k) + dist(k, j)
                        dp(i+2^(j-1), j) = dp(i+2^(k-1), k) + dist(k, j);
                        path(i+2^(j-1), j) = k;
                    end
                end
            end
        end
    end
end

% 回溯路径
p = 1;
for i = 2:n
    if dp(2^n-1, i) < dp(2^n-1, p)
        p = i;
    end
end
tsp_path = [p];
for i = 2:n
    tsp_path = [tsp_path path(bitshift(1, n)-1, tsp_path(end))];
end

% 输出结果
fprintf('最短路径长度为：%d\n', dp(2^n-1, p));
fprintf('最短路径为：%s\n', sprintf('%d ', tsp_path));

这段代码使用了二进制状态压缩的技巧，可以极大地减少计算量。其中，`bitand(i, bitshift(1, j-1))` 表示判断状态 `i` 是否包含城市 `j`，`dp(i+2^(j-1), j)` 表示状态 `i` 中包含城市 `j` 时的最短路径长度，`path(i+2^(j-1), j)` 记录从状态 `i` 转移到状态 `i+2^(j-1)` 时经过的最后一个城市。