Python代码
: 猜数字游戏8步以内的完全求解决策树生成程序
001
#coding=utf-8
002
003
#猜数字游戏8步以内的求解决策树生成程序
004
# 解题思路与一步步的解题程序参见:
005
# http://www.fayaa.com/code/view/116/
006
#
007
008
#使用方法:
009
# 1. 保存代码为guessall.py
010
# 2. 执行python guessall.py > result.txt
011
# 3. 打开result.txt看结果
012
013
#为了可读性和简单性使用了列表推导,其他方法参见:
014
# http://www.fayaa.com/code/view/114/
015
# http://www.fayaa.com/code/view/118/
016
def
init_set
():
017
r10
=
range
(
10
)
018
return
[(
i
,
j
,
k
,
l
)
019
for
i
in
r10
for
j
in
r10
for
k
in
r10
for
l
in
r10
020
if
(
i
!=
j
and
i
!=
k
and
i
!=
l
and
j
!=
k
and
j
!=
l
and
k
!=
l
)
]
021
022
#对给定的两组数,计算xAyB
023
#不知道能不能更快些
024
def
get_match_ab
(
target
,
source
):
025
la
,
lb
=
0
,
0
026
for
(
i
,
t
)
in
enumerate
(
target
):
027
for
(
j
,
s
)
in
enumerate
(
source
):
028
if
s
==
t
:
029
if
i
==
j
:
030
la
+=
1
031
else
:
032
lb
+=
1
033
#break this loop since we already found match
034
break
035
return
(
la
,
lb
)
036
037
#by lancer
038
#思路很好,把原来的16次比较变成了8次
039
#经过timeit验证确实速度有所提高
040
def
get_match_ab2
(
target
,
source
):
041
table
=
[
-
1
]
*
10
042
la
,
lb
=
0
,
0
043
for
i
in
xrange
(
len
(
source
)):
044
table
[
source
[
i
]]
=
i
045
for
i
in
xrange
(
len
(
target
)):
046
if
table
[
target
[
i
]]
==
i
:
047
la
+=
1
048
elif
table
[
target
[
i
]]
!=
-
1
:
049
lb
+=
1
050
return
(
la
,
lb
)
051
052
#nums: the number_set list to be checked
053
#guess: last guess
054
#a, b: the number of aAbB
055
#@return: the rest number_sets which matche last guess
056
def
check_and_remove
(
nums
,
guess
,
a
,
b
):
057
rest_nums
=
[]
058
for
num_set
in
nums
:
059
if
(
a
,
b
)
==
get_match_ab
(
num_set
,
guess
):
060
rest_nums
.
append
(
num_set
)
061
return
rest_nums
062
063
#计算在nums中选择target以后,所有ab分支里面的剩余组合个数
064
def
calc_ab_counts
(
target
,
nums
):
065
#a * 10 + b is used to indicate an "a & b" combination
066
ab_map
=
{}
067
#init ab_map
068
abs
=
(
0
,
1
,
2
,
3
,
4
,
10
,
11
,
12
,
13
,
20
,
21
,
22
,
30
,
31
,
40
)
069
for
ab
in
abs
:
070
ab_map
[
ab
]
=
0
071
#let's do the calculation
072
for
num_set
in
nums
:
073
(
a
,
b
)
=
get_match_ab
(
num_set
,
target
)
074
ab_map
[
a
*
10
+
b
]
+=
1
075
return
[
ab_map
[
ab
]
for
ab
in
abs
]
076
077
#计算一个选择相对于选择集的“标准差”
078
def
calc_standard_deviation
(
target
,
nums
):
079
ab_counts
=
calc_ab_counts
(
target
,
nums
)
080
total
=
sum
(
ab_counts
)
081
avg
=
float
(
total
)
/
len
(
ab_counts
)
082
sd
=
sum
([(
abc
-
avg
)
**
2
for
abc
in
ab_counts
])
083
return
sd
084
085
#根据现有集合寻找下一个集合
086
#采用“最小标准差”作为衡量标准
087
def
next_guess
(
nums
):
088
min_sd
=
0
089
min_set
=
()
090
touched
=
False
091
for
num_set
in
nums
:
092
sd
=
calc_standard_deviation
(
num_set
,
nums
)
093
if
not
touched
or
min_sd
>
sd
:
094
touched
=
True
095
min_set
=
num_set
096
min_sd
=
sd
097
return
min_set
098
099
#根据现有集合寻找下一个集合
100
#随机选取,会有4-5个超过八次
101
def
next_guess2
(
nums
):
102
return
nums
[
0
]
103
104
#折衷的方法:小于500用最小标准差
105
def
next_guess3
(
nums
):
106
if
len
(
nums
)
>
500
:
107
return
next_guess2
(
nums
)
108
else
:
109
return
next_guess
(
nums
)
110
111
#计算熵
112
import
math
113
def
calc_entropy
(
target
,
nums
):
114
ab_counts
=
calc_ab_counts
(
target
,
nums
)
115
total
=
sum
(
ab_counts
)
116
hs
=
[]
117
for
abc
in
ab_counts
:
118
h
=
0
119
if
abc
:
120
p
=
float
(
abc
)
/
total
121
h
=
p
*
math
.
log
(
p
,
2
)
122
hs
.
append
(
h
)
123
return
sum
(
hs
)
124
125
#使用信息量作为衡量标准
126
def
next_guess4
(
nums
):
127
min_sd
=
0
128
min_set
=
()
129
touched
=
False
130
for
num_set
in
nums
:
131
sd
=
calc_entropy
(
num_set
,
nums
)
132
if
not
touched
or
min_sd
>
sd
:
133
touched
=
True
134
min_set
=
num_set
135
min_sd
=
sd
136
return
min_set
137
138
#决策树生成思路
139
#1. 生成所有的四位0-9数字组合,用0123做初始选择,空列表queue=[], result={}
140
# result: (当前选择, {21:(下一个选择, {})}, 13:abcd<最终结果值>, ...})
141
# queue: [(rest_nums, 对应当前猜测状态的result节点), ...]
142
分享到:
相关推荐
在Matlab中利用避圈法(Kruskal算法、克鲁斯卡尔算法)求解图的最小生成树的程序
利用决策树求解回归问题,比较不同的depth下,决策树的效果
多种方法求解最小生成树问题的PDF文件 赋权有向图的最小生成树算法; 基于Kruskal算法的最小生成树的构建; 普里姆算法和克鲁斯卡尔算法构造最小生成树; 用遗传算法求最小生成树等。
设计程序完成如下功能:对于任意给定的的网和起点,用PRIM算法的基本思想求解出所有的最小生成树。
WinQSB求解决策分析问题,WinQSB求解决策分析问题,WinQSB求解决策分析问题
利用普里姆算法求解最小生成树 利用普里姆算法求解最小生成树 利用普里姆算法求解最小生成树
一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。 当用联通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的...
摘要:本文讨论了猜数字游戏的计算机求解的若干种策略,研究了如何减少平均猜测次数,优化启发式算法的运行效率,并以C++高效的实现了文中提及的算法。关键词:筛选法,
kruscal与Prim算法,两种经典的最小生成树算法,编译通过,代码含义明确(C++)
提出了一种基于混合决策树的调度知识获取算法...使用决策树评价混合方法中染色体编码的适应度,在得到不同调度目标下的最优特征子集和最优决策树参数后,生成调度知识。仿真实验结果表明,该算法在性能上优于其他算法。
摘要:本文讨论了猜数字游戏的计算机求解的若干种策略,研究了如何减少平均猜测次数,优化启发式算法的运行效率,并以 C++高效的实现了文中提及的算法。关键词:筛选法
用C语言、C++、数据结构编写算法实现图的遍历与最小生成树求解实现,带说明书、程序及任务书。
[MATLAB] Kruskal算法 最小生成树 求解最优树 源码程序 包含最全注释
手机智力游戏 数字九宫格 sudoku 求解算法 栈算法 非递归 手机 智力 游戏 数字九宫格 sudoku 求解 源码 算法 递归 堆栈 堆 栈 数据结构 (没有写过1000行以上代码者 请绕行,别浪费自己的时间!分不清堆和栈者靠边站...
本代码用面向对象的VC++,运用遗传算法求解最小生成树问题
最小生成树问题时指在由m个节点和n条边组成的网络模型中寻找连接所有节点的生成树,使得其所有边的权值之和最小。最小生成树问题广泛应用于系统设计、选址规划等组合优化问题中。
要求: 1. 先任意创建一个图; 2. 图的DFS,BFS的递归和非递归算法的实现 3. 最小生成树(两个算法)的实现,求连通分量的实现 4. 要求用邻接矩阵、邻接表、十字链表等多种结构存储实现
求解线性规划LINGO程序,约束180个左右,变量100个左右!
改进的生成树算法求解旅行商问题,南小康,赵媛,给出了一种基于最小生成树的TSP求解算法,该算法结合贪心算法和匹配算法,把传统近似算法的局部最优转化为全局最优,避免了最邻近
关于构建最小生成树的实验报告,里面是C代码,有详细的过程描述,PRIM算法