实质是创建一个状态树，边建立边剪枝，得到最终状态输出
步骤有：

  1. 列出表示状态的数据结构
  2. 列出在状态之间迁移的动作的数据结构
  3. 列出两个状态转换的所有动作列表
  4. 创建一个deque存储搜索的状态
  5. 从deque尾端取出状态，判断是否是最终状态，是的话打印当前deque，进行搜索search，循环所有动作，执行动作searchOnOneAction
  6. 判断新状态是否有效，有效则加入deque，继续递归调用搜索

有很多问题用到穷举搜索，比如过河问题

三个和尚和三个妖怪过河
船只能载两个
任何时候只要妖怪数量大于和尚数量
妖怪就要吃掉和尚
求解过河方案

这个问题首先确定状态的数据结构，状态就是两岸monk和monster的数量，同时有一些配套操作

  • 判断是否是最终状态
  • 状态迁移
  • 判断状态是否有效
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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;
};

动作有如下定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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的列表，作为穷举的依据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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}
};

搜索时

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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 &current, 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避免出现环路

1
2
3
4
5
6

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

最后的找到了四种方案

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195

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