2

ツリートラバーサルのアルゴリズムを考え出そうとしていますが、行き詰まっています。

これは（私が尋ねた他の人と比較して）かなり難しい質問なので、私は自分で考え続ける必要があるかもしれません。しかし、私はそれをここに捨てると思いました。

私は次のクラス構造を持っています：

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ステートメントに対して一度に1つずつ提供する方法を用意する必要があります。

私は以前にyield1を使用したことがあるので、それを理解できると思います。しかし、最短経路を見つけると同時に（関数で毎回再計算せずに）それを行う方法がわかりませんか？

これまで読んだことがあるなら、ありがとう。あなたが答えを提供するならば、それから二重の感謝。

4

2 に答える 2

6

yield最短経路を計算し、プロセス全体が完了した後に各経路セグメントを ing しないと、効率的にそれを行うことはできません。最短経路問題の性質は、そのような部分解を効率的に計算するアルゴリズムには向いていません。

遷移グラフは重み付けされていないため、単純に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
}
于 2010-02-10T23:53:47.187 に答える
4

If you need to find the shortest path from a node to a descendent node in an acyclic tree, then Mehrdad's solution is a good one. That is, first do a breadth-first-search until you find the destination node, and then work out the path from the start node to the destination.

If your graph is not an (acyclic) tree, but rather an arbitrary weighted graph, then naive breadth-first-search does not work. Either it goes into infinite loops (if you're not clever about keeping track of when you've seen a node already), or it is not guaranteed to find the least-weight path.

If you're in that situation then a good algorithm to use is the famous "A*" algorithm. I've got some notes on how to implement A* in C# here:

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

This is particularly useful if you have an "estimating function" that can make guesses about what the most likely next node on the shortest path is.

于 2010-02-11T00:29:46.373 に答える