Жизнь человека можно представить как цепь последовательно решаемых больших и малых проблем. Человек планирует свою деятельность на большие временные периоды, на средние периоды времени и краткосрочные, например, на день и даже часы.
Это планирование, как правило, носит многофакторный характер, то есть зависит от многих обстоятельств. Ожидаемый результат деятельности носит вероятностный, неоднозначный характер.
При таком планировании возникает интуитивное понятие сложной проблемы. Сложная проблема зависит от многих факторов и вероятность её разрешения не очевидна. Человек всячески проигрывает в воображении варианты решения проблемы при различных своих действий, пытаясь найти оптимальное решение. В зависимости от индивидуальных качеств личности, уровня образованности это планирование может носить правильный логически выстроенный подход, либо хаотические метания от одного варианта решения проблемы к другому. При хаотическом подходе могут быть пропущены лучшие варианты разрешения проблемы или даже совсем не найдены её решения.
Пример правильного подхода, алгоритма к решению проблем любой сложности демонстрируется в математике. Большинство людей после школы выносят представления о математике как о некотором наборе сложных формул, которые в повседневной жизни практически не встречаются и поэтому кажутся излишними.
ОCНОВНОЕ значение изучения математики состоит в том, чтобы показать на конкретном примере (математических задачах) методику, как формулируются и как решаются любые проблемы. Второе значение математики, это формирование у человека представления о количественных соотношениях в этом мире и о его геометрии.
Проблема определения трудности решения математических задач возникла практически одновременно с возникновением математики. Человечество всегда волновал вопрос, почему одни задачи решаются легко, а другие с трудом; один человек мог решить задачу, а другой нет. На бытовом языке, в школьной среде, формируется представление, если я решил задачу, то она простая, а если не решил то сложная.
Другой важнейший вопрос, связанный с трудностью задач, может быть сформулирован так: если задачу не удаётся решить, то существует ли у неё решение. Примеров таких задач, известных с древности, очень много, это и квадратура круга, и великая теорема Ферма и т.п. В настоящее время таких “неразрешимых” задач, задач для решения, которых не найдено алгоритмов еще больше.
Интерес к проблемам существования решения задач и создания алгоритмов обострился в конце 19 века. В это время появились различные механические устройства для автоматического проведения вычислений. С появлением реальных электронных вычислительных машин разработки по теории алгоритмов стали особенно актуальны и фактически обеспечили начало современной информационной революции. На часть вопросов, которые исследовались ранее, ответы были получены, но возникли новые более глубокие проблемы, связанные с решением задач и вычислимостью функций.
Для того чтобы проводить сравнительный анализ трудности задач, определим само понятие задачи и ряд характеристик задачи.
Под массовой задачей П понимается некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит несколько параметров, или свободных переменных, конкретные значения которых не определены.
Задача определяется следующей информацией:
1. общим списком всех параметров,
2. формулировкой тех свойств, которым должен удовлетворять ответ, т.е. решение задачи.
Индивидуальная задача I получается из массовой задачи П, если всем параметрам массовой задачи присвоить конкретные значения.
Под алгоритмом решения задачи будем понимать общую выполняемую шаг за шагом процедуру, позволяющую её решить.
Будем говорить, что алгоритм решает массовую задачу П, если он применим к любой индивидуальной задаче I из П и дает её решение.
Понятие эффективности алгоритма связано со всеми вычислительными ресурсами, необходимыми для его реализации. Обычно под «эффективным» алгоритмом решения задачи понимают самый быстрый алгоритм.
Время работы алгоритма удобно выражать в виде функции от одной переменной, характеризующей размер индивидуальной задачи, т.е. объёмом входных данных, требуемых для описания задачи.
Описание задачи осуществляется следующим образом.
Введём ; множество символов, которые образуют некоторый алфавит. Цепочки из символов этого алфавита образуют слова, множество таких цепочек ;*. Любое подмножество слов будем называть языком в алфавите ;.
Соответствие между задачами и языками устанавливаются с помощью схем кодирования.
Схема кодирования l задачи П описывает каждую индивидуальную задачу из П подходящими словами в некотором фиксированном алфавите .
Задача П и схема кодирования l разбивает слова ;* на три класса: слова, не являющиеся кодами задачи П, слова, являющиеся кодами индивидуальных задач П с положительным ответом на вопрос, и слова с отрицательным ответом.
Входная длина индивидуальной задачи I из П определяется числом символов в цепочке полученной применением к задаче I схемы кодирования для массовой задачи П. Именно это число используется в качестве формальной характеристики размера индивидуальной задачи.
Процедура решения любой задачи состоит в последовательном переводе её из описания на одном языке в описание в другом.
Приведём простейший пример кодирования массовой задачи.
1. Массовая задача может быть описана на естественном языке.
Дано число А и число В. Чему равно произведение чисел?
Индивидуальная задача. Дано число А равное двум и число В равное двум. Чему равно произведение чисел?
2. Математическая кодировка массовой задачи: А*В = ?
Индивидуальная задача 2*2=?
3. Массовая задача на языке программирования Сi.
1. /*Произведение двух чисел
2. #include ;<studio.h>;
3. void main ()
4. ;
5. int a,b,s;
6. printf(“\n Введите числа а и в”);
7. scanf(“”,&a,&b);
8. s=a*b;
9. printf(“\n Произведение S= ”,s);
10. ;
Индивидуальная задача может быть получена двумя способами, либо через введение значений А и В, либо изменением восьмой строки s=2*2;
Очевидно, что в приведённом примере длина кода задачи зависит от длины записи перемножаемых чисел и длинны результата.
В теории алгоритмов принято различать сложность алгоритма по изменению его длины в зависимости от входных параметров.
С каждой задачей П связана не зависящая от схемы кодирования функция определяющая длину записи алгоритма в символах выбранного алфавита, которая «полиномиальной эквивалентна» длине кода индивидуальной задачи, получаемой при кодировании функция в символах выбранного алфавита.
Приведем схему решения школьных задач. Пусть задана либо текстовая задача, либо задача по геометрии.
Имеется, как правило, индивидуальная постановка задачи, то есть, задана задача с конкретными параметрами, например, задана скорость автомобилей, некоторые расстояния и формулируется вопрос найти пройденный путь или что-то подобное. В геометрических задачах заданы размеры. В старших классах появляются массовые задачи, когда заданы параметры, а не конкретные значения.
На первом этапе решения задача переводится в задачу, записанную на формальном языке с использованием математической символики. Вводятся неизвестные и записываются уравнения, решив которые можно получить ответ.
На втором этапе осуществляется тождественные преобразования полученных уравнений: замены переменных, выполняются группировки подобных членов и тому подобное. На каждом этапе преобразовании мы переходим от исходной задачи к эквивалентной упрощенной задаче. В результате находится решение.
Можно ввести понятие временной сложности алгоритма, функцию которая отражает затраты времени для его работы. Это будет функция, которая каждой длине n (индивидуальной задачи) ставит в соответствие максимальное время, затрачиваемое алгоритмом на решение индивидуальных задач. Функция временной сложности полностью определена, если зафиксирована схема кодирования, определяющая входную длину индивидуальной задачи, и выбрано вычислительное устройство (или его модель), определяющее время работы. Поскольку речь идет о решении задачи человеком, в данном подходе в роли вычислительного устройства выступает конкретный человек.
Заметим, что сложность алгоритма связана с используемой для решения задачи памятью, причем это относится как компьютеру, так и к человеку.
Например, пусть требуется определить число единиц в двоичной последовательности длины n. Алгоритм, который считает единицы, последовательно просматривая все элементы последовательности, имеет трудоёмкость O(n). Можно предложить другой алгоритм, который требует 2^n ячеек памяти для хранения всех двоичных последовательностей длины n, причём номер ячейки это двоичная последовательность длины n, а в самой ячейке хранится число единиц этой последовательности. Задача решается за одно обращение к памяти, т.е. трудоёмкость алгоритма O(1).
Большинство алгоритмов носят полиномиальный характер. Сложность нарастает, как некоторая степень от количества параметров задачи. Например, количество умножений при решении системы линейных алгебраических уравнений растет, как n^3, где n – количество неизвестных.
Все не полиномиальные алгоритмы, как правило, считаются экспоненциальными. Большинство экспоненциальных алгоритмов являются вариантами полного перебора возможных частных решений задачи, и такие задачи относятся к задачам класса NP (Nondeterministically Polynomial).
Приведём пример наиболее широко изучаемых переборных массовых задач в теории алгоритмов.
Задача о коммивояжере.
Путешественник должен объехать n городов, побывав в каждом городе один раз и вернуться в исходный город, при этом затратить минимальную сумму на поездку.
Вопрос. Существует ли «маршрут», проходящий через все города из C, длина которого не превосходит некоторую сумму В?
Очевидно, что при малом количестве городов решение находится перебором возможных вариантов, но ростом n количество различных вариантов маршрута растёт как n!.
Задача о рюкзаке.
Дано n предметов, для каждого из которых известен объём и стоимость. Требуется этими предметами заполнить рюкзак ограниченного объема так, чтобы суммарная стоимость упакованных предметов была максимальной.
К NP сложным задачам относятся задачи поиска, например поиск корабля в игре «морской бой», поиск мин в игре « сапер», составление любого расписания, планирование производства и т.д.
Для исследования задач NP используют недетерминированный алгоритм, который состоит из двух этапов:
1. «угадывание» решения,
2. проверка найденного решения.
Заметим, что проверка осуществляется за полиномиальное время.
В 1971 году вышла работа С.А. Кука «Сложность процедур вывода теорем», в которой было показано:
1. Если одна задача сводится к другой задаче за полиномиальное время, то любой полиномиальный алгоритм второй задачи может быть превращён в полиномиальный алгоритм решения первой задачи.
2. Было показано, что любая задача из класса NP за полиномиальное время может быть сведена к тестовой задаче NP сложности.
Проверка решения каждой индивидуальной задачи из класса NP осуществляется за полиномиальное время, а выбор этого решения случайным образом, то есть имеет место недетерминированный алгоритм решения. Число вариантов решений, которые надо проверить растёт экспоненциально с ростом входных параметров задачи.
Вопрос о взаимоотношении классов P и NP является фундаментальным вопросом теории алгоритмов. Высказана гипотеза, что класс Р не равен классу NP, но доказательства её нет. Если бы она была доказана, то для каждой конкретной задачи можно было бы определить, к какому классу она принадлежит, к классу Р или к классу трудно решаемых задач NP.
Как конкретно можно применять данных подход для решения любой жизненной проблемы.
1. Записать все входящие параметры проблемы, лица, обстоятельства и т.д.
2. Сформулировать вопрос.
3. Попытаться оценить «сложность» задачи. Как усложняется задача, если добавить еще какие-то параметры. Как упростится задача, если какой-то параметр отбросить.
4. Если задача имеет небольшую сложность, то можно попытаться найти алгоритм действий.
5. Если задача сложная, то нужно рассмотреть возможность случайных пробных решений. Что будет если сделать так, а что будет, если сделать по-другому? Проиграв несколько раз ситуацию выбрать оптимальное решение.
6. Если решение проблемы не очевидно и задача сложная в смысле, введенном выше, то стоит попытаться изменить постановку задачи? Например, сформулировать так, чтобы изменилась целевая функция.
В любом случае такой анализ позволит глубже понять суть проблемы и найти оптимальное решение.