在給定開始點和結束點的圖中找到哈密爾頓路徑的數量

給定一個具有n2個路徑節點的圖，並且假定起始節點始終位於右上角（點A）並且終止節點始終處於在右下角（B點），我需要編寫一個C＃程序，該程序將給定n（假設n < = 10），確定從A到B的哈密爾頓路徑的數量。換句話說，我需要找到從A開始到B結束的每條路徑，每個節點只訪問一次，節點間的移動僅限於左，右，上，下（無對角線）。在給定開始點和結束點的圖中找到哈密爾頓路徑的數量

例如，如果n = 5，則一個可能的路徑將是該圖像中所示的一個：

理想情況下，我想開發一種智能算法利用一些啓發式，但現在我只需要開發一個蠻力方法。我假設我使用廣度優先搜索，但我真的不知道從哪裏開始實施使用C＃。

來源

2012-08-08 Steve Holt

您最困惑的問題的任何特定部分？要求某人簡單地解決問題可能不會得到太好的結果。 – 2012-08-08 12:25:46

這個問題是非常相似的http://stackoverflow.com/questions/5333161/algorithms-to-find-the-number-of-hamiltonian-paths-in-a-graph但是，不同的是，他已經拿出一個蠻力解決方案。我需要先到這一點。任何鏈接或僞代碼幫助我將不勝感激。我只需要朝正確的方向推。 – 2012-08-09 05:14:29

一些暴力事物

構建圖表。構建一個圖形轉輪。緩存所有運行信息。使跑步者重新運行圖形並排除運行信息中的所有決定。當跑步者不能運行時，過濾緩存的數據並計算結果。

在C中實現＃

安裝像nunit這樣的測試框架。編寫您需要的功能列表。

重複，直到featurelist爲空：

選擇的最小特徵
寫一個失敗的測試
寫代碼通過測試
確保所有的測試都通過了
重構作出的pritty
從功能列表中清除項目

做

編輯以回答一些問題在評論

You can download nunit from the internet.其解壓到你選擇的文件夾。
創建一個空的控制檯應用程序。
探索NUnit目錄來查找框架，將該框架添加到您的項目中。
探索NUnit目錄以查找gui runner，將其添加到您的項目中。
我們實際上不想使用控制檯運行項目，我們只是不想讓表單自動創建，打開屬性並重新聲明您的項目是一個Windows應用程序。
用下面的代碼替換你的program.cs。
編譯並運行。點擊GUI中，按F5運行，如果異常拿出
祝賀 - 你只使用NUnit的

下面是程序：

using System; 
using NUnit.Framework; 
namespace EC_Connect_Test 
{ 
    class Program 
    { 
     [STAThread] 
     static void Main(string[] args) 
     { 
      string fullPath = System.Reflection.Assembly.GetAssembly(typeof(Program)).Location; 
      NUnit.Gui.AppEntry.Main(new string[] { fullPath }); 
     } 
    } 
     public class MathClass 
     { 
      internal static double Divide(int A, int B) 
      { 
       if (B == 0) throw new DivideByZeroException(); 
       return (Double)A/(Double)B; 
      } 
     } 

     [TestFixture] 
     class MyFirstTestClass 
     { 
      [Test] 
      public void DividingTwoIntegersResultIsDouble() 
      { 
       Double expected = 3.3; 
       Double actual = MathClass.Divide(33, 10); 
       Assert.AreEqual(expected, actual); 
      } 

      [Test] 
      public void DividingByZeroShouldThrow() 
      { 
       Assert.Throws<DivideByZeroException>(
        () => { MathClass.Divide(33, 0); } 
       ); 
      } 
     } 

    }

您也可以啓動NUnit的外部，並給它你debugproject作爲目錄。這樣，異常不會出現，測試變得更容易。

功能列表就是您希望軟件執行的操作。在你的情況下，你以某種形式提供給定的圖形。這可能是一個文件或一張紙。所以一個功能是加載該信息並從中製作圖表。你提到的下一個特點是你的程序應該檢查n < = 10，如果不是，那麼拒絕工作，那也是一個特性。另一個是通過給定的界面返回結果。最後一個重要的是能否真正找到所有的連接。如果你自己列出這些，你可以選擇你認爲最簡單的那個，並從那個開始。

當測試不要忘記爲已知案例創建端到端測試時。所以固定圖形，已知數量出來。

使用野生假設你的圖是一個文本文件，其中每行列出北京時間其他線路的連接，你可以寫測試是這樣的：

[TestFixture] 
    class graphloadingSpex 
    { 
     String[] lines = new String[] { 
     "2,3,4", 
     "1", 
     "1,4", 
     "1,3" 
     }; 

     [Test] 
     public void ShouldShowConnectionsAfterLoading() 
     { 
      Graph tested = new Graph(lines); 
      Assert.AreEqual(new String[] { "2", "3", "4" }, tested["1"].GetConnextions()); 
      Assert.AreEqual(new String[] { "1"}, tested["2"].GetConnextions()); 
      Assert.AreEqual(new String[] { "1", "4" }, tested["3"].GetConnextions()); 
      Assert.AreEqual(new String[] { "1", "3" }, tested["4"].GetConnextions()); 
     } 
    }

這將無法編譯，因爲圖表尚不存在。但讓它編譯並通過測試通過將滿足你的第一個特性，你可以通過先寫測試繼續實現下一個測試。

來源

2012-08-08 12:42:29 Johannes

我以前從未使用過任何測試框架，所以我對nunit不熟悉，也從未聽說過某個功能列表。「選擇最小的功能」是什麼意思？測試失敗的過程是什麼？通過測試的過程是什麼？ – 2012-08-08 19:11:25

謝謝Johannes。我會給它一個鏡頭。 – 2012-08-09 19:31:30

在給定開始點和結束點的圖中找到哈密爾頓路徑的數量

回答

相關問題