- 浏览: 586130 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
一: 回溯法
有时我们要得到问题的解,先从其中某一种情况进行试探,在试探过程中,一旦发现原来的选择是错误的,那么就退回一步重新选择, 然后继续向前试探,反复这样的过程直到求出问题的解。比喻:“下棋”: 每一次走棋的位置都要考虑到是否是损人利己,如果是害人害己的走法就要回撤,找下一步损人利己的走法。又如玩RPG游戏中碰到“迷宫”大家是怎样出来的?
回溯跟深度优先遍历是分不开的,我们倾向于把回溯看做深度优先遍历的延伸。我们知道,图的深度优先遍历每个节点只会被访问一次,因为我们一旦走过一个点,我们就会做相应的标记,避免重复经过同一个点。而回溯的做法是,当走过某一个点时,标记走过,并把该点压栈;当该节点出栈时,我们再把它标记为没有走过,这样就能保证另外一条路也能经过该点了。
二:"深度优先搜索+回溯"递归框架:
函数DFS(节点){
如果(节点=目标节点) {找到目标,跳出}
遍历所有下一层节点for(int i=0;i<k;i++){
标记下一层节点i已访问;
DFS(下一层的节点i)
恢复i为未访问
}
}
三:举例
题目描述:
在一个4*5的棋盘上,马的起始位置坐标有键盘输入,求马能返回起始位置的不同走法总数并输出每一种走法(马走过的位置不能重复,马走“日”字。
输入输出样例
Sample input
1 1
Simple output
4596
分析:经典回溯。搜索过程是从起点(x,y)出发,按照深度优先的原则,从8个方向中尝试一个个可以走的点,直到返回起点,不能的话,回溯上一点,继续.
程序运行:
D:\tutu>java Main
输入马的起始坐标:
1 1
sx = 1, sy = 1
total=1
5 8 11 2 0
10 1 4 7 0
0 6 9 12 3
0 0 0 0 0
total=2
5 8 0 2 0
10 1 4 7 0
0 6 9 12 3
0 11 0 0 0
total=3
5 8 11 2 0
0 1 4 7 10
0 6 9 12 3
0 0 0 0 0
total=4
5 8 11 2 0
12 1 4 7 10
0 6 9 14 3
0 13 0 0 0
total=5
5 8 0 2 0
0 1 4 7 0
0 6 9 0 3
10 0 0 0 0
total=6
5 8 0 2 0
0 1 4 7 0
9 6 0 0 3
0 0 10 0 0
total=7
...........
total=4595
0 0 0 0 0
4 1 10 7 0
11 8 5 2 0
0 3 12 9 6
total=4596
0 0 0 0 0
4 1 0 0 0
0 0 5 2 0
6 3 0 0 0
源码:
有时我们要得到问题的解,先从其中某一种情况进行试探,在试探过程中,一旦发现原来的选择是错误的,那么就退回一步重新选择, 然后继续向前试探,反复这样的过程直到求出问题的解。比喻:“下棋”: 每一次走棋的位置都要考虑到是否是损人利己,如果是害人害己的走法就要回撤,找下一步损人利己的走法。又如玩RPG游戏中碰到“迷宫”大家是怎样出来的?
回溯跟深度优先遍历是分不开的,我们倾向于把回溯看做深度优先遍历的延伸。我们知道,图的深度优先遍历每个节点只会被访问一次,因为我们一旦走过一个点,我们就会做相应的标记,避免重复经过同一个点。而回溯的做法是,当走过某一个点时,标记走过,并把该点压栈;当该节点出栈时,我们再把它标记为没有走过,这样就能保证另外一条路也能经过该点了。
二:"深度优先搜索+回溯"递归框架:
函数DFS(节点){
如果(节点=目标节点) {找到目标,跳出}
遍历所有下一层节点for(int i=0;i<k;i++){
标记下一层节点i已访问;
DFS(下一层的节点i)
恢复i为未访问
}
}
三:举例
题目描述:
在一个4*5的棋盘上,马的起始位置坐标有键盘输入,求马能返回起始位置的不同走法总数并输出每一种走法(马走过的位置不能重复,马走“日”字。
输入输出样例
Sample input
1 1
Simple output
4596
分析:经典回溯。搜索过程是从起点(x,y)出发,按照深度优先的原则,从8个方向中尝试一个个可以走的点,直到返回起点,不能的话,回溯上一点,继续.
import java.util.*; public class Main { static int array[][] = {{-1, -1, -2, -2, 2, 2, 1, 1},{-2, 2, 1, -1, 1, -1, 2, -2}};//表示马跳的8个方向 private int chess[][];//chess[x][y]=k表示马的第k步的坐标为(x,y) private int total = 0;//统计走法的种数 private int sx, sy;//(sx,sy)表示马的起始坐标 public Main(int sx,int sy){ this.sx=sx; this.sy=sy; chess=new int[4][5]; chess[sx][sy] = 1; } public int getTotal(){ return this.total; } public void find_way(int p1, int p2,int step){//DFS+回溯 int i, pi, pj; for(i = 0; i < 8; i++){//向8个方向试探 pi = p1 + array[0][i]; pj = p2 + array[1][i]; if((sx == pi)&&(sy == pj)){ total++;//找到一种走法,(sx,sy)表示起点 output();//输出走法 } else if( (pi >= 0)&&(pi < 4)&&(pj >= 0)&&(pj < 5)&&(chess[pi][pj] == 0)){//继续试探 chess[pi][pj] = step;//马的第step步的坐标是(pi,pj) find_way(pi, pj,step+1);//从(pi,pj)出发继续找 chess[pi][pj] = 0;// 回溯,恢复未走标志 } }//for } public void output() { System.out.println("total=" + total); for (int y = 0; y < 4; y++) { System.out.println(""); for (int x = 0; x < 5; x++) { System.out.printf("%4d",chess[y][x]); } } System.out.println(""); } public static void main(String args[]){ Scanner sc=new Scanner(System.in); System.out.printf("输入马的起始坐标:\n"); int sx=sc.nextInt(); int sy=sc.nextInt(); System.out.printf("sx = %d, sy = %d\n", sx, sy); if ((sx < 0)||(sx >= 4)||(sy < 0)||(sy >= 5)) System.out.printf("ERROR\n"); else{ Main m=new Main(sx,sy); m.find_way(sx, sy,2);//从起始位置开始试探 // System.out.printf("total = %d\n", m.getTotal()); } } }
程序运行:
D:\tutu>java Main
输入马的起始坐标:
1 1
sx = 1, sy = 1
total=1
5 8 11 2 0
10 1 4 7 0
0 6 9 12 3
0 0 0 0 0
total=2
5 8 0 2 0
10 1 4 7 0
0 6 9 12 3
0 11 0 0 0
total=3
5 8 11 2 0
0 1 4 7 10
0 6 9 12 3
0 0 0 0 0
total=4
5 8 11 2 0
12 1 4 7 10
0 6 9 14 3
0 13 0 0 0
total=5
5 8 0 2 0
0 1 4 7 0
0 6 9 0 3
10 0 0 0 0
total=6
5 8 0 2 0
0 1 4 7 0
9 6 0 0 3
0 0 10 0 0
total=7
...........
total=4595
0 0 0 0 0
4 1 10 7 0
11 8 5 2 0
0 3 12 9 6
total=4596
0 0 0 0 0
4 1 0 0 0
0 0 5 2 0
6 3 0 0 0
源码:
- Main8976543.zip (982 Bytes)
- 下载次数: 1
发表评论
-
龙抬头
2014-11-10 15:06 554... -
求推箱子的最小步数(java)
2014-05-06 08:32 3676题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2990POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3158回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1875很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5829Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3993一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1213一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 1971先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2268一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2228继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4909深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1404如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1108例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1468广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1645有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2069再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2226凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1073最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1235矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
每个集成员可能有一个或多个与之有关联的特征,我们把这些特征称为属性。属性值可以预先给定,也可以是未知的,有待于LINGO求解。例如,产品集中的每个产品可以有一个价格属性;卡车集中的每辆卡车可以有一个牵引力...
算法中最基本和常用的是搜索,主要是回溯和分支限界法的使用。这里要说的是,有些初学者在学习这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉...
回溯法 机器人的运动范围 矩阵中的路径 leetcode刷题 动态规划相关 不用加减乘除作加法 一些公司的题目 推荐阅读 刷题必备 《剑指offer》 《编程之美》 《编程之法:面试和算法心得》 《算法谜题》 都是思维题 基础 ...
推荐的刷题顺序:二叉树—>线性表—>排序算法—>死磕二叉树—>动态规划—>滑动窗口—>回溯法—>其他类型(顺序随意)。一定要先刷二叉树,先刷二叉树,先刷二叉树,重要的事情说三遍。。。 (说一下本人的复习情况
首先从4个数字中有序地选出2个数字,并选择加、减、乘、除 4 种运算操作之一,用得到的结果取代选出的2个数字,剩下3个数字。然后在剩下的3个数字中有序地选出2个数字,并选择 4 种运算操作之一,用得到的结果取代...
《妙趣横生的算法(C语言实现)》可作为算法入门人员的教程,也可以作为学习过C语言程序设计的人士继续深造的理想读物,也可作为具有一定经验的程序设计人员巩固和提高编程水平,查阅相关算法实现和数据结构知识的参考...
leetcode 答案 leetcode 一个星期日穿leetcode 算法与数据结构是面试考察的重中之重,也是大家日后学习时需要着重...回溯法 回溯使用的是递归思想,解的模板 backtrack() if (base case) paths.add; return; foreach(c
第6章 复合数据之一:结构体 34 6.1 结构体 34 6.2 补充练习:绘制简单图形 36 6.3 结构体定义 38 6.4 数据定义 41 6.5 设计处理复合数据的函数 43 6.6 补充练习:圆和长方形的移动 46 6.7 补充练习:刽子手游戏 49 ...
《编程之法:面试和算法心得》 《算法谜题》都是思维题 基础 《 》 《 》 《 》 《 》 《 》 《 》 算法设计 《 》 《算法设计手册》-算法设计手册红皮书 -是一本对算法介绍比较全面的经典书籍 《关于字符...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
他是我国计算机普及和高校计算机基础教育开拓者之一,现任全国高等院校计算机基础教育研究会会长、教育部全国计算机应用技术证书考试委员会主任委员。 谭浩强教授创造了3个世界纪录:(1)20年来他(及和他人合作)...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
他是我国计算机普及和高校计算机基础教育开拓者之一,现任全国高等院校计算机基础教育研究会会长、教育部全国计算机应用技术证书考试委员会主任委员。 谭浩强教授创造了3个世界纪录:(1)20年来他(及和他人合作)...
•其结果可作为一个高层框架被用于需求分析之中。 (2)分析内容 •技术可行性:从技术与技术资源这两个方面作出可行性评估。 •经济可行性:从项目投资和经济效益这两个方面作出可行性评估。 •应用可行性:从法律...
第一部分 基本理论 第2章 听觉机理和汉语语音基础 2. 1 概述 2.2 听觉机理和心理 2.2.1 语音听觉器官的生理结构 2.2.2 语音听觉的心理 2.3 发音的生理机构与过程 2.4 汉语语音基本特性 2.4. 1 元音和辅音 ...