点阵路由算法

本算法解决点阵的路由选择问题，有点类似于计算出乘公交车从一点到另一点所有路由的算法。

问题描述如下：

图上显示了6个点以及点和点之间的路径，现在给出任意两点，求从一点到另外一点的所有可能路由。

代码分析如下，整个项目文件可从附件下载：

 

Point类，描述每个点，以及其相关点

package com.yingxia.routealgorithm;

import java.util.List;

public class Point {
	
	private Integer gid;
	private String name;
	
	private List<Point> points;

	public Integer getGid() {
		return gid;
	}

	public void setGid(Integer gid) {
		this.gid = gid;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public List<Point> getPoints() {
		return points;
	}

	public void setPoints(List<Point> points) {
		this.points = points;
	}

	@Override
	public boolean equals(Object obj) {
		Point p = (Point) obj;
		return this.getGid().equals(p.getGid());
	}
}

 

Route类

package com.yingxia.routealgorithm;

import java.util.LinkedList;

@SuppressWarnings("serial")
public class Route extends LinkedList<Point> {

	
}

 

Algorithm核心算法类，用了递归算法，注意递归终止的条件是环路或者到达终点。Dao类的实现请看附件，我用的是postgres数据库，在db.sql中附带了建表和插入数据的sql语句。

package com.yingxia.routealgorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Algorithm {
	
	private Dao dao;
	
	public Algorithm() {
		dao = new Dao();
	}
	
	private List<Route> routes;
	
	@SuppressWarnings("unchecked")
	public List<Route> queryRoutes(Point p1, Point p2) {
		
		routes = new ArrayList<Route>();
		
		Route route = new Route();
		route.add(p1);
		recursive(p1, p2, route);
		
		Collections.sort(routes, new Comparator(){

			@Override
			public int compare(Object arg0, Object arg1) {

				Route r1 = (Route) arg0;
				Route r2 = (Route) arg1;
				
				if(r1.size() < r2.size()) {
					return -1;
				}
				if(r1.size() > r2.size()) {
					return 1;
				}
				return 0;
			}}
		);
		
		return routes;
	}
	
	private void recursive(Point p, Point endPoint, Route route) {
		
		fillPointsField(p);
		
		for(Point nextP : p.getPoints()) {
			
			// route splited
			Route splitedRoute = new Route();
			splitedRoute.addAll(route);
			splitedRoute.add(nextP);
			
			// circle route, abandoned
			if(isPointOnRoute(nextP, route)) {
				
			}
			// reach end point
			else if(nextP.equals(endPoint)) {
				routes.add(splitedRoute);
			} 
			// recursive
			else {
				recursive(nextP, endPoint, splitedRoute);
			}
		}
	}
	
	private void fillPointsField(Point p) {
		dao.fillPointsField(p);
	}
	
	private boolean isPointOnRoute(Point p, Route route) {
		for(Point point : route) {
			if(point.equals(p)) {
				return true;
			}
		}
		return false;
	}

	public Dao getDao() {
		return dao;
	}

	public void setDao(Dao dao) {
		this.dao = dao;
	}
	
}

 

Main测试类

package com.yingxia.routealgorithm;

import java.util.List;

public class Main {

	public static void main(String[] args) {
		
		Algorithm algorithm = new Algorithm();
		
		Point p1 = new Point();
		p1.setGid(1);
		p1.setName("纺机厂");
		
		Point p2 = new Point();
		p2.setGid(6);
		p2.setName("韦博英语");
		
		List<Route> routes = algorithm.queryRoutes(p1, p2);
		
		printout(routes);
		
		p1.setGid(2);
		p1.setName("小东门");
		p1.setPoints(null);
		
		p2.setGid(4);
		p2.setName("花园街");
		p2.setPoints(null);
		
		routes = algorithm.queryRoutes(p1, p2);
		
		printout(routes);
	}
	
	public static void printout(List<Route> routes) {
		
		System.out.println("路由共有" + routes.size() + "条：");
		
		for(Route route : routes) {
			for(Point p : route) {
				System.out.print(p.getName() + "\t");
			}
			System.out.println();
		}
		
		System.out.println();
	}

}

 

测试输出如下：

 

路由共有3条：
纺机厂    三孝口    韦博英语   
纺机厂    小东门    栖巢咖啡    三孝口    韦博英语   
纺机厂    小东门    花园街    三孝口    韦博英语   

路由共有3条：
小东门    花园街   
小东门    纺机厂    三孝口    花园街   
小东门    栖巢咖啡    三孝口    花园街

 

个人感觉这种算法点阵一多就会效率很低，如果朋友们有什么好的方法，告诉我，谢谢。