`

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*,再加入一个限界,用于剪枝

分享到:
评论

相关推荐

    TC SRM 388 div 2 problem 3

    topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 &lt;= K &lt;= 1000.

    SRM2Mult_1.2_srm2_compositionqw7_

    SRM2Multi dumper for hsap

    VMWARE SRM快速部署手册

    2. **SRM服务器**:运行SRM软件的物理或虚拟服务器,操作系统需为Server 2008 x64。 3. **支持SRM的数据库**:这里指能够被SRM兼容的数据库系统,例如SQL Server 2005。该数据库用于存储SRM的相关配置信息。 4. **...

    2007年《华为》——c语言笔试题

    因此,`a[2]`被赋值为2,然后`a[2]`的值(也就是2)被赋给`a[2]`,所以数组的第三个元素值未变。 6. 多级指针数组的内存占用: 定义`int **a[3][4]`表示一个3x4的二维数组,其中每个元素都是指向指针的指针。在32...

    BS ISO IEC 24392-2023 网络安全——工业互联网平台安全参考模型(SRM-IIP).rar

    BS ISO IEC 24392-2023 网络安全——工业互联网平台安全参考模型(SRM-IIP).rar

    SRM SRM 平台功能介绍.pdf

    SAP SRM 介绍

    Installation Guide for SAP SRM 7.0 EHP2 -

    描述部分简单地重复了标题中的关键词“安装指南”,进一步强调了文档的主要目的——指导用户完成SAP SRM 7.0 EHP2的安装流程。 ### 标签:“sap” 标签“sap”明确了文档的主题是关于SAP软件,这是一个全球领先的...

    HASP-SRM-emulator-D.rar_SRM_SRM emulator_emulator_emulator hasp_

    Driver HASP SRM emulator (x86)

    omron系列CPM1/CPM1A/CPM2A/CPM2C/SRM1(-V2) PLC编程手册.pdf

    2. OMRON产品命名约定:OMRON公司产品的型号在本手册中都是以大写形式出现,包括“CPM1”,“CPM1A”,“CPM2A”,“CPM2C”,“SRM1(-V2)”等。这可能是为了方便阅读时对产品型号的快速识别。此外,手册中提到的...

    分享华为笔试题——绝对推荐,绝对好东西

    答:我不知道这段代码的具体功能,但明显有两个错误1,SRM_no 没有赋初值2,由于 static 的声明,使该函数成为不可重入(即不可预测结果)函数,因为 SRM_no 变量放在程序的全局存储区中,每次调用的时候还可以保持...

    SRM-MDM Catalog Setup – Ready Reference

    根据给定的文件信息,我们将深入探讨“SRM-MDM Catalog Setup – Ready Reference”这一主题,专注于SAP NetWeaver MDM系统中的SRM-MDM目录设置过程。这份文档不仅适用于SAP SRM(Supplier Relationship Management...

    irq_srm.rar_SRM_The Handle

    《SRM中的中断处理——以"irq_srm.rar_SRM_The Handle"为焦点》 在计算机系统中,中断处理是操作系统核心功能之一,它负责响应硬件设备发送的信号,以便进行相应的处理。当我们谈论"irq_srm.rar_SRM_The Handle"时...

    srm image segmentation code

    2. **边界长度**:`srm_boundarylen.cpp`可能是用于计算相邻区域边界的长度,这是评估区域合并代价的另一个因素。较长的边界通常意味着更高的合并成本,因为这会引入更多的不确定性。 3. **SRM主程序**:`srm.m`是...

    SRM影像分割的mtalab程序

    首先,我们关注到主要的函数文件——`SRM_new.m`,这通常是整个程序的入口点,包含了SRM影像分割的主要逻辑。在这个文件中,开发者可能定义了阈值设定、区域合并策略以及其它与分割相关的算法步骤。用户可以根据需求...

    SAP NetWeaver MDM – SRM Catalog Configuration

    ### SAP NetWeaver MDM – SRM Catalog Configuration #### 概述 本文档旨在总结配置SRM源系统向MDM系统提供产品目录数据的过程,这些数据将发布到SRM买家门户的EBP前端。文档主要通过截图的形式展示了配置步骤,...

    HASP SRM加密狗简介

    HASP SRM加密狗简介 HASP SRM加密狗是一种软件保护解决方案,由阿拉丁公司开发。它提供了多种型号,以满足不同业务需要。下面将对HASP SRM加密狗的各种型号进行详细介绍。 首先是HASP HL基本型,这是阿拉丁公司最...

    VSAN和SRM.rar

    【标题】"VSAN与SRM"涉及到的是VMware虚拟化环境中的两个关键组件:Virtual SAN(VSAN)和Site Recovery Manager(SRM)。这两个工具在企业级数据中心中发挥着至关重要的作用,确保业务连续性和灾难恢复能力。 VSAN...

    SAP SRM用途以及功能简介

    2. 扩展、加强与重要供应商的关系:SRM 能够帮助企业与其建立合作关系,共享计划、产品设计和规范信息,并运作方式上进行改进。 3. 建立竞争优势:SRM 能够主动地帮助企业去建立、改进与供应商之间的战略同盟,不是...

Global site tag (gtag.js) - Google Analytics