Найти минимальное проводное соединение

Question

Задача

Вам предоставляется доска размером a от a .На плате есть n компонентов, которые должны быть подключены к краям платы с минимально возможной длиной проводов.
Провода прямые и не могут перекрываться.

Найдите алгоритм соединения компонентов с ребрами с этими ограничениями.

Ограничения: :

время: 1 с
пространство: бесконечность
1<= a <= 30 <br>1 <= n <= 38 <br>

Пример:

Input:
4
3
2 1
2 3
3 3

Output:
5
DOWN
UP
UP

---

То, что я уже пробовал

Я нашел своего рода рекурсию, позвольте мне показать идею с данными, приведенными выше.

У меня есть n-битовая маска, где 1 в i-й позиции означает, что мы учитываем этот компонент, а 0 нет.

Когда я начинаю рекурсию, у меня n единиц:

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

Когда я вышел на самый низкий уровень, у меня ровно один 1.Я нахожу оптимальное решение (кратчайший путь) для этой простой задачи, а затем просто использую его для дальнейших вычислений.

Однако у меня есть проблема, что это оптимальное решение может привести к перекрытию.

Answer 1

На данный момент я не могу увидеть что-то лучшее или более умное, чем ветвь и связанный подход к решению этой проблемы. Это как-то похоже на то, что вы предложили, но не имеет избыточных вычислений.
Здесь это кратко описывается как питонический псевдокод:

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.