穷举搜索
实质是创建一个状态树，边建立边剪枝，得到最终状态输出
步骤有：
- 列出表示状态的数据结构
- 列出在状态之间迁移的动作的数据结构
- 列出两个状态转换的所有动作列表
- 创建一个deque存储搜索的状态
- 从deque尾端取出状态，判断是否是最终状态，是的话打印当前deque，进行搜索search，循环所有动作，执行动作searchOnOneAction
- 判断新状态是否有效，有效则加入deque，继续递归调用搜索
有很多问题用到穷举搜索，比如过河问题
三个和尚和三个妖怪过河
船只能载两个
任何时候只要妖怪数量大于和尚数量
妖怪就要吃掉和尚
求解过河方案
这个问题首先确定状态的数据结构，状态就是两岸monk和monster的数量，同时有一些配套操作
- 判断是否是最终状态
- 状态迁移
- 判断状态是否有效
class ItemState{
friend ostream& operator<<(ostream&, const ItemState&);
public:
bool operator==(const ItemState&);
bool isFinalState();
bool takeAction(ItemState& next, const ACTION_EFFECTION& action);
bool isValid();
int local_monster;
int local_monk;
int remote_monster;
int remote_monk;
BOAT_LOCATION boat;
};
动作有如下定义
typedef enum{
ONE_MONSTER_GO = 0,
TWO_MONSTER_GO,
ONE_MONK_GO,
TWO_MONK_GO,
ONR_MONSTER_ONE_MONK_GO,
ONE_MONSTER_BACK,
TWO_MONSTER_BACK,
ONE_MONK_BACK,
TWO_MONK_BACK,
ONR_MONSTER_ONE_MONK_BACK,
INVALID_ACTION_NAME,
}ACTION_NAME;
typedef struct{
ACTION_NAME act;
BOAT_LOCATION boat_to;
int move_monster;
int move_monk;
}ACTION_EFFECTION;
得到action的列表，作为穷举的依据
static ACTION_EFFECTION actEffect[] =
{
{ONE_MONSTER_GO, REMOTE, -1, 0},
{TWO_MONSTER_GO, REMOTE, -2, 0},
{ONE_MONK_GO, REMOTE, 0, -1},
{TWO_MONK_GO, REMOTE, 0, -2},
{ONR_MONSTER_ONE_MONK_GO, REMOTE, -1, -1},
{ONE_MONSTER_BACK, LOCAL, 1, 0},
{TWO_MONSTER_BACK, LOCAL, 2, 0},
{ONE_MONK_BACK, LOCAL, 0, 1},
{TWO_MONK_BACK, LOCAL, 0, 2},
{ONR_MONSTER_ONE_MONK_BACK, LOCAL, 1, 1}
};
搜索时
void searchState(deque<ItemState> &states)
{
int act;
ItemState current = states.back();
if(current.isFinalState())
{
printResult(states);
return;
}
for(act = 0; act < INVALID_ACTION_NAME; act++)
{
//debug_out << act <<endl;
searchStateOnOneAction(states, current, actEffect[act]);
}
}
void searchStateOnOneAction(deque<ItemState> &states, ItemState ¤t, ACTION_EFFECTION& actEff)
{
ItemState next;
bool canTackAction;
canTackAction = current.takeAction(next, actEff);
//debug_out << next;
if(canTackAction && !isProcessed(states, next))
{
//debug_out << "valid" << endl;
// printResult(states);
states.push_back(next);
searchState(states);
states.pop_back();
}
}
两个函数起到了递归的作用，同时使用deque避免出现环路
bool isProcessed(deque<ItemState> &states, ItemState& state)
{
auto it = states.end();
it = find_if(states.begin(), states.end(), [&](ItemState& s){return s==state;});
return(it!=states.end());
}
完整代码见https://github.com/lclei/algorithm_fun/tree/master/MonkAndMonster
最后的找到了四种方案
o stands for monk, and x stands for monster.
3o || 0o
3x || 0x
boat||
3o || 0o
1x || 2x
||boat
3o || 0o
2x || 1x
boat||
3o || 0o
0x || 3x
||boat
3o || 0o
1x || 2x
boat||
1o || 2o
1x || 2x
||boat
2o || 1o
2x || 1x
boat||
0o || 3o
2x || 1x
||boat
0o || 3o
3x || 0x
boat||
0o || 3o
1x || 2x
||boat
0o || 3o
2x || 1x
boat||
0o || 3o
0x || 3x
||boat
o stands for monk, and x stands for monster.
3o || 0o
3x || 0x
boat||
3o || 0o
1x || 2x
||boat
3o || 0o
2x || 1x
boat||
3o || 0o
0x || 3x
||boat
3o || 0o
1x || 2x
boat||
1o || 2o
1x || 2x
||boat
2o || 1o
2x || 1x
boat||
0o || 3o
2x || 1x
||boat
0o || 3o
3x || 0x
boat||
0o || 3o
1x || 2x
||boat
1o || 2o
1x || 2x
boat||
0o || 3o
0x || 3x
||boat
o stands for monk, and x stands for monster.
3o || 0o
3x || 0x
boat||
2o || 1o
2x || 1x
||boat
3o || 0o
2x || 1x
boat||
3o || 0o
0x || 3x
||boat
3o || 0o
1x || 2x
boat||
1o || 2o
1x || 2x
||boat
2o || 1o
2x || 1x
boat||
0o || 3o
2x || 1x
||boat
0o || 3o
3x || 0x
boat||
0o || 3o
1x || 2x
||boat
0o || 3o
2x || 1x
boat||
0o || 3o
0x || 3x
||boat
o stands for monk, and x stands for monster.
3o || 0o
3x || 0x
boat||
2o || 1o
2x || 1x
||boat
3o || 0o
2x || 1x
boat||
3o || 0o
0x || 3x
||boat
3o || 0o
1x || 2x
boat||
1o || 2o
1x || 2x
||boat
2o || 1o
2x || 1x
boat||
0o || 3o
2x || 1x
||boat
0o || 3o
3x || 0x
boat||
0o || 3o
1x || 2x
||boat
1o || 2o
1x || 2x
boat||
0o || 3o
0x || 3x
||boat
