Алгоритмизация труднорешаемых задач. Часть I. Простые примеры и простые эвристики

В статье мы излагаем свой взгляд на т.н. труднорешаемые вычислительные задачи и возможные подходы к их алгоритмизации – на уровне, «несколько превышающем научно-популярный», однако «несколько меньшем, чем научный». При этом мы делаем упор на описании методов разработки алгоритмов для них и не сводим рассмотрение трудных задач, а также нашу интерпретацию трудности, к т.н. NP-трудности. В центре нашего внимания находятся проблемы, для которых (пока) не доказаны ни NP-трудность, ни полиномиальная разрешимость, т.е. неизвестно, существуют ли алгоритмы, решающие эту задачу за т.н. полиномиальное время (время, ограниченное некоторым полиномом относительно размера входных данных). Однако, кроме того, мы считаем трудными и такие задачи, для которых полиномиальная разрешимость доказана – однако (пока) неизвестны полиномиальные алгоритмы малых степеней. Среди рассматриваемых нами примеров задач – известные интеллектуальные игры-головоломки, а также задача коммивояжера и проблемы минимизации недетерминированных конечных автоматов и дизъюнктивных нормальных форм. Среди алгоритмов мы в первую очередь рассматриваем эвристические – которые обычно не гарантируют получение оптимального решения, однако с приемлемо большой вероятностью дают решение, близкое к нему. Важной их разновидностью являются т.н. anytime-алгоритмы – алгоритмы реального времени, которые в каждый определенный момент работы имеют лучшее (на данный момент) решение; при этом пользователь в режиме реального времени может просматривать эти псевдооптимальные решения, а последовательность таких решений в пределе обычно дает оптимальное

труднорешаемые задачи, эвристические алгоритмы, искусственный интеллект, задачи дискретной оптимизации

1. Разборов А. Theoretical Computer Science: взгляд математика // Компьютерра. – 2001. – № 2.

2. Николенко С. Теория и практика сложности // Компьютерра. – 2005. – № 31.

3. http://habrahabr.ru/ – Habrahabr. – Режим доступа − свободный.

4. Левитин А. Алгоритмы: введение в разработку и анализ. Научно-популярное издание. – М.: Вильямс, 2006.

5. Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. – СПб.: БХВ- Петербург, 2010.

6. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. – М.: Вильямс, 2012.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.

8. Hromkovič J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. – Springer, 2004.

9. Мельников Б. Научим машину надежде? // Философские проблемы информационных технологий и киберпространства. – 2013. – № 1. – С. 51-64.

10. Гарднер М. От мозаик Пенроуза к надежным шифрам. – М.: Мир, 1993.

11. http://www.zcontest.ru/ – Открытый Зеленоградский турнир. – Режим доступа − свободный.

12. http://acm.sgu.ru/ – Saratov State University: Online Contester. – Режим доступа − свободный.

13. http://www.ioinformatics.org/index.shtml – International Olympiad in Informatics. – Режим доступа − свободный.

14. http:/ru.wikipedia.org/wiki/класс_NP – Класс NP. – Режим доступа − свободный.

15. Мельников Б. Программирование недетерминированных игр // Российская наука: дорога жизни. Сб. научно-популярных статей РФФИ. – М.: Октопус, 2002.

16. Мельников Б., Радионов А. О выборе стратегии в недетерминированных антагонистических играх // Программирование (РАН). – 1998. – № 5. – С. 55-62.

17. Рассел С., Норвиг П. Искусственный интеллект: современный подход. – Вильямс, 2006.

18. Люгер Дж. Искусственный интеллект. Стратегии и методы решения сложных проблем. – Вильямс, 2003.

19. Melnikov B., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems // Proceedings of 8th Int. Conf. on Enterprise Information Systems, ICEIS, 2006. – P. 360-364