`

SRM646 DIV2——分支限界搜索题

阅读更多
package srm646;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class TheGridDivTwo {

	//<1>state的比较函数,是"大于>"即大的在前面,属于降序排序
	//<2>比较函数在 score-step,这个是启发是搜索策略,可以让搜索,尽量向右搜索,而不是向左,即有一定的方向性。
	//当然,如果直接基于score排序,这也是可以的,但性能应该差一些。
	static public class State implements Comparator<State>,Comparable<State> {
		public State() {

		}

		public State(int x, int y, int score) {
			this.x = x;
			this.y = y;
			this.score = score;
		}

		int x;
		int y;
		int score;
		int step;

		@Override
		public int compare(State o1, State o2) {
			// TODO Auto-generated method stub
			if (o1.score-o1.step < o2.score-o2.step) {
				return 1;
			}
			if (o1.score-o1.step == o2.score-o2.step) {
				return 0;
			}
			return -1;
		}
		@Override
		public String toString(){
			return "{"+x+","+y+","+score+","+step+"}";
		}

		@Override
		public int hashCode() {
			return x ^ y;
		}

		@Override
		public boolean equals(Object src) {
			return src != null && src instanceof State && ((State) src).x == x
					&& ((State) src).y == y;
		}

		@Override
		public int compareTo(State o) {
			if (score -step< o.score-step) {
				return 1;
			}
			if (score-step == o.score-step) {
				return 0;
			}
			return -1;
		}
	}

	public int find(int[] x, int[] y, int k) {
		int ans = 0;

		Set<State> blockedMap = new HashSet<State>();
		for (int i = 0; i < x.length; i++) {
			blockedMap.add(new State(x[i], y[i], 0));
		}

		State start = new State();
		start.x = 0;
		start.y = 0;
		start.score = 0;
		start.step = 0;
		State maxState = new State(0, 0, 0);
		PriorityQueue<State> pq = new PriorityQueue<State>();
		Set<State> visited = new HashSet<State>();
		pq.add(start);
		visited.add(start);
	
		while (!pq.isEmpty()) {
			State cur = pq.poll();
			if (cur.step > k) {
				continue;
			}
			
			if (maxState.score < cur.score) {
				maxState.score = cur.score;
				maxState.x = cur.x;
				maxState.y = cur.y;
				maxState.step = cur.step;
			}
			//后面的得分会更小(这个是分支限界,剪枝策略)
			if(cur.score + k - cur.step <= maxState.score){
				continue;
			}
			if (cur.step < k) {
				// [cur.x+1][cur.y+1]
				State next = null;
				next = new State(cur.x + 1, cur.y, cur.score + 1);
				next.step = cur.step + 1;
				if (!blockedMap.contains(next)) {
					if (!visited.contains(next)) {
						pq.add(next);
						visited.add(next);
					}
				}

				next = new State(cur.x - 1, cur.y, cur.score -1);
				next.step = cur.step + 1;
				if (!blockedMap.contains(next)) {
					if (!visited.contains(next)) {
						pq.add(next);
						visited.add(next);
					}
				}

				next = new State(cur.x, cur.y + 1, cur.score);
				next.step = cur.step + 1;
				if (!blockedMap.contains(next)) {
					if (!visited.contains(next)) {
						pq.add(next);
						visited.add(next);
					}
				}
				next = new State(cur.x, cur.y - 1, cur.score);
				next.step = cur.step + 1;
				if (!blockedMap.contains(next)) {
					if (!visited.contains(next)) {
						pq.add(next);
						visited.add(next);
					}
				}
			}
		}
		System.out.println(maxState);
		ans = maxState.score;
		return ans;
	}
	
	public static void main(String args[])
	{
		TheGridDivTwo div2= new TheGridDivTwo();
		int ans = div2.find(new int[]{1,1,1,1},
						new int[]{-2,-1,0,1},4);
		
		System.out.println(ans);
		ans = div2.find(new int[]{1,0,0,-1,-1,-2,-2,-3,-3,-4,-4},
		new int[]{0,-1,1,-2,2,-3,3,-4,4,-5,5},47);
		System.out.println(ans);
		
	}
}

这是SRM646 的div2 题,刚开始,比较函数写成了<,后修改为降序排列,但没改正确,检查很多遍都没有发现。

 

这是一个基本的穷举搜索过程,但在brute-force search中可以加入一些策略,比如启发式的(score-step),这个也算A*,再加入一个限界,用于剪枝

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics