Алгоритмизация задач (стр. 2 из 2)

Обозначим задачу через П, ее реализацию – через π. Под размером реализации будем понимать число символов, необходимых для записи входных данных этой реализации. Размер реализации π будет обозначаться

. Под временем решения t_πреализации πпонимается сумма времен выполнения всех команд программы.

Введем понятие класса задач Р, разрешимых за полиномиальное время. Этот класс состоит из всех задач П, обладающих следующим свойством: для любой

существует АЛГОЛ-программа u_П и полином f_П (·), такие, что любая реализация u_П за время t_π (u_П) ≤ f_П ( ). Примерами задач из класса Р являются задачи нахождения кратчайшего пути между двумя вершинами графа, минимального разреза в сети, минимального дерева.

Общепринято, что если задачу нельзя решить быстрее, чем за экспоненциальное время, то ее следует рассматривать как трудно разрешимую. Такие задачи образуют класс задач, недетерминированным образом разрешимых за полиномиальное время (NP-класс). Для определения NPкласса необходимо расширить язык, добавив к нему новую команду CHOOSE(x). Эта команда придает недетерминированным образом переменной х значение О или 1. Расширенный за счет этой команды язык назовем N-АЛГОЛ. Будем говорить, что программа на N-АЛГОЛе (N-программа) выдает на некоторую реализацию задачи ответ ДА, если N-программа выдает ответ ДА при некоторой комбинации значений, реализовавшихся при выполнении команд CHOOSE(x). В этом случае под временем выполнения N-программы будем понимать минимальное время для всех детерминированных программ, полученных путем замены CHOOSE(x) нулями или единицами, которые выдают ответ ДА. Если N-программа дает ответ НЕТ, то время ее выполнения для данной реализации не определяется.

Отметим, что приведенное определение времени для реализации с ответом ДА является в значительной мере условным, так как любая реальная схема вычислений является детерминированной и для нее необходимо просмотреть все последовательности реализации CHOOSE(x), чтобы определить, выдает ли хоть одна из них ответ ДА. Это потребует времени, равного сумме времен, необходимых для каждого набора реализаций.

Определим класс NPкак подкласс всех таких задач П, для которых существует N-программа и_П и полином f_π (·), такие, что для любой реализации π задачи П, для которой имеется ответ ДА, программа и_П выдает ответ ДА за время t_π(u_П) ≤ f_П (

). Так как любая программа является N-программой, то, очевидно, .

Дадим определение: множество А полиномиально сводимо к В (обозначается А < В), если существует функция φ, вычислимая за полиномиальное время и такая, что при

Если

то А и В полиномиально эквивалентны.

Множество Е называется NP-полным (или универсальной переборной задачей), если

и для любого имеем . Множество NP-полных задач обозначается NPC, .

Поиск полиномиально разрешимых подклассов NP представляет большой теоретический и практический интерес. Класс NP-полных задач включает в себя многие классические задачи комбинаторики, такие, как задачу о коммивояжере, о гамильтоновом цикле, задачи целочисленного линейного программирования. Многолетнее изучение этих задач не привело к нахождению алгоритма полиномиальной сложности, и задачи рассматриваемого класса считаются теоретически трудно разрешимыми. Такими являются не только комбинаторные задачи, но и обычные задачи линейного программирования. При решении задачи линейного программирования стандартным симплекс-методом невозможно дать верхнюю оценку числа итераций, в виде полинома от параметров, характеризующих размер задачи.

Результаты машинных экспериментов и опыт решения прикладных задач показывают, что возможности точных методов ограничены и не удовлетворяют потребностям практики. Это подтверждается и теоретическим исследованием эффективности точных методов. Потребности практики чаще всего покрываются приближенными решениями, что объясняется неизбежной неточностью задания исходной информации во многих прикладных задачах и тем, что модели отражают реальные ситуации лишь с определенной степенью приближения.

Обычно различают два уровня повышения эффективности алгоритмов – локальный и глобальный. Под локальным уровнем понимаются любые приемы, позволяющие расширить имеющиеся на сегодняшний день возможности решения задач. Глобальный уровень предусматривает перевод определенных классов задач на более низкий уровень (например, из NPв Р). Такой переход обычно означает переход от точных методов к приближенным.

В тех случаях, когда рассматриваемая задача не имеет характера вопроса, а явным образом содержит целевую функцию, уместно ставить вопрос о нахождении не точных, а приближенных решений с оценкой их отклонения от оптимума.

Рассмотрим задачу нахождения оптимума функции f(x) на допустимом множестве G. Пусть х* – оптимальное решение этой задачи. Говорят, что допустимое решение х является

-приближенным, если

(3)

где

> 0 - заданное число (f(x*j≠ 0).

Величина

> 0 есть гарантированная характеристика приближенного алгоритма и, если для любой реализации задачи алгоритм дает приближенное решение х и выполняется неравенство (3). Сравнение приближенных алгоритмов проводится на основании гарантированных характеристик, которые позволяют выбрать оптимальный в определенном смысле эвристический алгоритм решения задачи.

Различные типы экстремальных задач из класса NPCведут себя при нахождении

-приближенного решения по-разному. Например, поиск -приближенного решения задачи коммивояжера снова представляет собой задачу класса NPC; дня задачи же о ранце и некоторых других приближенных задач существуют алгоритмы поиска -приближенного решения с полиномиальной сложностью. Таким образом, перспективным направлением повышения эффективности комбинаторных алгоритмов является выявление подклассов задач из класса NPC, для которых поиск -приближенных решений переводит их в класс Р.

Для задач массового счета перспективным является применение статистически эффективных алгоритмов. Такие алгоритмы в подавляющем большинстве случаев оптимальны (

-приближенное решение). Иначе говоря, с ростом размерности задачи доля точно оптимизируемых задач ( -оптимизируемых) среди всех задач стремится к 1.

При оценке эффективности алгоритмов теоретическими методами следует иметь в виду, что полученные результаты дают представление о поведении задач в наихудших возможных случаях, тогда как для вычислительной практики существенно более важно их поведение в среднем. Действительно, экспериментально известно, что для решения задачи линейного программирования с mограничениями и п переменными обычно требуется от mдо 3т итераций; как правило, для задач не слишком больших размеров число итераций близко к 3m/2. Кроме того, теоретические результаты практически ничего не говорят о том, как будет вести себя конкретный алгоритм на конкретной задаче. Например, среднее время прямого поиска в списке пропорционально N/2, где N - число элементов списка, а двоичного поиска (список упорядочен по ключу) – пропорционально log₂N. Однако двоичный поиск неэффективен для небольших списков, которые подлежат частому изменению, так как введение нового элемента может вызвать переписывание всех элементов. Разработка алгоритмов является в основном творческой деятельностью, хотя существует множество типовых методов и алгоритмов, которые могут применяться для решения задач, возникающих в АСУ. К таким методам прежде всего относятся методы исследования операций.

Наиболее разработанными приближенными методами решения экстремальных задач являются комбинаторные методы, основная идея которых состоит в использовании конечности множества решений и в замене полного перебора направленным перебором. При этом главную роль в сокращении перебора играет оценка и отбрасывание неперспективных (т.е. заведомо не содержащих оптимума) подмножеств решений. Общая схема комбинаторных методов (методы типа схемы "ветвей и границ") применима практически ко всем задачам дискретного программирования независимо от их линейности или иных свойств. Эта схема может быть применена непосредственно к исходной естественной формулировке экстремальной задачи, без сведения ее к целочисленной задаче линейного программирования. Кроме того, эти методы чаще всего обеспечивают конечность вычислительного процесса по самому своему построению.

Долгое время единственным способом оценки эффективности комбинаторных методов являлось численное экспериментирование. Основной тенденцией, выявленной в достаточно представительных сериях экспериментов, является тенденция к экспоненциальному возрастанию трудоемкости вычислений при росте числа переменных. Теоретические исследования комбинаторных задач также приводят к заключению об экспоненциальной трудоемкости решения комбинаторных задач. Однако практика показывает, что комбинаторные методы позволяют решать задачи АСУ достаточно больших размеров.

Использование комбинаторных методов типа "ветвей и границ" положено в основу стандартного пакета ЛП АСУ (для решения задач линейного программирования).