Presentamos Branch and Bound y discutimos el problema de la mochila 0/1 en las publicaciones a continuación.
- Rama y Atado | Set 1 (Introducción con 0/1 Mochila)
- Rama y Atado | Set 2 (Implementación de 0/1 Mochila)
En este acertijo se discute la solución del problema de los 8 acertijos.
Dado un tablero de 3×3 con 8 fichas (cada ficha tiene un número del 1 al 8) y un espacio vacío. El objetivo es colocar los números en los mosaicos para que coincidan con la configuración final utilizando el espacio vacío. Podemos deslizar cuatro fichas adyacentes (izquierda, derecha, arriba y abajo) en el espacio vacío.
Por ejemplo,
1. DFS (Fuerza bruta)
Podemos realizar una búsqueda en profundidad en el árbol de espacio de estado (conjunto de todas las configuraciones de un problema dado, es decir, todos los estados que se pueden alcanzar desde el estado inicial).
En esta solución, los movimientos sucesivos pueden alejarnos de la meta en lugar de acercarnos. La búsqueda del árbol de espacio de estado sigue el camino más a la izquierda desde la raíz, independientemente del estado inicial. Es posible que nunca se encuentre un Node de respuesta en este enfoque.
2. BFS (Brute-Force)
Podemos realizar una búsqueda en amplitud en el árbol de espacio de estado. Esto siempre encuentra un estado objetivo más cercano a la raíz. Pero no importa cuál sea el estado inicial, el algoritmo intenta la misma secuencia de movimientos como DFS.
3. Rama y límite
La búsqueda de un Node de respuesta a menudo se puede acelerar mediante el uso de una función de clasificación «inteligente», también llamada función de costo aproximado para evitar buscar en subárboles que no contienen un Node de respuesta. Es similar a la técnica de retroceso pero utiliza una búsqueda similar a BFS.
Básicamente, hay tres tipos de Nodes involucrados en Branch and Bound
1. El Node en vivo es un Node que se ha generado pero cuyos hijos aún no se han generado.
2. E-node es un Node vivo cuyos hijos se están explorando actualmente. En otras palabras, un Node E es un Node que se está expandiendo actualmente.
3. El Node muerto es un Node generado que no debe expandirse ni explorarse más. Todos los hijos de un Node muerto ya se han expandido.
Función de costo:
Cada Node X en el árbol de búsqueda está asociado a un costo. La función de costo es útil para determinar el próximo Node E. El siguiente E-Node es el que tiene el menor costo. La función de costo se define como
C(X) = g(X) + h(X) where
g(X) = cost of reaching the current node
from the root
h(X) = cost of reaching an answer node from X.
La función de costo ideal para un algoritmo de 8 rompecabezas:
Suponemos que mover una ficha en cualquier dirección tendrá un costo de 1 unidad. Teniendo eso en cuenta, definimos una función de costo para el algoritmo de 8 rompecabezas de la siguiente manera:
c(x) = f(x) + h(x) where
f(x) is the length of the path from root to x
(the number of moves so far) and
h(x) is the number of non-blank tiles not in
their goal position (the number of mis-
-placed tiles). There are at least h(x)
moves to transform state x to a goal state
Se dispone de un algoritmo para obtener una aproximación de h(x), que es un valor desconocido.
Algoritmo completo:
/* Algorithm LCSearch uses c(x) to find an answer node
* LCSearch uses Least() and Add() to maintain the list
of live nodes
* Least() finds a live node with least c(x), deletes
it from the list and returns it
* Add(x) adds x to the list of live nodes
* Implement list of live nodes as a min-heap */
struct list_node
{
list_node *next;
// Helps in tracing path when answer is found
list_node *parent;
float cost;
}
algorithm LCSearch(list_node *t)
{
// Search t for an answer node
// Input: Root node of tree t
// Output: Path from answer node to root
if (*t is an answer node)
{
print(*t);
return;
}
E = t; // E-node
Initialize the list of live nodes to be empty;
while (true)
{
for each child x of E
{
if x is an answer node
{
print the path from x to t;
return;
}
Add (x); // Add x to list of live nodes;
x->parent = E; // Pointer for path to root
}
if there are no more live nodes
{
print ("No answer node");
return;
}
// Find a live node with least estimated cost
E = Least();
// The found node is deleted from the list of
// live nodes
}
}
El siguiente diagrama muestra el camino seguido por el algoritmo anterior para llegar a la configuración final a partir de la configuración inicial dada del 8-Puzzle. Tenga en cuenta que solo se expanden los Nodes que tienen el menor valor de la función de costo.
C++14
// Program to print path from root node to destination node
// for N*N -1 puzzle algorithm using Branch and Bound
// The solution assumes that instance of puzzle is solvable
#include <bits/stdc++.h>
using namespace std;
#define N 3
// state space tree nodes
struct Node
{
// stores the parent node of the current node
// helps in tracing path when the answer is found
Node* parent;
// stores matrix
int mat[N][N];
// stores blank tile coordinates
int x, y;
// stores the number of misplaced tiles
int cost;
// stores the number of moves so far
int level;
};
// Function to print N x N matrix
int printMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf("%d ", mat[i][j]);
printf("\n");
}
}
// Function to allocate a new node
Node* newNode(int mat[N][N], int x, int y, int newX,
int newY, int level, Node* parent)
{
Node* node = new Node;
// set pointer for path to root
node->parent = parent;
// copy data from parent node to current node
memcpy(node->mat, mat, sizeof node->mat);
// move tile by 1 position
swap(node->mat[x][y], node->mat[newX][newY]);
// set number of misplaced tiles
node->cost = INT_MAX;
// set number of moves so far
node->level = level;
// update new blank tile coordinates
node->x = newX;
node->y = newY;
return node;
}
// bottom, left, top, right
int row[] = { 1, 0, -1, 0 };
int col[] = { 0, -1, 0, 1 };
// Function to calculate the number of misplaced tiles
// ie. number of non-blank tiles not in their goal position
int calculateCost(int initial[N][N], int final[N][N])
{
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (initial[i][j] && initial[i][j] != final[i][j])
count++;
return count;
}
// Function to check if (x, y) is a valid matrix coordinate
int isSafe(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
// print path from root node to destination node
void printPath(Node* root)
{
if (root == NULL)
return;
printPath(root->parent);
printMatrix(root->mat);
printf("\n");
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(const Node* lhs, const Node* rhs) const
{
return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);
}
};
// Function to solve N*N - 1 puzzle algorithm using
// Branch and Bound. x and y are blank tile coordinates
// in initial state
void solve(int initial[N][N], int x, int y,
int final[N][N])
{
// Create a priority queue to store live nodes of
// search tree;
priority_queue<Node*, std::vector<Node*>, comp> pq;
// create a root node and calculate its cost
Node* root = newNode(initial, x, y, x, y, 0, NULL);
root->cost = calculateCost(initial, final);
// Add root to list of live nodes;
pq.push(root);
// Finds a live node with least cost,
// add its childrens to list of live nodes and
// finally deletes it from the list.
while (!pq.empty())
{
// Find a live node with least estimated cost
Node* min = pq.top();
// The found node is deleted from the list of
// live nodes
pq.pop();
// if min is an answer node
if (min->cost == 0)
{
// print the path from root to destination;
printPath(min);
return;
}
// do for each child of min
// max 4 children for a node
for (int i = 0; i < 4; i++)
{
if (isSafe(min->x + row[i], min->y + col[i]))
{
// create a child node and calculate
// its cost
Node* child = newNode(min->mat, min->x,
min->y, min->x + row[i],
min->y + col[i],
min->level + 1, min);
child->cost = calculateCost(child->mat, final);
// Add child to list of live nodes
pq.push(child);
}
}
}
}
// Driver code
int main()
{
// Initial configuration
// Value 0 is used for empty space
int initial[N][N] =
{
{1, 2, 3},
{5, 6, 0},
{7, 8, 4}
};
// Solvable Final configuration
// Value 0 is used for empty space
int final[N][N] =
{
{1, 2, 3},
{5, 8, 6},
{0, 7, 4}
};
// Blank tile coordinates in initial
// configuration
int x = 1, y = 2;
solve(initial, x, y, final);
return 0;
}
Java
// Java Program to print path from root node to destination node
// for N*N -1 puzzle algorithm using Branch and Bound
// The solution assumes that instance of puzzle is solvable
import java.io.*;
import java.util.*;
class GFG
{
public static int N = 3;
public static class Node
{
// stores the parent node of the current node
// helps in tracing path when the answer is found
Node parent;
int mat[][] = new int[N][N];// stores matrix
int x, y;// stores blank tile coordinates
int cost;// stores the number of misplaced tiles
int level;// stores the number of moves so far
}
// Function to print N x N matrix
public static void printMatrix(int mat[][]){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
System.out.print(mat[i][j]+" ");
}
System.out.println("");
}
}
// Function to allocate a new node
public static Node newNode(int mat[][], int x, int y,
int newX, int newY, int level,
Node parent){
Node node = new Node();
node.parent = parent;// set pointer for path to root
// copy data from parent node to current node
node.mat = new int[N][N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
node.mat[i][j] = mat[i][j];
}
}
// move tile by 1 position
int temp = node.mat[x][y];
node.mat[x][y] = node.mat[newX][newY];
node.mat[newX][newY]=temp;
node.cost = Integer.MAX_VALUE;// set number of misplaced tiles
node.level = level;// set number of moves so far
// update new blank tile coordinates
node.x = newX;
node.y = newY;
return node;
}
// bottom, left, top, right
public static int row[] = { 1, 0, -1, 0 };
public static int col[] = { 0, -1, 0, 1 };
// Function to calculate the number of misplaced tiles
// ie. number of non-blank tiles not in their goal position
public static int calculateCost(int initialMat[][], int finalMat[][])
{
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (initialMat[i][j]!=0 && initialMat[i][j] != finalMat[i][j])
count++;
return count;
}
// Function to check if (x, y) is a valid matrix coordinate
public static int isSafe(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N)?1:0;
}
// print path from root node to destination node
public static void printPath(Node root){
if(root == null){
return;
}
printPath(root.parent);
printMatrix(root.mat);
System.out.println("");
}
// Comparison object to be used to order the heap
public static class comp implements Comparator<Node>{
@Override
public int compare(Node lhs, Node rhs){
return (lhs.cost + lhs.level) > (rhs.cost+rhs.level)?1:-1;
}
}
// Function to solve N*N - 1 puzzle algorithm using
// Branch and Bound. x and y are blank tile coordinates
// in initial state
public static void solve(int initialMat[][], int x,
int y, int finalMat[][])
{
// Create a priority queue to store live nodes of search tree
PriorityQueue<Node> pq = new PriorityQueue<>(new comp());
// create a root node and calculate its cost
Node root = newNode(initialMat, x, y, x, y, 0, null);
root.cost = calculateCost(initialMat,finalMat);
// Add root to list of live nodes;
pq.add(root);
// Finds a live node with least cost,
// add its childrens to list of live nodes and
// finally deletes it from the list.
while(!pq.isEmpty())
{
Node min = pq.peek();// Find a live node with least estimated cost
pq.poll();// The found node is deleted from the list of live nodes
// if min is an answer node
if(min.cost == 0){
printPath(min);// print the path from root to destination;
return;
}
// do for each child of min
// max 4 children for a node
for (int i = 0; i < 4; i++)
{
if (isSafe(min.x + row[i], min.y + col[i])>0)
{
// create a child node and calculate
// its cost
Node child = newNode(min.mat, min.x, min.y, min.x + row[i],min.y + col[i], min.level + 1, min);
child.cost = calculateCost(child.mat, finalMat);
// Add child to list of live nodes
pq.add(child);
}
}
}
}
//Driver Code
public static void main (String[] args)
{
// Initial configuration
// Value 0 is used for empty space
int initialMat[][] =
{
{1, 2, 3},
{5, 6, 0},
{7, 8, 4}
};
// Solvable Final configuration
// Value 0 is used for empty space
int finalMat[][] =
{
{1, 2, 3},
{5, 8, 6},
{0, 7, 4}
};
// Blank tile coordinates in initial
// configuration
int x = 1, y = 2;
solve(initialMat, x, y, finalMat);
}
}
// This code is contributed by shruti456rawal
Python3
# Python3 program to print the path from root
# node to destination node for N*N-1 puzzle
# algorithm using Branch and Bound
# The solution assumes that instance of
# puzzle is solvable
# Importing copy for deepcopy function
import copy
# Importing the heap functions from python
# library for Priority Queue
from heapq import heappush, heappop
# This variable can be changed to change
# the program from 8 puzzle(n=3) to 15
# puzzle(n=4) to 24 puzzle(n=5)...
n = 3
# bottom, left, top, right
row = [ 1, 0, -1, 0 ]
col = [ 0, -1, 0, 1 ]
# A class for Priority Queue
class priorityQueue:
# Constructor to initialize a
# Priority Queue
def __init__(self):
self.heap = []
# Inserts a new key 'k'
def push(self, k):
heappush(self.heap, k)
# Method to remove minimum element
# from Priority Queue
def pop(self):
return heappop(self.heap)
# Method to know if the Queue is empty
def empty(self):
if not self.heap:
return True
else:
return False
# Node structure
class node:
def __init__(self, parent, mat, empty_tile_pos,
cost, level):
# Stores the parent node of the
# current node helps in tracing
# path when the answer is found
self.parent = parent
# Stores the matrix
self.mat = mat
# Stores the position at which the
# empty space tile exists in the matrix
self.empty_tile_pos = empty_tile_pos
# Stores the number of misplaced tiles
self.cost = cost
# Stores the number of moves so far
self.level = level
# This method is defined so that the
# priority queue is formed based on
# the cost variable of the objects
def __lt__(self, nxt):
return self.cost < nxt.cost
# Function to calculate the number of
# misplaced tiles ie. number of non-blank
# tiles not in their goal position
def calculateCost(mat, final) -> int:
count = 0
for i in range(n):
for j in range(n):
if ((mat[i][j]) and
(mat[i][j] != final[i][j])):
count += 1
return count
def newNode(mat, empty_tile_pos, new_empty_tile_pos,
level, parent, final) -> node:
# Copy data from parent matrix to current matrix
new_mat = copy.deepcopy(mat)
# Move tile by 1 position
x1 = empty_tile_pos[0]
y1 = empty_tile_pos[1]
x2 = new_empty_tile_pos[0]
y2 = new_empty_tile_pos[1]
new_mat[x1][y1], new_mat[x2][y2] = new_mat[x2][y2], new_mat[x1][y1]
# Set number of misplaced tiles
cost = calculateCost(new_mat, final)
new_node = node(parent, new_mat, new_empty_tile_pos,
cost, level)
return new_node
# Function to print the N x N matrix
def printMatrix(mat):
for i in range(n):
for j in range(n):
print("%d " % (mat[i][j]), end = " ")
print()
# Function to check if (x, y) is a valid
# matrix coordinate
def isSafe(x, y):
return x >= 0 and x < n and y >= 0 and y < n
# Print path from root node to destination node
def printPath(root):
if root == None:
return
printPath(root.parent)
printMatrix(root.mat)
print()
# Function to solve N*N - 1 puzzle algorithm
# using Branch and Bound. empty_tile_pos is
# the blank tile position in the initial state.
def solve(initial, empty_tile_pos, final):
# Create a priority queue to store live
# nodes of search tree
pq = priorityQueue()
# Create the root node
cost = calculateCost(initial, final)
root = node(None, initial,
empty_tile_pos, cost, 0)
# Add root to list of live nodes
pq.push(root)
# Finds a live node with least cost,
# add its children to list of live
# nodes and finally deletes it from
# the list.
while not pq.empty():
# Find a live node with least estimated
# cost and delete it form the list of
# live nodes
minimum = pq.pop()
# If minimum is the answer node
if minimum.cost == 0:
# Print the path from root to
# destination;
printPath(minimum)
return
# Generate all possible children
for i in range(4):
new_tile_pos = [
minimum.empty_tile_pos[0] + row[i],
minimum.empty_tile_pos[1] + col[i], ]
if isSafe(new_tile_pos[0], new_tile_pos[1]):
# Create a child node
child = newNode(minimum.mat,
minimum.empty_tile_pos,
new_tile_pos,
minimum.level + 1,
minimum, final,)
# Add child to list of live nodes
pq.push(child)
# Driver Code
# Initial configuration
# Value 0 is used for empty space
initial = [ [ 1, 2, 3 ],
[ 5, 6, 0 ],
[ 7, 8, 4 ] ]
# Solvable Final configuration
# Value 0 is used for empty space
final = [ [ 1, 2, 3 ],
[ 5, 8, 6 ],
[ 0, 7, 4 ] ]
# Blank tile coordinates in
# initial configuration
empty_tile_pos = [ 1, 2 ]
# Function call to solve the puzzle
solve(initial, empty_tile_pos, final)
# This code is contributed by Kevin Joshi
Producción :
1 2 3 5 6 0 7 8 4 1 2 3 5 0 6 7 8 4 1 2 3 5 8 6 7 0 4 1 2 3 5 8 6 0 7 4
Fuentes:
www.cs.umsl.edu/~sanjiv/classes/cs5130/lectures/bb.pdf
https://www.seas.gwu.edu/~bell/csci212/Branch_and_Bound.pdf
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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