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

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

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

v = F, x = 12. A,B,F,I и F,G,C,D являются решениями.

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

Вершинно-взвешенный простой граф.


weighted graph-algorithm
person Michael Anslow    schedule 14.07.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

person DubioserKerl    schedule 15.07.2015
comment
Я согласен, что это может быть либо задача о рюкзаке, либо задача о сумме подмножеств, когда мы ограничены конкретной задачей поиска, ограниченной корневой вершиной и путями от нее. - person Michael Anslow; 20.07.2015