窮舉搜索
實質(zhì)是創(chuàng)建一個狀態(tài)樹，邊建立邊剪枝，得到最終狀態(tài)輸出
步驟有：
- 列出表示狀態(tài)的數(shù)據(jù)結(jié)構(gòu)
- 列出在狀態(tài)之間遷移的動作的數(shù)據(jù)結(jié)構(gòu)
- 列出兩個狀態(tài)轉(zhuǎn)換的所有動作列表
- 創(chuàng)建一個deque存儲搜索的狀態(tài)
- 從deque尾端取出狀態(tài)，判斷是否是最終狀態(tài)，是的話打印當(dāng)前deque，進行搜索search，循環(huán)所有動作，執(zhí)行動作searchOnOneAction
- 判斷新狀態(tài)是否有效，有效則加入deque，繼續(xù)遞歸調(diào)用搜索
有很多問題用到窮舉搜索，比如過河問題
三個和尚和三個妖怪過河
船只能載兩個
任何時候只要妖怪?jǐn)?shù)量大于和尚數(shù)量
妖怪就要吃掉和尚
求解過河方案
這個問題首先確定狀態(tài)的數(shù)據(jù)結(jié)構(gòu)，狀態(tài)就是兩岸monk和monster的數(shù)量，同時有一些配套操作
- 判斷是否是最終狀態(tài)
- 狀態(tài)遷移
- 判斷狀態(tài)是否有效
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的列表，作為窮舉的依據(jù)
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();
}
}
兩個函數(shù)起到了遞歸的作用，同時使用deque避免出現(xiàn)環(huán)路
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
