Software & Systems

Задача о назначениях относится к числу немногих дискретных оптимизационных задач, для которых известны точные алгоритмы решения с полиномиальной временной сложностью. Тем не менее при больших размерностях задачи (n³1000) время счета алгоритма становится неприемлемым, особенно при итеративном его использовании. В работе рассматриваются альтернативные подходы к решению задачи о назначениях: использование методов аппроксимации и использование ограничений на значения элементов матрицы.

Точный алгоритм решения задачи о назначениях

Традиционная формулировка задачи о назначениях такова.

Пусть имеется квадратная матрица a= порядка n.

Решением задачи о назначениях для этой матрицы называется такой набор из n элементов матрицы (по одному в каждой строке и каждом столбце), что сумма этих элементов минимальна по всем наборам.

В работе [1] предложен эффективный алгоритм решения данной задачи с временной вычислительной сложностью O(n3).

Идея алгоритма заключается в следующем.

Определение. Пусть имеется некоторый вектор D=(D1, …, Dn). Элемент называется D-минимальным, если aij - Dj £ aik - Dk для всех k, 1£ k£ n.

Лемма. Пусть для некоторого D имеется набор из n D-минимальных элементов a1j(1), a2j(2),…, по одному в каждом столбце и в каждой строке. Тогда этот набор является решением задачи о назначениях.

Доказательство.

.

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

Пусть для некоторого вектора D мы выделили в каждой строке один из D-минимальных элементов (назовем их основами). Дефект набора основ – это количество свободных столбцов (столбцов без основ). Из леммы следует, что набор основ с дефектом равным нулю является решением задачи о назначениях.

В работе [1] предложен алгоритм, позволяющий за время O(n2) сделать итерацию: по заданному вектору D и набору основ с дефектом не равным нулю найти новый вектор и набор основ, имеющий меньший дефект. Взяв в качестве исходных нулевой вектор D и некоторый набор основ для него, задачу решаем последовательными итерациями, число которых не может превышать n.

Приближенные алгоритмы решения задачи о назначениях

Рассмотрим один из приближенных алгоритмов решения задачи о назначениях.

На первом шаге в матрице выбирается минимальный элемент, и элементы строки и столбца, на пересечении которых находится данный элемент, помечаются как выбранные. На последующих шагах поочередно выбираются непомеченные минимальные элементы до тех пор, пока все элементы матрицы не окажутся помеченными. Данный алгоритм имеет вычислительную сложность O(n3) и дает среднюю ошибку около 30 %.

Предлагается следующая модификация данного алгоритма: на очередном шаге в каждом столбце и в каждой строке выбирается минимальный непомеченный элемент. Затем выбираются пары строка-столбец, у которых совпадают выбранные элементы, и все они одновременно включаются в частичное решение задачи. Данная модификация алгоритма при практически той же точности позволяет снизить вычислительную сложность до O(n2).

Алгоритмы решения задачи о назначениях на матрицах специального вида

Сформулируем задачу о назначениях для более общего случая прямоугольной матрицы. Решением задачи о назначениях в данном случае называется такой набор из n элементов матрицы (по одному в каждой строке и не более одного в каждом столбце), что сумма этих элементов минимальна по всем таким наборам.

Сформулируем данную задачу более формально.

Рассмотрим прямоугольную матрицу  i=1,…,n; j=1,…,m. Если n £ m, задача уменьшается до нахождения набора целых чисел {p(i)}, i=1,…,n, 1£ p(i) £ m, p(i) ¹  p(r) при i ¹  r таких, что

Условие p(i) < p(j), i < j                                     (1)

может быть либо дополнительным ограничением, либо необходимым условием оптимума из-за свойств матрицы C. Различные случаи матриц C, обладающих такими свойствами, рассмотрены в [2-4]. Назначение, удовлетворяющее условию (2), называется упорядоченным назначением.

Для изложения методов решения данной задачи введем следующие обозначения. Подматрицу матрицы C, образованную пересечением строк ii,i+1,…,r и столбцов jj,j+1,…,s, обозначим C(i,r;j,s), элементы оптимального упорядоченного назначения на этой подматрице обозначим  а цену оптимального упорядоченного назначения – Введем сокращенные обозначения C(i;j)=C(1,i;1,j); p(kïi;j) = p(kï1,i;1,j); f(i;j)=f(1,i;1,j), а также C(i,r) = C(i,r; 1,m); p(kïi,r)= = p(kïi,r;1,m), f(i,r)=f(i,r;1,m). Таким образом, C=C(n;m)=C(1,n) элементы оптимального упорядоченного решения равны = p(kïn;m) = p(kï1,n), а его цена

Первый метод основан на рекуррентном решении задачи для подматриц  расположенных в левом верхнем углу матрицы C. Формально положим

f(0;j)=0.                                                                  (2)

Очевидно, что

         (3)

Заметим, что если i<j, то оптимальный элемент строки i в решении на подматрице C(i;j) находится либо в одном из первых j–1 столбцов, либо в столбце j. В первом случае   Во втором случае   Таким образом, f(i;j)=min{f(i;j-1),f(i-1;j-1+cij}  для f(i;j-1) £ f(i-1;j-1)+cij  для .  (4)

Используя соотношения (2)-(4), последовательно вычисляем пары f(i;j),  для всех  Таким образом, после  шагов будут вычислены = =f(n;m) и  Для определения оптимальных значений всех компонент  на обратном проходе нужно использовать значения :

Трудоемкость выполнения каждого шага ал- горитма равна O(1) и, таким образом, доказа- на.

Теорема 1 [4]. Данный алгоритм находит оптимальное упорядоченное назначение за время O(n×m) и требует при этом O(n×m) единиц памяти.

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

Определение. Условие      (5)

называется неравенством четырехугольника.

Теорема 2 [7]. Если матрица C удовлетворяет неравенству четырехугольника (5), то среди оптимальных решений задачи о назначениях существует решение, удовлетворяющее условию (1).

Следствие. Условие (5) достаточно для оптимальности решения, получаемого данным алгоритмом, в классе всех решений задачи о назначениях.

Рассмотрим пример.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Следовательно,

Обратный проход:

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

Определение. Функция F(x) называется слабо унимодальной, если существует точка x0 такая, что F(x) является невозрастающей функцией при x £ x0 и неубывающей при x0 £ x.

Определение. Mатрицa C слабо унимодальна по строкам, если для любой строки i cij является слабо унимодальной функцией j.

Предлагаемый ниже алгоритм сдвига реализует процесс итерационного улучшения текущего упорядоченного назначения. Для его описания необходимо ввести дополнительные определения. Вектор =(p(i),..,p(n)) называется правым фрагментом упорядоченного назначения pr = (p(1), …, p(n)), если для любого l, i £ l £ n-1 выполняется равенство p(l+1)=p(l)+1. Сдвиг правого фрагмента увеличивает все его компоненты на 1. Стоимость сдвига оценивается следующим образом:

Алгоритм сдвига [2].

1. Инициализируется :

2. Если  то переходим к шагу 6.

3. Для каждого правого фрагмента  назначения оцениваем

4. Выбираем  Если существует несколько таких фрагментов, то из них выбирается самый длинный. Если то переходим к шагу 6.

5. Строим по  сдвигая фрагмент  Переходим к шагу 2.

6. Стоп.

Количество шагов работы алгоритма не превышает m-n, а каждый шаг требует единиц времени. Следовательно, данный алгоритм имеет вычислительную сложность

Следующая теорема устанавливает условия оптимальности найденных назначений.

Теорема 3 [2]. Если матрица C удовлетворяет неравенству четырехугольника и слабо унимодальна по строкам, то алгоритм сдвига решает задачу о назначениях за время O(m×n).

Рассмотрим пример:

 

 2  1  2  2  1

 |------------------

 

 -3 -2 -1  0 -1

                  |------

 

   -2 -1

Оптимальное решение: p(1)=2, p(2)=3, p(3)=4, p(4)=6, p(5)=7.

Определение. Функция F(x) называется унимодальной, если существуют точки x1 £ x2, такие, что F(x) является убывающей функцией при x £ x1  постоянной при x1 £ x £ x2 и возрастающей при x2 £ x.

Определение. Mатрицa C унимодальна по строкам, если для любой строки i является унимодальной функцией j.

В работе [3] представлен алгоритм, который позволяет за время  строить оптимальные решения для матриц, удовлетворяющих неравенству четырехугольника и унимодальных по строкам.

Применение алгоритмов решения задачи о назначениях

Рассмотрим несколько приложений описанных выше алгоритмов в САПР электронной аппаратуры для проектирования топологии межсоединений. Предварительно сравним их достоинства и недостатки.

Точный алгоритм решения задачи о назначениях на матрицах общего вида позволяет путем введения штрафов на значения элементов матрицы добиваться выполнения разнообразных ограничений, например, дает возможность строить решения, не содержащие определенных элементов матрицы. Однако кубическая временная сложность не позволяет использовать данный алгоритм для решения задач большого размера (n>1000). С другой стороны, алгоритм решения задачи о назначениях на матрицах специального вида, обладая квадратичной временной сложностью, допускает оптимальные решения только при условии, если элементы матрицы удовлетворяют неравенству четырехугольника. И, наконец, предложенная в данной работе модификация приближенного алгоритма при той же временной сложности позволяет на матрицах общего вида строить решения с относительной ошибкой около 30 %.

Назначение интерфейсных сигналов на периферийные элементы интегральных схем и на контакты разъемов многослойных печатных плат. Задача ставится следующим образом. Имеется множество точек на кристалле (печатной плате), которые требуется соединить с периферийными элементами кристалла (точками подсоединения к разъему платы) таким образом, чтобы суммарная длина трасс была минимальна (для оценки длин трасс при этом используется манхеттеновская метрика). Для задач не очень большой размерности решение может быть построено за приемлемое время с использованием точного алгоритма. Задачи большой размерности решаются в два этапа. На первом этапе с использованием приближенного алгоритма выбирается сторона кристалла (разъем платы), на которую будет выводиться каждый из сигналов. На втором этапе осуществляется переназначение сигналов поочередно на каждой из сторон кристалла (на каждом из разъемов платы) с использованием алгоритма решения задачи о назначениях на матрицах специального вида. При этом выводимые точки и точки подсоединения поочередно упорядочиваются по возрастанию значений координат их проекций на разделяющую оба множества горизонтальную или вертикальную прямые линии. Для манхеттеновской метрики это гарантирует выполнение неравенства четырехугольника в результирующей матрице.

Данный подход реализован в системе проектирования печатных плат на персональных компьютерах ЭРА-ПК [5] и системе проектирования больших интегральных схем на рабочих станциях COMPASS [6].

Проектирование проводных соединений при корпусировании интегральных схем. Специфика данной задачи заключается в том, что вместо манхеттеновской используется евклидова метрика. Оптимальность решения гарантирует при этом отсутствие пересечений проводов в силу того, что в любом выпуклом четырехугольнике сумма длин противоположных сторон не может превышать суммы длин его диагоналей. Использование точного алгоритма решения задачи о назначениях на матрицах общего вида позволяет в данном случае выполнять такие конструктивные ограничения, как ограничения на угол между проводом и перпендикуляром к краю кристалла, ограничения на соединение контактов для кристаллов и корпусов с двумя рядами контактов и т.д. При использовании двухэтапной схемы последовательность действий остается такой же, как и в предыдущем примере. Однако в данном случае для упорядочивания контактов кристалла на каждой из его сторон используются координаты точек пересечения прямой линии, проходящей по соответствующей границе кристалла с прямыми линиями, проходящими через центр противоположной стороны кристалла и контакты на его периферии. Аналогично для упорядочивания контактов корпуса на каждой из его сторон используются координаты точек пересечения прямой линии, проходящей по соответствующей стороне прямоугольника, ограничивающего внутреннюю часть кристалла, с прямыми линиями, проходящими через центр противоположной стороны ограничивающего прямоугольника, и контакты корпуса. Полученные в результате матрицы удовлетворяют неравенству четырехугольника. Двухэтапная схема используется, в частности, при подборе для данного кристалла корпусов из библиотеки. При этом в процессе подбора для каждого корпуса, подходящего по числу контактов и размерам, строится экспресс-назначение с последующей проверкой выполнения правил проектирования, в результате чего выбирается корпус с минимальным числом нарушений. Разводка проводов на шины земли и питания (номиналов и шин питания в корпусе может быть несколько) выполняется с использованием специально разработанного для этой цели эвристического алгоритма. Работа алгоритма включает следующие шаги.

1.  Шины разбиваются на точки (приемники) с минимально допустимым конструктивным шагом.

2.  Для очередного источника (контакта кристалла) определяется множество допустимых приемников, удовлетворяющих правилам проектирования и технологическим ограничениям (максимально допустимое значение угла между проводником и перпендикуляром к краю кристалла, наличие пересечений с уже существующими проводниками, минимально допустимое расстояние до соседних проводников и т.д.).

3.  Из оставшихся допустимых проводников выбирается оптимальный по критерию близости к лучу, проходящему через центр кристалла и разводимый контакт кристалла.

4.  Итерация повторяется, начиная с шага 2, до тех пор, пока не будут рассмотрены все источники.

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

Данный подход к проектированию проводных соединений реализован в системе под названием Package Constraint Manager (PCM), входящей в последнюю версию v9r4.1 системы COMPASS.

Список литературы

1.   Диниц Е.А., Кронрод М.А. Один алгоритм решения задачи о назначении./ДАН CССР.- 1969. - Т. 189. - № 1. - С. 23-25.

2.   Ершов В.А., Ирбенек В.С. Алгоритм решения задачи назначения на матрицах специального вида. -М., 1981. - 20 с. (Препр./АН СССР Ин-т точн. механ. и вычислит. техн. им. С.А.Лебедева; № 4).

3.   Флейшман С.Б. Оптимальные назначения специального вида. -М., 1990. - 15 с. (Препр./АН СССР Ин-т точн. механ. и вычислит. техн. им. С.А.Лебедева; № 2).

4.   Флейшман С.Б. Назначения с заданным порядком следования/ДАН СССР. –1991. - Т. 319. - № 1. - С. 581-584.

5.   Ирбенек В.С. Верификация временных соотношений и оптимизация размещения конструктивных элементов суперЭВМ. -М., 1993. - 29 с. (Препр/АН СССР Ин-т точн. механ. и вычислит. техн. им. С.А.Лебедева; № 2).

6.   Ирбенек В.С. Московский центр SPARC-технологий и Compass Design Automation: история и перспективы сотрудничества. //Автоматизация проектирования. -М., 1997. -№ 3. - C. 3-6.

7.   Hoffman A.J. On greedy algorithms that succeed/London Math Society Lecture Notes Series, 1985, v.103, pp.97-112.