Проблема с минимальной пропускной способностью

Меня интересует NP-полная проблема «минимальной пропускной способности» для нахождения минимальной пропускной способности графа. Для тех, кто не знаком, вот ссылка на это ...

http://en.wikipedia.org/wiki/Graph_bandwidth

Я реализовал алгоритм Катхилла-Макки, и он очень успешно дал мне перестановку вершин, в которых пропускная способность была уменьшена; однако я ищу минимальную пропускную способность, а не просто близкую к уменьшенной пропускной способности. Если у кого-то из вас есть опыт решения этой проблемы, какие алгоритмы предоставляют решения, которые являются минимальными, а не просто сокращенными. ? Мне не нужна реальная реализация какого-либо алгоритма, мне просто нужны предложения по алгоритмам для исследования, которые дают реальную минимальную полосу пропускания.


graph algorithm bandwidth minimum np-complete
person Nitrex88    schedule 11.04.2011    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Это интересная проблема, но когда я читаю Wiki (ваша ссылка):

И невзвешенная, и взвешенная версии являются частными случаями квадратичной задачи о назначении узких мест. Проблема пропускной способности NP-трудна даже для некоторых особых случаев. [4] Что касается существования эффективных алгоритмов аппроксимации, известно, что полосу пропускания NP-трудно аппроксимировать в пределах любой константы, и это справедливо даже тогда, когда входные графы ограничены деревьями-гусеницами (Dubey, Feige & Unger 2010). С другой стороны, известен ряд полиномиально разрешимых частных случаев.

Итак, вики говорит, что это NP-сложно аппроксимировать любой константой (так что для этой проблемы нет PTAS), и ваш шанс - просто использовать эвристические алгоритмы, убедитесь, что алгоритм грубой силы работает (узел нумерации с числами от 1 до n случайным образом в стартап, после этого используйте грубую силу), но вам придется потратить 1000 лет, чтобы решить эту проблему для гусеницы. Вам следует искать эвристические алгоритмы, а не приближения и точные алгоритмы.

person Saeed Amiri    schedule 11.04.2011
comment
1000 лет, наверное, очень оптимистично для грубой силы :) - person Geoffrey De Smet; 11.04.2011
comment
Спасибо за ваш совет. В итоге я использовал приближение из алгоритма Катхилла-Макки, чтобы установить верхнюю границу минимальной пропускной способности. Я также вычисляю нижнюю границу, а затем перебираю все перестановки, рассматривая только те, которые соответствуют определенным критериям, основанным на границах. Это дало мне решение, достаточно быстрое для размеров графиков, которые я использовал, и было значительно лучше, чем просто грубая сила! - person Nitrex88; 12.04.2011
comment
@ Nitrex88, хорошая работа, но вы найдете хорошую эвристику или ... для вашей проблемы, а не приближения, приближение означает, что существует коэффициент приближения, который ограничивает ваши ответы в худшем случае, некоторые проблемы, подобные этой, не имеют коэффициента приближения, если вы найдете алгоритм (в P), который является полиномиальным приближением грубой силы, вы можете решать проблемы NPC (я сказал это только для обучения, в этом случае не важно, например, приближение, но иногда это важно). - person Saeed Amiri; 12.04.2011

arrow_upward
1
arrow_downward

Поскольку это NP-полный, вы должны использовать какой-то алгоритм «грубой силы». Так что в основном у вас есть другой вариант грубой силы, например как ветвление и граница или линейное программирование (его LIP, поэтому его в NP).

Поскольку он является NP-завершенным, вы также можете принять каждое решение другой полной NP-проблемы (TSP, SAT, ...), преобразовав экземпляр проблемы из доказательства NP-полноты, применив алгоритм и преобразовав его обратно.

person flolo    schedule 11.04.2011
comment
@Chris Hopman: Оригинальный плакат написал: the NP-complete "minimum bandwidth", и у меня не было причин предполагать, что он неправ. - person flolo; 11.04.2011

arrow_upward
1
arrow_downward

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

См. этот ответ для обзора некоторых применяемых алгоритмов.

person Geoffrey De Smet    schedule 11.04.2011