产生状态转换中的最短路径

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,所以我想我可以搞清楚.但我不知道如何在找到最短路径的同时做到这一点(每次在func中重新计算)？

如果您已经读过这篇文章,谢谢.如果你提供答案,那么双重感谢.

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
}