最优性减枝

我们在搜索时常常会进行减枝操作，通常我们的减枝分为两种，一种是我们判断是否越界的可达性减枝，一种是能够抵达最终的答案，但是耗费的代价太过于高昂，我们将其进行最优性减枝。

举个例子，我们要从乳山走到青岛，你如果乘坐汽车去，结果出了青岛，这是否就是远离我们得到目的地了，这个时候我们就将这条路线舍去，因为它超出我们的目的地了，这就是无法抵达目的地的可达性减枝。另一种情况是，我们到青岛一号路线是走500公里，二号路线是700公里，如果你选择二号路线当走到501公里时，你就会发现不合适，因为已经超出一号路线的花费了。所以这就是最优性减枝

来个题把，考虑一下最优性的减枝。

注意本题最优性减枝会在第一个点超时，我们设置ww标记点，一旦超过我们设定的次数就会结束程序。这题的最优其实是dfs

P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {	
  public static void main(String[] args) throws NumberFormatException, IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] aStrings=br.readLine().split(" ");
bb=Integer.parseInt(aStrings[0]);
start=Integer.parseInt(aStrings[1]);
end=Integer.parseInt(aStrings[2]);
String[] bStrings=br.readLine().split(" ");
aa=new int[bb+1];
check=new int[bb+1];
int a;
for(a=1;a<=bb;a++) {
	aa[a]=Integer.parseInt(bStrings[a-1]);
}
dfs(start, 0);
check[start]=1;
if(answer==Integer.MAX_VALUE){
	System.out.println("-1");
	return;
}
System.out.println(answer);
  }
public static int answer=Integer.MAX_VALUE;//设为最大值
public static int[] aa;//记录电梯的上升下降几楼
public static int bb;//电梯的最大楼层
public static int[] check;//这个层是否被到达过
public static int start,end;
public static int www=0;//设计dfs跑几次
public static void dfs(int louceng,int a) {
	www++;
	if(www>=10000000) {
		return;//大于设定次数，结束dfs
	}
	if(louceng==end) {
		answer=Math.min(answer, a);//到达指定楼层记录
	}
	if(louceng<=0||louceng>bb) {//到达楼层不合理推退出
		return;
	}
	if(a>answer) {//当前答案大于已经搜到的的答案，推出
		return;
	}
	//System.out.println(a+"  "+louceng);
	if(louceng+aa[louceng]>=1&&louceng+aa[louceng]<=bb&&check[louceng+aa[louceng]]!=1) {
		check[louceng+aa[louceng]]=1;//往上探索
		//System.out.println("AAA"+" "+bb);
	dfs(louceng+aa[louceng] ,a+1);
	check[louceng+aa[louceng]]=0;
	}
	
if(louceng-aa[louceng]>=1&&louceng-aa[louceng]<=bb&&check[louceng-aa[louceng]]!=1) {
	check[louceng-aa[louceng]]=1;//往下探索
	//System.out.println("BB");
	dfs(louceng-aa[louceng], a+1);
	check[louceng-aa[louceng]]=0;
	}
}
}