作者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