Приводятся результаты сравнения двух эвристических методов применительно к решению систем псевдобулевых линейных неравенств - алгоритма Балаша и алгоритма имитации отжига, полученные в компьютерном эксперименте. Подтверждена большая эффективность и большее время работы алгоритма имитации отжига в сравнении с детерминированным методом Балаша. Приводятся рекомендации по совместному использованию алгоритмов. Предложена новая интерпретация случайного псевдобулевого линейного неравенства, которая может использоваться для определения эффективности эвристических методов решения указанной задачи.
Скачать электронную версию публикации
Загружен, раз: 147
- Title Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств
- Headline Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 7 (Приложение)
- Date:
- DOI
Ключевые слова
алгоритм имитации отжига, алгоритм Балаша, линейные неравенства, случайные линейные неравенства, simulated annealing, Balas algorithm, linear inequalities, random linear inequalitiesАвторы
Ссылки
Кочетов Ю. А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения: Сб. лекций молодежных и научных школ по дискретной математике и ее приложениям. М.: Изд-во центра прикл. исслед. при мех.-мат.
Балакин Г. В., Никонов В. Г. Методы сведения булевых уравнений к системам пороговых соотношений // Обозрение прикладной и промышленной математики. 1994. Т. 1. Вып.3. С.389-401.
Анашкина Н. В. Обзор методов решения систем линейных неравенств // Вестник московского университета леса. Лесной вестник. 2004. №1(32). С.144-148.
Goldwasser S. and Bellare M. Lecture Notes on Cryptography. 2001. http://theory.lcs.mit. edu/shafi. 283 p.
Muroga S., Tsuboi T., and Baugh C. R. Enumeration of threshold functions of eight variables // IEEE Trans. Comput. 1970. V. C-19. Iss.9. P. 818-825.
Подольский В. В. Оценки весов персептронов (полиномиальных пороговых булевых функций): автореф. дис.. канд. физ.-мат. наук. М.: МГУ им. М.В. Ломоносова, 2009.
Crama Y. and Hammer P. Boolean Functions. Theory, Algorithms and Applications. Encyclopedia of Mathematics and its Applications / eds. G.-C. Rota. Cambridge University Press, 2011.
Балакин Г. В. Линейные псевдобулевы неравенства // Математические вопросы криптографии. 2010. Т. 1. Вып.3. С. 5-18.
Анашкина Н. В., Шурупов А. Н. Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств // Прикладная дискретная математика. 2014. №3(25) (в печати).
Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств | Прикладная дискретная математика. 2014. № 7 (Приложение).
Скачать полнотекстовую версию
Загружен, раз: 1917