Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняГлава 15 алгоритмов и структур данных, также четвертый в серии динамического программирования.
В предыдущих статьях я говорил о проблеме с рюкзаком, не знаю, чувствуете ли вы себя немного уставшим. Хотя в классической статье девять лекций по рюкзакам, кроме конкурсантов, мы можем понятьМонотонная оптимизацияЭто уже было отлично. Подобно проблеме рюкзака с зависимостями и проблеме смешанного рюкзака, некоторые мечи наклонены, поэтому я не буду их здесь описывать. Если вам интересно, вы можете проверить это на рюкзаке Baidu.Сегодня мы рассмотрим интересный вопрос.Благодаря этому интересному вопросу, давайте узнаем одревовидная структураметод динамического программирования.
Смысл этого вопроса очень прост: учитывая дерево, это не обязательно бинарное дерево.ветки с грузом, что можно рассматривать как длину. Какова длина самой длинной ссылки в дереве?
Например, если мы наугад нарисуем дерево, оно может быть немного некрасивым, не вините его:
Если мы посмотрим на это невооруженным глазом, мы можем найти ответ, попробовав немного.Самый длинный путь должен быть красным на картинке ниже:
Но что, если бы мы использовали алгоритм?
На самом деле есть очень умный способ решить эту проблему, давайте не будем сначала говорить о нем, а посмотрим, как динамическое программирование решает эту проблему.
дерево ДП
На самом деле динамическое программирование может работать не только в массиве, пока выполняется динамическое программирование.Условия и отсутствие последствий переходов состоянийВы можете использовать динамическое программирование, независимо от того, в какой структуре данных оно находится. То же самое и на дереве.После понимания этого осталось только два вопроса.Первый вопрос что такое состояние, а второй вопрос как переходить между состояниями?
В предыдущей задаче о рюкзаке состояние — это текущий объем рюкзака, а перенос — это наше решение взять новый предмет. Но в этот раз мы будем делать динамическое программирование на дереве, условно говоря, состояние и соответствующий переход будут скрыты. Не беда, я организую свои мысли с самого начала и по крупицам объясню процесс вывода и мышления.
Прежде всего, все мы знаем, что переход между состояниями на самом делеПо сути, это процесс вычисления целого по частям.. Мы делаем переходы через относительно простые подсостояния, чтобы получить общий результат. В этом и заключается суть динамического программирования, в какой-то степени он также близок к методу «разделяй и властвуй», между большими проблемами и маленькими проблемами существует логическая связь. Поэтому, когда мы сталкиваемся с большой проблемой и ничего не можем сделать, мы можем извлечь уроки из метода «разделяй и властвуй» и подумать о том, чтобы начать с небольших проблем.
Итак, рассмотрим простейший кейс от мала до велика, от микро к макро:
В этом случае очевидно, что ссылка всего одна, поэтому длина, естественно, равна 5 + 6 = 11, что, очевидно, является наибольшей длиной. В этой ситуации нет проблем, давайте немного усложним ситуацию, добавим в дерево еще один слой:
Эта картина немного сложнее, но путь найти несложно, он должен бытьE-B-F-H. Общая длина пути равна 12:
Но если мы изменим длину пути, например, удлиним пути FG и FH, что будет в результате?
Очевидно, что в этом случае ответ меняется, FGH самый длинный.
Этот пример просто иллюстрирует очень простую проблему, а именноДля дерева самый длинный путь на нем не обязательно проходит через корневой узел. Например, в только что приведенном примере, если путь должен проходить через B, то наибольшая длина может составлять только 4+2+16=22, но если нет необходимости проходить через B, самая длинная длина, которую можно получить 31.
Может показаться бесполезным делать такой вывод, но на самом деле нам очень полезно прояснить свое мышление. Поскольку мы не можем гарантировать, что самый длинный путь будет проходить через корень, мы не можем напрямую передать ответ. так что нам делать?
Для ответа на этот вопрос недостаточно подумать, нужно еще наблюдать за проблемой и глубоко задуматься.
процесс передачи
Давайте посмотрим на следующие две картинки:
Вы нашли какую-нибудь закономерность?
Поскольку наша структура данных имеет древовидную форму, этот самый длинный путь не имеет значения, какие два узла он соединяет.Необходимо гарантировать, что он пройдет через корневой узел поддерева.. Не стоит недооценивать этот скромный вывод, он на самом деле очень важен. С таким выводом мы разрезаем весь путь в корневом узле.
После того, как мы вырезаемЕсть две ссылки на конечные узлы, вопрос, линков от корневого узла к листовому узлу много, зачем эти два?
Просто, потому что две ссылки самые длинные. так этоПосле сложения можно гарантировать самую длинную ссылку. Обе эти ссылки идут от конечного узла к A, поэтому самая длинная ссылка, которую мы получаем, — это самый длинный путь поддерева с A в качестве корневого узла.
Наш предыдущий анализ говорил, что самый длинный путь не может быть передан, ноНаибольшее расстояние до листа можно передать. Возьмем пример:
Наибольшее расстояние от F до листа, очевидно, больше, чем 5 и 6. B немного сложнее, а D и E оба являются листовыми узлами, что легко понять. У него также есть дочерний узел F, который не является конечным узлом для F, но мы подсчитали, что самое длинное расстояние от F до конечного узла равно 6, поэтому самое длинное расстояние от B до конечного узла через F равно 2 + 6 = 8. Это дает нам уравнение перехода состояния, но вместо требуемого ответа мы передаемСамое длинное и следующее самое длинное расстояние от текущего узла до конечного узла.
Потому что только самого длинного расстояния недостаточно, потому что мы должны добавить самое длинное расстояние корневого узла ко второму самому длинному расстоянию, чтобы получить самый длинный путь через корневой узел, потому что мы сказали ранее, что все пути должны проходить через корневой узел поддерево. Это бессмысленно понимать, но это условие действительно очень важно. Поскольку все ссылки проходят как минимум через корневой узел поддерева, тоНайдите самый длинный путь всех поддеревьев через корневой узел, разве не самый длинный ответ?
Ниже мы демонстрируем этот процесс:
используется на картинке вышеРозовая ручка отмечает процесс переноса, для листовых узлов самое длинное расстояние и второе самое длинное расстояние равны 0, а основной процесс передачи происходит на промежуточных узлах.
Процесс перехода также легко понять.Для промежуточного узла i мы обходим все его дочерние узлы j, а затем сохраняем максимальное и второе максимальное значения.Запишем уравнение перехода состояния:
Переход между состояниями требует понимания, а остальное — проблема кодирования. Выполнение переходов между состояниями на деревьях может показаться нелогичным, особенно при рекурсии, но на самом деле это несложно.Давайте напишем код и посмотрим на него.Давайте сначала рассмотрим эту часть построения дерева. Чтобы упростить задачу, мы можемРассматривайте все номера узлов в дереве как int, для каждого узла будет массив, хранящий все ребра, связанные с этим узлом, включая родительский узел.
Поскольку нас интересует только длина ссылок в дереве, а не структура дерева, после того, как дерево построено,Какая бы точка ни была взята в целом, результат корня дерева один и тот же. Таким образом, мы можем просто найти узел в качестве корневого узла всего дерева для рекурсии. Подчеркнем, что это очень важное свойство, поскольку по сути дерево представляет собой неориентированный ациклический полносвязный граф. Таким образом, независимо от того, какой узел является корневым узлом, все поддерево может быть связано.
Мы создаем класс для хранения информации об узле, включая идентификатор и длину самого длинного и второго по длине узла. Давайте взглянем на код, он должен быть намного проще, чем вы думаете.
class Node(object):
def __init__(self, id):
self.id = id
# 以当前节点为根节点的子树到叶子节点的最长链路
self.max1 = 0
# 到叶子节点的次长链路
self.max2 = 0
# 与当前节点相连的边
self.edges = []
# 添加新边
def add_edge(self, v, l):
self.edges.append((v, l))
# 创建数组，存储所有的节点
nodes = [Node(id) for id in range(12)]
edges = [(0, 1, 3), (0, 2, 1), (1, 3, 1), (1, 4, 4), (1, 5, 2), (5, 6, 5), (5, 7, 6), (2, 8, 7), (7, 9, 2), (7, 10, 8)]
# 创建边
for edge in edges:
u, v, l = edge
nodes[u].add_edge(v, l)
nodes[v].add_edge(u, l)
Поскольку мы только пытаемся передать идеи, много объектно-ориентированного кода опущено, но этого должно быть достаточно, чтобы мы поняли идею темы.
Далее рассмотрим код динамического программирования на дереве:
def dfs(u, f, ans):
nodeu = nodes[u]
# 遍历节点u所有的边
for edge in nodes[u].edges:
v, l = edge
# 注意，这其中包括了父节点的边
# 所以我们要判断v是不是父节点的id
if v == f:
continue
# 递归，更新答案
ans = max(ans, dfs(v, u, ans))
nodev = nodes[v]
# 转移最大值和次大值
if nodev.max1 + l > nodeu.max1:
nodeu.max2 = nodeu.max1
nodeu.max1 = nodev.max1 + l
elif nodev.max1 + l > nodeu.max2:
nodeu.max2 = nodev.max1 + l
# 返回当前最优解
return max(ans, nodeu.max1 + nodeu.max2)
Древовидный DP, который выглядит очень сложным, на самом деле состоит всего из дюжины строк кода, не правда ли, он удивительно прост?
Но это все еще общая тема, эти десятки строк кода кажутся простыми, но все же есть некоторые детали, особенно когда речь идет о рекурсивных операциях. Для студентов, не особо знакомых с рекурсией, может быть немного сложно, рекомендуется вручную проверить расчет на бумаге по предыдущей схеме, и я верю, что будет более глубокое понимание.
другой подход
Статья еще не закончена, у нас еще есть маленькая пасхалка. На самом деле, есть еще один способ сделать это, т.очень остроумный, а также представить его всем.
Как мы уже говорили, поскольку дерево записывает состояние подключения узлов, независимо от того, какой узел используется в качестве корневого узла, это не повлияет на длину и структуру пути во всем дереве. В этом случае, если у нас есть воображение, можем ли мы раздавить дерево, как связку веревок или палок, соединенных вместе?
Давайте посмотрим на картинку ниже:
мыпереместить точку C в точку B, не влияет на структуру дерева, ведь это абстрагированная архитектура, мы не обращаем внимания на угол между ветвями дерева. мы можем представить насПункт сбора А, другие точки прогибаются под действием силы тяжести и в конечном итоге выстраиваются в прямую линию.
Например, на картинке выше мы поднимаем точку А, а BCD висит вниз. Нижняя точка в это время – точка D. Затем мы берем точку D, нижняя точка становится точкой C, тогда расстояние между DC — самая длинная ссылка на дереве:
Давайте разберем весь процесс: сначала мы случайным образом выбираем точку как корень дерева, а затем находим самую дальнюю от него точку. Во второй раз мы выбираем эту самую дальнюю точку в качестве корня дерева и снова находим самую дальнюю точку. Расстояние между этими двумя самыми дальними точками и есть ответ.
Этот метод очень интуитивен, но я не могу придумать метод, который можно было бы строго доказать.Небольшой партнер с идеями может оставить мне сообщение в фоновом режиме. Если некоторые друзья не могут этого понять, они могут попытаться соединить их вместе с помощью нескольких веревок, а затем поднять их, чтобы провести эксперимент. Посмотрите, являются ли две точки, полученные при переносе его дважды, двумя самыми дальними точками на дереве.
Наконец, давайте посмотрим на код:
def dfs(u, f, dis, max_dis, nd):
nodeu = nodes[u]
for edge in nodes[u].edges:
v, l = edge
if v == f:
continue
nodev = nodes[v]
# 更新最大距离，以及最大距离的点
if dis + l > max_dis:
max_dis, nd = dis+l, nodev
# 递归
_max, _nd = dfs(v, u, dis+l, max_dis, nd)
# 如果递归得到的距离更大，则更新
if _max > max_dis:
max_dis, nd = _max, _nd
# 返回
return max_dis, nd
# 第一次递归，获取距离最大的节点
_, nd = dfs(0, -1, 0, 0, None)
# 第二次递归，获取最大距离
dis, _ = dfs(nd.id, -1, 0, 0, None)
print(dis)
На данный момент эта интересная тема была объяснена.Интересно, все ли усвоили два метода в тексте? В первый раз, когда вы посмотрите на него, вы можете почувствовать себя немного растерянным. Есть много проблем. Это нормально, ноОсновной принцип не сложный, нарисуйте картинку и сделайте хороший расчет, и вы обязательно получите правильный результат.
Кроме того, впервые сегодня я получил рекламу во второй статье, хе-хе, но я не буду оставлять себе деньги, я возьму весь соответствующий доход от рекламы и прежнее вознаграждение фанатов.Отдайте дань поклонникам, отправив книги. Конкретная форма и сопутствующие книги пока не продуманы, актуальную информацию буду синхронизировать внизу следующей статьи, так что не пропустите.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.