c# - 在状态转换中产生最短路径

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# 的 yield 特性为 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
}