`
ansjsun
  • 浏览: 199088 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

算法实现系列第四章.启发式搜索_A*搜索

阅读更多

..很郁闷启发式搜索和A*搜索.自己对照文档写了下..发现和之前学的有出入...算了先写这个吧..等我回去翻翻笔记...如果有问题再来补充..明白的同学可以直接拍砖...

 

下面我们对这个图进行..最短路径的查

 

package algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;

/**
 * A* 搜索见得的java例子,也是启发式搜索.和我映像里有点出入...
 * 
 * @author ansj
 * 
 */
public class HeuristicSearching {
	public static void main(String[] args) {
		// 设置节点
		Node v1 = new Node("v1", 0);
		Node v2 = new Node("v2");
		Node v3 = new Node("v3");
		Node v4 = new Node("v4");
		Node v5 = new Node("v5");
		Node v6 = new Node("v6");

		// 设置关联关系
		v1.hm.put(v2, 40);
		v1.hm.put(v3, 30);
		v1.hm.put(v4, 20);
		v1.hm.put(v5, 10);

		v2.hm.put(v6, 10);

		v3.hm.put(v2, 2);
		v3.hm.put(v6, 15);

		v4.hm.put(v2, 15);
		v4.hm.put(v3, 6);

		v5.hm.put(v4, 15);

		openNode(v1);

		System.out.println(v1);
		System.out.println(v2);
		System.out.println(v3);
		System.out.println(v4);
		System.out.println(v5);
		System.out.println(v6);

	}

	private static List<Node> open = new ArrayList<Node>();

	private static void openNode(Node from) {
		// TODO Auto-generated method stub

		Node temp = null;
		Integer pathWeight = null;
		if (from == null) {
			return;
		}
		for (Entry<Node, Integer> entry : from.hm.entrySet()) {
			temp = entry.getKey();
			// 如果此节点已经关闭.则忽略
			if (temp.close) {
				continue;
			}
			pathWeight = entry.getValue();
			if (temp.min > from.min + pathWeight) {
				temp.min = pathWeight + from.min;
			}
			open.add(temp);
		}
		// 每次关闭掉路径最短的节点
		Node nodeMin = findAndRemoveMinNode();
		if(nodeMin!=null){
			openNode(nodeMin);
		}

	}

	private static Node findAndRemoveMinNode() {
		// TODO Auto-generated method stub
		Node node = null;
		for (int i = 0; i < open.size(); i++) {
			if (node == null) {
				node = open.get(i);
			} else if (open.get(i).min < node.min) {
				node = open.get(i);
			}
		}
		open.remove(node) ;
		return node;
	}

	// 节点对象
	private static class Node {
		// 节点名称
		private String name;
		private boolean close = false;
		// 最短的路径
		private int min = Integer.MAX_VALUE;
		// 可以到达的节点及其长度
		private HashMap<Node, Integer> hm = new HashMap<Node, Integer>();

		private Node(String name) {
			this.name = name;
		}

		private Node(String name, Integer pathWeight) {
			this.name = name;
			this.min = pathWeight;
		}

		public String toString() {
			return this.name + ":" + this.min;
		}
	}
}
 

 

 

 

 

 

 

  • 大小: 48 KB
分享到:
评论

相关推荐

    基于A*算法的人工智能程序

    A*算法属于一种启发式搜索,它扩展结点的次序类似于广度优先搜索,但不同的是每生成一个子结点需要计算估价函数F,以估算起始结点的约束经过该结点至达目标结点的最佳路径代价;每当扩展结点时,意是在所有待扩展结点中...

    第四章搜索策略.ppt

    终止节点一定是端节点,但端节点不一定是终止节点。 状态空间表示法 与/或树表示法 状态空间的盲目搜索策略 宽度优先搜索 深度优先搜索 有界深度优先搜索 代价树的宽度优先搜索 ...博弈树的启发式搜索

    灰狼算法优化LSTM超参数-神经元个数-dropout-batch-size

    开始搜索:初始化所有狼的位置、迭代寻优、返回超出搜索空间边界的搜索代理、计算每个搜索代理的目标函数、更新 Alpha, Beta, and Delta 训练模型,使用灰狼算法找到的最好的全局最优参数 plt.show() 2、数据介绍 ...

    十五个经典算法研究与总结、目录+索引(定稿版)

    本经典算法研究系列,涵盖A*.Dijkstra.DP.BFS/DFS.红黑树.KMP.遗传.启发式搜索.图像特征提取SIFT.傅立叶变换.Hash.快速排序.SPFA.快递选择SELECT等15个经典基础算法,共计31篇文章,包括算法理论的研究与阐述,及其...

    启发式搜索8/15数码问题c++源码

    ①实验目的:熟悉掌握启发式搜索算法A*及其可采纳性 ②实验要求:编写程序实现8数码和15数码问题,采用至少两种估价函数,分析估价函数求解问题时候的效率差别,分析估价函数对搜索算法的影响 3、解题思路 ①首先,...

    基于蚁群算法实现寻找最优路径matlab源码+项目说明+超详细注释.zip

    **信息素启发式因子α** 代表信息量对是否选择当前路径的影响程度, 即反映蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度。 α 的大小反映了蚁群在路径搜索中随机性因素作用的强度, 其值越大, ...

    【优化算法Matlab代码】资源存储库-第四期-蝗虫(蚱蜢)优化算法(GOA ).zip

    蝗虫算法( Grasshopper Optimization Algorithm,GOA ) 是 由 Saremi 等[1]于2017 年提出的一种元启发式仿生优化算法。 GOA是一种用于全局优化的新型元启发式算法 提出的蝗虫优化算法(GOA)在数学上模拟并模拟了...

    MLCS-Astar:一种寻找多个字符串最长公共子序列的快速启发式搜索算法

    MLCS-Astar 是一种快速启发式搜索算法,用于查找多个字符串的最长(或接近最长)公共子序列。 它发表在 2010 年 AAAI 人工智能会议 (AAAI-2010) 上。 有关该算法的详细说明,请阅读以下论文。 Q. Wang、M. Pan、Y....

    基于自营配送模式的车辆路径规划设计与实现-kaic.docx

    第四章 算法设计 4.1编码 4.2 生成初始种群 4.3建立适应度函数 4.4选择策略 4.5交叉运算 4.6变异运算 4.7终止准则 第五章 实验结果及结论 5.1案例描述 5.2参数设置 5.2.1案例参数 5.2.2算法参数 5.3算例求解 5.4...

    实用语音识别基础

    第四部分对语音识别的4个主要应用领域进行了详尽的、深入浅出的讲解,并根据最新的研究与实验结果提供了大量的实际参数、图表,与实际工作联系紧密,具有很强的可操作性与实用性。章节之间紧密配合、前后呼应,具有...

    matlab写启发式算法代码-maze_search:迷宫搜索

    matlab写脑式算法代码迷宫搜索 在这个任务中,你将负责一个“吃豆子”代理,它需要通过迷宫找到路径,既要到达特定位置,又要有效地收集食物。 如课程开头所述,您可以自由使用任何您熟悉的高级编程语言。 这包括...

    实用语音识别基础电子版

    第四部分对语音识别的4个主要应用领域进行了详尽的、深入浅出的讲解,并根据最新的研究与实验结果提供了大量的实际参数、图表,与实际工作联系紧密,具有很强的可操作性与实用性。章节之间紧密配合、前后呼应,具有...

    harmonyos2-pyHarmonySearch:pyHarmonySearch是和声搜索(HS)全局优化算法的纯Python实现

    是一种元启发式搜索算法,类似于模拟退火、禁忌和进化搜索,它基于现实世界的现象。 具体来说,HS 模仿爵士乐队一起即兴表演。 礼貌 : 在 HS 算法中,每个音乐家(= 决策变量)一起演奏(= 生成)一个音符(= 一个...

    人工智能导论期末复习资料

    3、启发式搜索,八数码难题($h_1(x)=错放棋子数$、$h_2(x)=曼哈顿距离$)→ A*算法求解(OPEN、CLOSED标识); 4、子句集求取; 5、推理:消去互补对,消解式; 6、含变量的消解式(置换); 7、消解反演,反演求解...

    信息架构 超越Web设计(第4版).pdf

    启发式评估 259 内容分析 260 内容映射262 标杆法 263 用户 265 使用分析 266 搜索日志分析 267 参与者定义和招募 270 客户支持数据 270 调查 270 情景调查 270 焦点小组 271 用户研究会议 272 访谈 272 卡片分类法 ...

    灰狼优化器 (GWO):GWO 是一种用于全局优化的新型元启发式算法-matlab开发

    此外,还实现了狩猎、搜索猎物、包围猎物和攻击猎物三个主要步骤进行优化。 这是论文的源代码:S. Mirjalili、SM Mirjalili、A. Lewis、Grey Wolf Optimizer,工程软件进展,第 69 卷,2014 年 3 月,第 46-61 页,...

    信息架构:超越Web设计(第4版)(全彩).[美]Louis Rosenfeld(带详细书签) PDF 下载 高清 完整版

    启发式评估 259 内容分析 260 内容映射 262 标杆法 263 用户 265 使用分析 266 搜索日志分析 267 参与者定义和招募 270 客户支持数据 270 调查 270 情景调查 270 焦点小组 271 用户研究会议 272 访谈 ...

    数据库管理原型系统.doc

    实验内容 1、把查询的内部表示转换成语法树,查询功能包括: (1)选择:支持AND和OR条件 (2)投影 (3)连接:包括等值连接和自然连接 (4)集合操作:并、交、差 (5)分组聚集 2、实现启发式关系代数优化方法 ...

Global site tag (gtag.js) - Google Analytics