作者Pjack (pjack)
看板puzzle
標題Re: [問題] 如何儘量不Search 到重覆的Branch
時間Mon Jul 4 18:22:19 2005
※ 引述《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)
1F：→ sagarain:同時搜索是不可能吧 所以要兩個搜尋完再對照 218.14.1.121 07/07
2F：→ sagarain:原po有學過演算法嗎 218.14.1.121 07/07
推 alex2202:把資料put到一個set裡然後再check有沒有重覆 218.184.120.29 07/07
3F：→ Pjack:我是希望連Search 都不要Search 到重覆的盤面218.166.121.129 07/10
4F：→ Pjack:而不是用hash table 來檢查有沒有重覆218.166.121.129 07/10
5F：→ Pjack:回sagarain, 有學過, 所以如果有好的idea, 請告知218.166.121.129 07/10