算法实现系列第四章.启发式搜索_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;
		}
	}
}