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

Question

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

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

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

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

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

Я понимаю, что один из подходов, который подходит для этой задачи, заключается в использовании алгоритма поиска в глубину.

Это не домашняя работа ...

Answer 1

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

Вы можете посмотреть здесь на CodeProject , чтобы получить достаточно приличную реализацию Djikstra в C #.

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

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

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

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

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 3

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

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

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

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

Answer 5

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

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

Изменение внешнего цикла for при вычислении потенциалов состояния на цикл 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);        
      }
    }
  }
}

Answer 6

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