algorithm - 找到最小的电线连接

Question

问题

a给你一块大小为 a的板子。板上有n 个组件，它们必须以尽可能短的电线连接到板的边缘。 电线是直的，不能重叠。

找到算法以使用这些约束将组件连接到边缘。

约束是：

时间：1s
空间：无穷大
1 <= a <= 30
1 <= n <= 38

例子：

输入：
4
3
2 1
2 3
3 3

输出：
5
下
向上
向上

---

我已经尝试过的

我发现了一种递归，让我用上面提供的数据来展示这个想法。

我有一个 n 位掩码，在1第 i 个位置表示，我们考虑这个组件，0而不考虑。

当我开始递归时，我有 n 个：

           111
     / | \
   / | \
  011 101 110
 / \ / \ / \
001 010 001 100 010 100

当我来到最低级别时，我正好有一个1。我为这个简单的问题找到了最佳解决方案（最短的方法），然后我将它用于进一步的计算。

但是，我有一个问题，即这种最佳解决方案可能会导致重叠。

标签： algorithmdynamic-programming

Answer 1

目前，我真的没有看到比分支和绑定方法更好或更聪明的方法来解决这个问题。它在某种程度上类似于您提出的建议，但没有多余的计算。
在这里，它被简要描述为一个 pythonic 伪代码：

def BnB(grid, components):
    queue = new_priority_queue()  # classic priority queue
    empty_sol = [None for i in range(len(components))]  # we create an 'empty' solution
    queue.push((0, 0, empty_sol))  # we push an initial empty solution on the queue (a tuple total len, index, solution)
    best_length_so_far = infinite # we keep track of the best solution seen so far
    best_sol_so_far = None
    while not queue.is_empty():
        length, index, solution = queue.pop()
        if index == len(components):  # it is a feasible solution
            if best_len_so_far > length:
                best_len_so_far = length
                best_sol_so_far = solution
        elif length < best_len_so_far:
           #  check if components[index] can have its wire 'DOWN'
           if can_put_wire(grid, components, index, 'DOWN'):
               length_to_add = path_len(grid, component, index, 'DOWN')
               new_sol = copy(solution)
               new_sol[index] = 'DOWN'
               queue.push((length + length_to_add, index + 1, new_sol))
           # do the same thing for the other directions
           if can_put_wire(grid, components, index, 'UP'):
               ....
           if can_put_wire(grid, components, index, 'LEFT'):
               ....
           if can_put_wire(grid, components, index, 'RIGHT'):
               ....
return best_sol_so_far

解决方案树的探索将取决于您如何设置队列中的优先级。选择要考虑的组件（而不是按照上面代码中的顺序排列它们）也有助于更快地获得解决方案。这不会是有效的（时间复杂度与组件的数量成指数），但它可以找到解决方案。

另一种可能性是使用ILP（整数线性规划）来解决问题。它可以很容易地用线性约束来描述，并且可以享受 LP 求解器提供的所有优化。