2個節點碰撞的時間

我們得到了一個N節點圖。(1-N)，其中每個節點都有1指向某個節點的精確定向邊（該節點可以是同一個節點）。

我們需要回答: 型別的查詢A, B，它詢問兩個物件碰撞所需的時間，如果一個從 開始，A另一個從 開始B。兩個動作都1以1秒為單位。如果他們不可能發生碰撞，時間將是-1.

時間：從X-> 到Y：1 跳 = 1 秒。

約束：

N, Q <= 10^5 (number of nodes, number of queries).

示例：對于給定的圖形

   A -> B -> C -> D -> E
                  ^    |
                  K <- F

Query(A, E) : 3 seconds, as at time t = 3 secs they both will be on node D.
Query(C, D) : -1 seconds, as they will never collide.

回答每個查詢的最佳方式是什么？

蠻力方法：時間 - O(Q * N)

使用二元提升技術改進的解決方案：時間 -O(Q * log(N))

private static int[] collisionTime(int N, int Q, int[] A, int[][] queries) {

    // ancestor matrix : creation time- O(n * log(n))
    int M = (int) (Math.ceil(Math.log10(N) / Math.log10(2)))   1;
    int[][] ancestor = new int[N   1][M];
    for(int i = 1; i <= N; i  ) {
        ancestor[i][0] = A[i]; // 2^0-th ancestor. 
    }
    for(int j = 1; j < M; j  ) {
        for(int i = 1; i <= N; i  ) {
            ancestor[i][j] = ancestor[ancestor[i][j-1]][j-1];
        }
    }

    int[] answer = new int[Q];
    for(int i = 0; i < Q; i  ) { 
        int u = queries[i][0];
        int v = queries[i][1];
        answer[i] = timeToCollide(u, v, ancestor);
    }

    return answer;
}

// using binary lifting: time- O(log(n))
private static int timeToCollide(int u, int v, int[][] ancestor) {
    int m = ancestor[0].length;

    // edge cases
    if(u == v)                              // already in collision state
        return 0;              
    if(ancestor[u][m-1] != ancestor[v][m-1]) // their top most ancestor is not the same means they cannot collide at all.
        return -1;

    int t = 0;
    for(int j = m - 1; j >=0; j--) {
        if(ancestor[u][j] != ancestor[v][j]) {
            u = ancestor[u][j];
            v = ancestor[v][j];
            t  = Math.pow(2, j);
        }
    }
    return t   1;
}

uj5u.com熱心網友回復：

只有在有 1 個以上鏈接的節點上才會發生沖突。您的示例中的節點 D。

讓我們稱這些節點為“崩潰站點”

因此，您可以將圖形修剪為僅崩潰站點節點。通向崩潰站點節點的節點成為崩潰站點節點的屬性。

像這樣為你的例子：

D : { A,B,C }, { E,F,K }

只有當起始節點位于同一崩潰站點節點的兩個不同屬性串列上時，才會發生沖突。

一旦確定可能發生崩潰，您就可以檢查兩個起始節點與崩潰地點的距離是否相同。

演算法：

Prune graph to crash site nodes
LOOP over questions
Get 2 start nodes
LOOP over crash sites
   IF start nodes on two different attributes of crash site
        IF start nodes are equi-distant from crash site
             report crash time
             BREAK from crash site loop

這是一個隨機生成的圖，有 50 個節點，其中每個節點都有一個外邊連接到另一個隨機選擇的節點

碰撞地點是

5 7 8 9 10 11 18 19 23 25 31 33 36 37 39

所以演算法最多只需要回圈15個節點，而不是50個。

“兩個特定節點會發生碰撞嗎？”這個問題的答案 幾乎總是“不”。這樣有點無聊。所以讓我們問一個稍微不同的問題：“對于一個特定的圖，哪對節點會導致碰撞？” 這需要相同的演算法（應用于每對節點），但總是會產生一個有趣的答案。

對于這個圖

I get this answer

0 and 29 collide at 41
1 and 5 collide at 40
2 and 23 collide at 13
8 and 16 collide at 34
8 and 22 collide at 34
8 and 39 collide at 34
9 and 30 collide at 37
10 and 31 collide at 25
11 and 47 collide at 23
12 and 28 collide at 25
12 and 35 collide at 25
12 and 49 collide at 25
13 and 38 collide at 27
14 and 44 collide at 1
15 and 17 collide at 0
15 and 18 collide at 0
15 and 37 collide at 0
16 and 22 collide at 34
16 and 39 collide at 34
17 and 18 collide at 0
17 and 37 collide at 0
18 and 37 collide at 0
20 and 26 collide at 9
20 and 42 collide at 9
20 and 43 collide at 9
21 and 45 collide at 24
22 and 39 collide at 34
25 and 34 collide at 3
26 and 42 collide at 9
26 and 43 collide at 9
28 and 35 collide at 25
28 and 49 collide at 25
32 and 48 collide at 34
33 and 36 collide at 7
35 and 49 collide at 25
42 and 43 collide at 9

Some timing results

Notes:

• The mean time for a question is the average of checking every possible pair of nodes for a possible collision.
• Answering a single question is extremely fast, about 20 nanoseconds for moderately sized graphs ( < 10,000 nodes ) [ A previous timing report included outputting the results when a collision was found, which takes much longer than detecting the collision. These results were taken with all output to the console commented out. ]
• Setting up the crash sites and their tributaries gets slow with moderately sized graphs ( > 5,000 nodes ). It is only worth doing if a lot of questions are going to be asked.

此代碼可在https://github.com/JamesBremner/PathFinder 獲得

uj5u.com熱心網友回復：

1. 找出所有終止回圈并指定每個終止回圈中的任意頂點作為回圈根（O（N））
2. 對于每個頂點，記錄其終止回圈的長度、進入終止回圈的距離以及到終止回圈根的距離 (O(N))。
3. 切斷每個回圈根的傳出鏈接。這將圖形變成了森林。
4. 對于每個查詢，找到此林中兩個查詢節點的最近（最低）共同祖先。
5. 從保存的每個查詢節點和最低共同祖先的資訊中，您可以計算出恒定時間內發生碰撞的時間。

步驟 (4)，即最低公共祖先查詢，是一個經過充分研究的問題。最好的演算法只需要線性處理時間并提供恒定的查詢時間，導致這個問題的時間復雜度為 O(N Q)。

uj5u.com熱心網友回復：

我相信以下方法在技術上實作了O(N Q)時間復雜度。

public static int[] collisionTime(int N, int Q, int[] A, int[,] queries)
{
    // create the graph and fill-in the mapping attributes for all nodes
    var graph = new MPDGraph(A);
    graph.MapAllNodes();

    int[] answers = new int[queries.GetLength(0)];
    for (int i = 0; i < answers.Length; i  )
    {
        answers[i] = graph.FindCollision(queries[i, 0], queries[i, 1]);
    }

    return answers;
}

這使用了以下類，

MPDGraph 類：

// MPDG: Mono-Pointing, Directed Graph 
//  An MPDG is a directed graph where every node has exactly one out-edge.
//  (MPDG is my own term, I don't know the real name for these)
class MPDGraph
{
    public Node[] Nodes;
    Dictionary<(Node, Node), int> cachedDistances = new Dictionary<(Node, Node), int>();

    // constructor
    public MPDGraph(int[] Pointers)
    {
        Nodes = new Node[Pointers.Length];

        // first fill the array with objects
        for (int i = 0; i < Nodes.Length; i  ) { Nodes[i] = new Node(i); }

        // apply their pointers
        for(int i = 0; i < Nodes.Length; i  ) { Nodes[i].toNode = Nodes[Pointers[i]]; }
    }


    // map all of the nodes by filling their mapping properties
    public void MapAllNodes()
    {
        for(int i=0; i<Nodes.Length; i  )
        {
            if (!Nodes[i].isMapped)
                MapPath(Nodes[i], 1);
        }
    }

    // recursively map a path of unmapped nodes, starting from curr
    //  returns true if curr is in a cycle, false otherwise
    public Boolean MapPath(Node curr, int pathNo)
    {
        Boolean inCycle = false;
        curr.pathNo = pathNo;

        Node next = curr.toNode;

        if (next.IsInPath)
        {
            // we have found a new cycle
            Cycle Cycle = new Cycle(this, next, curr.pathNo - next.pathNo   1);
            curr.Map(Cycle);
            return true;
        }
        else if (next.isMapped)
        {
            // we are joining an already partially mapped tree
            if (next.IsInCycle)
            {
                // next is a tree-Base, the top of our tree and also in the cycle
                curr.Map(next.Cycle, false, next, 1);
            }
            else
            {
                // next is a normal tree-node
                curr.Map(next.Cycle, false, next.BaseNode, next.Distance   1);
            }
            return false;
        }
        else
        {
            // continue forward on the path, recurse to the next node
            inCycle = MapPath(next, pathNo 1);

            if (inCycle)
            {
                if (next.Cycle.Base == next || next.Distance == 0)
                {
                    //we have returned from the cycleBase, which is also a treeBase
                    // so, switch from Cycle to Tree
                    curr.Map(next.Cycle, false, next, 1);
                    return false;
                }
                else
                {
                    // still in the cycle
                    curr.Map(next.Cycle);
                }
            }
            else
            {
                //returned in tree
                curr.Map(next.Cycle, false, next.BaseNode, next.Distance   1);
            }

            return inCycle;
        }

    }


    // Given two starting nodes, determine how many steps it takes until their
    //  paths collide. Returns -1 if they will never collide.
    public int FindCollision(int index1, int index2)
    {
        Node node1 = Nodes[index1];
        Node node2 = Nodes[index2];

        // eliminate trivial cases
        if (node1.Cycle != node2.Cycle)
            return -1;      // cant collide if they're in different subgraphs
        else if (node1 == node2)
            return 0;       // if they're the same node, then distance = 0
        else if (node1.IsInCycle && node2.IsInCycle)
            return -1;      // different nodes in a cycle never collide
        
        else
        {  // they're both in the same subgraph, use math to tell if they collide

            // get their distances to the cycle base
            int dist1 = node1.Distance   (node1.IsInCycle ? 0 : node1.BaseNode.Distance);
            int dist2 = node2.Distance   (node2.IsInCycle ? 0 : node2.BaseNode.Distance);
            int cycleLen = node1.Cycle.Length;

            // use math:  modulo(cycle length)
            if ((dist1 % cycleLen) != (dist2 % cycleLen))
            {
                return -1;      // incompatible distances: cannot possibly collide
            }
            else
            {
                // they must collide somewhere, figure out how far that is
                if (node1.IsInCycle || node2.IsInCycle)
                {
                    // if one is in the cycle, they will collide when
                    // the other one reaches the cycle (it's treeBase)
                    return (!node1.IsInCycle ? node1.Distance : node2.Distance);
                }
                else if (node1.BaseNode != node2.BaseNode)
                {
                    // They are in different trees:  they will collide at
                    //  the treeBase of the node that is farther
                    return Math.Max(node1.Distance, node2.Distance);
                }
                else
                {
                    // They are in the same tree:
                    if (node1.Distance != node2.Distance)
                    {
                        //if they are in the same tree, but have different distances
                        //  to the treeBase, then they will collide at the treeBase
                        //  when the farther one arrives at the treeBase
                        return Math.Max(node1.Distance, node2.Distance);
                    }
                    else
                    {
                        //  the hard case, have to walk down their paths
                        //  to find their LCA (Lowest Common Ancestor)
                        return findTreeDistance(node1, node2);
                    }
                }
            }
        }
    }


    int findTreeDistance(Node node1, Node node2)
    {
        if (node1 == node2) return 0;

        // normalize their order
        if (node1.index > node2.index)
        {
            var tmp = node1;
            node1 = node2;
            node2 = tmp;
        }

        // check the cache
        int dist;
        if (cachedDistances.ContainsKey((node1,node2)))
        {
            dist = cachedDistances[(node1, node2)];
        }
        else
        {
            // keep recursing to find where they meet
            dist = findTreeDistance(node1.toNode, node2.toNode)   1;
            // cache this new distance
            cachedDistances.Add((node1, node2), dist);
        }
        return dist;
    }
}

節點類：

// Represents a node in the MPDG (Mono-Pointing Directed Graph) with the constraint
//  that all nodes have exactly one out-edge ("toNode").
class Node
{
    // Primary properties (from input)
    public int index { get; set; }      // this node's unique index (to the original array)
    public Node toNode { get; set; }    // what our single out-edge is pointing to


    public Node(int Index_) { this.index = Index_; }


    // Mapping properties
    // (these must be filled-in to finish mapping the node)

    //  The unique cycle of this node's subgraph (all MPDG-subgraphs have exactly one)
    public Cycle Cycle;

    //  Every node is either in their subgraphs cycle or in one of the inverted
    // trees whose apex (base) is attached to it.  Only valid when BaseNode is set.
    // (tree base nodes are counted as being in the cycle)
    public Boolean IsInCycle = false;

    // The base node of the tree or cycle that this node is in.
    //  If (IsInCycle) then it points to this cycle's base node (cycleBase)
    //  Else it points to base node of this node's tree (treeBase)
    public Node BaseNode;

    //  The distance (hops) from this node to the BaseNode
    public int Distance = -1;    // -1 if not yet mapped

    // Total distance from this node to the cycleBase
    public int TotalDistance { get { return Distance   (IsInCycle ? 0 : BaseNode.Distance); } }


    // housekeeping for mapping nodes
    public int pathNo = -1;          // order in our working path

    // Derived (implicit) properties
    public Boolean isMapped { get { return Cycle != null; } }
    public Boolean IsInPath { get { return (pathNo >= 0); } }


    public void Map(Cycle Cycle, bool InCycle = true, Node BaseNode = null, int distance_ = -1)
    {
        this.Cycle = Cycle; 
        IsInCycle = InCycle;

        if (InCycle)
        {
            this.BaseNode = Cycle.Base;
            Distance = (Cycle.Length   (Cycle.Base.pathNo - pathNo)) % Cycle.Length;
        }
        else
        {
            this.BaseNode = BaseNode;
            Distance = distance_;
        }

        pathNo = -1;    // clean-up the path once we're done
    }
}

回圈類：

// represents the cycle of a unique MPDG-subgraph
//  (should have one of these for each subgraph)
class Cycle
{
    public MPDGraph Graph; // the MPDG that contains this cycle
    public Node Base;      // the base node of a subgraph's cycle
    public int Length;     // the length of this cycle

    public Cycle(MPDGraph graph_, Node base_, int length_)
    {
        Graph = graph_;
        Base = base_;
        Length = length_;
    }
}

性能測量：

標籤：算法 数学 数据结构 图形 树

上一篇：如何使用貪婪演算法為這個問題獲得O(mlogn)的復雜度

下一篇：二進制表示中的最長公共前綴