Что необходимо знать при разработке алгоритма
Интуитивная разработка алгоритмов
Если вы программист, то, возможно, у вас возникали ситуации, когда в выбранном игровом движке или библиотеке нет нужной функции. За этим следовал ужасающий момент, когда вам приходилось обыскивать весь Интернет в поисках кода, написанного людьми, решавшими эту проблему до вас (я говорю о вас, пользователи StackOverflow). Конечно, в этом нет ничего плохого (я и сам так поступаю), но очень часто вы можете сделать это самостоятельно, даже когда речь идёт о таких теоретических задачах, как геометрия или перетасовка. Я один из тех людей, которые всегда пытаются понять, как всё работает, и разве есть способ понимания лучше, чем прийти к нему самому, заново изобретя решение на лету (если, конечно, оно существует)?
Ставим перед собой пример задачи
В этой статье я опишу несколько этапов, которые, как мне кажется, довольно эффективны для самостоятельного выведения решающего задачу алгоритма. Чтобы применить их к чему-то конкретному, мы рассмотрим пример задачи: выпуклое разбиение простых многоугольников. Это звучит сложно и по-научному, но на самом деле это не так трудно.
Простой многоугольник — это многоугольник, который не пересекает сам себя и не имеет отверстий. Выпуклый многоугольник — это тот, в котором все углы меньше 180°. Разумеется, выпуклый многоугольник является простым многоугольником, а простой многоугольник — это сложный многоугольник (наиболее общий класс многоугольников), однако обратное не всегда верно.
Выпуклый, простой и сложный многоугольники.
Очень хорошее свойство выпуклых многоугольников заключается в том, что проверка коллизий между двумя произвольными выпуклыми многоугольниками очень проста (мы не будем рассматривать это в статье), в то время как проверка коллизий между двумя произвольными сложными, или даже простыми многоугольниками неприлично сложна. И здесь в дело вступает выпуклое разбиение: если мы сможем разделить простой многоугольник на несколько меньших выпуклых многоугольников, то коллизия с ним аналогична коллизии по крайней мере с одним многоугольником из разбиения. Поэтому наш пример задачи будет таким: имея массив точек, описывающих простой многоугольник, вернуть массив массивов, описывающий выпуклые многоугольники, «в сумме» дающие исходный многоугольник.
В идеале наш алгоритм должен уметь выполнять такую операцию.
Изучи то, с чем работаешь
При разработке алгоритмов самое важное — опознать задачу, которую хочешь решить, то есть то, что в первую очередь должен делать алгоритм. Может это и звучит глупо, но важнее не то, как должен работать алгоритм, а то, что он должен получать на входе и выдавать на выходе (в том числе и структуры данных, если это необходимо). Чаще всего знание структур данных, с которыми вам предстоит работать, помогает сформулировать свои рассуждения. Например, если вы создаёте алгоритм сортировки, то есть вероятность, что на входе он будет получать массив, но что должно быть на выходе: новый массив, ничего или сортировка на месте (непосредственное изменение самого исходного массива)?
Прочитайте мою предыдущую статью про алгоритм для кривых, это хороший пример алгоритма, входные и выходные данные которого довольно сложно характеризировать. На самом деле, можно сказать, что алгоритм на входе получает функцию числа с плавающей запятой и целого числа, где функция описывает параметрическую кривую, а целое числое — количество этапов сэмплирования. Алгоритм должен возвращать на выходе другую функцию числа с плавающей запятой, то есть функцию «кривой», которой посвящена статья, и она, в сущности является более обычной версией исходной кривой.
В нашем примере задачи, как уже сказано выше, алгоритм будет получать на входе массив точек и возвращать на выходе массив массивов точек. Входными данными будут вершины простого многоугольника, а выходными данными будут вершины всех выпуклых многоугольников в выпуклом разбиении исходного многоугольника.
В первую очередь — мозг и бумага
Начинать с бумаги и карандаша (или ручки, если вы любите рисковать) — один из лучших способов восприятия задачи, и это относится не только к созданию алгоритмов (и даже не только к программированию). Разумеется, программирование — не исключение, поэтому давайте приступим и начнём с самого начала.
Во-первых, для разработки интуитивного подхода чаще всего стоит начинать с зарисовки (или записывания, в зависимости от того, над чем вы работаете) простых случаев, которые вы можете решить самостоятельно, не особо задумываясь над тем, что вы делаете. В процессе этой работы или после него вам стоит проанализировать способ размышлений над ним и упорядочить его, разбив на этапы. Идея заключается в том, что, хотите вы этого или нет, вы выполняете алгоритм: ваш мозг — тоже компьютер, самый мощный компьютер, известный человеку. Настолько мощный, что способен посмотреть на собственную работу и понять её; настолько мощный, что вы уже выполняете алгоритм, который пытаетесь записать, но почему-то пока не понимаете его (потому что ещё не осознали его!). Однако вы можете выполнить алгоритм шаг за шагом, чтобы понять, как он работает. Для проверки этой теории давайте вернёмся к нашему примеру задачи и воспользуемся тем самым простым многоугольником.
Рекомендую вам самим нарисовать такой многоугольник, и в этот момент прервать чтение, чтобы попытаться разделить этот многоугольник на меньшие фигуры таким образом, чтобы в них никогда не было внутренних углов больше 180°. Я показал моё решение на рисунке выше, но поскольку все думают по-разному, в конце у нас могут получиться другие фигуры. И это абсолютно нормально, на самом деле выпуклое разбиение простого многоугольника не уникально!
Оба этих разбиения являются выпуклыми.
После того, как мы за секунды применили алгоритм вычислительной геометрии, на самом деле не зная его, с помощью самого мощного в известной вселенной компьютера, мы можем обернуться назад и разбить алгоритм на этапы. Повторюсь, все мы мыслим по-разному, поэтому этапы могут отличаться: я применю его к своим рассуждениям, а ваши будут достаточно похожими.
Во-первых, я задал себе вопрос: почему этот многоугольник ещё не выпуклый? Ответ пришёл довольно быстро: потому что некоторые из внутренних углов больше 180° (а именно два из них, показанные на рисунке стрелками), что по определению не даёт многоугольнику быть выпуклым. Чтобы исправить это, я затем подумал, что нужно разрезать угол, чтобы получить два меньших угла, которые в идеале будут не больше 180°. Этого можно достичь, соединив «дефектную» вершину с какой-нибудь другой вершиной многоугольника. Повторим это для всех дефектных вершин и получим наше выпуклое разбиение!
Пошаговое интуитивное выпуклое разбиение; стрелками показаны «дефектные» вершины.
Отлично, всё произошло довольно быстро. Но что же случилось на самом деле? На этом этапе мы можем записать зародыш алгоритма в псевдокоде, напоминающем естественный язык. Это не совсем предложение из языка, но и не совсем программирование. Оно просто выглядит достаточно похоже на программирование, чтобы запустить в мозгу установку «думай, как программист».
Из этого становится понятно, что нам нужен способ определить, является ли вершина «дефектной». Для этого достаточно просто проверить, образуют ли две составляющих вершину ребра угол больше 180°. Однако есть и другая, более серьёзная задача: какую вершину мы выбираем для соединения с дефектной вершиной? Давайте ещё раз подумаем, как мы делали это в прошлый раз.
Я делал это так: я стремился включить в каждый многоугольник как можно больше вершин, чтобы минимизировать количество многоугольников в разбиении. В общем случае это хорошая мысль, потому что эффективнее обрабатывать один прямоугольник, чем два треугольника, которые соединяются в прямоугольник — хотя они описывают одинаковую форму, у нас в одном случае получается четыре вершины, а в другом — шесть. Мы делаем это следующим образом: по порядку проверяем каждую вершину, начиная с дефектной, пока не найдём ту вершину, которая превращает наш многоугольник в невыпуклый, после чего мы выбираем последнюю вершину, в которой он оставался выпуклым. Это возможно всегда, потому что треугольник всегда является выпуклым, поэтому в наихудшем случае мы получим треугольник. Теперь наш псевдокод будет выглядеть так:
Но эта проверка может привести к паре сомнительных ситуаций: что, если вершина сразу после нашей дефектной вершины тоже является дефектной? Что, если в процессе проверки мы дойдём до дефектной вершины? Второй вопрос вроде бы решает себя благодаря тому наблюдению, что в выпуклом многоугольнике не может быть дефектных вершин, необходимо сразу же остановиться и выбрать её, чтобы ребро, которое мы добавляем при разбиении угла превратила её в «правильную» вершину. Первый вопрос можно решить интуитивно: когда мы решаем задачу вручную, этого никогда не происходит, потому что мы намеренно начинаем или с самой левой, или самой правой дефектной вершины, а очевидно не с той, которая находится между другими дефектными вершинами. В коде это просто преобразуется в то, что мы начинаем исследование с дефектной вершины, у которой точно есть правильный сосед. Это возможно всегда, потому что простой многоугольник всегда имеет хотя бы одну «правильную» (то есть недефектную) вершину. Найдите её, используйте, чтобы избавиться от одной дефектной вершины, повторите. Наш псевдокод теперь выглядит так:
И при выполнении код даст нам что-то подобное:
Один шаг алгоритма: выбор вершины, с которой нужно соединить дефектную вершину.
Выглядит довольно неплохо!
Остаётся ещё один вопрос: сейчас мы сохраняем наши многоугольники как массив вершин, а не рёбер, что же означает тогда «соединение вершин»? Мы не добавляем и не удаляем вершины из многоугольника, поэтому, наверно, не можем изменять массив вершин? Или можем?
Давайте посмотрим на то, как мы подходили к этому вопросу при работе вручную: после прорисовки ребра нам становится совершенно неинтересна часть, ставшая выпуклой, и мы сосредоточены только на оставшихся вершинах. Однако нас по-прежнему интересует только что добавленное ребро, и мы по-прежнему добавляем в поиск составляющие его вершины. У этого есть довольно чёткая интерпретация: мы просто разбиваем многоугольник на две части, выпуклую и простую, и нас перестаёт интересовать выпуклая часть при повторном применении алгоритма к новому, меньшему простому многоугольнику!
Теперь мы понимаем, что же означает «соединение»: в сущности, это создание нового многоугольника из всех вершин между начальной и конечной точками (а именно зелёной и красной на рисунке; «между» означает, что мы двигаемся по многоугольнику) с вычитанием этого многоугольника из исходного многоугольника с повторным вызовом алгоритма для получившейся меньшей группы вершин. Помните, что в обоих многоугольниках должны присутствовать обе вершины, составляющие добавляемое ребро!
Каждый раз, когда мы завершаем полную итерацию алгоритма и получаем одну выпуклую и одну простую части, мы должны добавить выпуклую часть в массив: это массив, который вернёт алгоритм после своего завершения, массив выпуклых компонентов исходного многоугольника. Что касается простой части, то, как вы уже догадались, для неё мы снова вызываем алгоритм.
Теперь наш псевдокод выглядит вот так:
И на этом всё, мы закончили! Наш этап работы с мозгом и бумагой закончен; после этого этапа вся дальнейшая работа относится уже к реализации, поэтому оставляю её вам!
Начало разработки алгоритма
В основе разработки алгоритма исходной задачи лежит следующая аксиома.
При невыполнении любого из этих требований алгоритм решения задачи построить невозможно.
Алгоритм решения задачи
Одним из основных алгоритмов является алгоритм решения задачи. В настоящее время существует множество всевозможных его вариантов. Авторы предлагают следующий алгоритм решения (любой решаемой) задачи, запишем его в виде сценария с детализацией:
Начало алгоритма
Составление документации (если есть необходимость).
Рассмотрим в качестве примера постановки задачи следующую задачу.
Задача.
Имеется шляпа, галоши, трансформатор, секундомер. Определить высоту здания.
Шляпа, галоши, трансформатор, секундомер – наличие этих предметов подсказывает о возможности решения данной задачи с точки зрения физики, точнее исследуя движение тела в поле тяготения. В этом случае важнейшей характеристикой предмета для нас будет парусность предмета, с которой связана сила сопротивления воздуха, а, следовательно, точность определения высоты здания.
Для определения высоты данного здания можно предложить следующий эксперимент: определить время свободного падения предмета с нулевой начальной скоростью. В качестве предмета необходимо использовать трансформатор, имеющий наименьшую парусность на единицу массы из всех предложенных предметов (секундомер не в счет, так как ему хватит одного падения, чтобы он перестал работать). По полученному времени, используя закон всемирного тяготения, определить высоту здания.
С крыши здания свободно падает трансформатор. Время его падения определяем секундомером. Используя закономерности свободного падения тела в гравитационном поле, определить высоту здания.
Формулировка данной задачи существенно отличается от формулировки исходной, но с ее помощью мы сможем решить исходную задачу.
Далее для формализованной задачи можно разрабатывать алгоритм решения.
Рассмотренный алгоритм – это первое приближение решения исходной задачи. Здесь важно понять, что для решения поставленной задачи необходима детальная проработка первого шага алгоритма, то есть постановки задачи. По исходной задаче необходимо получить формализованную задачу, которая и будет решаться.
Рассмотрим возможности построения алгоритма формализованной задачи.
Принцип нисходящего проектирования алгоритма
Для дальнейшей разработки решения задачи можно воспользоваться основным инструментом построения алгоритма – это принципом нисходящего проектирования алгоритма.
Принцип нисходящего проектирования алгоритма состоит в иерархически – последовательной разработке алгоритма от сложного к простому. Схематически стандартно предлагается следующее.
И объясняется, что данная задача разбивается на несколько подзадач, каждая из которых решает свою часть поставленной задачи. Это первый уровень детализации поставленной задачи. При необходимости одну или несколько подзадач первого уровня детализации разбивают (каждую) на несколько подзадач, образуя второй уровень детализации и т.д. Принцип нисходящего проектирования алгоритма реализуется, как принцип декомпозиции структур. Все это можно найти в любом учебнике по началам алгоритмики и программирования.
Основным следствием принципа нисходящего проектирования алгоритма (по мнению авторов) является следующее утверждение, относящееся к самому первому уровню детализации алгоритма:
Таким образом, алгоритм любой решаемой задачи можно на первом уровне детализации представить в виде алгоритма, состоящего из трех вспомогательных алгоритмов:
Подобное разбиение мы видим при решении задач физики, математики, химии и т. д. (дано…решение [в буквенном виде…числовое решение]…ответ) названия разные – суть одна.
Это определяется тем, что исходные данные вводятся извне. Данным исполнителем проводится обработка информации. Результат обработки выводится на внешние носители информации. Наиболее четко это видно на вычислительных задачах.
Таким образом, самый верхний уровень необходимо рассматривать как один неделимый блок – формулировка исходной (формализованной) задачи. Далее самый первый уровень детализации необходимо представляется тремя подзадачами. Назовем это ТРИЕДИНОЙ ЗАДАЧЕЙ АЛГОРИТМИКИ. Она едина потому, что каждая из подзадач отдельно от остальных не имеет смысла. И это три задачи, так как каждая из них достаточно замкнута, имеет свои особенности и, поэтому, может разрабатываться отдельно от остальных. А так как задач ВводаИнформации и ВыводаРезультатов ограниченное количество и они решаются отдельно, то далее принцип нисходящего проектирования алгоритма применяется только к задаче ОбработкиИнформации.
Триединая задача алгоритмики
Сформулируем понятие триединой задачи алгоритмики в следующем определении.
Каждую из этих задач можно рассматривать в данном алгоритме как вспомогательный алгоритм. В приложениях №№ 1, 2 (Приложение 1, Приложение 2) рассмотрены задачи Ввода/Вывода для простой переменной. Важно отметить, что разработку алгоритма любой решаемой задачи не только можно, а чаще и необходимо, начинать с триединой задачи алгоритмики.
В дальнейшем геометрическое представление триединой задачи удобно делать в виде:
Над стрелкой задаются имена переменных и их типы, под стрелкой ограничения на эти переменные в заданной задаче; как уже говорилось, стрелки суть входной и выходной потоки, прямоугольник – блок обработки информации.
Важно уяснить, что триединая задача алгоритмики есть не что иное, как алгоритм решения задачи на первом уровне. Действительно, в виде сценария этот алгоритм можно представить в виде:
Для самостоятельной работы ученикам можно предложить любые (по сложности), но формализованные задачи. Основное задание – сформулировать триединую задачу для исходной задачи, то есть выделить и сформулировать задачи: ввода информации, вывода результатов и сформулировать задачу обработки информации. В Приложении 3 приведен пример решения подобных задач.
Обобщая изложенное, можно утверждать, что…
В основе разработки алгоритма исходной задачи лежит следующая аксиома.
Авторы предлагают следующий алгоритм решения (любой решаемой) задачи:
Первым шагом в построении алгоритма является, согласно принципа нисходящего проектирования алгоритма, ТРИЕДИНАЯ ЗАДАЧА АЛГОРИТМИКИ – это алгоритм решения формализоанной задачи. Он представляет исходную формализованную задачу как совокупность трех подзадач (вспомогательных алгоритмов):
При этом задачи ВводаИнформации и ВыводаРезультатом можно и нужно решать самостоятельно.
В заключении отметим, что данный материал нужно использовать в 10–11-х классах. Для его проработки с учениками требуется не менее 1часа.
Двадцать вопросов, которые помогают разработать алгоритм
Как разработать алгоритм, решающий сложную задачу? Многие считают, что для этого нужно «испытать озарение», что процесс этот не вполне рационален и зависит от творческой силы или таланта.
На самом деле решение любой задачи сводится к сбору информации о наблюдаемом объекте. Причем этот принцип применим как для решения самых сложных научно-исследовательских задач, так и для решения прикладных задач. Работа изобретателя напоминает не столько работу волшебника, сколько путешествие первооткрывателя по неизведанной территории. Главное качество хорошего изобретателя – умение собирать информацию.
Если вы хотите решить сложную задачу, собирайте информацию в самых разных направлениях. Ответив на следующие 20 вопросов, вы легко выстроите план работы над задачей.
Вопрос №1. Кто?
Начиная решать определенную задачу, составьте максимально длинный список людей, имеющих непосредственное отношение к ее решению. Выясните:
— кто в первую очередь заинтересован в ее решении?
— кто уже занимался решением этой или смежной задачи?
— кто определяет, хорошо задача решена или плохо?
— с кем можно советоваться по ходу решения задачи?
— кто может проверить решение?
— кто является автором статей в этой области?
Вопрос №2. Для чего?
Спросите себя несколько раз: «Почему я хочу решить эту задачу? Для чего это нужно?» Часто оказывается, что решение задачи A необходимо для того, чтобы решить задачу B, но при этом задачу B можно решить и другим путем. В этом случае, начиная думать над исходной задачей А, мы лишь теряем время.
Вопрос №3. Как?
Какими методами я буду руководствоваться, решая данную задачу? Как будет структурирован процесс ее решения? Есть ли готовые методологии, которые можно использовать?
Вопрос №4. Что?
Какие объекты присутствуют или подразумеваются в данной задаче? Нарисуйте их на бумаге и обозначьте стрелками всевозможные отношения между ними, связанные с данной задачей. Есть ли неучтенные или лишние объекты?
В каждый объект должны приходить и из каждого объекта должны исходить примерно одинаковое количество стрелок. В противном случае, как правило, мы либо упускаем важные связи между объектами, либо придаем неоправданно большое значение некоторым связям.
Вопрос №5. Когда?
Посмотрите на задачу с точки зрения времени. Выясните:
— как быстро должны работать отдельные блоки алгоритма?
— какие внешние факторы, связанные со временем, могут повлиять на их работу?
— сколько времени есть у вас на разработку, программирование и тестирование алгоритма?
Вопрос №6. Где?
Посмотрите на задачу с точки географической точки зрения. Ответьте на вопросы:
— где, в каких странах, городах, районах будет использоваться ваше решение?
— на каких компьютерных платформах оно будет работать?
— какие еще вопросы, связанные с месторасположением и географией, имеют отношение к данной задаче?
Вопрос №7. Что было?
Какие решения данной задачи существовали год, два, десять, сто лет назад? Ни одна задача не возникает на пустом месте – скорее всего, люди уже справлялись с этой проблемой в прошлом. Интересно и полезно бывает узнать, как именно это происходило.
Вопрос №8. Что есть?
Какие решения этой задачи существуют и используются сегодня? Выясните это и добейтесь четкого понимания альтернативных решений, доступных уже сейчас.
Вопрос №9. Что будет?
Как будут решать эту же задачу люди через три, пять, десять, сто лет? Определите этот тренд хотя бы приблизительно, подумайте над этой темой, пофантазируйте.
Прекрасно, если алгоритм, над которым вы сейчас работаете, будет частью долговременного тренда, а не устареет морально через год после реализации.
Вопрос №10. Частью чего является?
Частью какой более масштабной задачи (или системы) является данная задача? А частью чего является эта более масштабная система?
Вопрос №11. Из чего состоит?
Какие более мелкие подзадачи являются частью исходной задачи? На какие части можно разбить исходную задачу? А на какие еще более мелкие части можно разбить подзадачи?
Вопрос №12. На что похоже?
На что похожа данная задача? В данном случае ассоциации могут быть сколь угодно длинными и метафоричными, и это даже хорошо. Прекрасно, если вы найдете сходное явление в совершенно другой области человеческой деятельности.
Это очень мощный вопрос. Именно на аналогиях между совершенно неожиданными областями знания находятся самые красивые и гармоничные решения.
Вопрос №13. Что вижу?
Визуализируйте задачу, ее решение и все его компоненты. Нарисуйте их. Побудьте ребенком (или дизайнером), найдите наиболее подходящие цвета (даже для виртуальных, абстрактных объектов). Прочувствуйте визуальную гармонию этой задачи или найдите «некрасивые», проблематичные места, если такие есть.
Вопрос №14. Что слышу?
Это очень сложный и полезный вопрос, поскольку та мощнейшая часть мозга, которая отвечает за обработку звуковой информации, у большинства современных людей слаборазвита. При этом я знаю гениальных ученых и инженеров, которые именно «слышат» решение той или иной задачи.
Итак, постарайтесь «услышать» взаимодействие всех элементов задачи (для этого удобным бывает закрыть глаза), услышать характерные звучания ее элементов. Услышьте разговоры и тембры голосов людей, применяющих решение вашей задачи на практике.
Вопрос №15. Что чувствую?
Этот вопрос также может показаться необычным, хотя и не в такой степени, как предыдущий. Ощутите тактильные, температурные, вкусовые, дыхательные ассоциации, вызываемые данной задачей. Некоторые решения могут показаться «крепкими», в то же время как другие «холодными» или даже «горькими».
Подключите часть вашего мозга, отвечающую за ощущения, к анализу задачи. Конечно, это нестандартный путь анализа научной информации, но он также бывает полезным.
Вопрос №16. Каким может быть идеальное решение?
Пофантазируйте, как можно решить эту задачу в идеале; придумайте что-то совершенно невероятное — чем невероятнее, тем лучше. На этом принципе построен метод «мозгового штурма», когда предлагаются любые, даже самые неожиданные решения.
Представьте себе, что у вас нет границ, а условия работы самые благоприятные. Что бы вы могли сделать в этой ситуации?
Как можно было бы сделать решение этой задачи совершенно великолепным?
Вопрос №17. Почему все закончится неудачей?
Побудьте брюзгой и пессимистом-критиком. Найдите все причины, из-за которых у вас не получится решить эту задачу; а также все организационные проблемы, которые приведут к провалу этого проекта. Тщательно их запишите — чем больше, тем лучше.
Когда вы выйдете из состояния критики, записанное станет бесценной информацией о тех опасностях, которые поджидают вас на пути решения задачи, и от которых следует уклониться.
Вопрос №18. В чем польза для меня?
Какие выгоды лично вы извлечете из решения данной задачи? Чему научитесь? Сколько заработаете? Какие важные связи и контакты приобретете? Как улучшите свою репутацию?
Вопрос №19. В чем польза для других?
Какую именно пользу от решения этой задачи получит заказчик, клиент, тот человек, который будет пользоваться результатами вашего труда? Имеет ли решение вашей задачи большое значение для него?
Вопрос №20. В чем польза для общества?
Как повлияет решение вашей задачи на все общество, в котором мы живем? Будет ли она общественно-значимой? Чем и как она поможет всему человечеству в целом?
Уверен, что ответив на все эти вопросы, вы узнаете намного больше о той задаче, которая перед вами стоит. Причем, почти наверняка, вы увидите эту задачу с самых неожиданных сторон — и ваша фантазия сама подскажет вам необычные, надежные, красивые и гармоничные способы ее решения.
Конечно, ответы на эти вопросы не всегда приводят к получению окончательного решения. Существует много других способов, методов, которые помогают найти элегантное решение сложной задачи.
И все же я уверен, что вы ощутимо улучшите свою скорость и качество решения алгоритмических задач, если используете эти 20 опорных вопросов в своей научно-исследовательской и инженерной деятельности.