heuristic suite

啟發式套件

重要說明

該項目不再受到維護。請訪問linq以獲取A*以獲取最新版本。

概述

啟發式套件是通用編程中一系列啟發式算法的實驗實現。該項目的目的是提供一個可以應用於任何難題的基礎架構 - 只要可以通過算法解決難題即可。

實施算法：

• 一個*
• 迭代加深A*（IDA*）
• 最好的首次搜索
• 遞歸最佳首次搜索（RBFS）

該實現完全面向對象，並具有內置的.NET框架比較機制（例如ICOMPARER（T）和IEqualityComparer（T）），以與.NET標準和整個.NET生態系統創建出色的兼容性。源代碼可以輕鬆地帶到其他平台，例如Unity和Xamarin。

用算法解決難題

為了將算法應用於難題，需要以下實現：

1. 步驟定義定義拼圖步驟的類型將需要實現ISTEP（TKEY）接口。 Key屬性有兩個目的：

   • 測試兩個步驟是否等效。例如：董事會上的同一位置。
   • 比較兩個步驟以確定哪些具有更好的分數。例如：位置A和目標之間的距離，以及位置B和目標之間的距離，越接近一個的距離得分更好。

2. 根據Key屬性將步驟比較步驟相互比較，以確定哪些具有更好的分數。可以通過以下方式進行比較：

   • 可觀的（TKEY）實現。
   • 定制的ICOMPARER（TKEY）實例。
   • 明確給定的h（n）函數，其中參數n是Key 。

3. 可以通過實現INextStepFactory(TKey, TStep)接口或提供NextStepFactory委託來提供當前步驟下一步信息的可用步驟。

之後，可以通過from參數為目標步驟來調用FindSolution方法和goal步驟來運行該算法。如果解決方案存在，則可以通過調用Enumerate方法來獲得每個步驟。在枚舉開始之前，可以將步驟Reverse d。

啟發式比較和離散啟發式比較

該項目提供了HeuristicComparer和DiscreteHeuristicComparer ，以用於不同的步驟比較方案。

• 如果可以直接將Key屬性相互比較而沒有明確的h（n）函數，則默認情況下，將使用DiscreteHeuristicComparer Comparer進行更快的步驟比較。
• 如果要明確需要H（n）函數以比較每個步驟，則HeuristicComparer將用於執行傳統估計f（n）= g（n） + h（n） 。

啟發式功能偏好

HeuristicFunctionPreference輸入枚舉使用戶能夠更改估計的平衡f（n）= g（n） + h（n） 。當兩個步驟評估相同的分數時，枚舉決定首先考慮哪種功能G（n）或H（n） 。變化的平衡會影響啟發式算法的行為。

例子

• 路徑查找（algorithmforce.example.pathfinding）

  該示例展示了使用啟發式算法來解決的最常見和傳統難題。

• 8-Puzzle（Algorithmforce.example.eightpuzzle）

  該示例演示瞭如何使用啟發式算法解決8個式嘴。難題的初始和目標步驟如下：

• 硬幣翻轉拼圖（Algorithmforce.example.coinsflipping）

  此示例演示了遊戲AI如何解決硬幣翻轉拼圖。在難題中，只允許一對相鄰的硬幣同時翻轉。所有十枚頭腦都是目標。這個難題的靈感來自brine.org。

將來將添加更多示例。

平台

該項目目前針對.NET Core和.NET Framework 4.5或更高。