Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняВыпуск 16 тем в алгоритмах и структурах данных, а также пятая часть серии по динамическому программированию.
Содержание сегодняшней статьи — очень распространенная ветвь динамического программирования —Динамическое программирование сжатия состояний, Многие люди боятся сжатия состояния, но это не так уж и сложно, надеюсь, моя сегодняшняя статья поможет вам изучить это классическое приложение.
статус двоичного представления
Объясняя задачу о нескольких рюкзаках, мы говорили о двоичной записи для решения задачи о нескольких рюкзаках. Используя природу двоичного кода, несколько элементов разбиваются на несколько элементов и преобразуются в простой рюкзак с нулевой единицей для решения. Современное сжатие состояния также неотделимо от двоичного, но лично мне кажется, что современные двоичные приложения легче понять.
Многие приложения двоичного кода неотделимы отсобиратьЭта концепция, мы все знаем, что в компьютерах все данные хранятся в двоичной форме. Как правило, целое число занимает 4 байта, что является 32-битным битом.Мы можем представить до 2,1 миллиарда различных чисел с помощью комбинации 0 и 1 в этих 32-битных битах. Если рассматривать эти 32 бита как набор, тоКаждое число должно соответствовать состоянию множества, и состояние каждого числа отличается.
Например, на картинке выше мы перечислили 5 двоичных битов, два из них мы установили в 1, а остальные в 0. Путем вычислений мы можем получить число 6, тогда 6 также представляет состояние (00110).Между числами и состояниями существует однозначное соответствие, потому что каждое целое число, преобразованное в двоичное, уникально.
Другими словами, целое число может быть преобразовано в двоичное число, которое может представлять состояние множества, и эти два числа соответствуют один к одному. Это очень важно и является основой для всех последующих выводов.
переход состояния
Двоичное представление целого числа может представлять состояние двоичного множества, и, поскольку это состояние, его можно передавать. Исходя из этого, можно сделать еще один очень важный вывод -Мы можем представить переходы между состояниями сложением и вычитанием целых чисел.
Мы также используем пример только что в качестве примера.На приведенном выше рисунке мы перечислили двоичные биты 5. Предположим, мы используем эти 5 двоичных битов для представления 5 маленьких шариков, и номера этих маленьких шариков от 0 до 4 соответственно. Таким образом, только что 6 можно рассматривать как представление состояния взятия двух мячей № 1 и № 2.
Если в это время мы снова возьмем шар № 3, то состояние набора изменится, мы используем картинку для представления:
Ручка веера на картинке выше представляет собой решение.Например, мы взяли шарик № 3, что является решением.Под влиянием этого решения состояние множества изменилось. Число, представленное набором после переноса, равно 14, что представляет собой изменение, внесенное предыдущим набором 6 плюс перенос, то есть
принадлежит.
Это просто представляет решение взять 3 мяча, поэтому мы связываем весь процесс воедино.
Подводя итог, мы используем двоичные 0 и 1 для представления состояния двоичного набора. Состояние существования или отсутствия элемента можно просто рассмотреть. Поскольку двоичные 0 и 1 могут быть преобразованы в целое число, то есть мы используем целые числа для представления состояния набора. Таким образом, мы можемИспользуйте целочисленные вычисления сложения и вычитания для представления изменений в состоянии набора.
В этом суть сжатия состояния, так называемое сжатие, на самом деле означает сжатие набора в целое число, потому что целые числа могут использоваться как индексы массивов, что облегчит наше кодирование.
задача коммивояжера
Поняв значение сжатия состояния, давайте рассмотрим классический пример, известную задачу коммивояжера.
Интересным фоном проблемы коммивояжера является то, что есть бизнесмен, который хочетпутешествовать по всемуи торговля. Есть несколькоодносторонний каналПодключившись, бизнесмен начинает с одного места и хочет использовать кратчайшее расстояние, чтобы объехать все регионы Какое кратчайшее расстояние необходимо для кругосветки? В этой задаче мы предполагаем, что продавец начинает с позиции 0 и в конце возвращается на позицию 0.
Давайте взглянем на следующую картинку, чтобы почувствовать это интуитивно:
Предположим, наш продавец начинает с позиции 0 и хочетВернуться к 0 снова после недели кругосветки, то какое кратчайшее расстояние ему нужно преодолеть?
Эта картина относительно проста, если вВ крайнем случае есть линия между всеми точкамиПри , для каждой точки он может выбрать всего n-1 следующих позиций. Тогда всего можно выбрать n! видов маршрутов, это очень большое значение, которое для нас явно неприемлемо. Вот почему мы говорим, что задача коммивояжера является NP-сложной задачей.
НП проблема
Теперь, когда мы поговорили о проблеме NP, давайте кратко поговорим об определении проблемы NP.
Многие новички в алгоритмах очень путаются в этих понятиях, и действительно, эти понятия звучат похоже, и в них легко запутаться. Начнем с самой простой, сначала проблемы P.
Проблему P можно рассматривать как решенную проблему, определение которой состоит в том, чтобы сделатьполиномиальная временная сложностьрешать. так называемый многочлен, т.
, где k — константа. Есть много функций, обратных полиномам, таких как экспоненциальные функции, факториалы и так далее.
Проблема NP не является противоположностью проблемы P. N здесь нельзя понимать как Нет, точно так же, как noSQL не является значением non-SQL. Задача NP означает, что можноЗадача проверки решения внутри полинома.
Например, по отсортированной последовательности, давайте судить, упорядочена она или нет, это очень просто, нам нужно только пройти по ней. Другим примером является факторизация больших целых чисел. Нам будет сложно сделать факторизацию, но гораздо проще судить о правильности решения факторизации. Мы можем напрямую перемножить их и сравнить с исходной формулой.
очевидноВсе P-задачи — это NP-задачи., так как мы можем найти решение в многочлене, неизбежно, что мы также можем проверить, является ли решение правильным в многочлене. Но верно ли обратное, можно ли проверить решение за полиномиальное время, а также решить его за полиномиальное время по какому-то алгоритму?Это потому, что мы еще не придумали алгоритм, или есть решение, которого не существует изначально?
Вышеупомянутый вопрос является знаменитым вопросом о том, выполняется ли NP=P. Этот вопрос до сих пор остается загадкой. Некоторые люди верят, что это правда, а некоторые не верят. Это также считается одной из самых больших проблем 21-го века. век.
Чтобы доказать эту проблему, ученые придумали еще один способ, который состоит в том, чтобы сделать спецификацию проблемы. Например, такие как решение уравнений, мы очень легко решаем линейные уравнения с одной переменной, тогда как решение линейных уравнений с двумя переменными является более сложным. Если мы найдем способ понять линейное уравнение с двумя переменными, его также нужно использовать для решения линейного уравнения с одной переменной, потому что нам нужно только сделать другое неизвестное равным 0, чтобы оно было линейным уравнением с одной переменной.
Точно так же мы можем преобразовать задачу NP, усложнив ее.Рост до предела становится конечной проблемой. Поскольку эта окончательная проблема получается путем преобразования всех проблем NP, до тех пор, пока мы придумываем алгоритм для решения конечной проблемы, все проблемы NP могут быть решены легко. Например, если мы придумаем алгоритм для понимания N-элементных уравнений, то этот тип задачи решения уравнений будет решен. Возникающая после этого преобразования задача называетсяNP-полная проблема, также известная как проблема NPC..
Давайте рассмотрим классическую задачу NPC, задачу логической схемы.
На рисунке ниже показана логическая схема. Предположим, мы знаем, что ее выход имеет значение «Истина», а также мы знаем структуру схемы. Можем ли мы быть уверены, что сможем найти комбинацию входов, которая сделает окончательный вывод «Истинным»?
Очевидно, что это задача NP, потому что мы можем напрямую подставить решение в схему для вычисления и можем проверить правильность решения, но получить ответ сложно. После строгого доказательства все задачи NP можно преобразовать, чтобы получить его, то есть если мы найдем решение, которое может решить эту задачу в полиноме, то мы решили все задачи NP.
Наконец, есть NP-сложная задача, NP-сложная задача означает, что все NP-задачи можно преобразовать, чтобы получить ее, ноЭто не проблема NP как таковая, что означает, что мы не можем сказать, является ли его решение правильным за полиномиальное время.
Например, только что упомянутая задача коммивояжера является NP-сложной задачей, потому что даже если нам дано решение, мы можемНевозможно быстро определить правильность данного решения., вы должны пройти все случаи, прежде чем сможете это сделать. Сложность нашей проверки выходит за рамки многочленов, поэтому это не NP-задача, она сложнее, чем NP-задача, поэтому это NP-сложная задача.
решение для сжатия состояния
Сказав о задаче NP, вернемся к самому алгоритму.
Поскольку для решения этой задачи мы используем идею динамического программирования, мыНельзя отделить от государства и принятия решений. Как упоминалось выше, мы можем использовать двоичный код для представления состояния множества с целым числом.Мы можем легко рассматривать это состояние как состояние в динамическом программировании, но на самом деле это неправильно.
Ограничений на перенос между простыми наборами нет, например, в предыдущем примере мы взяли шары 1 и 2, а затем сколько угодно оставшихся шаров, но задача коммивояжера другая. 0 и 1, мы в настоящее время находимся в позиции 1, мы не можем обновить это состояние связью между 2 и 5, потому что в настоящее время мы можем начать только с позиции 1. То есть мыРешения, которые могут быть приняты, ограничены.
Таким образом, мы не можем просто принять состояние множества за состояние.Чтобы обеспечить правильный порядок перемещения между локациями, нам также необходимо добавить одно измерение, которым является текущая локация. такРеальное состояние — это состояние локации, которую мы прошли ранее, плюс текущая локация, комбинация двух.
Как только статус определен, принятие решения становится очень простым.Любое место, которое можно посетить в текущем местоположении, которое не посещалось ранее, может представлять собой принятие решения.
Ранее мы говорили, что в задаче динамического программированияСложность равна количеству состояний, умноженному на количество решений., количество состояний
, количество решений равно n, поэтому общая сложность равна
. Хотя это число все еще кажется преувеличенно большим, оно все же намного меньше, чем n!.
Давайте возьмем пример, чтобы увидеть, если n = 10, n! = 3628800,
,Разница между ними более чем в тридцать раз. По мере увеличения n разрыв между ними будет увеличиваться.
Наконец, давайте реализуем следующий алгоритм:
import math
if __name__ == "__main__":
inf = 1 << 31
# 邻接矩阵存储边权重
d = [[inf for _ in range(10)] for _ in range(10)]
# 测试数据
edges = [[0, 1, 3], [1, 2, 5], [2, 3, 5], [3, 4, 3], [4, 0, 7], [4, 1, 6], [0, 3, 4], [2, 0, 4]]
for u, v, l in edges:
d[u][v] = l
# 初始化成近似无穷大的值
dp = [[inf for _ in range(5)] for _ in range((1 << 5))]
dp[0][0] = 0
# 遍历状态
for s in range(1, (1 << 5)):
for u in range(5):
# 遍历决策
for v in range(5):
# 必须要求这个点没有去过
if (s >> v) & 1 == 0:
continue
dp[s][v] = min(dp[s][v], dp[s - (1 << v)][u] + d[u][v])
print(dp[(1 << 5) - 1][0])
В стиле кодирования соревнования acm мы обычно используем u для представления начала ребра и v для представления конца ребра. Таким образом, первый из трех циклов выше должен пройти все состояния, а последние два цикла перечисляют начальную точку и конечную точку, то есть все ребра. Мы пересекаем ребро последнего хода перед текущим состоянием, то есть текущая точка — v, предыдущая точка — u, поэтому предыдущее состояние — s —
, стоимость решения равна d[u][v], что является расстоянием от u до v.
Если вы читали предыдущие статьи, то обнаружите, что это обратное динамическое программирование. Мы перечисляем текущее состояние и все источники текущего состояния, чтобы найти оптимальное решение для текущего состояния. Если вы не знакомы с этой концепцией, вы можете предварительно ознакомиться с другими статьями по динамическому программированию.
В этом коде две детали, перваямы не выносили юридическое решение, возможно, что наше u недопустимо, например, в нашем множестве всего две точки 2 и 3, но мы пронумеровали стратегии с 4 по 5. Это нормально, потому что мы начали со всех состояний, установленных на бесконечность,Только правовые состояния не бесконечны, так как мы хотим, чтобы конечный результат был как можно меньше, недопустимое состояние не будет использоваться для обновления.
Вторая деталь немного более тонкая, то есть мы устанавливаем dp[0][0] = 0 во время инициализации. Это означает, что мы начинаем с пустого набора, а не с 0. Поскольку число, соответствующее состоянию, которое было пройдено в точке 0, равно 1, конечно, мы также можем установить его равным 0, которое было посещено, начиная с точки 0. В этом случае, поскольку к каждой точке нельзя обращаться повторно, мы не может в конце концов вернуться в точку 0. Да, чтобы получить правильный результат, нам также нужно добавить стоимость возврата в 0.
Анализ обнаружит, что первая точка является основой второй точки.Если мы судим, является ли точка u также допустимой при перечислении стратегии, то этот алгоритм не может быть выполнен, потому чтоДля пустого набора все точки не посещены, также являются незаконными, мы не можем найти посещенный u в качестве отправной точки для принятия решения.
Неважно, если вы не понимаете описанный выше метод, я приложу чуть более простой метод:
# 我们从0点已经遍历开始
dp[1][0] = 0
for s in range(2, (1 << 5)):
for u in range(5):
# 严格限制u必须已经遍历过
if (s >> u) & 1 == 0:
continue
for v in range(5):
if (s >> v) & 1 == 0:
continue
dp[s][v] = min(dp[s][v], dp[s - (1 << v)][u] + d[u][v])
ans = inf
# 最后加上回到0点的距离
for i in range(5):
ans = min(ans, dp[(1 << 5) - 1][i] + d[i][0])
print(ans)
В этом подходе мыиз состояния 1, то есть мы рассматриваем позицию 0 как текущую точку, и она была пройдена, поэтому она помечается как 1. Проблема в том, что у нас нет способа вернуться к 0, потому что точку можно пройти только один раз, поэтому в конце нам нужно найти оптимальный путь обратно к 0.
(1
Суммировать
Я не знаю, сколько людей успешно это видели.Динамическое программирование действительно не простое.Это нормально,что сложно и трудно понять,если вы изучаете его в первый раз. Но это относится к тому типу, который мне показался особенно трудным до того, как я начал, ноОчень простой вопрос, когда разберешься. И вы также можете видеть по количеству кода, что я использовал несколько тысяч слов для описания алгоритма, но было написано всего десяток строк.
Алгоритмы динамического программирования всегда были такими, код не длинный, но суть в каждой строчке. С этой точки зрения, это действительно хорошее соотношение цены и качества.
Хорошо, это все для сегодняшней статьи. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.