※ 引述《r5e97nk63 (yapin)》之銘言：
: 如題相信很多手速不夠快，狠，準的人視此為目標。然而相關教導文又太少，大多只能從
: 網站獲得。
: 可是之前太陽教主又認為光看解答著實困難，因此我在這想問一下，有人知道網頁最短路
: 徑的剖析順序嗎，具體一點便是它是如何被運算出來的，如果它真是模擬”所有路徑結果
: “那小弟就真的認了。（雖然我是認為這不可能啦）
: 哪怕只知道一點點，我相信這對”非常理”疊珠的分析都會有蠻大的突破。
如果以找到特定 combo 數作為目標，找最短路徑的解法，最適合的作法是 BFS 。
不過即使是 20 步左右的路徑，對於電腦而言要計算，搜尋完所有可能的解，
時間還是太長了。在不考慮斜轉的情況底下，一步最多可以有四個方向可以走，
以這個數字作粗略的計算， 20 步所產生的可能盤面有 4^20 ，也就是 2^40 ，
要作這樣的計算需要的時間其實滿長的，以此來產生最短路徑並不太實用。
另外一種作法是用 A* 演算法作搜尋，每走一步給與所產生的四個盤面一個分數，
挑分數最高的盤面再走下一步。但直接這樣做不太行得通，因為從啟始盤面只走一步，
可能產生的 combo 數很少，可能產生出來的四個盤面都沒有消任何珠，
根本沒辦法用計算分數的方式分出往哪一個方向走比較好。
因此比較實際的作法是，每走 n 步給予所有產生的盤面一個分數，
例如一個計算階段走 8 步，那麼就會產生 4^8 (2^16) 個盤面，
然後去評估這 64K 個盤面哪一個盤面最好，然後再從這個盤面繼續往下找。
這樣做的好處是每一階段的計算時間都不長，可以重複好幾次。
上述這兩種作法 (一次走一步的 A* 跟一次走 n 步的 A* ) 都不能保證找到最佳解。
而這個作法還有另外一個缺點，就是可能會卡在區域最佳解。
因為一個前幾步就產生不錯的解的路徑，不能保證後面可以產生好解。
所以還是需要某種回溯的機制，在找不到好解的時候放棄已經找到的解。
不過這樣做缺點就是馬上會增加總計算量。
另外一個可以試著改進的部份是 A* 的評分機制，最原始的作法可能是 combo 數，
但產生一個 combo 可不是亂走就可以走出來。因此為了要分辨解的好壞，
除了 combo 數以外可能還要其它的條件加進來。例如在消完以後，可能還有某些同色珠，
則可以設定同色餘珠的位置越接近的解，分數越高。因為這種盤面，
可能再走幾步就可以多產生一個 combo ，應該要比那些同色餘珠離很遠的來得高分。
至於路徑的起手位置，除了所有三十個位置都一起嘗試以外，因為整個盤面移動上，
最自由的珠就是直接被移動的珠，因此可能挑選某一個很分散的珠會是比較好的選擇，
例如有兩個水珠在最左邊，一個在最右邊，這時候如果選擇最右邊的水珠，
可能就可以把三個水珠拉在一起，相對地如果選擇其它的珠，要把最右邊的水珠運來，
可能要花的步數就會多上很多。
至於 branch and bound 或 divide and conquer 當然都可以做，
不過前者如果想要做到保證最佳解，那步數可能得要壓得很短才能夠算得完。
後者的話除了不能保證得到最佳解以外，其實得到的解可能會滿差的，
除非剛好足夠形成 combo 的珠都在同一邊，否則如何 divide 會是一個問題。
當然不同的人可能會有一些不同的 optimization 技巧，不過講下去可能太多話了，
總之 search algorithm 如果要解的問題本身沒有某些非常良好的特性，
那麼頂多就是在暴力解上面加上一些 heuristic 去縮短時間來得到次佳解，
因此一定是在某些盤面表現得不錯，在另外一些盤面表現的普普通通，
然後在某些剛好剋到的盤面，就找不太到好的解。
不過以 6*5 的轉珠盤面而言，大概要在五十步以內找出一個不錯的解，都滿有機會的。

可以斜轉有8個方向!! (?

目前看過類似的東西都是直接放棄斜轉......

快推 求翻譯

嗯嗯 原來如此 看不懂

麥子大竟然會降臨PAD版...

原來是這樣喔 這篇是中文嗎

考慮到不可能往回走，所以其實只要計算 3 個方向 XD若只考慮 30 步，大概只有 6000 兆種路徑... 吧 XDDD

推~~

先建立某些常見解法成路徑TABLE 先LOOKUP TABLE不知道行得通嗎?!

我是覺得暴力算不太可能。個人電腦的速度還不夠看 XD@followwar: 查表法也不太可能。記憶體/硬碟還不夠大 XD

我的意思是某些常見解交錯的方法先內建遇上時直接使用解這些交錯的路徑

不考慮斜轉 應該只有三個方向走可以吧，因不會往回頭走除了起手步之外

已知目標combo數的話 有沒有可能先產生轉完的盤面 在從結果反推回去?

主要是目標combo數的盤面有複數個，所以沒辦法用反推的方式來做雙頭BFS加速

強者推一個!

是麥大0.0

先產生一定量的目標盤面 再跟目前盤面作比對 取相似度最高(或前幾名)的來作 這樣可以嗎

為什麼要讓我想起被當的演算法orz

推，好奇這類演算法很久了

學習了

http://shouryan.blogspot.tw/ 是在討論類似這種東西的演算法嗎?

查到麥大的網站了 拜讀中

有趣

為什麼會在PAD版看到這些眼熟的名詞XDDDD

Sito大(拜

樓上的演算法超眼熟 跟這個好像阿https://github.com/kennytm/pndopt明天被水桶就知道了?!XD 不過那是網頁

推麥子大 居然在PAD版降臨 原來能用這種文釣出來 XDD

不知道的人還是不知道 知道的人早就知道了

邊緣的連珠權值要比較高因為比較不影響盤面運作

竟然在pad板看到sitos大 XD

如果用GA/SA之類的randomized algorithm效果如何呢?先找一個比較差的解，再慢慢mutate到比較短的路徑

竟然在PAD版看到演算法!!

Dijkstra可以保證找到最短路徑 可是計算量會爆炸...不過感覺Dijkstra 應該不適合用在這種轉珠分析上

專業

專業給推

天吶 有沒有這麼專業

原來如此 !!!???!?!?

以這CASE來說 交配跟適應函數都會跟傳統的例子有差

看不懂只能推了

直覺會想用最佳優先搜尋，修正評分函數就好特殊面板或者圖形可以給特定的評分函數基因演算法的部分 交配要用你的例子 要記錄最後位置才能做....適應函數必須要把長度也納入考量至於怎調整到適應函數優化 我想要討論出來 發PAPER比較快

恩 跟我想得差不多

快推 不然人家會以為看不懂

有app可以跑最大三斜轉

基因演算法的部分你誤會我的意思了...我是說紀錄每次位置你在做交配的時候只會用相同位置做組合 可以省去聯不連貫的問題 並且還要交換最後的色珠關於最佳優先搜尋的部分 我們可以一次考慮深度三層事實上多考慮幾層深度 還是要照盤面來看 但是考慮是不需要總之....要是考量最短路徑來看 BFS為最基本的走向

感謝麥大的說明，因為我一開始真的對網頁那種近似瞬間的運算感到不可思議，才會想求解答。看來結論是”漂亮”的演算法與伺服器的暴力破解，這樣理解沒錯吧？

基因演算法的部分你是從交配開始討論，我則是把結果交負適應函數...簡單來說是應函數做的跟評分函數不會差太多BFS的意思是說演算法對於樹的走向....不是完整的跑BFS因為對於路徑來說 樹的高度等於路徑的長度...DFS的走向是不必要的....我想我們可以討論到更細點的部分那你等我晚點有空 基因演算法的部分先回答看完你回應的點 我想你是陷入交配必定產生最好的下一代基因演算法的順序為 交配 突變 適應函數 天擇的順序如果交配必定保留最好的下一代....那後面步驟都可以省略了結論就是.....產生的下一代不一定會最好..至於如何證明近似最佳....請看黑盒子理論....

我以為我走到計算數學版...

基因演算法就是....不用花啥腦袋....省去證明....的方法..ORZ....XDDD 你明白就好了.....不然不會這麼多論文....XD至於你講的A* 我忽然明白我們講的差異在哪我印象中A*都有明確目標....但是在轉珠途中我並沒有如果換成A*的方式 我所講的走向BFS 每次3曾判斷事實上就是A* 每次走一個3*3區域以後 在找最好的HGA強大的地方在於跳脫local optimal...其他部分我不覺得特別突出那就變成最佳搜尋法+登山法...A*在特定條件下就是BFS.....只是名稱不同我會考量深度為3的情況 是假想切珠問題....

記得有個 single player monte-carlo tree search也許可以試試看 (?) XD

tabu哩?