试探算法思想

试探算法也称为回溯法，它是一种系统地搜索问题解的方法。例如在棋手思考下一步该走哪里时，就是采用试探算法：首先试想下一步所在的位置，计算对手的应对，在计算自己的对应，若对手应对与我不利，则取消该下一步设想，然后重新计算另一个下一步的位置。从一条路往前走，能进则进，不能进则退回来，换一条路再试。

1算法思路

1、定义一个解空间，它包含问题的解。

2、利用适于搜索的方法组织解空间。

3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

对解集合中的各个解进行试探

{

if(满足条件)

{

保存结果

if(完成集合中所有解的试探)

输出解

else

重复本过程进行下一步的试探(递归调用本函数)

}else{

恢复至上一部保存结果之前的状态，进行另一步试探(递归调用本函数)

}

}

2.实例：生成彩票号码组合

常见的彩票号码都是由一些数字组成的，生成彩票号码其实就是将所有数字进行不同的组合。例如，假设有一种彩票，每注由7个1-29的数字组成，且这七个数字不能重复。

package练习;public class 试探法生成彩票 {;//控制台输出时候显示会有一定缓存，所有结果不一定对，但是算法一定对的

public static int MAX_=7;public static int NUM_=29;public static int num[]=new int[NUM_];public static int lottey[]=new int[MAX_];public static voidmain(String[] args) {for(int i=0;i

num[i]=i+1;

}for(int i=0;i

lottey[i]=0;

}

conbine(NUM_,MAX_);

}public static void conbine(int nUM_2, intmAX_2) {//TODO Auto-generated method stub

for(int i=nUM_2;i>=mAX_2;i--){

lottey[mAX_2-1]=num[i-1];if(mAX_2>1){

conbine(i-1,mAX_2-1);

}else{for(int c=MAX_-1;c>=0;c--)

System.out.print(lottey[c]+" ");

System.out.println();

}

}

}

}

结果：

...

29 28 18 15 14 6 5

29 28 18 15 14 6 4

29 28 18 15 14 6 3

29 28 18 15 14 6 2

29 28 18 15 14 6 1

29 28 18 15 14 5 4

29 28 18 15 14 5 3

29 28 18 15 14 5 2

29 28 18 15 14 5 1

...