Le plus court chemin dans le graphique acyclique dirigé

Question

On me donne une chaîne de caractères, dans laquelle chaque paire de caractères conséquente comprend un bord. Ce que je veux dire par là est la chaîne: ABBCAD. Les bords de la chaîne sont:

A->B 
B->C 
A->D 

distance de chemin Shortest est A-> D

La tâche est de construire un graphe acyclique orienté dans la mémoire de la chaîne en utilisant la règle ci-dessus et trouver le plus court chemin fixant le nœud racine (dans l'exemple donné, c'est une étiquette) se terminant au nœud terminal.

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

Je crois l'une des approches que les suites de la tâche est d'utiliser la profondeur de recherche d'abord algo.

Ce n'est pas devoirs ...

Answer 1

Ceci est un emploi pour Djikstra's Algorithm. Une fois que vous avez construit une représentation de votre graphique, il devrait être assez facile de produire la traversée de coût la plus faible ... puisque dans votre cas, il semble que tous les chemins ont un coût égal (1).

Vous pouvez look here on CodeProject pour une implémentation raisonnablement décente de Djikstra en C#.

pourriez-vous me présenter un pseudo code de votre version de la représentation graphique pour ce cas?

Il existe plusieurs façons de représenter un graphique dans un tel problème. Si le nombre de sommets dans votre graphique est susceptible d'être petit - il suffira d'utiliser un adjacency matrix pour la représentation des arêtes. Dans ce cas, vous pouvez simplement utiliser un .NET multidimensional array. L'astuce ici est que vous devez convertir les sommets étiquetés avec des caractères en valeurs ordinales. Une approche serait d'écrire une classe wrapper qui associe les codes de caractères à des indices dans la matrice de contiguïté:

class AdjacencyMatrix 
{ 
    // representation of the adjacency matrix (AM) 
    private readonly int[,] m_Matrix; 
    // mapping of character codes to indices in the AM 
    private readonly Dictionary<char,int> m_Mapping; 

    public AdjacencyMatrix(string edgeVector) 
    { 
     // using LINQ we can identify and order the distinct characters 
     char[] distinctChars = edgeVector.Distinct().OrderBy(x => x); 

     m_Mapping = distinctChars.Select((c,i)=>new { Vertex = c, Index = i }) 
           .ToDictionary(x=>x.Vertex, x=>x.Index); 

     // build the adjacency cost matrix here... 
     // TODO: I leave this up to the reader to complete ... :-D 
    } 

    // retrieves an entry from within the adjacency matrix given two characters 
    public int this[char v1, char v2] 
    { 
     get { return m_Matrix[m_Mapping[v1], m_Mapping[v2]]; 
     private set { m_Matrix[m_Mapping[v1], m_Mapping[v2]] = value; } 
    } 
} 

Answer 2

réponse de LBushkin est correcte. Eric Lippert a a series sur la mise en œuvre du A* algorithm en C#. A * est un cas plus général de l'algorithme de Dijkstra: si votre fonction d'estimation des coûts retourne toujours 0, elle est exactement équivalente à Dijkstra.

Answer 3

Pour ce cas particulier, Dijkstra pourrait être grandement simplifié. J'imagine que quelque chose comme ça ferait l'affaire.

class Node { 
    public object Value; 

    // Connected nodes (directed) 
    public Node[] Connections; 

    // Path back to the start 
    public Node Route; 
} 

Node BreadthFirstRoute(Node[] theStarts, Node[] theEnds) { 
    Set<Node> visited = new Set<Node>(); 

    Set<Node> frontier = new Set<Node>(); 
    frontier.AddRange(theStarts); 

    Set<Node> ends = new Set<Node>(); 
    ends.AddRange(theEnds); 

    // Visit nodes one frontier at a time - Breadth first. 
    while (frontier.Count > 0) { 

     // Move frontier into visiting, reset frontier. 
     Set<Node> visiting = frontier; 
     frontier = new Set<Node>(); 

     // Prevent adding nodes being visited to frontier 
     visited.AddRange(visiting); 

     // Add all connected nodes to frontier. 
     foreach (Node node in visiting) {    
      foreach (Node other in node.Connections) { 
       if (!visited.Contains(other)) { 
        other.Route = other; 
        if (ends.Contains(other)) { 
         return other; 
        } 
        frontier.Add(other); 
       } 
      } 
     } 
    } 

    return null; 
} 

Answer 4

Une autre option consisterait à utiliser une bibliothèque de graphes ayant divers algorithmes de chemin le plus court implémentés. Un que j'ai utilisé dans le passé et trouvé pour être bon est QuickGraph. La documentation est assez bonne. Par exemple, here is a page dans la documentation qui explique comment utiliser l'algorithme de Dijkstra.

Answer 5

Juste pour l'enregistrement. Ceci est votre exemple graphique:

Lorsque le chemin le plus court de A à M est marqué en bleu.

Il est un programme très court Mathematica:

a = StringSplit["NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM", ""] 
b = Table[a[[i]] -> a[[i + 1]], {i, Length@a - 1}] 
vertexNumber[g_, vName_] := Position[ Vertices[g, All], vName][[1, 1]]; 
Needs["Combinatorica`"] 

c  = ToCombinatoricaGraph[b] 
sp = ShortestPath[c, vertexNumber[c, "A"], vertexNumber[c, "M"]] 
vlsp = GetVertexLabels[c, sp] 
vlspt = Table[{vlsp[[i]], vlsp[[i + 1]]}, {i, Length@vlsp - 1}] 

GraphPlot[b, VertexLabeling -> True, ImageSize -> 250, 
     DirectedEdges -> True, Method -> {"SpringEmbedding"}, 
     EdgeRenderingFunction -> 
      (If[Cases[vlspt, {First[#2], Last[#2]}] == {}, 
       {Red, Arrowheads[Medium], Arrow[#1, .1]}, 
       {Blue, Arrowheads[Medium], Arrow[#1, .1]}] &)] 

Answer 6

Parce que votre graphe est acyclique l'algorithme de Viterbi peut être utilisé, consultez les états pour topologique et mettre à jour les coûts dans les sommets précédents (états).

Le code ci-dessous implémente l'algorithme de recherche et la structure de données. Je n'étais pas sûr à 100% de la définition de la validité basée sur la question originale. Mais il devrait être simple de modifier le code pour construire d'autres topologies et résoudre diverses tâches de programmation dynamique à l'aide d'un DAG. Si vous modifiez la boucle for externe lorsque vous calculez les potentiels d'état sur while avec une file d'attente, vous pouvez facilement modifier différents algorithmes de raccourci en modifiant la discipline de la file d'attente. Par exemple, une file d'attente basée sur le tas binaire donnera l'algorithme de Dijkstra ou une file d'attente FIFO sera l'algorithme de Bellman-Ford.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace DAGShortestPath 
{ 
    class Arc 
    { 
    public Arc(int nextstate, float cost) 
    { 
     Nextstate = nextstate; 
     Cost = cost; 
    } 
    public int Nextstate { get; set; } 
    public float Cost { get; set; } 
    }; 

    class State 
    { 
    public bool Final { get; set; } 
    public List<Arc> Arcs { get; set; } 

    public void AddArc(int nextstate, float cost) 
    { 
     if (Arcs == null) 
     Arcs = new List<Arc>(); 
     Arcs.Add(new Arc(nextstate, cost)); 
    } 
    } 
    class Graph 
    { 
    List<State> _states = new List<State>(); 
    int _start = -1; 

    public void AddArc(int state, int nextstate, float cost) 
    { 
     while (_states.Count <= state) 
     AddState(); 
     while (_states.Count <= nextstate) 
     AddState(); 
     _states[state].AddArc(nextstate, cost); 
    } 

    public List<Arc> Arcs(int state) 
    { 
     return _states[state].Arcs; 
    } 

    public int AddState() 
    { 
     _states.Add(new State()); 
     return _states.Count - 1; 
    } 

    public bool IsFinal(int state) 
    { 
     return _states[state].Final; 
    } 

    public void SetFinal(int state) 
    { 
     _states[state].Final = true; 
    } 

    public void SetStart(int start) 
    { 
     _start = -1; 
    } 

    public int NumStates { get { return _states.Count; } } 

    public void Print() 
    { 
     for (int i = 0; i < _states.Count; i++) 
     { 
     var arcs = _states[i].Arcs; 
     for (int j = 0; j < arcs.Count; j++) 
     { 
      var arc = arcs[j];   
      Console.WriteLine("{0}\t{1}\t{2}", i, j, arc.Cost); 
     } 
     } 
    } 
    } 

    class Program 
    { 
    static List<int> ShortertPath(Graph graph) 
    { 
     float[] d = new float[graph.NumStates]; 
     int[] tb = new int[graph.NumStates]; 
     for (int i = 0; i < d.Length; i++) 
     { 
     d[i] = float.PositiveInfinity; 
     tb[i] = -1; 
     }  
     d[0] = 0.0f; 
     float bestscore = float.PositiveInfinity; 
     int beststate = -1; 

     for (int i = 0; i < graph.NumStates; i++) 
     { 
     if (graph.Arcs(i) != null) 
     { 
      foreach (var arc in graph.Arcs(i)) 
      { 
      if (arc.Nextstate < i) 
       throw new Exception("Graph is not topologically sorted"); 

      float e = d[i] + arc.Cost; 
      if (e < d[arc.Nextstate]) 
      { 
       d[arc.Nextstate] = e; 
       tb[arc.Nextstate] = i; 

       if (graph.IsFinal(arc.Nextstate) && e < bestscore) 
       { 
       bestscore = e; 
       beststate = arc.Nextstate; 
       } 
      } 
      } 
     } 
     } 

     //Traceback and recover the best final sequence 

     if (bestscore == float.NegativeInfinity) 
     throw new Exception("No valid terminal state found"); 
     Console.WriteLine("Best state {0} and score {1}", beststate, bestscore); 
     List<int> best = new List<int>(); 
     while (beststate != -1) 
     { 
     best.Add(beststate); 
     beststate = tb[beststate]; 
     } 

     return best; 
    } 

    static void Main(string[] args) 
    { 
     Graph g = new Graph(); 
     String input = "ABBCAD";  
     for (int i = 0; i < input.Length - 1; i++) 
     for (int j = i + 1; j < input.Length; j++) 
     { 
      //Modify this of different constraints on-the arcs 
      //or graph topologies 
      //if (input[i] < input[j]) 
      g.AddArc(i, j, 1.0f); 
     } 
     g.SetStart(0); 
     //Modify this to make all states final for example 
     //To compute longest sub-sequences and so on... 
     g.SetFinal(g.NumStates - 1); 
     var bestpath = ShortertPath(g); 

     //Print the best state sequence in reverse 
     foreach (var v in bestpath) 
     { 
     Console.WriteLine(v);   
     } 
    } 
    } 
}