Pas minimum pour gagner Snake Ladder

Ont un coup d'oeil à cette blog, il fait un complète l'analyse mathématique de serpents et Échelles, à l'aide de simulations Monte-Carlo et chaînes de Markov. Il ne le fait montrer un moyen de calculer le nombre minimum d'étapes pour gagner (essentiellement de construire une matrice de transition et de voir comment beaucoup de fois vous devez multiplier le vecteur de départ pour arriver à une solution non nulle position finale). Ce n'est probablement pas le moyen le plus efficace de le faire, mais le post est bien la peine de le lire.

Ici est une solution rapide en python, en utilisant des ensembles. J'ai obtenu des numéros dans le saut-le tableau de l'article du blog. À chaque étape, on calcule simplement tous les postes accessibles à partir de l'étape précédente, et continue de le faire jusqu'à ce que la position finale est entre les accessible positions:

jumps = {1: 38, 4: 14, 9: 31, 21: 42, 28: 84, 36: 44, 51: 67, 71: 91, 80: 100,
  98: 78, 95: 75, 93: 73, 87: 24, 64: 60, 62: 19, 56: 53, 49: 11, 48: 26, 16: 6}
final_pos = 100
positions = {0} #initial position off the board
nsteps = 0

while final_pos not in positions:
    nsteps += 1
    old_positions = positions
    positions = set()
    for pos in old_positions:
        for dice in range(1, 7):
            new_pos = pos + dice
            positions.add(jumps.get(new_pos, new_pos))

print 'Reached finish in %i steps' % nsteps            

Temps d'exécution est négligeable et il crache de la réponse correcte (voir blog) de 7.

J'ai mis en place, dans C#. Vous pouvez consulter mon gist ici. Je vais aussi coller le code ci-dessous.

Dans mon application j'ai examiné les points suivants:

• en évitant les boucles : Ce qui se passe quand un serpent traverse une échelle. Par exemple lors de la fin d'une échelle est à la tête d'un serpent et la queue du serpent est le début de la même échelle. C'est un simple exemple, mais il y a peut être plus complexe boucles.
• prendre de bonnes serpents : j'ai remarqué que vous n'avez pas à éviter tous les serpents. Parfois, vous avez besoin de prendre le serpent, car il vous aide à obtenir à la cible plus rapidement. Je les appelle "les bonnes serpents". Par exemple, 3>60 puis 61>50 51>100 (cible). Si vous prenez le serpent min dés le comte sera 3 et sans le serpent 8.
• facultatives et obligatoires sauts : Lorsque l'option saut est défini à false, l'algorithme doit prendre le saut quand arrive à l'un.

• plus court chemin de sensibilisation : Lorsque l'algorithme devient la cible, il enregistre le chemin le plus court et au cours du calcul, il fera tomber les recherches qui sont plus long que l'actuel trouvé la solution. Qui rend le processus beaucoup plus rapide dans des situations complexes.

  using System;
  using System.Collections.Generic;
  using System.Linq;
  namespace SnakeAndLaddersSolution
  {
    public class SnakeAndLadder
    {
      private struct Jump
     {
       public int Start;
       public int End;
     }
  
     private const int TOP = 100;
     private const int STEP_SIZE = 6;
     private int _minDiceCount = int.MaxValue;
     private readonly List<Jump> _jumps = new List<Jump>();
  
     public bool OptionalJump { get; set; }
  
     public void AddJump(int start, int end)
     {
         _jumps.Add(new Jump { Start = start, End = end });
     }
  
     public int Solve()
     {
         var path = new Stack<int>();
         path.Push(1); //start from square 1
         return FindMinimumDice(path, 0);
     }
  
     private int FindMinimumDice(Stack<int> path, int diceCount)
     {
         if (diceCount >= _minDiceCount)
         {
             //too long. we've already found a shortest path.
             //drop going deeper
             return -1;
         }
         var currentSquare = path.Peek();
         var diceCounts = new List<int>();
         int newDiceCount;
  
         var ignoreNormalJump = false;
  
      for (var i = 0; i <= STEP_SIZE; i++)
      {
          var newSquare = currentSquare + i;
          if (newSquare == TOP)
          {
              //got there
              var totalDiceCount = diceCount + (i == 0 ? 0 : 1);
              _minDiceCount = Math.Min(_minDiceCount, totalDiceCount); //register the shortest path
              return totalDiceCount;
          }
  
  
          if (_jumps.All(j => j.Start != newSquare)) continue; //only process jumps
  
          var jump = _jumps.First(j => j.Start == newSquare);
          if (path.Contains(jump.End))
              continue; //already been here
          path.Push(jump.Start);
          path.Push(jump.End);
          newDiceCount = FindMinimumDice(path, diceCount + (i == 0 ? 0 : 1));
          path.Pop();
          path.Pop();
          if (newDiceCount != -1)
              diceCounts.Add(newDiceCount);
          if (i == 0 && !OptionalJump) //the current squre is a jump that should be taken
          {
              ignoreNormalJump = true;
              break;
          }
      }
      if (!ignoreNormalJump)
      {
          var longestJump = 0;
          for (var i = STEP_SIZE; i > 0; i--)
          {
              if (_jumps.All(j => j.Start != currentSquare + i))
              {
                  longestJump = currentSquare + i;
                  break;
              }
          }
          if (longestJump != 0)
          {
              path.Push(longestJump);
              newDiceCount = FindMinimumDice(path, diceCount + 1);
              path.Pop();
              if (newDiceCount != -1)
                  diceCounts.Add(newDiceCount);
          }
      }
      return !diceCounts.Any() ? -1 : diceCounts.Min();
     }
    }
  
    class Program
    {
  
     static void Main(string[] args)
     {
         var sal = new SnakeAndLadder();
         //set OptionalJump to true if the jump is optional
         //sal.OptionalJump = true;
         sal.AddJump(10,60);
         sal.AddJump(51,100);
         Console.WriteLine(sal.Solve());
         Console.ReadLine();
     }
    }
    }
  

Solution en C# en o(n).

Construire une aide de la matrice d'aller au cours de chaque étape et de voir ce qui est le minimum pour y arriver et ajoutez une.

const int BoardSize = 100;
const int MaxStep = 6;
static void Main()
{

    //- means a ledder ending at the pos
    //+ means a snake (taking you back n steps)
    int[] arr = new int[] {     
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,      8,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -71,    -1,     -1      };

    Console.WriteLine("Steps needed: " + solve(arr));
}

public static int solve(int[] inArr)
{
    int[] arr = new int[BoardSize];

    arr[0] = 1;

    for (int i = 0; i < BoardSize; ++i)
    {
        //steps here is the minimum of all the positions in all the previos 6 cells +1
        if (i < MaxStep)
            arr[i] = 1;
        else
        {
            int extraOption = int.MaxValue;
            if (inArr[i] < -1 || inArr[i] > 0)
                extraOption = arr[i + inArr[i]];
            else if (inArr[i] > 0)
                extraOption = arr[i + inArr[i]];
            arr[i] = min(arr[i - 1], arr[i - 2], arr[i - 3], arr[i - 4], arr[i - 5], arr[i - 6], extraOption) + 1;
        }
    }

    for (int i = 0; i < BoardSize; ++i)
    {
        Console.Write(arr[i] + "\t");
        if ((i + 1) % 10 == 0)
            Console.WriteLine("");
    }

    return arr[arr.Length-1];
}

public static int min(int a, int b, int c, int d, int e, int f, int g)
{
    int ab = Math.Min(a,b);
    int cd = Math.Min(c,d);
    int ef = Math.Min(e,f);
    return Math.Min(Math.Min(ab, cd), Math.Min(ef,g));
}

1. Considérer chacun comme un sommet dans le graphe orienté.
   2.À partir de la cellule 1, vous pouvez goto cellules 2, 3, 4, 5, 6, 7 donc vertex 1 aura dirigé bord vers le vertex 2, vertex 3....vertex 7. De même pris en compte pour le repos des cellules.
2. De serpent - connect dirigé bord de la tête de serpent vertex à la queue de serpent sommet.
3. Pour échelle - se connecter dirigé bord du bas de l'échelle, sommet de sommet de l'échelle de vertex.
   1. Maintenant le problème est réduit à un court-circuit problème de chemin d'accès.Par la Largeur de la Première Recherche (à l'aide de la file d'attente), nous pouvons résoudre le problème.

Voir le code complet de la solution ici - https://algorithms.tutorialhorizon.com/snake-and-ladder-problem/