### Goldstein分支切割算法代码实现 Goldstein分支定界法是一种用于解决组合优化问题的有效方法。该算法通过系统地探索解空间树来寻找最优解，同时剪枝不可能包含更优解的子树。 下面是一个简单的Python实现示例： ```python import numpy as np def goldstein_branch_and_bound(objective_function, lower_bounds, upper_bounds, tolerance=1e-6): """ 使用Goldstein分支定界法求解最小化问题 参数: objective_function (callable): 定义的目标函数 f(x)，返回浮点数 lower_bounds (list or array-like): 变量下限列表 upper_bounds (list or array-like): 变量上限列表 tolerance (float): 终止条件精度，默认为 1e-6 返回: tuple: 最优点坐标及其对应的最低目标值 """ class Node: def __init__(self, bounds, estimate=None): self.bounds = bounds self.estimate = estimate if estimate is not None else float('inf') root_node = Node(list(zip(lower_bounds, upper_bounds))) best_solution = None node_queue = [root_node] while node_queue: current_node = min(node_queue, key=lambda n: n.estimate) # 如果当前节点估计优于已知最佳，则更新之 if best_solution is None or current_node.estimate < objective_function(best_solution): best_solution = [(lb + ub) / 2 for lb, ub in current_node.bounds] new_nodes = [] # 对每个维度尝试分割区间 for i, ((lbound, rbound), lbest, rbest) in enumerate( zip(current_node.bounds, [objective_function([*best_solution[:i], lbound, *best_solution[i+1:]])], [objective_function([*best_solution[:i], rbound, *best_solution[i+1:]])] ) ): mid_point = (rbound + lbound) / 2 left_child_est = max(lbest, objective_function([*best_solution[:i], mid_point, *best_solution[i+1:]])) right_child_est = max(rbest, objective_function([*best_solution[:i], mid_point, *best_solution[i+1:]])) if abs(left_child_est - right_child_est) > tolerance: new_nodes.append(Node([ (*current_node.bounds[:i], (lbound, mid_point)), *(current_node.bounds[i+1:]) ], left_child_est)) new_nodes.append(Node([ (*current_node.bounds[:i], (mid_point, rbound)), *(current_node.bounds[i+1:]) ], right_child_est)) node_queue.remove(current_node) node_queue.extend(new_nodes) return best_solution, objective_function(best_solution) if __name__ == "__main__": # 测试用例：二次多项式极小化 test_objective_func = lambda x: sum((xi ** 2 for xi in x)) dims = 5 lbs = [-5]*dims ubs = [5]*dims solution, value = goldstein_branch_and_bound(test_objective_func, lbs, ubs) print(f"找到的最佳解是 {solution} ，其对应的目标函数值为 {value}") ``` 此段代码实现了基于Goldstein原则的分支定界框架，并应用于多维连续变量上的简单凸优化问题上作为示范[^1]。