Dado un árbol binario, encuentre el tamaño del conjunto independiente más grande ( LIS ) en él. Un subconjunto de todos los Nodes del árbol es un conjunto independiente si no hay borde entre dos Nodes cualesquiera del subconjunto.
Por ejemplo, considere el siguiente árbol binario. El conjunto independiente más grande (LIS) es {10, 40, 60, 70, 80} y el tamaño del LIS es 5.
Una solución de Programación Dinámica resuelve un problema dado utilizando soluciones de subproblemas de manera ascendente. ¿Se puede resolver el problema dado usando soluciones a subproblemas? En caso afirmativo, ¿cuáles son los subproblemas? ¿Podemos encontrar el tamaño de conjunto independiente más grande (LISS) para un Node X si conocemos LISS para todos los descendientes de X? Si un Node se considera parte de LIS, entonces sus hijos no pueden ser parte de LIS, pero sus nietos sí pueden serlo. A continuación se muestra la propiedad óptima de la subestructura.
1) Subestructura óptima:
Sea LISS(X) que indique el tamaño del conjunto independiente más grande de un árbol con raíz X.
LISS(X) = MAX { (1 + sum of LISS for all grandchildren of X),
(sum of LISS for all children of X) }
La idea es simple, hay dos posibilidades para cada Node X, o X es miembro del conjunto o no es miembro. Si X es miembro, entonces el valor de LISS(X) es 1 más LISS de todos los nietos. Si X no es miembro, entonces el valor es la suma de LISS de todos los hijos.
2) Subproblemas superpuestos A
continuación se presenta una implementación recursiva que simplemente sigue la estructura recursiva mencionada anteriormente.
C++
// A naive recursive implementation of
// Largest Independent Set problem
#include <bits/stdc++.h>
using namespace std;
// A utility function to find
// max of two integers
int max(int x, int y)
{
return (x > y) ? x : y;
}
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
class node
{
public:
int data;
node *left, *right;
};
// The function returns size of the
// largest independent set in a given
// binary tree
int LISS(node *root)
{
if (root == NULL)
return 0;
// Calculate size excluding the current node
int size_excl = LISS(root->left) +
LISS(root->right);
// Calculate size including the current node
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 the maximum of two sizes
return max(size_incl, size_excl);
}
// A utility function to create a node
node* newNode( int data )
{
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver Code
int main()
{
// Let us construct the tree
// given in the above diagram
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;
}
// This is code is contributed
// by rathbhupendra
C
// A naive recursive implementation of Largest Independent Set problem
#include <stdio.h>
#include <stdlib.h>
// A utility function to find max of two integers
int max(int x, int y) { return (x > y)? x: y; }
/* A binary tree node has data, pointer to left child and a pointer to
right child */
struct node
{
int data;
struct node *left, *right;
};
// The function returns size of the largest independent set in a given
// binary tree
int LISS(struct node *root)
{
if (root == NULL)
return 0;
// Calculate size excluding the current node
int size_excl = LISS(root->left) + LISS(root->right);
// Calculate size including the current node
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 the maximum of two sizes
return max(size_incl, size_excl);
}
// A utility function to create a node
struct node* newNode( int data )
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us construct the tree given in the above diagram
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
// A naive recursive implementation of
// Largest Independent Set problem
class GFG {
// A utility function to find
// max of two integers
static int max(int x, int y)
{
return (x > y) ? x : y;
}
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
static class Node
{
int data;
Node left, right;
};
// The function returns size of the
// largest independent set in a given
// binary tree
static int LISS(Node root)
{
if (root == null)
return 0;
// Calculate size excluding the current node
int size_excl = LISS(root.left) +
LISS(root.right);
// Calculate size including the current node
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 the maximum of two sizes
return max(size_incl, size_excl);
}
// A utility function to create a node
static Node newNode( int data )
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver Code
public static void main(String args[]) {
// Let us construct the tree
// given in the above diagram
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));
}
}
// This code has been contributed by 29AjayKumar
Python3
# A naive recursive implementation of # Largest Independent Set problem # A utility function to find # max of two integers def max(x, y): if(x > y): return x else: return y # A binary tree node has data, #pointer to left child and a #pointer to right child class node : def __init__(self): self.data = 0 self.left = self.right = None # The function returns size of the # largest independent set in a given # binary tree def LISS(root): if (root == None) : return 0 # Calculate size excluding the current node size_excl = LISS(root.left) + LISS(root.right) # Calculate size including the current node size_incl = 1 if (root.left != None): size_incl += LISS(root.left.left) + \ LISS(root.left.right) if (root.right != None): size_incl += LISS(root.right.left) + \ LISS(root.right.right) # Return the maximum of two sizes return max(size_incl, size_excl) # A utility function to create a node def newNode( data ) : temp = node() temp.data = data temp.left = temp.right = None return temp # Driver Code # Let us construct the tree # given in the above diagram 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) print( "Size of the Largest" , " Independent Set is " , LISS(root) ) # This code is contributed by Arnab Kundu
C#
// C# program for calculating LISS
// using dynamic programming
using System;
class LisTree
{
/* A binary tree node has data, pointer
to left child and a pointer to right
child */
public class node
{
public int data, liss;
public node left, right;
public node(int data)
{
this.data = data;
this.liss = 0;
}
}
// A memoization function returns size
// of the largest independent set in
// a given binary tree
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;
// Calculate size excluding the
// current node
int liss_excl = liss(root.left) + liss(root.right);
// Calculate size including the
// current node
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));
}
// Maximum of two sizes is LISS,
// store it for future uses.
return root.liss = Math.Max(liss_excl, liss_incl);
}
// Driver code
public static void Main(String[] args)
{
// Let us construct the tree given
// in the above diagram
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));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// A naive recursive implementation of
// Largest Independent Set problem
// A utility function to find
// max of two integers
function max(x, y)
{
return(x > y) ? x : y;
}
// A binary tree node has data,
// pointer to left child and a
// pointer to right child
class Node
{
constructor(data)
{
this.data = data;
this.left = this.right = null;
}
}
// The function returns size of the
// largest independent set in a given
// binary tree
function LISS(root)
{
if (root == null)
return 0;
// Calculate size excluding the current node
let size_excl = LISS(root.left) +
LISS(root.right);
// Calculate size including the current node
let 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 the maximum of two sizes
return max(size_incl, size_excl);
}
// Driver Code
// Let us construct the tree
// given in the above diagram
let 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);
document.write("Size of the Largest" +
" Independent Set is " +
LISS(root));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Size of the Largest Independent Set is 5
La complejidad temporal del enfoque recursivo ingenuo anterior es exponencial. Cabe señalar que la función anterior calcula los mismos subproblemas una y otra vez. Por ejemplo, el LISS del Node con valor 50 se evalúa para el Node con valores 10 y 20, ya que 50 es nieto de 10 e hijo de 20.
Dado que los mismos subproblemas se vuelven a llamar, este problema tiene la propiedad Superposición de subproblemas. Entonces, el problema LISS tiene ambas propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica (DP), los cálculos de los mismos subproblemas se pueden evitar almacenando las soluciones a los subproblemas y resolviendo los problemas de manera ascendente.
A continuación se muestra la implementación de la solución basada en la programación dinámica. En la siguiente solución, se agrega un campo adicional ‘liss’ a los Nodes del árbol. El valor inicial de ‘liss’ se establece en 0 para todos los Nodes. La función recursiva LISS() calcula ‘liss’ para un Node solo si aún no está configurado.
C++
/* Dynamic programming based program
for Largest Independent Set problem */
#include <bits/stdc++.h>
using namespace std;
// A utility function to find max of two integers
int max(int x, int y) { return (x > y)? x: y; }
/* A binary tree node has data, pointer
to left child and a pointer to
right child */
class node
{
public:
int data;
int liss;
node *left, *right;
};
// A memoization function returns size
// of the largest independent set in
// a given binary tree
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);
// Calculate size excluding the current node
int liss_excl = LISS(root->left) + LISS(root->right);
// Calculate size including the current node
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);
// Maximum of two sizes is LISS, store it for future uses.
root->liss = max(liss_incl, liss_excl);
return root->liss;
}
// A utility function to create a node
node* newNode(int data)
{
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
temp->liss = 0;
return temp;
}
// Driver code
int main()
{
// Let us construct the tree
// given in the above diagram
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;
}
// This code is contributed by rathbhupendra
C
/* Dynamic programming based program for Largest Independent Set problem */
#include <stdio.h>
#include <stdlib.h>
// A utility function to find max of two integers
int max(int x, int y) { return (x > y)? x: y; }
/* A binary tree node has data, pointer to left child and a pointer to
right child */
struct node
{
int data;
int liss;
struct node *left, *right;
};
// A memoization function returns size of the largest independent set in
// a given binary tree
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);
// Calculate size excluding the current node
int liss_excl = LISS(root->left) + LISS(root->right);
// Calculate size including the current node
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);
// Maximum of two sizes is LISS, store it for future uses.
root->liss = max(liss_incl, liss_excl);
return root->liss;
}
// A utility function to create a node
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;
}
// Driver program to test above functions
int main()
{
// Let us construct the tree given in the above diagram
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
// Java program for calculating LISS
// using dynamic programming
public class LisTree
{
/* A binary tree node has data, pointer
to left child and a pointer to right
child */
static class node
{
int data, liss;
node left, right;
public node(int data)
{
this.data = data;
this.liss = 0;
}
}
// A memoization function returns size
// of the largest independent set in
// a given binary tree
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;
// Calculate size excluding the
// current node
int liss_excl = liss(root.left) + liss(root.right);
// Calculate size including the
// current node
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));
}
// Maximum of two sizes is LISS,
// store it for future uses.
return root.liss = Math.max(liss_excl, liss_incl);
}
public static void main(String[] args)
{
// Let us construct the tree given
// in the above diagram
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));
}
}
// This code is contributed by Rishabh Mahrsee
Python3
# Python3 program for calculating LISS
# using dynamic programming
# A binary tree node has data,
# pointer to left child and a
# pointer to right child
class node:
def __init__(self, data):
self.data = data
self.left = self.right = None
self.liss = 0
# A memoization function returns size
# of the largest independent set in
# a given binary tree
def liss(root):
if root == None:
return 0
if root.liss != 0:
return root.liss
if (root.left == None and
root.right == None):
root.liss = 1
return root.liss
# Calculate size excluding the
# current node
liss_excl = (liss(root.left) +
liss(root.right))
# Calculate size including the
# current node
liss_incl = 1
if root.left != None:
liss_incl += (liss(root.left.left) +
liss(root.left.right))
if root.right != None:
liss_incl += (liss(root.right.left) +
liss(root.right.right))
# Maximum of two sizes is LISS,
# store it for future uses.
root.liss = max(liss_excl, liss_incl)
return root.liss
# Driver Code
# Let us construct the tree given
# in the above diagram
root = node(20)
root.left = node(8)
root.left.left = node(4)
root.left.right = node(12)
root.left.right.left = node(10)
root.left.right.right = node(14)
root.right = node(22)
root.right.right = node(25)
print("Size of the Largest Independent "\
"Set is ", liss(root))
# This code is contributed by nishthagoel712
C#
// C# program for calculating LISS
// using dynamic programming
using System;
public class LisTree
{
/* A binary tree node has data, pointer
to left child and a pointer to right
child */
public class node
{
public int data, liss;
public node left, right;
public node(int data)
{
this.data = data;
this.liss = 0;
}
}
// A memoization function returns size
// of the largest independent set in
// a given binary tree
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;
// Calculate size excluding the
// current node
int liss_excl = liss(root.left) + liss(root.right);
// Calculate size including the
// current node
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));
}
// Maximum of two sizes is LISS,
// store it for future uses.
return root.liss = Math.Max(liss_excl, liss_incl);
}
// Driver code
public static void Main(String[] args)
{
// Let us construct the tree given
// in the above diagram
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));
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program for calculating LISS
// using dynamic programming
/* A binary tree node has data, pointer
to left child and a pointer to right
child */
class node {
constructor(data) {
this.data = data;
this.liss = 0;
this.left = null;
this.right = null;
}
}
// A memoization function returns size
// of the largest independent set in
// a given binary tree
function liss(root) {
if (root == null) return 0;
if (root.liss != 0) return root.liss;
if (root.left == null && root.right == null)
return (root.liss = 1);
// Calculate size excluding the
// current node
var liss_excl = liss(root.left) + liss(root.right);
// Calculate size including the
// current node
var 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);
}
// Maximum of two sizes is LISS,
// store it for future uses.
return (root.liss = Math.max(liss_excl, liss_incl));
}
// Driver code
// Let us construct the tree given
// in the above diagram
var 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);
document.write(
"Size of the Largest Independent Set is " + liss(root)
);
</script>
Producción:
Size of the Largest Independent Set is 5
Complejidad de tiempo: O (n) donde n es el número de Nodes en el árbol binario dado.
Las siguientes extensiones a la solución anterior se pueden probar como ejercicio.
1) Extienda la solución anterior para el árbol n-ario.
2) La solución anterior modifica la estructura de árbol dada agregando un campo adicional ‘liss’ a los Nodes del árbol. Extienda la solución para que no modifique la estructura de árbol.
3) La solución anterior solo devuelve el tamaño de LIS, no imprime elementos de LIS. Extienda la solución para imprimir todos los Nodes que forman parte de LIS.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA