Можно решить вашу проблему за время O (n 2 ), объединив вместе два известных алгоритма.
Когда я впервые увидел вашу проблему, я сначала подумал, что это будет связано с чем-то вроде поиска максимума или минимального разреза на графике. Однако, поскольку вы специально ищете способ разделения узлов на две группы, в которых между этими группами вообще нет ребер, я думаю, что то, что вы ищете, гораздо ближе к поиску связанных компонентов * 1010. * графика. В конце концов, если разбить график на связанные компоненты, между этими компонентами не будет ребер. Поэтому вопрос сводится к следующему:
Найдите все связанные компоненты графика, отметив, сколько узлов в каждом компоненте.
Разделите два соединенных компонента на две группы примерно одинакового размера - в частности, размер группы на одной стороне должен быть не более чем на один размер больше, чем размер группы на другой.
Шаг (1) - это то, что вы можете сделать, используя поиск в ширину или в глубину, чтобы идентифицировать все подключенные компоненты. Это займет у вас время O (m + n), где m - количество ребер, а n - количество узлов.
Шаг (2), на первый взгляд кажется, что это может быть довольно сложно. Это напоминает проблему с разделами , которая известна как NP-hard. Проблема с разделением работает следующим образом: вы вводите список чисел и хотите определить, существует ли разделение этих чисел на две группы, итоговые значения которых равны друг другу. (Эту проблему можно адаптировать так, чтобы вы могли допустить, что расщепление отключено на плюс или минус единица без изменения сложности). Эта проблема является NP-полной, что предполагает, что ваша проблема может быть сложной.
Тем не менее, есть небольшой нюанс, который фактически делает очевидной NP-сложность проблемы раздела не проблемой. Проблема разбиения является NP-сложной в том случае, если указанные вами числа записаны в binary . С другой стороны, если числа записаны в унарных , то проблема разбиения имеет решение за полиномиальное время. Более конкретно, существует алгоритм для задачи разбиения, который выполняется за время O (kU), где k - это число чисел, а U - сумма всех этих чисел. В случае проблемы, которую вы описываете, вы знаете, что сумма размеров соединенных компонентов в вашем графе должна быть n, число узлов в графе, и вы знаете, что число соединенных компонентов также больше ограниченный п. Это означает, что время выполнения O (kU) при подключении k = O (n) и U = O (n) работает до O (n 2 ), что можно сделать в полиномиальном режиме. время.
(Еще один способ убедиться в этом - есть алгоритм псевдополиномиального времени для задачи разбиения, но, поскольку в вашем случае максимально возможная сумма ограничена фактическим полиномом по размеру ввода, общее время выполнения является полиномом.)
Алгоритм, на который я ссылаюсь выше, является стандартным упражнением по динамическому программированию. Вы выбираете некоторый порядок чисел - не обязательно в отсортированном порядке - и затем заполняете двумерную таблицу, где каждая запись соответствует ответу на вопрос "есть ли подмножество первых i чисел, которое в сумме в точности соответствует j?" Если вы не знакомы с этим алгоритмом, я предоставлю вам возможность разобраться в деталях, поскольку решить действительно красивую задачу, имеющую довольно простое и элегантное решение.
В целом, этот алгоритм будет работать за время O (n 2 ), поскольку вы будете выполнять работу O (m + n) = O (n 2 ), чтобы найти подключенного компонентов, за которым следует время O (n 2 ) для запуска проблемы разбиения DP, чтобы определить, существует ли разделение.
Надеюсь, это поможет!