カーナビの経路探索の原理

カーナビ等の経路探索のアルゴリズムを考えてみた。
まず、前提として地図に対して座標を適用する。
各座標に情報として「道路」、「その他」を与える。
その後、スタート地点の座標とゴール地点の座標を指定したら。
後はスタート地点から始めて、上下左右の「道路」情報の座標に対して
ゴール地点までの座標を走査する。

実際は、高速道路の下に普通道路があったりして、単純に2次元で表現できないから、工夫が必要になってくる。

ソースはこんな感じ。

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author kensir0u
 *
 */
public class RootSearch {
	
	//経路パターンカウンタ
	private static int pathPattern = 1;
	
	//出発地点の緯度・経度（座標）
	private static int startr;
	private static int startc;
	
	//到着地点の緯度・経度（座標）
	private static int endr;
	private static int endc;
	
	//走査結果
	private static boolean success;
	//スタックポインタ
	private static int  sp;
	//経度（座標）
	private static List<Integer> r = new ArrayList<Integer>();
	//緯度（座標）
	private static List<Integer> c = new ArrayList<Integer>();
	
	//地図を座標であらわす。
	static char root[][] = {  
		  {'┌','─','─','─','─','─','─','─','┐'},
		  {'│','□','□','□','□','□','□','□','│'},
		  {'│','□','■','■','□','■','□','■','│'},
		  {'│','□','■','■','□','■','□','■','│'},
		  {'│','□','■','■','□','■','□','■','│'},
		  {'│','■','□','■','■','■','□','■','│'},
		  {'│','■','□','■','□','■','□','■','│'},
		  {'│','■','□','□','□','□','□','□','│'},
		  {'└','─','─','─','─','─','─','─','┘'},};
	
	public static void main(String args[]){

		//出発地点の設定
		startr = 1;
		startc = 1;
		
		//到着地点の設定
		endr = 7;
		endc = 7;
		
		System.out.println("経路探索開始");
		if (search(startr,startc) == false) {
			System.out.println("探索失敗");
		}
	}
	
	private static boolean search(int i,int j) {
		
		root[i][j] = 1;
		if (r.size() > sp) {
			r.set(sp, i);
			c.set(sp, j);
		} else {
			r.add(i);
			c.add(j);
		}
		sp++;
		if (i == endr && j == endc) {
			System.out.println("pathPattern=" + pathPattern++);
			
			for (int k = 0; k < sp;k++) {
				System.out.println("" + r.get(k) +  "," + c.get(k));
			}
			success = true;
		}
		
		//地図の場合は方角によって上下左右の探索順を変更する。
		//移動可能な場合確認する。（下）
		if (root[i][j+1] == '□') {
			search(i,j+1);
		}
		//（右）
		if (root[i+1][j] == '□') {
			search(i+1,j);
		}
		//（上）
		if (root[i][j-1] == '□') {
			search(i,j-1);
		}
		//（左）
		if (root[i-1][j] == '□') {
			search(i-1,j);
		}
		
		//インデックスを戻す
		sp--;
		//とおってきた道を戻す。
		root[i][j] = '□';
		
		return success;
	}

}