其主要思想是,在解空间树(状态空间树)上动态、随机的产生一条路径,然后沿此路径来估算解空间树中所有满足约束条件的节点总数(这里计算的是最差时间复杂度,假设要走遍所有满足约束条件的节点)。
...此时,假设我们随机选择了当前可行的1号位置;
在第一行的基础上,我们有5种选择(3, 4, 5, 6, 7),这时可以“草率的”假设:对于每一种第一行的可行的选择(8种),我们在第二行都有5种不同的选择...此时,假设我们随机选择了当前可行的3号位置;
在前两行的基础上,我们有4种选择(0, 5, 6, 7),这时可以“草率的”假设:对于每一种前两行的可行排列(8*5=40),我们在第三行都有4种不同的选择...此时,假设我们随机选择了当前可行的0号位置;
在前三行的基础上,我们有3种选择(2, 6, 7),这时可以“草率的”假设:对于每一种前三行的可行排列(8*5*4=160),我们在第四行都有3种不同的选择...此时,假设我们随机选择了当前可行的2号位置;
在前四行的基础上,我们有2种选择(4, 7),这时可以“草率的”假设:对于每一种前四行的可行排列(8*5*4*3=480),我们在第四行都有3种不同的选择,