Выход кратчайшего пути в государственных переходах

Question

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

Это довольно сложный вопрос (по сравнению с другими, которые я задавал), поэтому мне, возможно, придется продолжать самостоятельно разбираться. Но я думал, что выкину это сюда.

У меня следующая структура класса:

public class Transition
{
    // The state we are moving from.
    public String From { get; set; }
    // All the To states for this from
    public List<String>To { get; set; }
}

List<Transition> currentTransistions;

Когда currentTransistions полностью заполнен, это выглядит так (для меня):

<?xml version="1.0" encoding="utf-8"?>
<ArrayOfTransition xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <Transition>
    <From />
    <To>
      <string>Not Done</string>
    </To>
  </Transition>
  <Transition>
    <From>Not Done</From>
    <To>
      <string>In Progress</string>
      <string>Deleted</string>
    </To>
  </Transition>
  <Transition>
    <From>Deleted</From>
    <To>
      <string>Not Done</string>
    </To>
  </Transition>
  <Transition>
    <From>In Progress</From>
    <To>
      <string>Done</string>
      <string>Ready For Test</string>
      <string>Deleted</string>
    </To>
  </Transition>
  <Transition>
    <From>Done</From>
    <To>
      <string>In Progress</string>
    </To>
  </Transition>
  <Transition>
    <From>Ready For Test</From>
    <To>
      <string>In Progress</string>
      <string>Done</string>
      <string>Deleted</string>
    </To>
  </Transition>
</ArrayOfTransition>

Идея в том, что я сопоставил переходы состояний для рабочих элементов TFS. Теперь мне нужен способ сказать: «Учитывая текущее состояние, как мне добраться до другого состояния».

В идеале это будет выглядеть так:

 foreach (string state in GetToFinalState(finalState, currentState, currentTransistions)
 {
     // Save the workitem at the state so we can get to the final state.
 }

GetToFinalState должен был бы иметь возможность рассчитать кратчайший путь и использовать функцию выхода C #, чтобы предлагать их по одному для оператора foreach.

Я раньше использовал yield one, поэтому думаю, что смогу это выяснить. Но я не уверен, как это сделать одновременно с поиском кратчайшего пути (без пересчета каждый раз в функции)?

Если вы прочитали это далеко, спасибо. Если вы предлагаете ответ, то двойное спасибо.

Answer 1

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

Поскольку граф переходов не взвешен, вы можете просто запустить на нем BFS , чтобы вычислить кратчайший путь. Вам нужно сделать что-то вроде этого (я не уверен в свойствах объекта TFS, так что это просто псевдокод):

IEnumerable<string> ShortestPath(string fromState, string toState, Transition[] currentTransitions) {
    var map = new Dictionary<string, string>();
    var edges = currentTransitions.ToDictionary(i => i.From, i => i.To);
    var q = new Queue<string>(); 
    map.Add(fromState, null);
    q.Enqueue(fromState);
    while (q.Count > 0) {
        var current = q.Dequeue();
        foreach (var s in edges[current]) {
            if (!map.ContainsKey(s)) {
                map.Add(s, current);
                if (s == toState) {
                    var result = new Stack<string>();
                    var thisNode = s;
                    do {
                        result.Push(thisNode);
                        thisNode = map[thisNode];
                    } while (thisNode != fromState);
                    while (result.Count > 0)
                        yield return result.Pop();
                    yield break;
                }
                q.Enqueue(s);
            }
        }
    }
    // no path exists
}

Answer 2

Если вам нужно найти кратчайший путь от узла к дочернему узлу в ациклическом дереве, то решение Мерадада является хорошим. То есть сначала выполняйте поиск в ширину, пока не найдете узел назначения, а затем определите путь от начального узла до места назначения.

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

Если вы находитесь в такой ситуации, то хорошим алгоритмом является известный алгоритм «A *». У меня есть некоторые заметки о том, как реализовать A * в C # здесь:

http://blogs.msdn.com/ericlippert/archive/tags/AStar/default.aspx

Это особенно полезно, если у вас есть «оценочная функция», которая может угадать, каков наиболее вероятный следующий узел на кратчайшем пути.