Введение к работе
Актуальность темы. Для многих практически важных задач еще не найдены реально осуществимые алгоритмы. Поэтому коренным вопросом теории вычислительной сложности является следующий : существуют ли для конкретной задачи практически приемлемые алгоритмы или она имеет сложность, которая не допускает быстрых алгоритмов? В том случае, когда задача имеет высокую сложность, встает проблема разработки приближенных или эвристических алгоритмов (концепций вычислений) для ее решения.
Наиболее очевидный метод решения комбинаторных задач -поочередно перебрать все варианты решения и выбрать требуемый'. Однако, как правило, число вариантов очень велико и их просмотр потребовал бы больших затрат времени. Поэтому этот простой алгоритм не эффективен по времени и практически непригоден. Многие известные комбинаторные проблемы входят в класс NP-полных задач, поэтому маловероятно найти для них эффективные алгоритмы.
Острая практическая нужда в решении комбинаторных проблем заставляет искать пути преодоления трудностей, связанных с их решением. В качестве таких путей можно отметить следующие : улучшение переборных алгоритмов за счет разумной организации их работы, выделение эффективно разрешимых подклассов задач в обзей проблеме, разработка приближенных алгоритмов. Что касается улучшения организации работы переборных алгоритмов, то это позволило несколько расширить размерность решаемых задач, однако ситуация качественно не изменилась. Попытки выделить эффективно разрешимые подклассы из NP-полных задач не привели к сколько-нибудь значительным результатам. Особый интерес в классе приближенных методов представляют статистически эффективные алгоритмы.
Многие вопросы,касающиеся разработки эффективных алгоритмов для решения комбинаторных задач и оценки их вычислительной сложности, уже ' исследованы отечественными и зарубежными математиками. Отдельные аспекты данной проблемы широко освещены в работах М.Гэри, Д.Джонсона, С.Кука, Р.Ладнера, Ю.И.Журавлева, В.А.Йіеличева, М.М.Ковалева, М.К.Кравцова, В.И.Сарванова, Р~. И. Тышкевич, Н.Н.Метельского, В.А.Мощенского, А.Е.Будько, А.Д.Закревского, Н.А.Лепешинского и др. Этими учеными внесен значительный вклад в разработку теоретических и методологических
вопросов вычислительной сложности.
Однако до сих пор многие вопросы теории сложности далеки от своего окончательного решения и нуждаются в дальнейшем углублении и развитии. До настоящего времени не найдено универсального метода, классифицирующего задачи по их вычислительной сложности и для многих задач остается открытым вопрос о существовании эффективных алгоритмов их решения.
Необходимость углубления исследований в втом важном направлении и потребность практики в разработке вффективных алгоритмов для решения комбинаторных задач и обусловили выбор темы данной диссертационной работы. Настоящая работа является продолжением исследований, начатых О.В. Германом.
Связь работы с крупными научными программами и темами. Диссертация выполнялась с 1991 по 1994 год на кафедре АСУ Белгосуниверситета информатики и радиоэлектроники в соответствии с плановыми научными исследованиями по теме: "Логические и эвристические методы синтеза управления в технических системах".
Цель и задачи исследования. Основной целью исследования в диссертации является выяснение вопроса о существовании рекурсивной процедуры, устанавливающей подлинную вычислительную сложность комбинаторных проблем, а также разработка более вффективных (по сравнению с имеющимися) методов решения комбинаторных задач. Исходя из этого, разрабатывались методы для решения следующих задач: проблема выполнимости булевых формул исчисления высказываний, задача о покрытий множества, задача о максимальной нулевой подматрице, проблема поиска в пространстве состояний.
Научная новизна работы. Представлены новые результаты, касающиеся структуры класса NP, в частности показано, что при условии справедливости гипотезы Р * NP не существует алгоритма, который бы для каждой задачи из NP устанавливал, принадлежит ли она к классу Р или нет. Класс конструктивных трансрекурсивных алфавитных операторов может быть не замкнут относительно операции композиции при некоторой непрерывной хаусдорфовой топологии на пространстве слов. Доказан ряд теорем по корректности, сходимости и трудоемкости алгоритмов, которые легли в основу статистически-аффективных методов решения некоторых комбинаторных проблем.
Практическая значииость. Полученные теоретические
результаты, касающиеся алгоритмической неразрешимости некоторых свойств классов NP и Р, могут быть использованы при оценки относительной сложности задач из NP. Разработанные вычислительные методы дают возможность значительно ускорить решение комбинаторных задач, что существенно снижает временные затраты и повышает эффективность использования вычислительных средств. Программа, разработанная на базе новых методов, позволяет быстро решать задачи о покрытии большой размерности на персональных ЭВМ. Идеи доказательства статистической эффективности разработанных методов решения комбинаторных задач могут быть применены в дальнейших исследованиях при построении и обосновании новых методов дискретной оптимизации.
Экономическая значииость. Оценить экономическую значимость результатов диссертации на данном этапе не представляется возможным.
Основные положения диссертации, выносимые на зашиту:
-
Новые свойства классов NP и Р.
-
Топология конструктивных трансрекурсивных алфавитных операторов.
-
Статистически эффективные алгоритмы для решения комбинаторых задач о покрытии, независимом множестве графа, выполнимости КНФ и поиска в пространстве состояний.
Личный вклад соискателя. Основные результаты, приведенные в диссертационной работе, получены автором лично. Из совместно опубликованных работ в диссертацию вошли результаты, полученные-лично автором, а также результаты, полученные на паритетных началах с соавторами.
Апробация основных результатов. Материалы диссертации
докладывались на научно-практической конференции по
искусственному интеллекту (г. Туапсе), на научной конференции студентов, молодых ученых и аспирантов в БГУИР, а также на научных семинарах в Институте математики АНБ. Программа по решению задач о покрытии на основе разработанных методов принята в фонд алгоритмов и программ АН РБ с регистрационным номером 00679-
Опубликованность результатов. Основные результаты диссертации опубликованы в 11 работах.
Структура работы. Диссертация состоит из введения, общей
характеристики работы, четырех глав, выводов, списка
использованных источников (76 наименований) и приложения. Работа
изложена на 97 страницах машинописного текста, содержит 2
таблицы и 12 рисунков.