商人过河问题的python递归解法

最近上课老师提到商人过河这个经典的智力问题,留给我们作课后作业。直觉告诉我直接用python岂不是分分钟的事,于是就直接用python递归开始实现。由于深受C的影响,中途发现python递归比起C语言递归实现起来差别不小。趁热打铁,这里就把求解过程记录下来。

目录

问题描述

三名商人各带一个随从乘船渡河,一只小船只能容纳二人,由他们自己划行。随从们密约,在河的任意一岸,一旦随从的人数比商人多,就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢?

求解思路

首先需要把这个问题用数学语言表示出来。商人与随从过河的过程,就是两岸人数状态不断变化的一个过程。我们可以用坐标(商人,随从)来表示源河岸当前的人数状态。
初始状态,设源河岸商人和随从均为N人,表示为:

1
start_point = [N,N]     # starting point

中间过程,船往返于两岸之间一次,两岸的人数变化一次。这个步骤中的每一次往返都涉及到两个因素,一是船的方向direct,二是对该次上船人员的决策decision。当船的方向是从源河岸驶向对面目的地时,可以表示为:

1
2
derict = 1   # at source river bank
src_decision = [[-2,0], [-1,0], [-1,-1], [0,-1], [0,-2]]

当船返回源河岸时:

1
2
derict = -1     # at dst river bank 
dst_decision = [[1,0], [2,0], [1,1], [0,1],[0,2]]

成功渡河后,源河岸随从和商人均为0人。

1
END = [0, 0]        # destation point

递归搜索

船往返于两岸之间,岸上人数的变化对应与坐标上的一个个点。需要把已经到达过状态记录下来,防止后面再次重复已经搜索过的路线:

1
2
src_reached_list = []
dst_reached_list = []

已经搜索过的状态以参数的形式传入递归搜索。此外,还需要传入的参数有当前状态下源岸边的人数,当前方向以及该方向对应的可行的决策。递归代码如下:

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
# return 0: success
# 1: not found
# 2: error
def SearchCrossRiver(start_p, derict, src_reached, dst_reached):
s_reached = copy.deepcopy(src_reached)
d_reached = copy.deepcopy(dst_reached)

if derict == 1:
if start_p not in s_reached:
s_reached.append(start_p)

for decison in src_decision:
point = []
for i in xrange(2):
point.append(start_p[i]+decison[i])
if point == END:
print "It succesed !!"
result_path.append(s_reached)
result_path.append(d_reached)
return 0
elif (point in restrict_point_list) and (point not in d_reached):
SearchCrossRiver(point, -1, s_reached, d_reached)
else:
pass
return 1

elif derict == -1:
if start_p not in d_reached:
d_reached.append(start_p)

for decison in dst_decision:
point = []
for i in xrange(2):
point.append(start_p[i] + decison[i])
if point == END:
result_path.append(s_reached)
result_path.append(d_reached)
return 0
elif (point in restrict_point_list) and (point not in s_reached):
SearchCrossRiver(point, 1, s_reached, d_reached)
else:
pass
return 1
else:
print "error"
return 2

求解结果

可以得到四组结果。每组结果由source reached point序列和dst reached point序列构成。

1
2
3
4
5
6
7
8
9
10
11
12
13
 [
[[3, 3], [3, 2], [3, 1], [2, 2], [0, 3], [1, 1]],
[[2, 2], [3, 0], [1, 1], [0, 2], [0, 1]],

[[3, 3], [3, 2], [3, 1], [2, 2], [0, 3], [0, 2]],
[[2, 2], [3, 0], [1, 1], [0, 2], [0, 1]],

[[3, 3], [3, 2], [3, 1], [2, 2], [0, 3], [1, 1]],
[[3, 1], [3, 0], [1, 1], [0, 2], [0, 1]],

[[3, 3], [3, 2], [3, 1], [2, 2], [0, 3], [0, 2]],
[[3, 1], [3, 0], [1, 1], [0, 2], [0, 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
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
import os
import sys
import copy

N = 3 # Total people number
END = [0, 0] # destation point

# goble decison
src_decision = [[-2,0], [-1,0], [-1,-1], [0,-1], [0,-2]]
dst_decision = [[1,0], [2,0], [1,1], [0,1],[0,2]]

# global AVAIABLE point
restrict_point_list = []

# global list to record suceess path
result_path = []

def init_restrict_point():
for y in range(0,N+1):
a = [0,y]
restrict_point_list.append(a)
for x in range(1,N):
a = [x,x]
restrict_point_list.append(a)
for y in range(0,N+1):
a = [N,y]
restrict_point_list.append(a)

# return 0: success
# 1: not found
# 2: error
def SearchCrossRiver(start_p, derict, src_reached, dst_reached):
s_reached = copy.deepcopy(src_reached)
d_reached = copy.deepcopy(dst_reached)

if derict == 1:
if start_p not in s_reached:
s_reached.append(start_p)

for decison in src_decision:
point = []
for i in xrange(2):
point.append(start_p[i]+decison[i])
if point == END:
print "It succesed !!"
result_path.append(s_reached)
result_path.append(d_reached)
return 0
elif (point in restrict_point_list) and (point not in d_reached):
SearchCrossRiver(point, -1, s_reached, d_reached)
else:
pass
return 1

elif derict == -1:
if start_p not in d_reached:
d_reached.append(start_p)

for decison in dst_decision:
point = []
for i in xrange(2):
point.append(start_p[i] + decison[i])
if point == END:
result_path.append(s_reached)
result_path.append(d_reached)
return 0
elif (point in restrict_point_list) and (point not in s_reached):
SearchCrossRiver(point, 1, s_reached, d_reached)
else:
pass
return 1
else:
print "error"
return 2

def find_function():
start_point = [N,N] # starting point
init_restrict_point()

src_reached_list = []
dst_reached_list = []

result = SearchCrossRiver(start_point, 1, src_reached_list, dst_reached_list)
print "result = ", result_path
print '\n'

if __name__ == '__main__':
find_function()
0%