Рубрики

Минимальный номер итераций для передачи информации всем узлам дерева

Деревья

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

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

Минимальное число итераций для дерева ниже — 6. Корень A сначала передает информацию в B. В следующей итерации A передает информацию в E, а B передает информацию в H и так далее.

Мы настоятельно рекомендуем свернуть браузер и попробовать это в первую очередь.

Это можно сделать с помощью пост-заказа. Идея состоит в том, чтобы учесть рост, и дети рассчитывают на каждый узел.
Если дочерний узел i принимает ci итераций для передачи информации ниже своего поддерева, то его родительский элемент будет принимать (ci + 1) итераций для передачи информации в поддерево с корнем в этом дочернем i.
Если у родителя больше детей, он будет передавать им информацию в последующих итерациях. Допустим, дочерние элементы родительского элемента принимают итерации c1, c2, c3, c4,…, cn для передачи информации в собственное поддерево. Теперь родительский элемент должен передавать информацию этим n дочерним элементам один за другим в n итерациях. Если родитель выбирает дочерний элемент i в i-й итерации, то родительский процесс будет выполнять (i + ci) итераций для передачи информации дочернему элементу i и всему его поддереву.
На любой итерации, когда родитель передает информацию дочернему элементу i + 1, потомки (от 1 до i), которые получили информацию от родителя уже на предыдущих итерациях, передают информацию дальше вниз на последующих итерациях, если какой-либо дочерний элемент (от 1 до i) имеет собственный ребенок дальше вниз.
Чтобы передать информацию всему дереву за минимальные итерации, необходимо убедиться, что полоса пропускания используется максимально эффективно (т. Е. Максимально проходимый ни один из узлов не должен передавать информацию дальше вниз в любой итерации)
Наилучшим из возможных сценариев было бы то, что в n-й итерации n различных узлов передают информацию своему дочернему элементу.
Узлы с высотой = 0: (тривиальный случай) Конечный узел не имеет дочерних элементов (передача информации не требуется), поэтому ни одна из итераций не будет нулевой.
Узлы с высотой = 1: здесь узел должен передавать информацию всем дочерним элементам один за другим (все дочерние узлы являются конечными, поэтому больше никакой информации не будет проходить дальше). Поскольку все дочерние элементы являются конечными, узел может передавать информацию любому дочернему элементу в любом порядке (выберите любого дочернего элемента, который еще не получил информацию). Одна итерация, необходимая для каждого дочернего элемента, и поэтому ни одна из итераций не будет дочерней. Таким образом, узел с высотой 1 с n дочерними элементами будет принимать n итераций.
Возьмите счетчик, инициализированный нулем, обведите все дочерние элементы и продолжайте увеличивать счетчик.
Узлы с высотой> 1. Предположим, что существует n дочерних элементов (от 1 до n), и минимальное число итераций для всех n дочерних элементов равно c1, c2,…., Cn.
Чтобы обеспечить максимальное количество узлов, участвующих в передаче информации в любой итерации, родитель должен 1-й передать информацию тому дочернему элементу, который примет максимальную итерацию, чтобы передать информацию далее в последующих итерациях. т. е. в любой итерации родитель должен выбрать потомка, который в дальнейшем получит максимальную итерацию. Это можно считать жадным подходом, когда родитель выбирает того ребенка 1-го, которому нужно максимальное количество итераций, чтобы все последующие итерации могли эффективно использоваться.
Если родительский узел работает любым другим способом, то, в конце концов, могут быть некоторые узлы, которые выполняются довольно рано, бездействуют, и поэтому пропускная способность не используется эффективно в дальнейших итерациях.
Если есть два дочерних элемента i и j с минимальными итерациями ci и cj, где ci> cj, то если родительский элемент выбирает дочерний элемент j 1st, то ни одна из итераций, необходимых родительскому элементу для передачи информации обоим дочерним элементам и их поддереву, не будет равна: max (1 + cj) , 2 + ci) = 2 + ci
Если родитель выбирает child i 1st, то ни одна из итераций, необходимых родителю для передачи информации обоим дочерним элементам и их поддереву, будет: max (1 + ci, 2 + cj) = 1 + ci (поэтому выбор ci дает лучший результат, чем выбор cj)

Это говорит о том, что родитель должен всегда выбирать child i с максимальным значением ci в любой итерации.
ТАК вот жадный подход:
сортировать все значения ci в порядке убывания,
скажем, после сортировки значения c1> c2> c3>…. > сп
возьмите счетчик c, установите c = 1 + c1 (для ребенка с максимальным числом итераций)
для всех детей от 2 до n, c = c + 1 + ci
тогда общее количество итераций, необходимых родителю, равно max (n, c)

Пусть minItr (A) будет минимальной итерацией, необходимой для передачи информации из узла A во все это поддерево. Пусть child (A) будет подсчетом всех дочерних элементов для узла A. Таким образом, рекурсивное отношение будет:

1. Get minItr(B) of all children (B) of a node (A)
2. Sort all minItr(B) in descending order
3. Get minItr of A based on all minItr(B)
    minItr(A) = child(A)
    For children B from i = 0 to child(A)
             minItr(A) = max ( minItr(A), minItr(B) + i + 1)

Base cases would be:
If node is leaf, minItr = 0
If node's height is 1, minItr = children count

Ниже приводится реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска минимального количества итераций для передачи
// информация от корня ко всем узлам в n-арном дереве
#include<iostream>
#include<list>
#include<cmath>
#include <stdlib.h>

using namespace std;

   
// Класс для представления n-арного дерева (Обратите внимание, что реализация
// аналогичен графу для простоты реализации

class NAryTree

{

    int N;    // Количество узлов в дереве

   

    // Указатель на массив, содержащий список детей

    list<int> *adj;

   

    // Функция, используемая getMinIter (), она в основном выполняет порядок

    void getMinIterUtil(int v, int minItr[]);

public:

    NAryTree(int N);   // Конструктор

   

    // функция для добавления дочернего элемента w в v

    void addChild(int v, int w);

   

    // Основная функция для поиска минимальных итераций

    int getMinIter();

  

    static int compare(const void * a, const void * b);

};

   

NAryTree::NAryTree(int N)

{

    this->N = N;

    adj = new list<int>[N];

}

   
// Чтобы добавить потомка w в v

void NAryTree::addChild(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

}

   
/ * Рекурсивная функция, используемая getMinIter (). Эта функция
// в основном выполняет обход по порядку и получает минимальную итерацию для всех детей
// узла u, сортируем их по убыванию, а затем получаем минимальную итерацию
// узла u

  
1. Получите minItr (B) всех дочерних элементов (B) узла (A)
2. Сортировать все minItr (B) в порядке убывания
3. Получить minItr из A на основе всех minItr (B)

    minItr (A) = child (A) - >> child (A) - число детей узла A

    Для детей B от i = 0 до ребенка (A)

             minItr (A) = max (minItr (A), minItr (B) + i + 1)

  
Базовые случаи были бы:
Если узел является листом, minItr = 0
Если высота узла равна 1, minItr = количество детей
* /

  

void NAryTree::getMinIterUtil(int u, int minItr[])

{

    minItr[u] = adj[u].size();

    int *minItrTemp = new int[minItr[u]];

    int k = 0, tmp = 0;

    // Повторение для всех вершин, смежных с этой вершиной

    list<int>::iterator i;

    for (i = adj[u].begin(); i!= adj[u].end(); ++i)

    {

        getMinIterUtil(*i, minItr);

        minItrTemp[k++] = minItr[*i];

    }

    qsort(minItrTemp, minItr[u], sizeof (int), compare);

    for (k = 0; k < adj[u].size(); k++)

    {

        tmp = minItrTemp[k] + k + 1;

        minItr[u] = max(minItr[u], tmp);

    }

    delete[] minItrTemp;

}

   
// Функция для обхода PostOrder. Оно использует
// рекурсивный getMinIterUtil ()

int NAryTree::getMinIter()

{

    // Установить минимальную итерацию всех вершин как ноль

    int *minItr = new int[N];

    int res = -1;

    for (int i = 0; i < N; i++)

        minItr[i] = 0;

   

    // Начать обход почтового заказа из корня

    getMinIterUtil(0, minItr);

    res = minItr[0];

    delete[] minItr;

    return res;

}

  

int NAryTree::compare(const void * a, const void * b)

{

        return ( *(int*)b - *(int*)a );

}

   
// Функция драйвера для проверки вышеуказанных функций

int main()

{

    // TestCase 1

    NAryTree tree1(17);

    tree1.addChild(0, 1);

    tree1.addChild(0, 2);

    tree1.addChild(0, 3);

    tree1.addChild(0, 4);

    tree1.addChild(0, 5);

    tree1.addChild(0, 6);

   

    tree1.addChild(1, 7);

    tree1.addChild(1, 8);

    tree1.addChild(1, 9);

   

    tree1.addChild(4, 10);

    tree1.addChild(4, 11);

   

    tree1.addChild(6, 12);

   

    tree1.addChild(7, 13);

    tree1.addChild(7, 14);

    tree1.addChild(10, 15);

    tree1.addChild(11, 16);

   

    cout << "TestCase 1 - Minimum Iteration: "

         << tree1.getMinIter() << endl;

   

    // TestCase 2

    NAryTree tree2(3);

    tree2.addChild(0, 1);

    tree2.addChild(0, 2);

    cout << "TestCase 2 - Minimum Iteration: "

         << tree2.getMinIter() << endl;

   

    // TestCase 3

    NAryTree tree3(1);

    cout << "TestCase 3 - Minimum Iteration: "

         << tree3.getMinIter() << endl;

   

    // TestCase 4

    NAryTree tree4(6);

    tree4.addChild(0, 1);

    tree4.addChild(1, 2);

    tree4.addChild(2, 3);

    tree4.addChild(3, 4);

    tree4.addChild(4, 5);

    cout << "TestCase 4 - Minimum Iteration: "

         << tree4.getMinIter() << endl;

   

    // TestCase 5

    NAryTree tree5(6);

    tree5.addChild(0, 1);

    tree5.addChild(0, 2);

    tree5.addChild(2, 3);

    tree5.addChild(2, 4);

    tree5.addChild(2, 5);

    cout << "TestCase 5 - Minimum Iteration: "

         << tree5.getMinIter() << endl;

   

    // TestCase 6

    NAryTree tree6(6);

    tree6.addChild(0, 1);

    tree6.addChild(0, 2);

    tree6.addChild(2, 3);

    tree6.addChild(2, 4);

    tree6.addChild(3, 5);

    cout << "TestCase 6 - Minimum Iteration: "

         << tree6.getMinIter() << endl;

   

    // TestCase 7

    NAryTree tree7(14);

    tree7.addChild(0, 1);

    tree7.addChild(0, 2);

    tree7.addChild(0, 3);

    tree7.addChild(1, 4);

    tree7.addChild(2, 5);

    tree7.addChild(2, 6);

    tree7.addChild(4, 7);

    tree7.addChild(5, 8);

    tree7.addChild(5, 9);

    tree7.addChild(7, 10);

    tree7.addChild(8, 11);

    tree7.addChild(8, 12);

    tree7.addChild(10, 13);

    cout << "TestCase 7 - Minimum Iteration: "

         << tree7.getMinIter() << endl;

   

    // TestCase 8

    NAryTree tree8(14);

    tree8.addChild(0, 1);

    tree8.addChild(0, 2);

    tree8.addChild(0, 3);

    tree8.addChild(0, 4);

    tree8.addChild(0, 5);

    tree8.addChild(1, 6);

    tree8.addChild(2, 7);

    tree8.addChild(3, 8);

    tree8.addChild(4, 9);

    tree8.addChild(6, 10);

    tree8.addChild(7, 11);

    tree8.addChild(8, 12);

    tree8.addChild(9, 13);

    cout << "TestCase 8 - Minimum Iteration: "

         << tree8.getMinIter() << endl;

  

    // TestCase 9

    NAryTree tree9(25);

    tree9.addChild(0, 1);

    tree9.addChild(0, 2);

    tree9.addChild(0, 3);

    tree9.addChild(0, 4);

    tree9.addChild(0, 5);

    tree9.addChild(0, 6);

  

    tree9.addChild(1, 7);

    tree9.addChild(2, 8);

    tree9.addChild(3, 9);

    tree9.addChild(4, 10);

    tree9.addChild(5, 11);

    tree9.addChild(6, 12);

  

    tree9.addChild(7, 13);

    tree9.addChild(8, 14);

    tree9.addChild(9, 15);

    tree9.addChild(10, 16);

    tree9.addChild(11, 17);

    tree9.addChild(12, 18);

      

    tree9.addChild(13, 19);

    tree9.addChild(14, 20);

    tree9.addChild(15, 21);

    tree9.addChild(16, 22);

    tree9.addChild(17, 23);

    tree9.addChild(19, 24);

  

    cout << "TestCase 9 - Minimum Iteration: "

         << tree9.getMinIter() << endl;

   

    return 0;

}

Джава

// Java программа для поиска минимального количества
// итерации для передачи информации из
// корень ко всем узлам в n-арном дереве

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.Iterator;

import java.util.List;

  

class GFG 

{

  

    // Количество узлов

    private static int N;

      

    // список смежности, содержащий

    // список детей

    private static List<List<Integer>> adj;

  

    GFG(int N) 

    {

        this.N = N;

        adj = new ArrayList<>(N);

  

        for (int i = 0; i < N; i++)

            adj.add(new ArrayList<>());

    }

  

    // функция для добавления дочернего элемента w в v

    void addChild(int v, int w)

    {

        adj.get(v).add(w);

    }

  

    // Основная функция для поиска

    // минимальные итерации

    private int getMinIteration() 

    {

        // Базовый случай: if height = 0 или 1;

        if (N == 0 || N == 1)

            return 0;

        int[] mintItr = new int[N];

          

        // Начать обход почтового заказа из корня

        getMinIterUtil(0, mintItr);

        return mintItr[0];

    }

  

    / * Рекурсивная функция, используемая getMinIter ().

    Эта функция в основном выполняет обход заказа

    и получить минимальную итерацию всех детей

    родительского узла, сортируйте их в порядке убывания

    а затем получить минимальную итерацию родительского узла

  

    1. Получите minItr (B) всех дочерних элементов (B) узла (A)

    2. Сортировать все minItr (B) в порядке убывания

    3. Получить minItr из A на основе всех minItr (B)

        minItr (A) = ребенок (A) - >> ребенок (A)

        это число детей узла A

        Для детей B от i = 0 до ребенка (A)

                minItr (A) = max (minItr (A),

                                 minItr (B) + i + 1)

  

    Базовые случаи были бы:

    Если узел является листом, minItr = 0

    Если высота узла равна 1, minItr = количество детей

    * /

    private void getMinIterUtil(int u, int[] minItr) 

    {

        // Базовый случай: конечный узел

        if (adj.get(u).size() == 0)

            return;

        minItr[u] = adj.get(u).size();

  

        Integer[] minItrTemp = new Integer[minItr[u]];

  

        int k = 0;

  

        Iterator itr = adj.get(u).iterator();

  

        while (itr.hasNext()) 

        {

            int currentChild = (int) itr.next();

            getMinIterUtil(currentChild, minItr);

            minItrTemp[k++] = minItr[currentChild];

        }

  

        Arrays.sort(minItrTemp, Collections.reverseOrder());

  

        for (k = 0; k < adj.get(u).size(); k++)

        {

            int temp = minItrTemp[k] + k + 1;

            minItr[u] = Math.max(minItr[u], temp);

        }

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        // TestCase1

        GFG testCase1 = new GFG(17);

        testCase1.addChild(0, 1);

        testCase1.addChild(0, 2);

        testCase1.addChild(0, 3);

        testCase1.addChild(0, 4);

        testCase1.addChild(0, 5);

        testCase1.addChild(0, 6);

        testCase1.addChild(1, 7);

        testCase1.addChild(1, 8);

        testCase1.addChild(1, 9);

        testCase1.addChild(4, 10);

        testCase1.addChild(4, 11);

        testCase1.addChild(6, 12);

        testCase1.addChild(7, 13);

        testCase1.addChild(7, 14);

        testCase1.addChild(10, 15);

        testCase1.addChild(11, 16);

  

        System.out.println("TestCase 1 - Minimum Iteration: " + 

                                  testCase1.getMinIteration());

  

        // TestCase2

        GFG testCase2 = new GFG(3);

  

        testCase2.addChild(0, 1);

        testCase2.addChild(0, 2);

  

        System.out.println("TestCase 2 - Minimum Iteration: " + 

                                  testCase2.getMinIteration());

  

        // TestCase3

        GFG testCase3 = new GFG(1);

        System.out.println("TestCase 3 - Minimum Iteration: " + 

                                  testCase3.getMinIteration());

  

        // TestCase4

        GFG testCase4 = new GFG(6);

        testCase4.addChild(0, 1);

        testCase4.addChild(1, 2);

        testCase4.addChild(2, 3);

        testCase4.addChild(3, 4);

        testCase4.addChild(4, 5);

  

        System.out.println("TestCase 4 - Minimum Iteration: " +

                                  testCase4.getMinIteration());

  

        // TestCase 5

        GFG testCase5 = new GFG(6);

        testCase5.addChild(0, 1);

        testCase5.addChild(0, 2);

        testCase5.addChild(2, 3);

        testCase5.addChild(2, 4);

        testCase5.addChild(2, 5);

  

        System.out.println("TestCase 5 - Minimum Iteration: " + 

                                  testCase5.getMinIteration());

  

        // TestCase 6

        GFG testCase6 = new GFG(6);

        testCase6.addChild(0, 1);

        testCase6.addChild(0, 2);

        testCase6.addChild(2, 3);

        testCase6.addChild(2, 4);

        testCase6.addChild(3, 5);

  

        System.out.println("TestCase 6 - Minimum Iteration: " + 

                                  testCase6.getMinIteration());

  

        // TestCase 7

        GFG testCase7 = new GFG(14);

        testCase7.addChild(0, 1);

        testCase7.addChild(0, 2);

        testCase7.addChild(0, 3);

        testCase7.addChild(1, 4);

        testCase7.addChild(2, 5);

        testCase7.addChild(2, 6);

        testCase7.addChild(4, 7);

        testCase7.addChild(5, 8);

        testCase7.addChild(5, 9);

        testCase7.addChild(7, 10);

        testCase7.addChild(8, 11);

        testCase7.addChild(8, 12);

        testCase7.addChild(10, 13);

  

        System.out.println("TestCase 7 - Minimum Iteration: " +     

                                  testCase7.getMinIteration());

  

        // TestCase 8

        GFG testCase8 = new GFG(14);

        testCase8.addChild(0, 1);

        testCase8.addChild(0, 2);

        testCase8.addChild(0, 3);

        testCase8.addChild(0, 4);

        testCase8.addChild(0, 5);

        testCase8.addChild(1, 6);

        testCase8.addChild(2, 7);

        testCase8.addChild(3, 8);

        testCase8.addChild(4, 9);

        testCase8.addChild(6, 10);

        testCase8.addChild(7, 11);

        testCase8.addChild(8, 12);

        testCase8.addChild(9, 13);

  

        System.out.println("TestCase 8 - Minimum Iteration: " + 

                                  testCase8.getMinIteration());

  

        // TestCase 9

        GFG testCase9 = new GFG(25);

        testCase9.addChild(0, 1);

        testCase9.addChild(0, 2);

        testCase9.addChild(0, 3);

        testCase9.addChild(0, 4);

        testCase9.addChild(0, 5);

        testCase9.addChild(0, 6);

        testCase9.addChild(1, 7);

        testCase9.addChild(2, 8);

        testCase9.addChild(3, 9);

        testCase9.addChild(4, 10);

        testCase9.addChild(5, 11);

        testCase9.addChild(6, 12);

        testCase9.addChild(7, 13);

        testCase9.addChild(8, 14);

        testCase9.addChild(9, 15);

        testCase9.addChild(10, 16);

        testCase9.addChild(11, 17);

        testCase9.addChild(12, 18);

        testCase9.addChild(13, 19);

        testCase9.addChild(14, 20);

        testCase9.addChild(15, 21);

        testCase9.addChild(16, 22);

        testCase9.addChild(17, 23);

        testCase9.addChild(19, 24);

  

        System.out.println("TestCase 9 - Minimum Iteration: " +

                                  testCase9.getMinIteration());

    }

}

  
// Этот код добавлен
// МиталиСривастава

Выход:

TestCase 1 - Minimum Iteration: 6
TestCase 2 - Minimum Iteration: 2
TestCase 3 - Minimum Iteration: 0
TestCase 4 - Minimum Iteration: 5
TestCase 5 - Minimum Iteration: 4
TestCase 6 - Minimum Iteration: 3
TestCase 7 - Minimum Iteration: 6
TestCase 8 - Minimum Iteration: 6
TestCase 9 - Minimum Iteration: 8

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

Рекомендуемые посты:

Минимальный номер итераций для передачи информации всем узлам дерева

0.00 (0%) 0 votes