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

Герман, О. В.; Герман, Ю. О.; German, O.; German, J.

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

Герман, О. В., Герман, Ю. О., German, O., German, J.

Дата публикации: 2021

Дата публикации в реестре: 2024-03-01T13:44:22Z

Аннотация:

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

Ключевые слова:
публикации ученых, групповые резолюции, бинарные матрицы, минимальное взвешенное покрытие, minimum weighted cover, group resolution principle, binary matrice

Тип: Статья