Кратчайший путь в результирующем ациклическом графике

Question

Мне задана строка символов, в которой каждая последующая пара символов содержит ребро. Я имею в виду, что это строка: ABBCAD. Края строки являются:

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

Наименьшее расстояние пробега A-> D

Задача под рукой, чтобы построить ориентированный ациклический граф в памяти из строки, используя описанную выше правило и найти самый короткий путь, смотрящий на корневой узел (в примере с меткой A), заканчивающийся на терминальном узле.

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

Я собираю один из подходов, Suítes задача заключается в использовании Depth First Search Algo.

Это не домашнее задание ...

Answer 1

Это работа для Djikstra's Algorithm. Как только вы создадите представление своего графика, оно должно быть достаточно простым, чтобы произвести самый дешевый обход ... поскольку в вашем случае кажется, что все пути имеют равную стоимость (1).

Вы можете look here on CodeProject для разумно достойной реализации Djikstra в C#.

Можете ли вы представить мне псевдокод вашей версии графического представления для этого случая?

Существует множество способов представления графика в такой проблеме. Если число вершин на вашем графике может быть небольшим, достаточно было бы использовать adjacency matrix для представления ребер. В этом случае вы можете просто использовать .NET multidimensional array. Трюк здесь в том, что вам нужно преобразовать вершины, помеченные символами, в порядковые значения. Один подход должен был бы написать класс-оболочку, которая отображает коды символов с индексами в матрицу смежности:

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

ответ LBushkin является правильным. Эрик Липперт имеет a series о внедрении A* algorithm в C#. A * - более общий случай алгоритма Дейкстры: если ваша функция оценки стоимости всегда возвращает 0, она в точности эквивалентна Dijkstra.

Answer 3

Для этого конкретного случая Dijkstra's может быть значительно упрощен. Я предполагаю, что что-то подобное сделает трюк.

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

Другим вариантом было бы использовать библиотеку графов с различными алгоритмами кратчайшего пути. Один из тех, что я использовал в прошлом, и нашел, что это хорошо, - QuickGraph. Документация неплохая. Например, here is a page в документации, в которой объясняется, как использовать алгоритм Дейкстры.

Answer 5

Только для записи. Это ваш график пример:

Где кратчайший путь от А до М отмечен синим цветом.

Это очень короткая программа в 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

Поскольку ваш граф ациклический алгоритм Витерби можно использовать, посетить государства в топологическом порядке и обновлять затраты в предшествующих вершин (состояний).

В приведенном ниже коде реализованы алгоритм поиска и структура данных. Я не был на 100% уверен в определении действительного в соответствии с исходным вопросом. Но нужно прямо изменить код для построения других топологий и решить различные задачи динамического программирования с помощью DAG.

Изменение внешнего контура при вычислении потенциалов состояния для цикла while с очередью позволит использовать различные алгоритмы кратчайшего пути, которые могут быть легко изменены путем изменения дисциплины в очереди. Например, двоичная очередь на основе кучи даст алгоритм Дейкстры или очередь FIFO - алгоритм Беллмана-Форда.

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);   
     } 
    } 
    } 
}