Re: [問題] 如何儘量不Search 到重覆的Branch

[Pjack (pjack)]

※ 引述《Pjack (pjack)》之銘言：
:   最近在玩一套Boardgame 叫Titan
:   他的戰鬥地圖可以在這邊找到 http://colossus.sourceforge.net/
:   就是由一堆六角形形成一個大六角形的地圖
:   目前我想做的事是當生物上戰場時, 用電腦找出他所有能走的路徑
:   我簡單講一下戰鬥的規則, 他大至上分為兩個phase
:   第一個 phase 是移動, 第二個 phase 是攻擊, 必須要全部移動完才進行攻擊
:   每隻生物的移動力不完全相同, 他可以選擇不動或是移動到某一個地方
:   每隻生物只能動一次, 但每次的移動都必須有合理的行徑路線
:   例如不會飛的生物甲, 他前方剛好有自己的同伴乙擋著他的路
:   他如果想前進, 就必須要先移走同伴乙, 然後自己再來移動, 或者是趬遠路
:   所以我的問題就是先移動甲再移動乙, 和先移動乙再移動甲可能會產生同樣的版面
:   在Search 這些路徑時, 如果能夠儘量不重覆Search 到同樣的版面
:   將可以節省大量的時間
:   請大家幫忙想看看囉
:   如果這問題不適合在這裡, 請版主不用客氣:)



   有人推文說聽不懂

   改個例子解釋好了, 象棋原本一次只能走一隻

   現在如果改了規則, 一次走二隻, 以電腦來Search 的話

   一定是先試動甲再動乙, 然後再試先動乙再動甲

   但這兩種情況內常有重覆的盤面, 現在就是希望能不能有什麼方法

   可以不要Search 到重覆的盤面

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.123.68
※ 編輯: Pjack           來自: 218.166.123.68       (07/04 18:22)
→ sagarain:同時搜索是不可能吧 所以要兩個搜尋完再對照
→ sagarain:原po有學過演算法嗎
推 alex2202:把資料put到一個set裡然後再check有沒有重覆     218.184.120.29 07/07
→ Pjack:我是希望連Search 都不要Search 到重覆的盤面
→ Pjack:而不是用hash table 來檢查有沒有重覆
→ Pjack:回sagarain, 有學過, 所以如果有好的idea, 請告知