分支限界法圆排列

分支限界法可以用来解决圆排列问题。具体来说，可以采用深度优先搜索的方式，每一层搜索对应放置一个圆的决策，每个节点记录当前已经放置的圆和剩余空间，每次搜索时，优先考虑放置半径较大的圆，对于每个放置方案，计算当前圆排列的总长度，作为上界返回。当搜索到叶子节点时，记录当前的最优解，如果当前节点的上界小于最优解，则剪枝。此外，可以使用启发式函数对上界进行估计，以加速搜索。

下面是一个简单的 Matlab 代码实现：

function [opt_path, opt_val] = branch_bound_circle_arrangement(R)
% R：待排列的圆的半径，大小为 n×1 的向量
% opt_path：最优排列方案，大小为 n×1 的向量，表示每个圆的编号
% opt_val：最小圆排列距离

n = length(R);
path = zeros(n, 1); % 当前节点的决策向量
opt_path = []; % 最优排列方案
opt_val = inf; % 最小圆排列距离
queue = struct('path', path, 'val', 0, 'space', 1); % 优先队列
queue = [queue, queue, queue, queue, queue]; % 初始化队列
head = 1; % 队列头指针
tail = 5; % 队列尾指针

% 计算当前节点的上界
function bound = get_upper_bound(path, space)
    [~, idx] = sort(R, 'descend'); % 按半径从大到小排序
    i = 1;
    while space > 0 && i <= n
        if 2 * R(idx(i)) <= space
            space = space - 2 * R(idx(i));
        else
            bound = sum(path(1:i-1)) + space/R(idx(i)) + sum(R(idx(i:end))) + i - 1;
            return
        end
        i = i + 1;
    end
    bound = sum(path) + sum(R) + n - 1;
end

% 搜索队列中的节点
while head <= tail
    curr_node = queue(head);
    head = head + 1;
    
    if curr_node.val > opt_val % 更新最优解
        opt_path = curr_node.path;
        opt_val = curr_node.val;
    end
    
    if head > tail % 队列为空
        break
    end
    
    remain_R = R(~ismember(1:n, curr_node.path)); % 剩余圆的半径
    [~, idx] = sort(remain_R, 'descend'); % 按半径从大到小排序
    
    for i = 1:length(remain_R)
        if curr_node.space >= 2 * remain_R(idx(i)) % 可以放下
            next_node