Дерево проходит со взвешенными узлами

Question

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

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

Answer 1

Мы выполним алгоритм наводнения на дереве, начиная с каждого листа, и запустим алгоритм maximum subsequence sum на путях, которые мы обнаруживаем во время заливки. Это дает максимальное максимальное значение для каждой пары листьев; и мы выбираем самый большой из них как наш истинный ответ. Это решение принимает O (n^2) время: существуют O (n) листья, и мы выполняем O (n), чтобы выполнить наводнение для максимальной суммы последовательности подпоследовательности на каждом листе, что дает O (n^2) общая работа для стадии производства кандидата. Затем мы делаем O (n^2), чтобы выбрать максимальный путь из выбранных нами O (n^2) кандидатов.

Я приведу пример реализации в Haskell. Некоторые импорта вы можете в основном игнорируют:

import Data.List 
import Data.Monoid 

Для простоты представим наше дерево как функцию, которая, учитывая узел, говорит вес и то, что соседи доступны. При наименовании типов и терминов я буду использовать w для весов и n для узлов.

type Tree w n = n -> (w, [n]) 

Это будет удобно иметь способ ссылаться на пути и его вес:

type WeightedPath w n = (Sum w, [n]) 

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

data Summary w n = Summary 
    { endingHere  :: WeightedPath w n 
    , endingAnywhere :: WeightedPath w n 
    } 

emptySummary :: Num w => Summary w n 
emptySummary = Summary mempty mempty 

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

flood :: Eq n => (w -> n -> s -> s) -> s -> Tree w n -> n -> [s] 
flood extend summary t = go Nothing summary where 
    go nPrevious summary nCurrent = case maybe id delete nPrevious ns of 
     [] -> [summary'] 
     ns -> ns >>= go (Just nCurrent) summary' 
     where 
     (w, ns) = t nCurrent 
     summary' = extend w nCurrent summary 

Например, мы можем найти все листья, сделав наше «резюме» только последним узлом, который мы видели. Если дерево пусто, мы будем бросать свои руки в отвращении:

findLeaves :: Eq n => Tree w n -> n -> [n] 
findLeaves = flood (\w n s -> n) undefined 

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

extend :: (Num w, Ord w, Ord n) => w -> n -> Summary w n -> Summary w n 
extend w n s = answer where 
    answer = s 
     { endingHere = max (0, []) ((Sum w, [n]) <> endingHere s) 
     , endingAnywhere = max (endingHere answer) (endingAnywhere s) 
     } 

Эта функция слотов в наш алгоритм наводнения заполнения красиво, чтобы найти кандидат на пути, начиная с определенным узла:

findCandidates :: (Num w, Ord w, Ord n) => Tree w n -> n -> [Summary w n] 
findCandidates t n = findLeaves t n >>= flood extend emptySummary t 

функция верхнего уровня просто делает затопленную заливку и выбирает максимальный кандидат. (Ties сломаны произвольно, так как они были в extend.)

maximalPath :: (Num w, Ord w, Ord n) => Tree w n -> n -> WeightedPath w n 
maximalPath t n = maximum . map endingAnywhere $ findCandidates t n 

Давайте посмотрим его запустить.Мы определим очень простое дерево образцов: это звездное дерево с узлом 0 в центре и узлами 1 через 5, каждый из которых подключен к центральному концентратору. Центр имеет вес -1, а листья взвешены 1 через 5, согласно которому они являются.

sampleTree :: Tree Int Int 
sampleTree 0 = (-1, [1..5]) 
sampleTree n = (n, [0]) 

В GHCI, мы можем теперь найти найти максимальный путь, предоставляя дерево и любой узел в дереве:

> maximalPath sampleTree 0 
(Sum {getSum = 8},[5,0,4]) 

... в котором говорится, что наибольшая сумма 8, и может быть достигнуто путем путешествия пути от внешнего узла 5 к ступице узлу 0, а затем наружу к узлу 4.

Answer 2

на каждом узле дерева вычислений:

1) путь с крупной суммой, возникающей сюда m любой потомок этого узла к этому узлу.

2) Путь с наибольшей суммой, который можно найти в поддереве, внедренном в этот узел.

Оба они могут быть вычислены с использованием значений, вычисленных на дочерних узлах этого узла.

В случае (1) ответ является либо путём длины 0, либо пуском на этом узле, либо суммой значения в этом узле и наибольшим значением (1) для любого дочернего элемента.

В случае (2) ответ представляет собой либо сумму двух наибольших (1) значений для этого узла, либо минус значение на этом узле, либо наибольшее (2) значение от любого дочернего элемента.

Значение, которое вы ищете, это значение (2) в корне, и вы можете добавить дополнительный бухгалтерский учет, чтобы определить путь.

Стоимость здесь в основном стоимость рекурсивно обхода дерева, делает большую часть работы, как вы возвращаетесь из глубины первого поиска, поэтому я думаю, что это O (п)