|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Вычислительные методы в дискретной математике
Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств
Н. В. Анашкинаa, А. Н. Шуруповb a Лаборатория ТВП, г. Москва
b МИРЭА, г. Москва
Аннотация:
Предложен эвристический алгоритм решения систем псевдобулевых линейных неравенств, являющийся модификацией алгоритма Балаша. Выход из тупиковой точки производится с помощью техники выбора очередного состояния, как в алгоритме имитации отжига. Приводятся результаты экспериментального сравнения предложенного алгоритма и упомянутых эвристик для решения случайных систем линейных неравенств с использованием двух типов целевых функций – суммы и максимума невязок неравенств решаемой системы.
Экспериментально установлена бо́льшая эффективность предложенного алгоритма. Этот же алгоритм был применён к решению систем линейных неравенств, описывающих линейный регистр сдвига с булевой пороговой функцией выхода. Описывающая линейный регистр сдвига система линейных неравенств характеризуется экспоненциальным числом неравенств по отношению к длине выходной последовательности линейного регистра сдвига. Описываются способы сокращения объёма указанной системы линейных неравенств без сокращения длины выхода. Во всех исследованных случаях предложенный алгоритм находит решения системы линейных неравенств, не всегда совпадающие с оригинальным решением.
Ключевые слова:
алгоритм имитации отжига, алгоритм Балаша, псевдобулевые линейные неравенства.
Образец цитирования:
Н. В. Анашкина, А. Н. Шурупов, “Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств”, ПДМ. Приложение, 2015, № 8, 136–138
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma200 https://www.mathnet.ru/rus/pdma/y2015/i8/p136
|
Статистика просмотров: |
Страница аннотации: | 142 | PDF полного текста: | 80 | Список литературы: | 55 |
|