寻找最小的电线连接

Question

问题

您在给定尺寸的板一个由一个。板上有n个组件，这些组件必须以尽可能短的导线长度连接到板的边缘。
电线是直的，不能重叠。

找到将这些约束连接到边缘的算法。

约束是：

时间：1秒
空间：无限
1 <= a <= 30
1 <= n <= 38

例：

输入：
4
3
2 1
2 3
3 3

输出：
5
下
上
上

---

我已经尝试过的

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

我有一个n位掩码，在1第i个位置代表我们考虑了此组件，而0没有考虑。

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

           111
     / | \
   / | \
  011101110
 / / / \ / \
001 010 001 100 010 100

当我达到最低水平时，我只有一个1。我找到了针对这个简单问题的最佳解决方案（最简单的方法），然后将其用于进一步的计算。

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

Answer 1

目前，我确实看不到比分支定界方法更好或更聪明的方法来解决这个问题。它在某种程度上与您提出的类似，但没有多余的计算。
这里将其简单描述为Python伪代码：

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 求解器提供的所有优化。