最短哈密顿回路 matlab

以下是一个求解最短哈密顿回路的 Matlab 代码示例：

% 输入邻接矩阵
adj_mat = [
    0 10 15 20;
    10 0 35 25;
    15 35 0 30;
    20 25 30 0
];

% 计算所有节点的排列组合
n = size(adj_mat, 1);
perms = perms(1:n);

% 初始化最短哈密顿回路的长度为无穷大
min_length = Inf;

% 遍历所有的排列组合
for i = 1:size(perms, 1)
    perm = perms(i,:);
    
    % 计算当前排列组合的哈密顿回路的长度
    length = 0;
    for j = 1:n-1
        length = length + adj_mat(perm(j), perm(j+1));
    end
    length = length + adj_mat(perm(n), perm(1)); % 回到起点
    
    % 如果当前哈密顿回路的长度小于最短长度，则更新最短长度
    if length < min_length
        min_length = length;
        shortest_path = perm;
    end
end

% 输出最短哈密顿回路的长度和路径
fprintf('Shortest Hamiltonian circuit length: %d\n', min_length);
fprintf('Shortest Hamiltonian circuit path: ');
fprintf('%d ', shortest_path);
fprintf('%d\n', shortest_path(1));

这个代码示例中，我们首先输入了一个邻接矩阵，表示有向带权图的边权情况。然后，我们使用 `perms` 函数计算出所有节点的排列组合，即可能的哈密顿回路的路径。接下来，我们遍历所有的排列组合，计算每个排列组合的哈密顿回路的长度，并更新最短长度和最短路径。最后，我们输出最短哈密顿回路的长度和路径。