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

Одна из причин, по которой некоторые вещи могут казаться такими сложными, заключается в том, что они являются многоэтапными задачами, и они предполагают, что мы сначала понимаем проблему, затем рассматриваем простейшее решение, а затем повторяем это решение, чтобы сделать его лучше, эффективнее и элегантнее. . Я часто вспоминаю фразу, которую приписывают Кенту Беку, который сказал: Сделай это, сделай это правильно, сделай это быстро.

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

В этой серии статей мы затронули несколько сложных тем, но одна из наиболее сложных тем возникла совсем недавно, когда мы столкнулись с проблемой коммивояжера (TSP ). Поскольку мы уже сделали первый шаг, пытаясь найти решение для TSP, которое просто работает, теперь мы можем заняться следующими шагами: сделать его правильным (или более элегантным) и, надеюсь, немного быстрее.

Никаких забавных факториалов

Когда мы впервые наткнулись на задачу коммивояжера, мы имели дело с продавцом, перед которым стояла довольно простая задача: посетить четыре города в определенном порядке, при условии, что он посетил каждый город один раз и оказался в том же городе, что и он. началось в.

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

Мы также начали понимать, что факторное время выполнения метода грубой силы для решения TSP со временем не будет масштабироваться. Фактически, мы поняли, что его нельзя будет масштабировать почти немедленно! Например, что произойдет, если нашему коммивояжеру нужно будет посетить не только четыре города, но и пять городов? Когда мы имели дело с четырьмя городами, мы сделали шесть рекурсивных вызовов. Итак, добавить еще один город не должно быть слишком сложно, не так ли? В конце концов, это всего лишь один город.

Не совсем так. Вот как наш алгоритм масштабируется с четырех городов до пяти:

Когда нашему продавцу нужно было посетить всего четыре города, мы сделали шесть рекурсивных звонков. Но теперь мы буквально в четыре раза увеличили наше дерево «потенциальных путей», что кажется действительно, действительно, действительно плохим. Решение TSP для пяти городов означает, что нам нужно сделать 4! или четыре факториальных рекурсивных вызова, используя технику грубой силы. Как оказалось, 4! равно 24, что означает, что теперь нам нужно сделать 24 рекурсивных вызова, чтобы разместить только один дополнительный город на карте нашего коммивояжера.

Если мы сравним иллюстрированную версию дерева рекурсивных вызовов функций из нашего предыдущего примера TSP с тем, что нарисовано выше, мы начнем получать довольно хорошее представление о том, насколько неустойчиво Факториальный алгоритм действительно есть.

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

Если постоянное, логарифмическое и линейное время - это хорошо, а квадратичное и экспоненциальное время - плохо, остается исследовать только одну вещь: уродливую. Факторные алгоритмы именно такие: уродливые.

Для алгоритма, который выполняется за время факториала или O (n!), любые операции, которые необходимо выполнить, в конечном итоге займут n! больше времени. в отношении данных, с которыми выполняется операция, или набора входных данных.

Хорошо, но что это на самом деле означает? Что ж, давайте посмотрим, как факторный алгоритм сравнивается со всеми другими формами нотации Big O, с которыми мы уже знакомы.

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

Все это говорит о том, что наш первый подход к решению TSP с использованием прямой рекурсии, вероятно, не лучшее решение. Да, это работает, но, вероятно, это не так «правильно», как могло бы быть; его можно было улучшить и, конечно, сделать более элегантным. И, конечно, не быстро - совсем!

Итак, как мы можем улучшить эту первую сделанную нами попытку?

Что ж, если мы вспомним наш набег на динамическое программирование (DP), мы вспомним, что существует несколько подходов. когда дело доходит до решения проблемы DP. В своем первоначальном решении этой проблемы мы попытались решить TSP, используя своего рода подход сверху вниз: мы начали с большой сложной проблемы и разбили ее на более мелкие. части. Затем, когда мы подошли к нашему базовому случаю и расширили проблему до минимально возможных частей, мы использовали рекурсию, чтобы построить все возможные пути, по которым может идти наш коммивояжер, что позволило нам выбрать лучший (самый короткий) перестановка всех найденных нами путей.

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

Есть только один способ узнать - мы должны попробовать!

Переворачивая TSP с ног на голову

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

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

На второй взгляд, мы заметим, что здесь происходит кое-что интересное: сначала мы начинаем с более сложного вызова функции, а затем изнутри вызываем три рекурсивных вызова функций из внутри это. Каждый из этих трех рекурсивных вызовов функций порождает еще два собственных рекурсивных вызова, что создает третий уровень «дерева» вызовов этой функции. Это, конечно, согласуется с нашим рабочим определением подхода сверху вниз: сначала начать с самой большой проблемы и разбить ее на мельчайшие части. Но теперь, когда мы можем более четко видеть мельчайшие детали, мы можем изменить наш подход с метода сверху вниз на метод снизу вверх.

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

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

Мы увидим, что каждый из этих вызовов соединяется с w, как и следовало ожидать. Напомним, что мы используем нотацию списка, чтобы отслеживать узлы, к которым мы можем перейти. Поскольку мы имеем дело с минимально возможными подзадачами, нам некуда перейти из этих узлов; вместо этого все, что мы можем сделать, это вернуться к нашему начальному узлу w. Вот почему каждый из списков для этих трех подзадач пуст ({}).

Однако здесь нам действительно нужно отслеживать стоимость и расстояние, поскольку нам неизбежно придется найти кратчайший путь для нашего коммивояжера, независимо от того, используем ли мы сверху вниз или снизу вверх. Таким образом, нам нужно будет отслеживать расстояние между узлами при построении нашего дерева «снизу вверх». На изображении выше мы видим, что у нас есть значения 6, 1 и 3 рядом с узлами x, y и z соответственно. Эти числа представляют собой расстояние от каждого узла до исходного узла w.

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

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

Итак, как бы выглядел второй уровень «дерева» вызовов нашей функции? Что ж, вопрос, на который мы пытаемся ответить для каждой из наших минимально возможных подзадач, заключается в следующем:

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

Другой способ думать об этом - в терминах узлов. В конечном итоге мы пытаемся определить, какие возможные узлы позволят нам добраться до рассматриваемого узла. Таким образом, в случае узла x единственным способом добраться до узла x потенциально может быть узел y или узел z. Помните, что здесь мы используем подход снизу вверх, поэтому мы почти возвращаемся назад, начиная с конца, и возвращаемся обратно по кругу.

Обратите внимание, что мы отслеживаем стоимость / расстояние от каждого из этих узлов до следующего. Они нам очень скоро понадобятся!

Опять же, мы можем немного расширить это «дерево» вызовов функций, чтобы добавить еще один уровень. Помните, мы пытаемся ответить на вопрос: какая еще функция могла бы вызывать эту функцию, которую мы не можем расширять дальше?

На изображенном здесь рисунке мы увидим, как это на самом деле выглядит на практике. Например, глядя на крайнюю левую ветвь этого «дерева» вызовов функции, мы заметим, что единственный возможный вызов функции, который позволит нам добраться до пустого узла x, - это либо узел y, либо узел z, где набор содержит только возможный «следующий» узел x, например: {x}. Для обоих узлов y и z в крайнем левом поддереве мы увидим, что единственный возможный способ добраться до y - из узла z, когда набор содержит как x, так и y (или {x, y}). Точно так же единственный возможный способ добраться до z - из узла y, когда набор содержит как x, так и z (или {x, z}).

Эта визуализация иллюстрирует то, что мы имеем в виду, когда говорим, что перечисляем вызовы функций, а не перечисляем потенциальные пути. По мере того, как мы продолжаем определять все возможные вызовы функций, которые позволяют нам вызывать другие функции изнутри, кое-что начинает становиться очень очевидным: здесь у нас есть некоторые перекрывающиеся подзадачи!

Мы заметим, что есть два вызова функций, которые являются экземплярами z, когда его набор содержит как x, так и y (или {x, y}), который выделен желтым цветом. Точно так же есть два вызова функций, которые являются экземплярами y, когда его набор содержит как x, так и z (или {x, z}), выделенные розовым цветом. Наконец, мы увидим два вызова функций, которые являются экземплярами x, когда его набор содержит как y, так и z (или {y, z}), выделенные зеленым цветом.

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

Динамическое программирование на помощь продавцу

Теперь, когда мы определили наши перекрывающиеся и повторяющиеся подзадачи, осталось сделать только одно: конечно же, исключить повторение!

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

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

Теперь становится очевидным, чем подход снизу вверх отличается от нашего предыдущего метода сверху вниз.

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

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

На иллюстрации, показанной ниже, каждый из вызовов функций, которые позволяют нашему продавцу перемещаться от одного узла к другому, имеет связанный с ним номер (стоимость или расстояние). Продолжая движение вниз по этому дереву, мы суммируем стоимость каждого набора вызовов функций. Например, если мы выберем вызовы функций, ведущие из w <- x <- y <- z, мы суммируем стоимость между этими узлами, которая составляет 6 + 4 + 2 = 12.

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

В конце концов, продолжая суммировать расстояния / затраты, мы увидим, что в итоге получили не те же результаты, что и наш метод грубой силы, полученный на прошлой неделе. Самая короткая цена для нашего коммивояжера будет 11, и есть два возможных пути, которые позволят им достичь этой самой низкой стоимости. Однако, используя подход снизу вверх, мы оптимизировали наш алгоритм TSP, поскольку у нас больше нет шести рекурсивных вызовов, выполняемых в этом методе. Кроме того, мы также не создаем такую ​​большую древовидную структуру! Если мы вспомним, когда мы впервые познакомились с динамическим программированием, мы вспомним, что мы также могли использовать мемоизацию и сохранять результаты наших вызовов функций, когда мы рассчитать их, еще больше оптимизируя наше решение.

Итак, мы пошли по этому пути, чтобы сделать следующий шаг в изречении «Сделайте это, сделайте это правильно, сделайте это быстро».

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

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

Единственный вопрос, на который мы должны сейчас ответить, это, конечно, как время выполнения этого метода сравнивается с нашим уродливым факториалом, O (n!), Из более раннего?

Что ж, как оказалось, подход снизу вверх, который мы здесь изучали, на самом деле является основой так называемого алгоритма Хельда-Карпа, который также часто называется как алгоритм Беллмана-Хелда-Карпа. Этот алгоритм был разработан в 1962 году Майклом Хелдом и Ричардом М. Карпом, а также Ричардом Беллманом, который в то время независимо работал над своим собственным исследованием.

Алгоритм Хельда-Карпа фактически предложил подход динамического программирования снизу вверх в качестве решения для улучшения метода грубой силы для решения задачи коммивояжера. Было установлено, что алгоритм Беллмана, Хелда и Карпа работает в экспоненциальном времени, поскольку он по-прежнему выполняет основную часть работы по перечислению всех потенциальных наборов вызовов функций, которые возможный. Экспоненциальное время выполнения алгоритма Хельда-Карпа все еще не идеально - на самом деле, это далеко не так! Но это не так уродливо, как факторный алгоритм, и все же это улучшение.

И, честно говоря, я уверен, что коммивояжер с радостью примет все, что ему удастся.

Ресурсы

О проблеме коммивояжера писали, исследовали и много учили. Оказывается, есть много разных подходов к решению этой проблемы, и алгоритм Хельда-Карпа - лишь один из них. Если вы хотите глубже изучить эту конкретную тему, вот несколько хороших мест для начала.

  1. Задача коммивояжера, 0612 TV w / NERDfirst
  2. Задача коммивояжера Динамическое программирование Held-Karp, Тушар Рой
  3. Что такое NP-complete в информатике?, StackOverflow
  4. Обозначение Big O и сложность, Пустельга Блэкмор
  5. Алгоритм динамического программирования для TSP, Coursera
  6. Задача коммивояжера: обзор приложений, формулировок и подходов к решению, Раджеш Матай, Сурья Сингх и Мурари Лал Миттал