Рубрики

Самая большая проблема независимых множеств | DP-26

Учитывая бинарное дерево, найти размер L argest I ndependent S и др (LIS) в нем. Подмножество всех узлов дерева является независимым, если между любыми двумя узлами подмножества нет ребра.
Например, рассмотрим следующее двоичное дерево. Самый большой независимый набор (LIS) равен {10, 40, 60, 70, 80}, а размер LIS равен 5.

Решение динамического программирования решает данную проблему, используя решения подзадач в восходящем порядке. Можно ли решить данную проблему, используя решения подзадач? Если да, то каковы подзадачи? Можем ли мы найти наибольший независимый размер набора (LISS) для узла X, если мы знаем LISS для всех потомков X? Если узел рассматривается как часть LIS, то его дочерние элементы не могут быть частью LIS, но его внуки могут быть. Следующее является оптимальным свойством субструктуры.

1) Оптимальная подструктура:
Пусть LISS (X) обозначает размер наибольшего независимого набора дерева с корнем X.

     LISS(X) = MAX { (1 + sum of LISS for all grandchildren of X),
                     (sum of LISS for all children of X) }

Идея проста, есть две возможности для каждого узла X, либо X является членом набора, либо не является членом. Если X является членом, то значение LISS (X) равно 1 плюс LISS всех внуков. Если X не является членом, то значение является суммой LISS всех дочерних элементов.

2) Перекрывающиеся подзадачи
Ниже приводится рекурсивная реализация, которая просто следует рекурсивной структуре, упомянутой выше.

C ++

// Наивная рекурсивная реализация
// Самая большая проблема независимых множеств
#include <bits/stdc++.h>

using namespace std; 

  
// Полезная функция для поиска
// максимум двух целых

int max(int x, int y) 

    return (x > y) ? x : y; 

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

class node 

    public:

    int data; 

    node *left, *right; 

}; 

  
// Функция возвращает размер
// самый большой независимый набор в данном
// двоичное дерево

int LISS(node *root) 

    if (root == NULL) 

    return 0; 

  

    // Расчет размера без учета текущего узла

    int size_excl = LISS(root->left) + 

                    LISS(root->right); 

  

    // Рассчитать размер, включая текущий узел

    int size_incl = 1; 

    if (root->left) 

        size_incl += LISS(root->left->left) +

                     LISS(root->left->right); 

    if (root->right) 

        size_incl += LISS(root->right->left) + 

                     LISS(root->right->right); 

  

    // Возвращаем максимум двух размеров

    return max(size_incl, size_excl); 

  
// Вспомогательная функция для создания узла

node* newNode( int data ) 

    node* temp = new node();

    temp->data = data; 

    temp->left = temp->right = NULL; 

    return temp; 

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

int main() 

    // Построим дерево

    // дано на диаграмме выше

    node *root = newNode(20); 

    root->left = newNode(8); 

    root->left->left = newNode(4); 

    root->left->right = newNode(12); 

    root->left->right->left = newNode(10); 

    root->left->right->right = newNode(14); 

    root->right = newNode(22); 

    root->right->right = newNode(25); 

  

    cout << "Size of the Largest" 

         << " Independent Set is " 

         << LISS(root); 

  

    return 0; 

  
// Это код добавлен
// ратбхупендра

С

// Наивная рекурсивная реализация задачи о наибольшем независимом множестве
#include <stdio.h>
#include <stdlib.h>

  
// Полезная функция, чтобы найти максимум двух целых

int max(int x, int y) { return (x > y)? x: y; }

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка и указатель на

   правильный ребенок * /

struct node

{

    int data;

    struct node *left, *right;

};

  
// Функция возвращает размер наибольшего независимого набора в данном
// двоичное дерево

int LISS(struct node *root)

{

    if (root == NULL)

       return 0;

  

    // Расчет размера без учета текущего узла

    int size_excl = LISS(root->left) + LISS(root->right);

  

    // Рассчитать размер, включая текущий узел

    int size_incl = 1;

    if (root->left)

       size_incl += LISS(root->left->left) + LISS(root->left->right);

    if (root->right)

       size_incl += LISS(root->right->left) + LISS(root->right->right);

  

    // Возвращаем максимум двух размеров

    return max(size_incl, size_excl);

}

  

  
// Вспомогательная функция для создания узла

struct node* newNode( int data )

{

    struct node* temp = (struct node *) malloc( sizeof(struct node) );

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

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

int main()

{

    // Построим дерево, указанное на диаграмме выше

    struct node *root         = newNode(20);

    root->left                = newNode(8);

    root->left->left          = newNode(4);

    root->left->right         = newNode(12);

    root->left->right->left   = newNode(10);

    root->left->right->right  = newNode(14);

    root->right               = newNode(22);

    root->right->right        = newNode(25);

  

    printf ("Size of the Largest Independent Set is %d ", LISS(root));

  

    return 0;

}

Джава

// Наивная рекурсивная реализация
// Самая большая проблема независимых множеств

class GFG {

  
// Полезная функция для поиска
// максимум двух целых

static int max(int x, int y) 

    return (x > y) ? x : y; 

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

static class Node 

    int data; 

    Node left, right; 

}; 

  
// Функция возвращает размер
// самый большой независимый набор в данном
// двоичное дерево

static int LISS(Node root) 

    if (root == null

    return 0

  

    // Расчет размера без учета текущего узла

    int size_excl = LISS(root.left) + 

                    LISS(root.right); 

  

    // Рассчитать размер, включая текущий узел

    int size_incl = 1

    if (root.left!=null

        size_incl += LISS(root.left.left) +

                    LISS(root.left.right); 

    if (root.right!=null

        size_incl += LISS(root.right.left) + 

                    LISS(root.right.right); 

  

    // Возвращаем максимум двух размеров

    return max(size_incl, size_excl); 

  
// Вспомогательная функция для создания узла

static Node newNode( int data ) 

    Node temp = new Node();

    temp.data = data; 

    temp.left = temp.right = null

    return temp; 

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

public static void main(String args[]) {

    // Построим дерево

    // дано на диаграмме выше

    Node root = newNode(20); 

    root.left = newNode(8); 

    root.left.left = newNode(4); 

    root.left.right = newNode(12); 

    root.left.right.left = newNode(10); 

    root.left.right.right = newNode(14); 

    root.right = newNode(22); 

    root.right.right = newNode(25); 

  

    System.out.println("Size of the Largest"

        + " Independent Set is "

        + LISS(root)); 

    }

}

  
// Этот код предоставлен 29AjayKumar

C #

// C # программа для расчета LISS
// используя динамическое программирование

using System;

  

class LisTree 

    / * Узел двоичного дерева имеет данные, указатель

    слева от ребенка и указатель вправо

    ребенок * /

    public class node 

    

        public int data, liss; 

        public node left, right; 

  

        public node(int data) 

        

            this.data = data; 

            this.liss = 0; 

        

    

  

    // Функция памятки возвращает размер

    // самого большого независимого набора в

    // данное двоичное дерево

    static int liss(node root) 

    

        if (root == null

            return 0; 

        if (root.liss != 0) 

            return root.liss; 

        if (root.left == null && root.right == null

            return root.liss = 1; 

          

        // Расчет размера без учета

        // текущий узел

        int liss_excl = liss(root.left) + liss(root.right); 

          

        // Рассчитать размер, включая

        // текущий узел

        int liss_incl = 1; 

        if (root.left != null

        

            liss_incl += (liss(root.left.left) + 

                        liss(root.left.right)); 

        

        if (root.right != null

        

            liss_incl += (liss(root.right.left) + 

                        liss(root.right.right)); 

        

          

        // Максимум двух размеров - LISS,

        // сохранить его для использования в будущем.

        return root.liss = Math.Max(liss_excl, liss_incl); 

    

  

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

    public static void Main(String[] args) 

    

        // Построим данное дерево

        // на схеме выше

          

        node root = new node(20); 

        root.left = new node(8); 

        root.left.left = new node(4); 

        root.left.right = new node(12); 

        root.left.right.left = new node(10); 

        root.left.right.right = new node(14); 

        root.right = new node(22); 

        root.right.right = new node(25); 

        Console.WriteLine("Size of the Largest Independent Set is " + liss(root)); 

    

  
// Этот код предоставлен Принчи Сингхом


Выход:

Size of the Largest Independent Set is 5

Временная сложность вышеуказанного наивного рекурсивного подхода является экспоненциальной. Следует отметить, что вышеуказанная функция снова и снова вычисляет одни и те же подзадачи. Например, LISS узла со значением 50 оценивается для узла со значениями 10 и 20, так как 50 — это внук 10 и потомок 20.
Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, проблема LISS имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP), повторных вычислений с одинаковыми подзадачами можно избежать, храня решения подзадач и решая проблемы снизу вверх.

Ниже приводится реализация решения на основе динамического программирования. В следующем решении дополнительное поле «liss» добавляется к узлам дерева. Начальное значение 'liss' установлено в 0 для всех узлов. Рекурсивная функция LISS () вычисляет liss для узла, только если он еще не установлен.

C ++

/ * Программа на основе динамического программирования
для самой большой проблемы независимых множеств * /
#include <bits/stdc++.h>

using namespace std; 

  
// Полезная функция, чтобы найти максимум двух целых

int max(int x, int y) { return (x > y)? x: y; } 

  
/ * Узел двоичного дерева имеет данные, указатель
оставить ребенка и указатель на
правильный ребенок * /

class node 

    public:

    int data; 

    int liss; 

    node *left, *right; 

}; 

  
// Функция памятки возвращает размер
// самого большого независимого набора в
// данное двоичное дерево

int LISS(node *root) 

    if (root == NULL) 

        return 0; 

  

    if (root->liss) 

        return root->liss; 

  

    if (root->left == NULL && root->right == NULL) 

        return (root->liss = 1); 

  

    // Расчет размера без учета текущего узла

    int liss_excl = LISS(root->left) + LISS(root->right); 

  

    // Рассчитать размер, включая текущий узел

    int liss_incl = 1; 

    if (root->left) 

        liss_incl += LISS(root->left->left) + LISS(root->left->right); 

    if (root->right) 

        liss_incl += LISS(root->right->left) + LISS(root->right->right); 

  

    // Максимум двух размеров - LISS, сохраните его для использования в будущем.

    root->liss = max(liss_incl, liss_excl); 

  

    return root->liss; 

  
// Вспомогательная функция для создания узла

node* newNode(int data) 

    node* temp = new node(); 

    temp->data = data; 

    temp->left = temp->right = NULL; 

    temp->liss = 0; 

    return temp; 

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

int main() 

    // Построим дерево

    // дано на диаграмме выше

    node *root     = newNode(20); 

    root->left         = newNode(8); 

    root->left->left     = newNode(4); 

    root->left->right     = newNode(12); 

    root->left->right->left = newNode(10); 

    root->left->right->right = newNode(14); 

    root->right         = newNode(22); 

    root->right->right     = newNode(25); 

  

    cout << "Size of the Largest Independent Set is " << LISS(root); 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

/ * Программа на основе динамического программирования для задачи с наибольшим независимым множеством * /
#include <stdio.h>
#include <stdlib.h>

  
// Полезная функция, чтобы найти максимум двух целых

int max(int x, int y) { return (x > y)? x: y; }

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка и указатель на

   правильный ребенок * /

struct node

{

    int data;

    int liss;

    struct node *left, *right;

};

  
// Функция памятки возвращает размер наибольшего независимого набора в
// данное двоичное дерево

int LISS(struct node *root)

{

    if (root == NULL)

        return 0;

  

    if (root->liss)

        return root->liss;

  

    if (root->left == NULL && root->right == NULL)

        return (root->liss = 1);

  

    // Расчет размера без учета текущего узла

    int liss_excl = LISS(root->left) + LISS(root->right);

  

    // Рассчитать размер, включая текущий узел

    int liss_incl = 1;

    if (root->left)

        liss_incl += LISS(root->left->left) + LISS(root->left->right);

    if (root->right)

        liss_incl += LISS(root->right->left) + LISS(root->right->right);

  

    // Максимум двух размеров - LISS, сохраните его для использования в будущем.

    root->liss = max(liss_incl, liss_excl);

  

    return root->liss;

}

  
// Вспомогательная функция для создания узла

struct node* newNode(int data)

{

    struct node* temp = (struct node *) malloc( sizeof(struct node) );

    temp->data = data;

    temp->left = temp->right = NULL;

    temp->liss = 0;

    return temp;

}

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

int main()

{

    // Построим дерево, указанное на диаграмме выше

    struct node *root         = newNode(20);

    root->left                = newNode(8);

    root->left->left          = newNode(4);

    root->left->right         = newNode(12);

    root->left->right->left   = newNode(10);

    root->left->right->right  = newNode(14);

    root->right               = newNode(22);

    root->right->right        = newNode(25);

  

    printf ("Size of the Largest Independent Set is %d ", LISS(root));

  

    return 0;

}

Джава

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

  

public class LisTree 

{

    / * Узел двоичного дерева имеет данные, указатель

       слева от ребенка и указатель вправо

       ребенок * /

    static class node 

    {

        int data, liss;

        node left, right;

  

        public node(int data) 

        {

            this.data = data;

            this.liss = 0;

        }

    }

  

    // Функция памятки возвращает размер

    // самого большого независимого набора в

    // данное двоичное дерево

    static int liss(node root) 

    {

        if (root == null)

            return 0;

        if (root.liss != 0)

            return root.liss;

        if (root.left == null && root.right == null)

            return root.liss = 1;

          

        // Расчет размера без учета

        // текущий узел

        int liss_excl = liss(root.left) + liss(root.right);

          

        // Рассчитать размер, включая

        // текущий узел

        int liss_incl = 1;

        if (root.left != null

        {

            liss_incl += (liss(root.left.left) + liss(root.left.right));

        }

        if (root.right != null

        {

            liss_incl += (liss(root.right.left) + liss(root.right.right));

        }

          

        // Максимум двух размеров - LISS,

        // сохранить его для использования в будущем.

        return root.liss = Math.max(liss_excl, liss_incl);

    }

  

    public static void main(String[] args) 

    {

        // Построим данное дерево

        // на схеме выше

          

        node root = new node(20);

        root.left = new node(8);

        root.left.left = new node(4);

        root.left.right = new node(12);

        root.left.right.left = new node(10);

        root.left.right.right = new node(14);

        root.right = new node(22);

        root.right.right = new node(25);

        System.out.println("Size of the Largest Independent Set is " + liss(root));

    }

}

  
// Этот код предоставлен Rishabh Mahrsee

C #

// C # программа для расчета LISS
// используя динамическое программирование

using System;

      

public class LisTree 

{

    / * Узел двоичного дерева имеет данные, указатель

    слева от ребенка и указатель вправо

    ребенок * /

    public class node 

    {

        public int data, liss;

        public node left, right;

  

        public node(int data) 

        {

            this.data = data;

            this.liss = 0;

        }

    }

  

    // Функция памятки возвращает размер

    // самого большого независимого набора в

    // данное двоичное дерево

    static int liss(node root) 

    {

        if (root == null)

            return 0;

        if (root.liss != 0)

            return root.liss;

        if (root.left == null && root.right == null)

            return root.liss = 1;

          

        // Расчет размера без учета

        // текущий узел

        int liss_excl = liss(root.left) + liss(root.right);

          

        // Рассчитать размер, включая

        // текущий узел

        int liss_incl = 1;

        if (root.left != null

        {

            liss_incl += (liss(root.left.left) + liss(root.left.right));

        }

        if (root.right != null

        {

            liss_incl += (liss(root.right.left) + liss(root.right.right));

        }

          

        // Максимум двух размеров - LISS,

        // сохранить его для использования в будущем.

        return root.liss = Math.Max(liss_excl, liss_incl);

    }

  

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

    public static void Main(String[] args) 

    {

        // Построим данное дерево

        // на схеме выше

          

        node root = new node(20);

        root.left = new node(8);

        root.left.left = new node(4);

        root.left.right = new node(12);

        root.left.right.left = new node(10);

        root.left.right.right = new node(14);

        root.right = new node(22);

        root.right.right = new node(25);

        Console.WriteLine("Size of the Largest Independent Set is " + liss(root));

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /
// C # программа для расчета LISS
// используя динамическое программирование

using System;

      

public class LisTree 

{

    / * Узел двоичного дерева имеет данные, указатель

    слева от ребенка и указатель вправо

    ребенок * /

    public class node 

    {

        public int data, liss;

        public node left, right;

  

        public node(int data) 

        {

            this.data = data;

            this.liss = 0;

        }

    }

  

    // Функция памятки возвращает размер

    // самого большого независимого набора в

    // данное двоичное дерево

    static int liss(node root) 

    {

        if (root == null)

            return 0;

        if (root.liss != 0)

            return root.liss;

        if (root.left == null && root.right == null)

            return root.liss = 1;

          

        // Расчет размера без учета

        // текущий узел

        int liss_excl = liss(root.left) + liss(root.right);

          

        // Рассчитать размер, включая

        // текущий узел

        int liss_incl = 1;

        if (root.left != null

        {

            liss_incl += (liss(root.left.left) + liss(root.left.right));

        }

        if (root.right != null

        {

            liss_incl += (liss(root.right.left) + liss(root.right.right));

        }

          

        // Максимум двух размеров - LISS,

        // сохранить его для использования в будущем.

        return root.liss = Math.Max(liss_excl, liss_incl);

    }

  

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

    public static void Main(String[] args) 

    {

        // Построим данное дерево

        // на схеме выше

          

        node root = new node(20);

        root.left = new node(8);

        root.left.left = new node(4);

        root.left.right = new node(12);

        root.left.right.left = new node(10);

        root.left.right.right = new node(14);

        root.right = new node(22);

        root.right.right = new node(25);

        Console.WriteLine("Size of the Largest Independent Set is " + liss(root));

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход:

Size of the Largest Independent Set is 5


Сложность времени:
O (n), где n — количество узлов в данном двоичном дереве.

Следующие дополнения к вышеупомянутому решению можно попробовать в качестве упражнения.
1) Расширим вышеприведенное решение для n-арного дерева.

2) Приведенное выше решение модифицирует заданную древовидную структуру, добавляя дополнительное поле 'liss' к узлам дерева. Расширьте решение, чтобы оно не изменило древовидную структуру.

3) Приведенное выше решение возвращает только размер LIS, оно не печатает элементы LIS. Расширьте решение, чтобы распечатать все узлы, которые являются частью LIS.

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

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

Самая большая проблема независимых множеств | DP-26

0.00 (0%) 0 votes