用分支限界法实现圆排列问题 matlab

以下是用分支限界法实现圆排列问题的Matlab程序：

function [Vmin, Path] = MinCircleArrange(R, n)
% 输入：待排列的全部圆的半径R集合，圆的总数n
% 输出：最小圆排列距离Vmin，最优排列方案Path

% 1. 初始化
Vmin = inf; % 初始值为正无穷
Path = []; % 初始路径为空
ANode = zeros(n+1, n); % 初始化ANode
ANode(1,:) = 1:n; % 第一行填入1~n
ANode(n+1,:) = 1; % 最后一行填入1
AVal = zeros(1, n); % 初始化AVal
ABound = zeros(1, n); % 初始化ABound

% 2. 计算AVal和ABound
for j = 1:n
    AVal(j) = 2 * R(j);
    for i = 1:j-1
        AVal(j) = max(AVal(j), AVal(i) + 2*sqrt(R(i)*R(j)));
    end
    ABound(j) = AVal(j) + 2*sqrt(R(j)*(n-j));
end

% 3. 循环处理
while ~isempty(ANode)
    % 选择最小的ABound
    [minABound, loc] = min(ABound);
    X = ANode(1:n, loc); % 取出X
    k = ANode(n+1, loc);
    
    % 计算当前排列的距离
    if k == n % 叶结点
        tmpDist = R(X(1)) + R(X(n)) + 2*sqrt(R(X(1))*R(X(n)));
        if tmpDist < Vmin % 如果当前距离小于Vmin，则更新Vmin和Path
            Vmin = tmpDist;
            Path = X;
        end
    else % 非叶结点
        for i = setdiff(1:n, X(1:k))
            lb = AVal(k) + 2*sqrt(R(X(k+1))*R(i)) + 2*sqrt(R(i)*(n-k-1));
            if lb < Vmin % 可行结点
                ANode(:, end+1) = [X; i; k+1]; % 将[X; i; k+1]加入ANode
                AVal(end+1) = AVal(k) + 2*sqrt(R(X(k+1))*R(i)) + 2*R(i); % 计算对应的AVal
                ABound(end+1) = lb; % 将lb加入ABound
            end
        end
    end
    
    % 从ANode、AVal、ABound中删除对应的项
    ANode(:, loc) = [];
    AVal(loc) = [];
    ABound(loc) = [];
end

该算法是一种启发式搜索算法，通过计算代价函数，选择最有可能成为解的结点进行拓展，从而逐步逼近最优解。时间复杂度为O(n!)，但是由于剪枝的存在，实际计算量要比暴力枚举的方法小很多。