Поиск дешевого пути по двоичному дереву?

Question

Я изо всех сил, чтобы найти алгоритм для следующей задачи:

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

Может кто-нибудь рекомендовать мне самый простой способ, чтобы закончить это упражнение?

Answer 1

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

Надеюсь, это поможет!

Answer 2

Поскольку дерево просто специализированный граф, алгоритм Дейкстров прекрасно работает здесь:

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

1. Присвоить каждый узел предварительного значение расстояния: установить его на ноль для нашего начального узла и до бесконечности для всех остальных узлов.
2. Установите начальный узел как текущий. Отметьте все остальные узлы невидимыми. Создайте набор всех невидимых узлов, называемых невидимым множеством.
3. Для текущего узла рассмотрите все его невидимые соседи и вычислите их предварительные расстояния. Сравните недавно просчитанное предварительное расстояние до текущего назначенного значения и назначьте меньшее значение. Например, если текущий узел A отмечен расстоянием 6, а край, соединяющий его с соседним B, имеет длину 2, то расстояние до B (через A) будет равно 6 + 2 = 8. Если бы B был ранее отмеченное на расстоянии больше 8, затем измените его на 8. В противном случае сохраните текущее значение.
4. Когда мы закончили рассмотрение всех соседей текущего узла, пометьте текущий узел как посещенный и удалите его из невидимого набора. Посещенный узел больше никогда не будет проверен.
5. Если целевой узел был отмечен посещенным (при планировании маршрута между двумя конкретными узлами) или если наименьшее предварительное расстояние между узлами в невидимом множестве бесконечно (при планировании полного обхода, происходит, когда нет связи между начальный узел и оставшиеся невидимые узлы), затем остановитесь. Алгоритм завершен.
6. В противном случае, выберите Непосещенные узел, помеченный с наименьшим предварительным расстоянием, установить его в качестве нового «текущего узла», и вернуться к шагу 3.

Просто следить, какая ветвь имеет самый низкий стоимость в конце. Верните список с этой веткой.

Answer 3

Я предлагаю сначала пересечь глубину дерева.

Вам понадобятся три переменные:

1) current cost, которым представляет собой сумму значений от корневого узла до текущего узла.

2) cheapest path от корня до любого листа до сих пор (INIT ней пусто)

; 3) cheapest cost которые представляют собой стоимость самого дешевого пути

Если вы достигаете узел, добавьте его стоимость узла к current cost (1).

Если вы достигли листа, добавьте его стоимость узла также к current cost. Затем проверьте, стоит ли его стоимость дешевле, чем cheapest cost (3). Если это (или нет дешевой стоимости существует, потому что ее первый лист вы достигаете), установите cheapest cost = current cost. и установите cheapest path на текущий путь (вы можете сохранить его в самой переменной или просто пройти назад от текущего отпуска до корневого узла) Затем перейдите на один узел вверх и проверьте, есть ли ветка, которую вы еще не посетили. Если есть, пойдите, проверьте это. Если нет, то другой узел и проверить (и так далее ...)

Ярлык: При достижении узла и current cost к нему больше, чем cheapest cost, вы можете пропустить все поддерево этого узла.

Answer 4

Вам необходимо построить priority_queue (C++ STL имеет этот контейнер) пар:

индексный узел

• стоимость

Приоритет является стоимость, по возрастанию.

Алгоритм:

Put в priority_queue пары (корень, cost_of_root). После этого цикл:

1. Извлечение пары (узел, стоимость) от priority_queue
2. Если этот узел является листом - возвращение пара как лучший лист/стоимость.
3. Else - добавьте в priority_queue две пары: (left_son, cost + left_son.cost), (right_son, cost + right_son.cost).

Это все.

Answer 5

Это можно легко сделать рекурсивно. Функция печатает все корневые пути на листах вместе с самой дешевой ветвью. Я использовал Arraylist, чтобы добавить все узлы от корня до листа. Всякий раз, когда достигнут лист узла, я просто проверяю, насколько maxSum пока меньше, чем текущий корневой каталог, и обновляет его.

class Node { 

    public int info; 
    public Node left; 
    public Node right; 

    public Node(int info) { 
     this(info, null, null); 
    } 

    public Node(int info, Node left, Node right) { 
     this.info = info; 
     this.left = left; 
     this.right = right; 
    } 

} 

public class RootToLeaf { 

    private static int maxSum = Integer.MAX_VALUE; 
    private static ArrayList<Integer> finalList = new ArrayList<>(); 

    public static void main(String[] args) { 

     Node root = new Node(8); 
     root.left = new Node(4); 
     root.left.left = new Node(3); 
     root.left.right = new Node(1); 
     root.right = new Node(5); 
     root.right.right = new Node(11); 
     ArrayList<Integer> list = new ArrayList<Integer>(); 
     path(root, list,0); 
     System.out.println("Cheapest list is - " + finalList.toString() + " and minimum sum is " + maxSum); 

    } 

    private static void path(Node root, ArrayList<Integer> list,int s) { 

     if(root==null) { 
      return; 
     } else { 
      list.add(root.info); 
      s = s+root.info; 
     } 

     if ((root.left == null && root.right == null)) { 
      System.out.println(list); 
      if(maxSum>s) { 
       maxSum = s; 
       finalList = new ArrayList<>(list); 
      } 
      return; 
     } 

     path(root.left, new ArrayList<Integer>(list),s); 
     path(root.right, new ArrayList<Integer>(list),s); 

    } 

} 

из положить выглядит следующим образом:

[8, 4, 3] 
[8, 4, 1] 
[8, 5, 11] 
Cheapest list is - [8, 4, 1] and minimum sum is 13