Время выполнения алгоритма Blossom составляет O (E * V ^ (1/2)) согласно википедии. Поскольку алгоритм используется 4 раза, общее время работы также будет равно O (E * V ^ (1/2)).
отаю над проблемой, которая может быть сведена к задаче оптимизации графика, как показано ниже.
Задан набор цветных узлов. Все они не связаны, то есть в графе нет ребра.
Края должны быть вставлены между узлами.
У узла может быть только 4 ребра при макс.
В таблице приведены правила получения прибыли от ребер.
Например.,
Ребро, соединяющее красный с красным: прибыль равна 10
Край, соединяющий красный с синим: прибыль 20
Общее количество узлов составляет около 100.
Общее количество цветов обычно составляет от 20 до 30, но может доходить до 50. Соответственно, таблица для получения прибыли (ребра) будет длинным списком, но не будет перечислять все возможные комбинации. Прибыль по ребрам, не указанным в таблице, принимается равной нулю.
Задача состоит в том, чтобы оптимизировать соединения (ребра) так, чтобы общая прибыльмаксимизируется.
Мне интересно, если эта проблема, может быть, каким-то другим образом, известна. Если да, пожалуйста, предоставьте любые указатели, которые могут помочь. Благодарю.