Алгоритм Кернигана – Лина - Kernighan–Lin algorithm

Эта статья посвящена эвристическому алгоритму решения задачи разбиения графа. Об эвристике задачи коммивояжера см. Эвристика Лин-Кернигана.

В Алгоритм Кернигана – Лина это эвристический алгоритм за поиск разбиений графов.Алгоритм имеет важные приложения при компоновке цифровых схем и компонентов в СБИС.^[1][2]

Описание

Входом в алгоритм является неориентированный граф грамм = (V, E) с множеством вершин V, набор кромок E, и (необязательно) числовые веса на ребрах в E. Цель алгоритма - разбить V на два непересекающихся подмножества А и B равного (или почти равного) размера таким образом, чтобы минимизировать сумму Т весов подмножества ребер, пересекающихся из А к B. Если граф невзвешенный, то вместо этого цель состоит в том, чтобы минимизировать количество пересекающихся ребер; это эквивалентно присвоению веса по одному каждому ребру. Алгоритм поддерживает и улучшает раздел на каждом проходе, используя жадный алгоритм объединить вершины А с вершинами B, так что перемещение парных вершин с одной стороны разбиения на другую улучшит разбиение. После сопоставления вершин он затем выполняет подмножество пар, выбранных так, чтобы иметь лучший общий эффект на качество решения. Т.Дан график с п вершины, каждый проход алгоритма выполняется во времени О(п² бревно п).

Более подробно по каждому ${\displaystyle a\in A}$, позволять ${\displaystyle I_{a}}$ быть внутренняя стоимость из а, то есть сумма затрат ребер между а и другие узлы в А, и разреши ${\displaystyle E_{a}}$ быть внешняя стоимость из а, то есть сумма затрат ребер между а и узлы в B. Аналогичным образом определим ${\displaystyle I_{b}}$, ${\displaystyle E_{b}}$ для каждого ${\displaystyle b\in B}$. Кроме того, пусть

${\displaystyle D_{s}=E_{s}-I_{s}}$

быть разницей между внешними и внутренними затратами s. Если а и б меняются местами, то снижение стоимости составляет

${\displaystyle T_{old}-T_{new}=D_{a}+D_{b}-2c_{a,b}}$

куда ${\displaystyle c_{a,b}}$ стоимость возможного преимущества между а и б.

Алгоритм пытается найти оптимальную серию операций обмена между элементами ${\displaystyle A}$ и ${\displaystyle B}$ что максимизирует ${\displaystyle T_{old}-T_{new}}$ а затем выполняет операции, создавая раздел графа на А и B.^[1]

Псевдокод

Источник:^[2]

функция Керниган-Лин (G (V, E)) является    определить сбалансированное начальное разбиение узлов на множества A и B делать        вычислить значения D для всех a в A и b в B, пусть gv, av и bv будут пустыми списками за п: = 1 к | V | / 2 делать            найти a из A и b из B, такие, что g = D [a] + D [b] - 2 × c (a, b) является максимальным, удалите a и b из дальнейшего рассмотрения в этом проходе добавьте g в gv, a в av и b в bv обновляют значения D для элементов A = A  a и B = B  b конец для        найти k, который максимизирует g_max, сумму gv [1], ..., gv [k] если g_max> 0 тогда            Обменять av [1], av [2], ..., av [k] на bv [1], bv [2], ..., bv [k] до (g_max ≤ 0)    вернуть G (V, E)

Смотрите также

• Алгоритм Фидуччи – Маттезеса

Рекомендации

1. Керниган, Б.В.; Линь, Шен (1970). «Эффективная эвристическая процедура разбиения графов». Технический журнал Bell System. 49: 291–307. Дои:10.1002 / j.1538-7305.1970.tb01770.x.
2. Равикумар, С. П. (1995). Параллельные методы проектирования топологии СБИС. Издательская группа "Гринвуд". п. 73. ISBN  978-0-89391-828-6.