Учитывая эффективный алгоритм решения системы разностных ограничений, когда некоторые из x должны быть целыми числами

Это упражнение из CLRS 24.4-12 (не домашнее задание, я просто пытаюсь решить все упражнения в CLRS)

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

Если все xi являются целыми числами, мы можем положить b = floor (b) и с помощью алгоритма Беллмана-Форда найти кратчайший путь для решения проблемы в графе ограничений, но как насчет того, чтобы некоторые из xi были целыми числами, а некоторые - нет? Это похоже на задачу целочисленного программирования, но целочисленное программирование NP-сложно. Этот вопрос имеет меньше ограничений, есть ли более эффективный алгоритм?


algorithm clrs
person meteorgan    schedule 11.04.2012    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Сначала найдите элемент с минимальным абсолютным значением в векторе b, умножьте его на C, чтобы все значения в векторе b были целыми (например, если минимальное абсолютное значение равно 3,102, мы можем умножить вектор b на 1000), затем решите его следующим образом: Алгоритм Беллмана-Форда и, наконец, разделить его на C!

person Arian    schedule 21.03.2013

arrow_upward
0
arrow_downward

У вас есть похожие вещи в линейной оптимизации - единственная разница в том, что у вас нет минимальных или максимальных требований. Возможно, вам удастся адаптировать некоторые методы. Начиная с решения с действительным знаком, есть алгоритм Гомори, добавляющий дополнительные ограничения, чтобы заставить целое число xi стать целым, и есть алгоритмы Branch-and-Bound, пытающиеся как можно скорее исключить большие части пространства поиска.

person Landei    schedule 11.04.2012
comment
Я предполагаю, что мое решение -12 можно рассматривать как добавление рубанков Гомори, но я не думаю, что это особенно продуктивный способ думать об этом. Ветвление и граница не имеют отношения к этой проблеме. - person oldboy; 11.04.2012
comment
Если вы решите это как линейное программирование, как я уже упоминал, это NP-сложно. Я хочу знать, существует ли эффективное решение. - person meteorgan; 11.04.2012

arrow_upward
0
arrow_downward

Что ж. Чувак, это упражнение «Введение в алгоритм». Мой собственный способ - адаптировать алгоритм Беллмана-Форда, который заключается в построении ориентированного взвешенного графа на основе неравенств, а затем при ослаблении ребер разрешить только целые числа быть ключевым значением узла. Я думаю, это сработает.

person Yang Jiang    schedule 25.07.2013