Тип публикации: статья из журнала
Год издания: 2016
Ключевые слова: доминирование, доминирующее множество, число доминирования, задачи размещения, методы дискретной оптимизации, NP-полнота, динамическое программирование, прямо-двойственный алгоритм, жадный алгоритм, остовное дерево, задача о наименьшем покрытии.
Аннотация: В данной статье с алгоритмической точки зрения исследуется одна из оптимизационных задач теории графов — задача о доминировании, которая является естествен-ной моделью для многих задач размещения, изучаемых в исследовании операций и возникающих в многочисленных приложениях. Приведено обоснование её значимости как широко применимой Показать полностьюзадачи, для которой доказано свойство NP-полноты. Автором разработана и описана программа, реализованная на основе алгоритмов дискретной оптимизации и жадного алгоритма, позволяющая различными методами найти решения задачи о доминировании для последующего их сравнения.
Журнал: Молодой ученый
Выпуск журнала: № 2
Номера страниц: 6-12
ISSN журнала: 20720297
Место издания: Казань
Издатель: Общество с ограниченной ответственностью Издательство Молодой ученый