Новая редакция принципа групповых резолюций для задачи о минимальном взвешенном покрытии

Abstract

Представлен новый вариант метода на основе принципа групповых резолюций для решения комбинаторной оптимизационной задачи о минимальном взвешенном покрытии 0,1-матрицы. Во-первых, размеры матрицы (число столбцов) при добавлении новых групповых резольвент ограничены удвоенным числом строк, так что реализована возможность писать новые резольвенты поверх старых без потери решения. Во-вторых, принцип резолюций для взвешенного случая тот же, что и для невзвешенного случая. В третьих, метод усилен возможностью строить групповые резольвенты, не отыскивая на каждой итерации полного покрытия – имеются ситуации, когда процесс можно остановить и строить резольвенту на сокращенной синдромной матрице, что усиливает общую сходимость метода. Сложностная оценка метода соответствует ранее сообщенной и характеризует полиномиальность метода в среднестатистическом случае.