Применение высокопроизводительных вычислений для поиска троек взаимно частично ортогональных диагональных латинских квадратов порядка 10
Автор: Заикин О.С., Ватутин Э.И., Журавлев А.Д., Манзюк М.О.
Рубрика: Дискретная математика и математическая кибернетика
Статья в выпуске: 3 т.5, 2016 года.
Бесплатный доступ
Статья посвящена поиску троек взаимно частично ортогональных диагональных латинских квадратов порядка 10. Для каждой известной пары ортогональных диагональных латинских квадратов порядка 10 достраивается третий диагональный латинский квадрат таким образом, чтобы условие ортогональности между ним и квадратами из рассматриваемой пары нарушалось в как можно меньшем количестве ячеек. Используются два подхода: первый основан на сведении исходной задачи к задаче о булевой выполнимости, а второй - на использовании метода грубой силы. Построено несколько троек указанного вида с рекордными характеристиками. Эксперименты были проведены в проекте добровольных распределенных вычислений SAT@home, а также на вычислительном кластере.
Диагональные латинские квадраты, частичная ортогональность, задача о булевой выполнимости, добровольные распределенные вычисления, метод грубой силы, вычислительный кластер
Короткий адрес: https://sciup.org/147160600
IDR: 147160600 | DOI: 10.14529/cmse160304
Список литературы Применение высокопроизводительных вычислений для поиска троек взаимно частично ортогональных диагональных латинских квадратов порядка 10
- Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs. Second Edition. Chapman&Hall, 2006. 984 p.
- Малых А.Е., Данилова В.И. Об историческом процессе развития теории латинских квадратов и некоторых их приложениях//Вестник Пермского университета. Серия: Математика. Механика. Информатика. 2010. № 4. С. 95-104.
- Тужилин М.Э. Об истории исследований латинских квадратов//Обозрение прикладной и промышленной математики. 2012. Т. 19, Вып. 2. С. 226-227.
- Brown J.W., Cherry F., Most L., Most M., Parker E.T., Wallis W.D. Completion of the spectrum of orthogonal diagonal Latin squares//Lecture notes in pure and applied mathematics. 1992. Vol. 139. P. 43-49.
- Egan J.E., Wanless I.M. Enumeration of MOLS of small order//Mathematics of Computation. 2015. Vol. 85. P. 799-824.
- Biere A., Heule V., van Maaren H., Walsh T. (eds.) Handbook of Satisfiability. IOS Press. 2009.
- Семенов А.А., Беспалов Д.В. Технологии решения многомерных задач логического поиска//Вестник Томского государственного университета. 2005. № 14. С. 61-73.
- Zhang H. Combinatorial Designs by SAT Solvers. In: Biere A., Heule V., van Maaren H., Walsh T. (eds.) Handbook of Satisfiability. IOS Press. 2009. P. 533-568.
- Заикин О.С., Семенов А.А., Посыпкин М.А. Процедуры построения декомпозиционных множеств для распределенного решения SAT-задач в проекте добровольных вычислений SAT@home//Управление большими системами. М.: ИПУ РАН. Вып. 43. 2013. С. 138-156.
- Заикин О.С., Посыпкин М.А., Семенов А.А., Храпов Н.П. Опыт организации добровольных вычислений на примере проектов OPTIMA@home и SAT@home//Вестник Нижегородского университета им. Н.И. Лобачевского. 2012. № 5-2. С. 340-347.
- Заикин О.С., Кочемазов С.Е. Поиск пар ортогональных диагональных латинских квадратов порядка 10 в проекте добровольных распределенных вычислений SAT@home//Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2015. Т.4, № 3. С. 95-108.
- Een N., Sorensson N. An Extensible SAT-solver//Lecture Notes in Computer Science. 2003. Vol. 2919. P. 502-518.
- Zaikin O., Kochemazov S. The search for systems of diagonal Latin squares using the SAT@home project//Proceedings of the Second International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2015), Petrozavodsk, Russia, 2015. CEUR-WS. Vol. 1502. P. 52-63.
- Biere A. Lingeling, Plingeling and Treengeling Entering the SAT Competition 2013//Proceedings of SAT Competition 2013. 2013. Vol. B-2013-1. P. 51-52.
- Maric F., Janicic P. Formal Correctness Proof for DPLL Procedure//Informatica. 2010. Vol. 21, Issue 1. P. 57-78.
- Ватутин Э.И., Журавлев А.Д., Заикин О.С., Титов В.С. Особенности использования взвешивающих эвристик в задаче поиска диагональных латинских квадратов//Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2015. № 3(16). С. 18-30.
- Land A.H., Doig A.G. An automatic method of solving discrete programming problems//Econometrica. 1960. Vol. 28, No. 3. P. 497-520.
- Ватутин Э.И., Романченко А.С., Титов В.С. Исследование влияния порядка рассмотрения пар на качество расписаний при использовании жадного подхода//Известия Юго-Западного государственного университета. 2013. № 1(46). С. 58-64.
- Ватутин Э.И., Бобынцев Д.О., Романченко А.С. Исследование влияния частичного упорядочивания пар и локального улучшения окрестности пары на качество расписаний при использовании жадного подхода//Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2014. № 1. С. 8-16.
