Путь маршрутизации минимальной длины — динамическое программирование

На линии есть 2 * N контактов, N из них входные контакты, N из них выходные контакты. Каждый входной контакт должен быть подключен к одному выходному контакту и наоборот, как на этом изображении:

введите здесь описание изображения

Линии соединения могут быть выполнены только вертикально и горизонтально в верхней полуплоскости, и линии соединения не могут перекрываться.

Вопрос в том, какой минимальной длины всех линий можно добиться при соединении всех выводов.

В приведенном выше примере длина равна 31.

Жадный подход с использованием стека, аналогичный задаче сопоставления скобок, не является оптимальным решением.


algorithm dynamic-programming greedy
person vasile_t    schedule 01.04.2016    source источник
comment
Домашнее задание? Вопрос интервью?   -  person Erick G. Hagstrom    schedule 01.04.2016
comment
Находятся ли входные и выходные контакты в фиксированных местах? В противном случае ответ, скорее всего, будет 3*N.   -  person user1952500    schedule 01.04.2016
comment
входные и выходные штифты находятся в фиксированных местах.   -  person vasile_t    schedule 02.04.2016
comment
Могут ли контакты соединяться в любом направлении? Имеется в виду, может ли 1 соединиться с 0 с левой стороны?   -  person גלעד ברקן    schedule 02.04.2016

Ответы (2)


arrow_upward
1
arrow_downward

Если вы посмотрите на крайнюю линию между 1 и 8, то она разбивает контакты на две группы. Один между 2 и 7, а другой между 9 и 10.

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

Это дает функцию lineLength(leftPin, rightPin, maxHeight), которая может получить свое значение, найдя высоту h и контакт i так, чтобы h <= maxHeight и pin[i] находились между leftPin+1 и rightPin и противоположным типом pin[leftPin].

Тогда длина строки будет rightPin-leftPin+2*h + lineLength(leftPin+1, i-1, h-1) + lineLength(i+1, rightPin-1, 5)

Для этой функции существует O(n^3) возможных значений, и вычисление каждого значения с запоминанием потребует O(n^2) времени из-за итераций h и i. Таким образом, общее время равно O(n^5).

Должна быть возможность улучшить это с помощью бинарного поиска на максимальной высоте.

person fgb    schedule 01.04.2016

arrow_upward
0
arrow_downward

Разделяй и властвуй может сократить это число до n^2.

В общем, первый пин должен быть с чем-то спарен — и единственные варианты его спаривания — когда строка пинов имеет четное количество входных и выходных битов. Таким образом, в примере № 1 может сочетаться с № 8 или № 10.

Для каждой из этих пар вы добавляете стоимость этого провода к подзадаче внутри провода и к подзадаче вне провода.

Например: если мы соединяем 1 и 8, то

cost = recursiveCost (2,7) + recursivecost(9,end) + wireCost(1,8)

Вам также потребуется отслеживать максимальную рекурсивную глубину вызова внутренней функции, потому что это потребуется для вычисления wireCost(a,b).

person Chris    schedule 01.04.2016
comment
Как бы вы отслеживали высоту в своей рекурсии? В примере OP (при условии, что соединения могут идти в любом направлении), соединение 3 с 6 будет означать разную высоту для более ранних вызовов функций, переменная, которая, по-видимому, зависит от конфигурации вложенности. - person גלעד ברקן; 02.04.2016
comment
Рекурсивный метод может возвращать свою глубину и свою стоимость в объекте-оболочке — например, в структуре или в каком-то классе — так что вызывающая сторона также может вычислить свою стоимость и добавить ее к глубине и т. д. - person Chris; 02.04.2016