深度优先－途径的选择

深度优先－路径的选择

class PathInfo //数据存储结构
{
	String from;
	String to;
	int distance;
	boolean skip; // used in backtracking

	PathInfo(String f, String t, int d)
	{
		from = f;
		to = t;
		distance = d;
		skip = false;
	}
}

public class Depth
{
	final int MAX = 100;
	PathInfo paths[] = new PathInfo[MAX];
	int pathCount = 0;

	Stack<PathInfo> goInfo = new Stack<PathInfo>();

	public static void main(String args[])
	{
		String from = "", to = "";
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try
		{
			System.out.print("From? ");
			from = br.readLine();
			System.out.print("To? ");
			to = br.readLine();
		} catch (IOException exc)
		{
			System.out.println("Error on input.");
		}

		Depth depth = new Depth();
		depth.setup();
		depth.isOK(from, to);
		depth.route();

	}

	void isOK(String from, String to)// 将可行的路径压栈
	{
		int dist = match(from, to);
		if (dist != 0) // 一站到达
		{
			goInfo.push(new PathInfo(from, to, dist));
			return;
		}

		PathInfo pinfo = findFrom(from);
		if (pinfo != null)
		{
			goInfo.push(new PathInfo(from, to, pinfo.distance));
			isOK(pinfo.to, to); // 直到有“一站到达”

		} else if (goInfo.size() > 0)
		{
			pinfo = (PathInfo) goInfo.pop();// 死路一条
			isOK(pinfo.from, pinfo.to);// 回头再走，成立即可
		}
	}

	void route()
	{
		if (goInfo.size() == 0)
			return;

		int num = goInfo.size();
		Stack<PathInfo> backInfo = new Stack();
		for (int i = 0; i < num; i++)
			backInfo.push(goInfo.pop());// 倒出来,再pop，就是正序了

		int dist = 0;
		PathInfo pinfo = null;
		for (int i = 0; i < num; i++)
		{
			pinfo = (PathInfo) backInfo.pop();
			System.out.print(pinfo.from + " to ");
			dist += pinfo.distance;
		}

		System.out.println(pinfo.to);
		System.out.println("Distance is " + dist);
	}

	// 看能不能直到，能的话，就返回权重，不能返回0
	int match(String from, String to)
	{
		for (int i = pathCount - 1; i > -1; i--)
		{
			if (paths[i].from.equals(from) && paths[i].to.equals(to) && !paths[i].skip)
			{
				paths[i].skip = true; // prevent reuse
				return paths[i].distance;
			}
		}
		return 0;
	}

	// Put flights into the database.
	void addFlight(String from, String to, int dist)
	{
		if (pathCount < MAX)
		{
			paths[pathCount] = new PathInfo(from, to, dist);
			pathCount++;
		} else
			System.out.println("Flight database full.\n");
	}

	// Given from, find any connection.
	// 找到一个起点为from的，并再new一份出来，这段路的条件是未走过。
	PathInfo findFrom(String from)
	{
		for (int i = 0; i < pathCount; i++)
		{
			if (paths[i].from.equals(from) && !paths[i].skip)
			{
				PathInfo pinfo = new PathInfo(paths[i].from, paths[i].to, paths[i].distance);
				paths[i].skip = true; // prevent reuse
				return pinfo;
			}
		}
		return null;
	}

	// Initialize the path database.
	// 地图是有限的，每个点周边相邻的点，两两成一直线，且是有方向性的
	// 查找的时候，数据的分布，会影响结果
	public void setup()
	{
		databaseGen();
	}

	private void databaseGen()
	{
		addFlight("A", "B", 500);
		addFlight("A", "D", 900);
		addFlight("A", "C", 1800);
		addFlight("A", "J", 700);
		addFlight("J", "K", 300);

		addFlight("B", "A", 1700);
		addFlight("B", "F", 1700);
		// addFlight("B", "H", 600);
		addFlight("B", "D", 500);

		addFlight("C", "G", 1000);
		addFlight("C", "E", 1000);
		addFlight("C", "H", 1000);

		addFlight("D", "C", 1000);
		addFlight("E", "H", 1500);
	}

	private void databaseGood() // 最理想的情况,A to B
	{
		addFlight("A", "B", 500);
	}

	private void databaseLong()// 不理想的数据分布, A to J
	{
		addFlight("A", "B", 1500);
		addFlight("A", "I", 1500);
		addFlight("I", "J", 1500);

		addFlight("B", "C", 1500);
		addFlight("B", "A", 1500);

		addFlight("C", "D", 1500);
		addFlight("C", "B", 1500);
		addFlight("D", "C", 1500);
	}

	private void databaseLong2()// 不理想的数据分布, A to J
	{
		addFlight("A", "B", 1500);
		addFlight("A", "I", 1500);
		addFlight("I", "J", 1500);

		addFlight("B", "A", 1500);// --
		addFlight("B", "C", 1500);// --

		addFlight("C", "B", 1500);// --
		addFlight("C", "D", 1500);// --

		addFlight("D", "C", 1500);
	}

}

数据存储特征：
一、上面的地图数据结构，映射为二维表。
二、起点集合性（就是from集在一起）
三、from按A->Z,to 是A->Z 或 Z->A

数据查找特征：
一、深度优先，如果是二维表的角度来说是，从左到右，从上至下。

查找优化：
一、将from分成块，那就能加快from的查找；
二、较短路径：
1、先得到起点与终点的直线距离X值，再由X经某种公式得到K值。
2、查找时判断时，排除权值大于K的

飞机就是典型、理想的点对点模型，
汽车的GPS导航就更复杂了，有路径最短、最省钱、最快速的

深度优先 － 途径的选择

相关推荐