泡泡破碎機遊戲解算器比貪婪更好嗎？

對於腦力鍛鍊我決定嘗試和解決氣泡破碎遊戲許多蜂窩電話以及這裏的例子發現：Bubble Break Game 泡泡破碎機遊戲解算器比貪婪更好嗎？

隨機（N，M，C）板由N行×M個使用C顏色的列
目標是通過挑選最終導致最高分數的氣泡組序列來獲得最高分數
氣泡組是具有相同顏色且相鄰的2個或更多個氣泡在x或y方向上。對角線不計算
當一個組被挑選出來時，氣泡消失，任何孔都從上面的第一個氣泡中填充，即向下移動，然後通過向右移動來填充任何孔
氣泡組分數= n *（ N - 1）其中n是氣泡的氣泡羣

第一種算法的數量是探索通過板行通過柱拾取氣泡組要去由行和列的簡單窮舉遞歸算法。一旦挑選了氣泡組，我們創建一個新的電路板並嘗試解決該電路板，遞歸降序

我正在使用的一些想法包括標準化memoization。一旦董事會得到解決，我們將董事會和最佳成績存儲在記事表中。

我創建了一個prototype in python，它顯示（2,15,5）電路板需要在大約3秒內解決8859個電路板。（3,15,5）板在服務器上50分鐘內需要12,384,726塊板。解算器速率爲〜3k-4k板/秒，並且隨着記憶搜索需要更長時間而逐漸減小。記憶表格增長至5,692,482張，達到6,713,566次。

除了窮舉搜索之外，還有哪些其他方法可以產生高分？

我沒有看到任何明顯的分而治之的方法。但趨向于越來越大的氣泡組似乎是一種方法

感謝大衛洛克發佈的紙張鏈接，上面談到一個窗口解算器，它使用恆定深度的前瞻啓發式。

來源

2009-10-08 Gregory

我實際上認爲解決這個同樣的問題，作爲一種業餘愛好。在我的Windows Mobile手機中投入了超過數千輪的遊戲後，從蝙蝠身上挑選更大的泡泡羣並不是最好的方法。我發現你想試圖通過擺脫將它們分開的小團體來將大羣體合併在一起。 – Larsenal 2009-10-08 23:37:44

是的，這絕對是我正在考慮的一種方法。 – Gregory 2009-10-09 05:51:25

根據this paper，確定是否可以清空電路板（與您要解決的問題有關）是NP-Complete。這並不意味着你不能找到一個好的算法，這只是意味着你可能找不到一個有效的算法。

來源

2009-10-09 00:01:34

這不是我的專業領域，但我想推薦一本書給你。獲取Steven Skiena的副本The Algorithm Design Manual。這有一個不同的算法的完整列表，一旦你通讀它，你可以用它作爲參考。如果沒有別的，它會幫助你考慮你的選擇。

來源

2009-10-08 23:37:57 steveha

我想你可以嘗試一個分支限界搜索與以下想法：

鑑於遊戲S，你在分公司的狀態，打破它在M組的硅每個Si是在給定狀態S之後採取所有合法移動的合法移動之後的狀態S
需要兩個函數U（S）和L（S）分別計算給定狀態S的下限和上限。

對於U（S）函數，我在想如果你能夠在棋盤上自由地拖曳K個泡泡（每次移動）並以這樣一種方式安排塊，你將得到的分數將會導致最高分，其中K是您自己選擇的值。當你計算給定S的U（S）時，如果你選擇較高的K（條件放寬），它應該更快，所以選擇K的值將是一個快速找到U（S）和質量一個上限U（S）是。）

對於L（S）函數，計算您得到的分數，如果您只是隨機保持點擊，直到您達到無法進一步解決的狀態。你可以通過多次獲得最高的下限。

一旦你有了這兩個功能，你可以應用標準的綁定和分支搜索。請注意，搜索的速度很大程度上取決於您的上限有多緊張以及您的下界有多緊。

來源

2009-10-09 00:02:44 ldog

爲了獲得比徹底搜索更快的解決方案，我想你想要的可能是動態編程。在動態編程中，您會發現某種「步驟」，它可能會使您更接近您的解決方案，並在大矩陣中跟蹤每個步驟的結果。然後，一旦填好了矩陣，就可以找到最好的結果，然後反向工作以獲得通過矩陣的路徑，從而獲得最佳結果。矩陣實際上是一種記憶形式。

動態編程在The Algorithm Design Manual中討論過，但在網絡上也有很多關於它的討論。這裏有一個很好的介紹：http://20bits.com/articles/introduction-to-dynamic-programming/

我不確定這個問題到底是什麼「步驟」。也許你可以爲董事會制定一個評分指標，簡單地總結每個泡沫組的分數，然後在嘗試彈出氣泡時記錄此分數？良好的步驟往往會導致泡沫團體凝聚，提高分數，糟糕的步驟會破壞泡沫團體，使得分數變得更糟。

來源

2009-10-09 00:10:10 steveha

您可以將此問題轉化爲在圖上搜索最短路徑的問題。 http://en.wikipedia.org/wiki/Shortest_path_problem

我想試試惠普A *和啓發式將包括島的數量。

來源

2009-10-09 06:09:15

在我的國際象棋程序中，我使用了一些可能適用於這個問題的想法。

移動訂購。首先找到所有可能的移動，將它們存儲在列表中，並根據啓發式對它們進行排序。首先是「更好」的，「壞」的最後。例如，這可能是該組的大小的函數（更喜歡中型基），或相鄰的色彩，組的數量等
迭代深化。而不是運行一個純粹的深度優先搜索，削減搜索後，一定深，並使用一些啓發式來評估的結果。現在先研究樹「」，首先「更好」移動。
修剪。不要搜索似乎「明顯」壞的移動，根據一些，再次，啓發式。這涉及到這個風險，你不會再找到最佳解決方案，但是取決於你的啓發式，你很可能會發現它很早。
哈希表。沒有必要存儲每一個你來過的板，只記得一定數量並覆蓋較舊的的。

來源

2009-10-09 08:27:33 hirschhornsalz

我差不多完成了用Java編寫我的「求解器」版本。它既進行詳盡的搜索，以更長的棋盤大小爲代價進行窮舉搜索，並且基於可能路徑的「池」進行有針對性的搜索，並在每一代之後對其進行修剪，以及用於修剪池的適應度函數。我只是想調整現在的適應度函數...

更新 - 這是現在可以在http://bubblesolver.sourceforge.net/

來源

2010-06-15 11:38:38 mreddin

泡泡破碎機遊戲解算器比貪婪更好嗎？

回答

相關問題