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

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

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

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

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





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