Я пытаюсь решить следующую проблему:
Учитывая связный граф G = (V, E) и вершину t ∈ V, мне нужно найти подграф G '= (V', E '), где t ∈ V'. G 'должен максимизировать некоторую целевую функцию и минимизировать количество содержащихся в ней вершин.
Max f(G')
Min |V'|
В этой многоцелевой задаче оптимизации максимизировать f (G ') важнее, чем минимизировать количество вершин.
Давайте проверим практическую ситуацию с похожей проблемой:
Предположим, что мы должны спроектировать беспроводную сеть ad hoc в здании, где клиентские устройства имеют фиксированное местоположение и есть только одна точка доступа, подключенная к проводной сети. Первоначально мы помещаем точку доступа в каждую комнату и рассчитываем, используя модель распространения, точки доступа, которые можно подключить, и клиентские устройства, для которых они предоставляют покрытие. В этом начальном распределении, вероятно, несколько точек доступа будут обеспечивать покрытие одного и того же клиентского устройства, поэтому нам необходимо его оптимизировать.
Рис. 1. Красная точка обозначает точку доступа, подключенную к проводной сети, а черные точки обозначают остальные точки доступа. Сплошные линии между точками доступа показывают нам, как они связаны.
График, который формирует соединения AP на рис. 1, представляет связанный граф G нашей проблемы, а точка доступа, подключенная к проводной сети, является узлом t. Оптимизировать график, который представляет этот первоначальный проект сети, означает найти подграф, который содержит точку доступа, подключенную к проводной сети, и максимизировать процент покрытых клиентских устройств (Max f (G ')), сводя к минимуму количество точек доступа (Min | V' | ). Как и в этой задаче, основной целью является максимизация процента клиентских устройств.
Рис 2. Возможное решение.
Использование алгоритма грубой силы выглядит как проблема NP-полноты; Чтобы найти оптимальное решение, необходимо изучить все потенциальные подграфы (все из которых содержат узел t), а также проверить возможное решение. О чем ты думаешь?