WordPress 你所有的基地屬於 Dijkstra

問題描述

CATS, willing to get a hold of all the bases, asked Dijkstra to give him a hand designing the most powerful algorithm to reach all bases with the least distance travelled.

我試圖用 TDD 實現 Dijkstra’s algorithm 。該算法旨在找到到達圖的所有節點的最快路由。現在，我擔心如果我以很好的角度實現了算法。我測試了 (顯然)，我的所有測試通過，所以我很自信的算法工作，我只是不知道是否應該寫的方式。

這些是我用來表示圖表的兩個類：

[DebuggerDisplay("{Name}")]
public class Node
{
    public string Name { get; }
    public ICollection<Link> Links { get; }

    public Node(string name)
    {
        if (String.IsNullOrWhiteSpace(name)) throw new ArgumentNullException(nameof(name));

        Name = name;
        Links = new Collection<Link>();
    }

    public override bool Equals(object obj)
    {
        Node node = obj as Node;
        if (node == null) return false;

        return Name.Equals(node.Name);
    }

    public override int GetHashCode()
    {
        return Name.GetHashCode();
    }

    /// <summary>
    /// Creates links betwen two nodes
    /// </summary>
    /// <param name="a">First node</param>
    /// <param name="b">Second node</param>
    /// <param name="distance">Distance between nodes</param>
    /// <remarks>There is no order in the nodes</remarks>
    public static void Join(Node a, Node b, int distance)
    {
        if (a == null) throw new ArgumentNullException("a");
        if (b == null) throw new ArgumentNullException("b");

        Link linkAToB = new Link(a, b, distance);
        Link linkBToA = new Link(b, a, distance);

        a.Links.Add(linkAToB);
        b.Links.Add(linkBToA);
    }
}

[DebuggerDisplay("({From.Name}) to ({To.Name}), Distance : {Distance}")]
public class Link
{
    public Guid Id { get; } = Guid.NewGuid();

    public Node From { get; }
    public Node To { get; }
    public int Distance { get; }

    public Link(Node from, Node to, int distance)
    {
        if (from == null) throw new ArgumentNullException("from");
        if (to == null) throw new ArgumentNullException("to");

        From = from;
        To = to;
        Distance = distance;
    }

    public bool ConnectsSameNodes(Link other)
    {
        if (other == null) throw new ArgumentNullException("other");

        bool connectsSameFrom = other.From.Equals(From) || other.To.Equals(From);

        return connectsSameFrom && (other.From.Equals(To) || other.To.Equals(To));
    }

    public override bool Equals(object obj)
    {
        Link link = obj as Link;
        if (link == null) return false;

        return Id == link.Id;
    }

    public override int GetHashCode()
    {
        return Id.GetHashCode();
    }
}

這是算法的實現：

public interface IGraphSolverStrategy
{
    IEnumerable<Link> Solve(Node head);
}

class LinkDistanceComparer : IComparer<Link>
{
    public int Compare(Link x, Link y)
    {
        if (y == null) throw new ArgumentNullException("y");
        if (x == null) throw new ArgumentNullException("x");

        return Math.Sign(x.Distance - y.Distance);
    }

}

public class DijkstraSolverStrategy : IGraphSolverStrategy
{
    public IEnumerable<Link> Solve(Node head)
    {
        if (head == null) throw new ArgumentNullException(nameof(head));

        var orderedLinks = new SortedSet<Link>(new LinkDistanceComparer());
        AddLinksToSet(orderedLinks, head.Links);
        var traveledLinks = new List<Link>();

        while (orderedLinks.Count != 0)
        {
            var link = orderedLinks.ElementAt(0);
            orderedLinks.Remove(link);

            if (traveledLinks.Any(l => l.To.Equals(link.To))) continue;

            traveledLinks.Add(link);
            var linksToAdd = link.To.Links.Where(l => !l.ConnectsSameNodes(link));
            AddLinksToSet(orderedLinks, linksToAdd);
        }

        return traveledLinks;
    }

    private static void AddLinksToSet(SortedSet<Link> linkSet, IEnumerable<Link> linksToAdd)
    {
        foreach (var item in linksToAdd)
        {
            linkSet.Add(item);
        }
    }
}

基本上，我從頭節點開始，從這個節點添加鏈接到 SortedSet，然後選擇最小的鏈接。我從集合中刪除當前鏈接，添加新節點的鏈接，選擇最小的鏈接，然後重複。我確保沒有關閉循環，確保具有相同 To 節點的鏈接不能在集合中兩次。

由於我使用 TDD，我認為包括我的單元測試將是一個很好的舉措：

[TestFixture]
public class DijsktraSolverStrategyTest
{
    private DijkstraSolverStrategy solver = new DijkstraSolverStrategy();

    #region Helpers

    private static Node CreateHeadWithChilds(params int[] nodesDistance)
    {
        var head = new Node("head");

        for (int i = 0; i < nodesDistance.Length; i++)
        {
            var distance = nodesDistance[i];
            var child = new Node($"child {i + 1}");
            Node.Join(head, child, distance);
        }

        return head;
    }

    private static Node CreateHeadWithTriangleLink(int triangleDistance, params int[] nodesDistance)
    {
        var head = CreateHeadWithChilds(nodesDistance);
        var otherNodes = head.Links.Select(l => l.To);
        Node.Join(otherNodes.ElementAt(0), otherNodes.ElementAt(1), triangleDistance);

        return head;
    }


    #endregion

    [Test]
    public void Solve_NullHead()
    {
        Assert.Throws<ArgumentNullException>(() => solver.Solve(null));
    }

    [Test]
    public void Solve_OneNode_ReturnsEmptyList()
    {
        //Build
        var head = new Node("Node");
        var expected = new List<Link>();

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_TwoNodes_ReturnsLinkBetweenNodes()
    {
        //Build
        var head = CreateHeadWithChilds(1);
        var expected = new []{ head.Links.Single() };

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_TwoNodesWithTwoLinks_PicksFastestLink()
    {
        //Build
        const int smallestDistance = 2;
        var head = CreateHeadWithChilds(smallestDistance);
        Node.Join(head, head.Links.Single().To, smallestDistance + 1);
        var expected = head.Links.Where(l => l.Distance == smallestDistance);

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_HeadWithMultipleChilds_TravelsByOrder()
    {
        //Build
        var distances = new []{ 5, 7, 4 };
        var head = CreateHeadWithChilds(distances);
        var expected = head.Links.OrderBy(l => l.Distance).ToList();

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_TriangleNodes_DoesntCloseTheLoop()
    {
        //Build
        var distances = new []{ 5, 7 };
        var head = CreateHeadWithTriangleLink(3, distances);
        var unexpected = head.Links.Single(l => l.Distance == 7);

        //Test
        var links = solver.Solve(head);

        //Assert
        CollectionAssert.DoesNotContain(links, unexpected);
    }

    [Test]
    public void Solve_ThreeLevelHierarchyWithPossibleLoop()
    {
        var distances = new int[]{ 1, 700000 };
        var head = CreateHeadWithTriangleLink(2, distances);
        var thirdLevelNode = new Node("3rd child");
        Node.Join(head.Links.First().To, thirdLevelNode, 3);
        var expected = new List<Link>
        {
            head.Links.Single(l => l.Distance == 1),
            head.Links.First().To.Links.Single(l => l.Distance == 2),
            head.Links.First().To.Links.Single(l => l.Distance == 3),
        };

        var actual = solver.Solve(head);

        CollectionAssert.AreEqual(expected, actual);
    }

    [Test]
    public void Solve_InvertedFromTo_TravelIsNonDirectional()
    {
        //Build
        var head = CreateHeadWithChilds(10);
        var otherNode = head.Links.Single().To;
        var thirdNode = new Node("case");
        Node.Join(thirdNode, otherNode, 5);
        var expected = new List<Link>(){ head.Links.Single(), otherNode.Links.Single(l => l.Distance == 5) };

        //Test
        var actual = solver.Solve(head);

        //Assert
        CollectionAssert.AreEqual(expected, actual);
    }
}

最佳解決方案

我一直在想這一段時間，我很確定你沒有實現 Dijkstra 的算法 (這是圖中兩個節點之間的最短路徑) 。看起來您正在計算最小生成樹 (以最小的成本連接所有節點的邊集合) 。

一些額外的評論：

1. Link 是一個奇怪的名稱 – 更一般來説，術語 Edge 用於連接圖中的兩個節點。

2. 我認為你的抽象有點太漏洞 – 算法需要了解節點和鏈接的內部結構 (我指的是 link.To.Links.Where(l => !l.ConnectsSameNodes(link)) 。我會規定您可以使用以下公共接口實現一個 Graph 對象，並且還可以創建獨立的圖形算法：class Graph<TNode> : IEnumerable<TNode>
{
// adds an edge between two nodes with the provided cost
// creates the nodes if not present
public Graph<TNode> AddEdge(TNode from, TNode to, int cost)
{
}

   // returns a list of nodes connected to the source via an edge and the associated cost
   public IEnumerable<Tuple<TNode, int>> GetEdges(TNode source)
   {
   }

   // plus IEnumerable<TNode> implementation - enumerate all nodes in the graph
   }
   這具有以下優點：

   1. 用户可以定義自己的節點類型，並將他們喜歡的任何元數據關聯起來。

   2. 如何存儲節點和邊的內部實現是隱藏的，因為他們不必關心它 – 也不應該。

更新：

為了清楚和總結 @BenAaronson 留下的評論：Dijkstra’s algorithm as explained on wikipedia 在圖中找到兩個節點之間的最短路徑。在這種情況下，您將期望為算法提供一個開始和結束節點。如果您的目標是通過 Dijkstra 找到從給定節點到任何其他節點的所有最短路徑，那麼這不是您正在做的。

一個簡單的例子就是這個圖：

  A -6-> D
  |      ^
  5      |
  |      1
  v      |
  B -2-> C

您的算法產生序列 A – > B，B – > C，C – > D，總成本為 7，這確實是以最小的成本連接所有節點的一組邊。如果要使用 Dijkstra 算法來計算從 A 到其他節點的所有最短路徑，您將得到：A – > B，A – > B – > C，A – > D，費用為 13(如果您不計算 A – > B 兩次)，因為從 A 到 D 的最小成本的路徑確實是成本為 6 的邊。

因此，您的實現將找到所有邊的集合，以便所有節點以最小的成本連接。如上所述，通常稱為 a minimum spanning tree，其中存在幾種算法，最顯著的是 Prim’s algorithm 和 Kruskal’s algorithm 。

我沒有詳細檢查它，但它看起來像你的算法本質上是 Kruskal’s algorithm 的一個實現。所以這不是完全錯誤的 – 它不是你開始執行的算法。

您可以將您的實現重命名為 KruskalSolverStrategy，然後再次使用 Dijkstra(如果您需要幫助，則 Stackoverflow 將是更好的地方，因為 CodeReview 是關於檢查現有代碼) 。

次佳解決方案

Nest 和 Link 應實施 IComparable<T>

那麼 LinkDistanceComparer 可以使用它們。這是行動中的單一責任原則。

public int Compare(Link x, Link y) {
    // ...
    return x.CompareTo(y);
}

並確保實現 IComparable<T> 不是 IComparable 。通用型可以讓您安全。

public int CompareTo (object other)   // IComparable
public int CompareTo (Link other )    // IComparable<T>

---

實施 IEquatable<Node> 和 IEquatable<Link>

`IEquatable MSDN documentation:

The IEquatable interface is used by generic collection objects such as Dictionary, List, and LinkedList when testing for equality in such methods as Contains, IndexOf, LastIndexOf, and Remove. It should be implemented for any object that might be stored in a generic collection.

public bool Equals (Node other) {

  if (other == null) return false;

  return this.Name.Equals(other.Name);
}

object.Equals 如何覆蓋？再次，MSDN：

If you implement IEquatable, you should also override the base class implementations of Object.Equals(Object) and GetHashCode so that their behavior is consistent with that of the IEquatable.Equals method.

public bool override Equals (object other) {
    if (!other is Node ) return false;
    return Equals ((Node)other));
}

---

例外

使用 Exception.Data 來捕獲上下文。當事情爆炸時，知道參數值非常方便。

為了方便上述，Node 和 Link 應該覆蓋 ToString()。那麼你可以這樣做

new whateverException() {
    Data = {
         { "Node A" , NodeA.ToString() }
        ,{ "Node B", NodeB.ToString() }
    }
}

---

重組 DijkstraSolverStrategy.Solve

我看不到森林的樹; 它沒有結構化。 Solve 是做什麼的？這是高級代碼，應該這樣閲讀。

public IEnumerable<Link> Solve(Node head) {
    var orderedLinks = AddLinksToHead( SortedSet<Link>(new LinkDistanceComparer()), head) ;

    // this may be several steps, but I'm not looking at the specific
    // algorithm implementation here.
    // The point is to express the steps.
    // It is not about how many LOC are in a method.
    // It is not about LOC --> yes, I said this twice.

    return BuildShortestPathSet(orderedLinks);
}

---

測試更深

我的傾向是測試我的基本類中的重要事物，如等於覆蓋。

• 太麻煩了？測試也是關於 future-proofing 的變化。

• 在這個特殊的代碼中，Equals 是至關重要的。如果 Equals 是 FUBARed，沒有任何作用。

• 當您構建系統合成和交互對象時，知道這些部件的工作非常好。

• 附：在實施 IEquatable 之前編寫該測試。

---

創建自定義集合

這引發了許多 OO 原則，如封裝和 Demeter 法，但主要是單一的責任原則。定製系列將對以下內容負責：

• 不允許重複節點

• 不允許為空

• 確保有效的元素加入

優點

• 客户端代碼將被清理。例如 Solve 不會隱藏 「大圖」，因為這麼繁忙的代碼循環，並且使用普通的 Collection 對象。

• 隱藏底層集合的公共接口，使其只執行應該的事情。

• 創建自定義 Find，Contains 等，所以它只做我們想要的方式。

• 總體而言，代碼更加強大。

• 我們限制客户端代碼中的潛在 WTFery 。客户必須做正確的事情。

• 收集功能有適當的位置。

  • Node.Join

  • Links.ConnectsSameNodes

  • DijkstraSolverStrategy.AddLinksToSet

  • 客户端不能將 foreach 的一個集合添加到另一個。

• 客户端不必知道如何構建集合

  • var orderedLinks = new SortedSet<Link>(new LinkDistanceComparer()); 可以簡單地是 new SortedLinkSet()。

  • 如果我們有不同的 IComparer 注射，請使用出廠模式。

• 代碼將開始自然地以領域語言表達

。

public class SortedLinkSet {
    public SortedSet<Link> Links {get; protected set; }
    protected LinkDistanceComparer LinkComparer ( get; set; }

    public SortedLinkSet() {
        Links = new SortedSet<Link>(new LinkDistanceComparer());
    }

    public void Add(Link newLink) {
        if ( newLink == null ) return;
        if ( Links.Contains(newLink) return;

        Links.Add(newLink);
    }

    public void Add(SortedLinkSet<Link>()) { }

    public void Join (Node a, Node b, int distance) {
        // I "return" for expediency. do what you want.
        // perhaps return a boolean so we can handle a failed join
        // without throwing exceptions.

        if (a == null || b == null) return;
        if (a.Equals(b)) return;
        if (distance <= 0) return;

        // ok, now we can join ...
}

參考文獻

• All your bases are belong to Dijkstra

注：本文內容整合自 Google/Baidu/Bing 輔助翻譯的英文資料結果。如果您對結果不滿意，可以加入我們改善翻譯效果：薇曉朵技術論壇。