A *的搜索啓發式功能搜索排序

我的問題是使用A *搜索的實現對三個列表中的字符串進行排序，所以我需要開發一個啓發式函數來解決這個問題的各種實例。A *的搜索啓發式功能搜索排序

狀態可以表示S的3所列出的列表，例如：[[C B]，[d]，[H G + F A E]]

我拿起任何堆棧的頂部部分和其移動到任何其他。例如，上面的H可以移動到C或D的頂部，[HG]可以移動到第二個堆棧上以創建[HGD]等等。在這個領域，單位操作員的成本是這樣的，因此每個移動成本1，無論有多少字被移動。

目標是採取初始配置塊並將它們全部從上到下按排序順序移動到左側堆棧。例如，在上面的例子中給出8個塊，目標是[[A B C D E F G H] [] []]。

我需要開發一種可以與A *搜索一起使用的啓發式方法，以使搜索更有效率。我應該儘量保持你開發的啓發式是可以接受的。爲此，您可以嘗試使用啓發式方法估計達到目標狀態的剩餘步數。

我在考慮啓發式依賴於每個堆棧中的排序字，每個堆棧的點總數是狀態的啓發式，但這不是有效的，我認爲我需要包含每個堆棧的ascii代碼寫信給我的計算，有什麼想法？

2014-11-14 faris hamarshi

所以你想通過解決問題的步驟數排序這些問題的列表？提示：如果你有成對的比較，就像在Java中一樣，確保搜索函數只對列表中的每個元素被調用一次，而不是每個組合都調用一次。例如，使用散列表來緩存搜索結果。也許這僅僅是一種加速。 – 2014-11-14 14:22:23

此外，您的問題與河內問題非常相似，只是隨機初始配置。也許這可以幫助你尋找一個好的A *啓發式。 – 2014-11-14 14:24:49

是的，我使用java進行編程，唯一需要的是每個狀態的啓發式值，所以我需要一個算法可以計算每種可能狀態的啓發式值，然後我可以選擇更好的啓發式值。搜索功能究竟意味着什麼？ – 2014-11-14 14:28:49

在開始時，嘗試一個簡單或樸實的啓發式。例如，「h」將是兩個字母的非升序的總和。比方說，當你開發一個新的孩子，你有這樣的事情[ACBED]在這裏採取第一對夫婦[AC]他們是升序，什麼也不做，但對於下一對[CB]它不是升序，然後加一個「H」。 [BE]很好。對於[ED]添加一個「h」。所以「h == 2」。這種啓發式看起來很簡單，但我相信它比盲搜索更好（即廣度/深度搜索）。從這個想法中，您可以添加更多的規則來根據對結果的分析來增強啓發式。我希望這很有用。

來源

2016-02-17 19:40:56

A *的搜索啓發式功能搜索排序

回答

相關問題