Сетевой научный журнал "Философские проблемы
информационных технологий
и киберпространства" (ISSN:2305-3763)

Алгоритмизация труднорешаемых задач. Часть II. Более сложные эвристики // стр. 4-14

DOI: 10.17726/philIT.2014.7.1.004.023

Автор: Громкович Ю., Мельников Б.Ф.

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

Ключевые слова: труднорешаемые задачи; эвристические алгоритмы; искусственный интеллект; задачи дискретной оптимизации.

Ссылка: Громкович, Ю.; Мельников, Б. Ф. Алгоритмизация труднорешаемых задач. часть II. Более сложные эвристики. // Философские проблемы информационных технологий и киберпространства, 2014, №1  (7), pp. 4–14. URL:http://cyberspace.pglu.ru/upload/iblock/fa2/hromkovich.pdf.

Полный текст статьи



Reference: Hromkovič, Juraj; Melnikov Boris (2014): Algorithmics for hard problems. Part II. Some difficult heurisrics. In Philosophical Problems of Information Technologies and Cyberspace) 7 (1), pp. 4–14. Available online at http://cyberspace.pglu.ru/upload/iblock/fa2/hromkovich.pdf.



← Назад в выпуск