Алгоритм поиска связного подграфа взвешенного графа вершин с суммой, близкой к заданному значению

Question

Учитывая граф с взвешенным по вершине графом G (изображенный ниже), вершина v из этого графика и целочисленное значение x, есть ли известный алгоритм для нахождение подключенного подграфа G такого, что целевая вершина находится в этом подграфе, а сумма весов этого подграфа максимально приближена к x? Более того, если точное совпадение x не может быть найдено, алгоритм должен по-прежнему возвращать подграфы, наиболее близкие к x.

Некоторые примеры, приведенные на графике ниже:

v = Р, х = 12. А, В, F, I и F, G, С, D представляют собой растворы.

v = C, x = 16. C, D, E, H - решение.

Answer 1

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

Один подход заключается, чтобы проверить все возможные подграфы, содержащие v и поиск максимального веса (до вашего x):

Вы могли бы использовать какое-то жадный алгоритм, начиная с узлом v, а затем добавить один соседний узел после другого, отслеживая общий вес субграфа. если вы достигнете x, вы закончите, если перерегулировать x, вы должны вернуться и выбрать другие узлы вашего подграфа. В течение всего алгоритма вы отслеживаете свой «лучший» подграф, поэтому, если в конце концов не найдено точного решения, вы все равно будете иметь наилучшее приближение.

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