Предлагаемый сценарий, который я хотел бы решить, представляет собой задачу максимизации, в которой каждая вершина в связном ненаправленном графе имеет значение. Однако каждое ребро и вершина также имеют стоимость.
Учитывая начальную вершину и бюджет затрат, существует ли рекомендуемый алгоритм или подход для поиска связного подграфа, который максимизирует значение вершины (включая начальную вершину)?
Это NP-сложно, потому что вы можете использовать алгоритм для этого для решения проблемы дерева Штайнера в графах, установив значение для каждого терминала равным 1, стоимость каждой вершины равной 0 и стоимость каждого ребра равной 1. Существует дерево Штейнера с весом k тогда и только тогда, когда ваш алгоритм со стоимостью бюджет k может захватывать значение со всех терминалов.
Это может помочь изучить литературу по деревьям Штейнера, чтобы получить некоторые идеи для приближенных идей решения.
