Torre de Hanoi basada en costos

Posted on by Rudeus Greyrat

El problema estándar de la Torre de Hanoi se explica aquí . En el problema estándar, todas las transacciones del disco se consideran idénticas. Dada una array de 3×3 de costos[][] que contiene los costos de transferencia del disco entre las barras, donde costos[i][j] almacena el costo de transferir un disco de la barra i a la barra j . El costo de transferencia entre la misma barra es 0 . Por lo tanto, los elementos diagonales de la array de costos son todos ceros . La tarea es imprimir el costo mínimo en el que todos los N discos se transfieren de la barra 1 a la barra 3 .
Ejemplos: 
 

Entrada: N = 2 
costos = { 
{ 0, 1, 2}, 
{ 2, 0, 1}, 
{ 3, 2, 0}} 
Salida: 4 
Hay 2 discos, el más pequeño está sobre el más grande. 
Transfiere el disco más pequeño de la varilla 1 a la varilla 2. 
El costo de esta transferencia es igual a 1. 
Transfiere el disco más grande de la varilla 1 a la varilla 3. 
El costo de esta transferencia es igual a 2. 
Transfiere el disco más pequeño de la varilla 2 a la varilla. 3. 
El costo de esta transferencia es igual a 1 
El costo mínimo total es igual a 4.
Entrada: N = 3 
costos = { 
{ 0, 1, 2}, 
{ 2, 0, 1}, 
{ 3, 2, 0}} 
Salida: 12 
 

Enfoque: la idea es utilizar la programación dinámica de arriba hacia abajo . 
Digamos que mincost(idx, src, dest) sea el costo mínimo para transferir los discos de índices idx a N de rod src a rod dest . La tercera varilla que no es ni la fuente ni la varilla de destino tendría el valor rem = 6 – (i + j) ya que los números de varilla son 1, 2 y 3 y su suma es 6. Si la primera y la tercera varilla son la fuente y destino respectivamente, entonces la barra auxiliar tendrá un número como 6 – (1 + 3) = 2. 
Ahora divida el problema en sus subproblemas de la siguiente manera: 
 

  • Caso 1: Primero transfiera todos los discos con índice (idx + 1) a N a la barra restante. Ahora transfiera el disco más grande a la barra de destino. Nuevamente transfiera todos los discos de la barra restante a la barra de destino. Este proceso costaría como. 
     

Costo = mincost(idx + 1, src, rem) + costos[src][dest] + mincost(idx + 1, rem, dest) 
 

  •  
  • Caso 2: Primero transfiera todos los discos con índice (idx + 1) a N a la varilla de destino. Ahora transfiera el disco más grande a la barra restante. Nuevamente, transfiera todos los discos de la barra de destino a la barra de origen. Ahora transfiera el disco más grande de la barra restante a la barra de destino. Nuevamente transfiera los discos de la barra de origen a la barra de destino. Este proceso costaría como: 
     

Costo = mincost(idx + 1, src, dest) + costos[src][rem] + mincost(idx + 1, dest, src) + cost[rem][dest] + mincost(idx + 1, src, dest) 
 

  • La respuesta sería igual al mínimo de los dos casos anteriores.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define RODS 3
#define N 3
int dp[N + 1][RODS + 1][RODS + 1];
 
// Function to initialize the dp table
void initialize()
{
 
    // Initialize with maximum value
    for (int i = 0; i <= N; i += 1) {
        for (int j = 1; j <= RODS; j++) {
            for (int k = 1; k <= RODS; k += 1) {
                dp[i][j][k] = INT_MAX;
            }
        }
    }
}
// Function to return the minimum cost
int mincost(int idx, int src, int dest,
            int costs[RODS][RODS])
{
 
    // Base case
    if (idx > N)
        return 0;
 
    // If problem is already solved,
    // return the pre-calculated answer
    if (dp[idx][src][dest] != INT_MAX)
        return dp[idx][src][dest];
 
    // Number of the auxiliary disk
    int rem = 6 - (src + dest);
 
    // Initialize the minimum cost as Infinity
    int ans = INT_MAX;
 
    // Calculationg the cost for first case
    int case1 = costs[src - 1][dest - 1]
                + mincost(idx + 1, src, rem, costs)
                + mincost(idx + 1, rem, dest, costs);
 
    // Calculating the cost for second case
    int case2 = costs[src - 1][rem - 1]
                + mincost(idx + 1, src, dest, costs)
                + mincost(idx + 1, dest, src, costs)
                + costs[rem - 1][dest - 1]
                + mincost(idx + 1, src, dest, costs);
 
    // Minimum of both the above cases
    ans = min(case1, case2);
 
    // Store it in the dp table
    dp[idx][src][dest] = ans;
 
    // Return the minimum cost
    return ans;
}
 
// Driver code
int main()
{
    int costs[RODS][RODS] = { { 0, 1, 2 },
                              { 2, 0, 1 },
                              { 3, 2, 0 } };
    initialize();
    cout << mincost(1, 1, 3, costs);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
static int RODS = 3;
static int N = 3;
static int [][][]dp=new int[N + 1][RODS + 1][RODS + 1];
 
// Function to initialize the dp table
static void initialize()
{
 
    // Initialize with maximum value
    for (int i = 0; i <= N; i += 1)
    {
        for (int j = 1; j <= RODS; j++)
        {
            for (int k = 1; k <= RODS; k += 1)
            {
                dp[i][j][k] = Integer.MAX_VALUE;
            }
        }
    }
}
 
// Function to return the minimum cost
static int mincost(int idx, int src, int dest,int costs[][])
{
 
    // Base case
    if (idx > N)
        return 0;
 
    // If problem is already solved,
    // return the pre-calculated answer
    if (dp[idx][src][dest] != Integer.MAX_VALUE)
        return dp[idx][src][dest];
 
    // Number of the auxiliary disk
    int rem = 6 - (src + dest);
 
    // Initialize the minimum cost as Infinity
    int ans = Integer.MAX_VALUE;
 
    // Calculationg the cost for first case
    int case1 = costs[src - 1][dest - 1]
                + mincost(idx + 1, src, rem, costs)
                + mincost(idx + 1, rem, dest, costs);
 
    // Calculating the cost for second case
    int case2 = costs[src - 1][rem - 1]
                + mincost(idx + 1, src, dest, costs)
                + mincost(idx + 1, dest, src, costs)
                + costs[rem - 1][dest - 1]
                + mincost(idx + 1, src, dest, costs);
 
    // Minimum of both the above cases
    ans = Math.min(case1, case2);
 
    // Store it in the dp table
    dp[idx][src][dest] = ans;
 
    // Return the minimum cost
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
         
    int [][]costs = { { 0, 1, 2 },
                            { 2, 0, 1 },
                            { 3, 2, 0 } };
    initialize();
        System.out.print (mincost(1, 1, 3, costs));
         
}
}
 
// This code is contributed by ajit..23@

Python3

# Python3 implementation of the approach
import numpy as np
import sys
 
RODS = 3
N = 3
dp = np.zeros((N + 1,RODS + 1,RODS + 1));
 
# Function to initialize the dp table
def initialize() :
 
    # Initialize with maximum value
    for i in range(N + 1) :
        for j in range(1, RODS + 1) :
            for k in range(1, RODS + 1) :
                dp[i][j][k] = sys.maxsize;
             
 
# Function to return the minimum cost
def mincost(idx, src, dest, costs) :
 
    # Base case
    if (idx > N) :
        return 0;
 
    # If problem is already solved,
    # return the pre-calculated answer
    if (dp[idx][src][dest] != sys.maxsize) :
        return dp[idx][src][dest];
 
    # Number of the auxiliary disk
    rem = 6 - (src + dest);
 
    # Initialize the minimum cost as Infinity
    ans = sys.maxsize;
 
    # Calculationg the cost for first case
    case1 = costs[src - 1][dest - 1] + mincost(idx + 1, src, rem, costs) + mincost(idx + 1, rem, dest, costs);
 
    # Calculating the cost for second case
    case2 = (costs[src - 1][rem - 1] + mincost(idx + 1, src, dest, costs) + mincost(idx + 1, dest, src, costs) + costs[rem - 1][dest - 1] + mincost(idx + 1, src, dest, costs));
 
    # Minimum of both the above cases
    ans = min(case1, case2);
 
    # Store it in the dp table
    dp[idx][src][dest] = ans;
 
    # Return the minimum cost
    return ans;
 
 
# Driver code
if __name__ == "__main__" :
 
    costs = [ [ 0, 1, 2 ],
            [ 2, 0, 1 ],
            [ 3, 2, 0 ] ];
    initialize();
    print(mincost(1, 1, 3, costs));
 
    # This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
     
class GFG
{
     
static int RODS = 3;
static int N = 3;
static int [,,]dp=new int[N + 1,RODS + 1,RODS + 1];
 
// Function to initialize the dp table
static void initialize()
{
 
    // Initialize with maximum value
    for (int i = 0; i <= N; i += 1)
    {
        for (int j = 1; j <= RODS; j++)
        {
            for (int k = 1; k <= RODS; k += 1)
            {
                dp[i,j,k] = int.MaxValue;
            }
        }
    }
}
 
// Function to return the minimum cost
static int mincost(int idx, int src, int dest,int [,]costs)
{
 
    // Base case
    if (idx > N)
        return 0;
 
    // If problem is already solved,
    // return the pre-calculated answer
    if (dp[idx,src,dest] != int.MaxValue)
        return dp[idx,src,dest];
 
    // Number of the auxiliary disk
    int rem = 6 - (src + dest);
 
    // Initialize the minimum cost as Infinity
    int ans = int.MaxValue;
 
    // Calculationg the cost for first case
    int case1 = costs[src - 1,dest - 1]
                + mincost(idx + 1, src, rem, costs)
                + mincost(idx + 1, rem, dest, costs);
 
    // Calculating the cost for second case
    int case2 = costs[src - 1,rem - 1]
                + mincost(idx + 1, src, dest, costs)
                + mincost(idx + 1, dest, src, costs)
                + costs[rem - 1,dest - 1]
                + mincost(idx + 1, src, dest, costs);
 
    // Minimum of both the above cases
    ans = Math.Min(case1, case2);
 
    // Store it in the dp table
    dp[idx,src,dest] = ans;
 
    // Return the minimum cost
    return ans;
}
 
// Driver code
public static void Main (String[] args)
{
         
    int [,]costs = { { 0, 1, 2 },
                            { 2, 0, 1 },
                            { 3, 2, 0 } };
    initialize();
        Console.WriteLine(mincost(1, 1, 3, costs));
         
}
}
 
/* This code is contributed by PrinciRaj1992 */

Javascript

<script>
    // Javascript implementation of the approach
     
    let RODS = 3;
    let N = 3;
    let dp = new Array(N + 1);
     
 
    // Function to initialize the dp table
    function initialize()
    {
 
        // Initialize with maximum value
        for (let i = 0; i <= N; i += 1)
        {
            dp[i] = new Array(RODS + 1);
            for (let j = 1; j <= RODS; j++)
            {
                dp[i][j] = new Array(RODS + 1);
                for (let k = 1; k <= RODS; k += 1)
                {
                    dp[i][j][k] = Number.MAX_VALUE;
                }
            }
        }
    }
 
    // Function to return the minimum cost
    function mincost(idx, src, dest, costs)
    {
 
        // Base case
        if (idx > N)
            return 0;
 
        // If problem is already solved,
        // return the pre-calculated answer
        if (dp[idx][src][dest] != Number.MAX_VALUE)
            return dp[idx][src][dest];
 
        // Number of the auxiliary disk
        let rem = 6 - (src + dest);
 
        // Initialize the minimum cost as Infinity
        let ans = Number.MAX_VALUE;
 
        // Calculationg the cost for first case
        let case1 = costs[src - 1][dest - 1]
                    + mincost(idx + 1, src, rem, costs)
                    + mincost(idx + 1, rem, dest, costs);
 
        // Calculating the cost for second case
        let case2 = costs[src - 1][rem - 1]
                    + mincost(idx + 1, src, dest, costs)
                    + mincost(idx + 1, dest, src, costs)
                    + costs[rem - 1][dest - 1]
                    + mincost(idx + 1, src, dest, costs);
 
        // Minimum of both the above cases
        ans = Math.min(case1, case2);
 
        // Store it in the dp table
        dp[idx][src][dest] = ans;
 
        // Return the minimum cost
        return ans;
    }
     
    let costs = [ [ 0, 1, 2 ],
                 [ 2, 0, 1 ],
                 [ 3, 2, 0 ] ];
    initialize();
      document.write(mincost(1, 1, 3, costs));
 
// This code is contributed by divyeshrabadiya07.
</script>
Producción: 

12

 

Complejidad temporal: O(N) donde N es el número de discos en una barra determinada.
 

Publicación traducida automáticamente

Artículo escrito por CrazyPro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *