A*(エースター)法による最短コストの探索|HTML5

A*(エースター)法による最短コストの探索|HTML5

A*(エースター)法による最短コスト(ルート)の探索を導き出すアルゴリズムをJavaScriptでコーディングしました。

A*法はダイクストラ法よりも、探索回数が少なくてすむのが特徴です。前回のダクストラ法は23回。今回のA*法は10回で済んでいます。

A*法では、実コスト+推定コストで探索経路を求めます。推定コストとは、終着点のノードから現在のノードの座標位置を引いたものです。斜め移動がある場合は以下の式で求めます。エッジのコストはすべて1です。

dx = tx – x
dy = ty – y
dx と dy を比較して高い値が推定コストとなります。

縦横(4方向)移動のみの場合は、推定コストは dx + dy になります。

A*法では、この推定コストに実コストを加算してスコアを求め、探索コストを計算します。

ここでも前回と同じように、n2というノードが出発点、n24というノードが終着点となっています。両者とも自由に他のノードに置き換えることができます。エッジのコストはすべて1にしています。コードを実行すると、上記の図のような経路が導き出されます。

A*(エースター)法による最短コストの探索(HTML5, JavaScript) : デモ

A*(エースター)法による最短コストの探索(HTML5, JavaScript) : ZIPファイル(47kb)

1.HTML

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1, maximum-scale=1, user-scalable=no">
    <title>A*法 最短コスト(ルート)探索</title>
    <script>
        // A*法 最短ルート探索
        var nodes = [];
        var nodeDone = null;
 
        function CreateNode(node, x, y){
            this.node = node;
            this.x = x;
            this.y = y;
            this.cost = -1;
            this.score = -1;
            this.done = false;
            this.previousNode = null;
            this.nextNode = null;
            this.edgesTo = [];
            this.edgesCost = [];
            this.edgesScore = [];
        }
 
        // ノードを作る
        var node1 = new CreateNode(1,0,0);
        var node2 = new CreateNode(2,1,0);
        var node3 = new CreateNode(3,2,0);
        var node4 = new CreateNode(4,3,0);
        var node5 = new CreateNode(5,4,0);
        var node6 = new CreateNode(6,0,1);
        var node7 = new CreateNode(7,1,1);
        var node8 = new CreateNode(8,2,1);
        var node9 = new CreateNode(9,3,1);
        var node10 = new CreateNode(10,4,1);
        var node11 = new CreateNode(11,0,2);
        var node12 = new CreateNode(12,1,2);
        var node13 = new CreateNode(13,2,2);
        var node14 = new CreateNode(14,3,2);
        var node15 = new CreateNode(15,4,2);
        var node16 = new CreateNode(16,0,3);
        var node17 = new CreateNode(17,1,3);
        var node18 = new CreateNode(18,2,3);
        var node19 = new CreateNode(19,3,3);
        var node20 = new CreateNode(20,4,3);
        var node21 = new CreateNode(21,0,4);
        var node22 = new CreateNode(22,1,4);
        var node23 = new CreateNode(23,2,4);
        var node24 = new CreateNode(24,3,4);
        var node25 = new CreateNode(25,4,4);
 
 
        // 各ノードから連結する他のノードとのコストを設定する
        node1.edgesTo.push(node2,node6,node7);
        node1.edgesCost.push(1,1,1);
        nodes.push(node1);
 
        node2.edgesTo.push(node1,node3,node6,node7,node8);
        node2.edgesCost.push(1,1,1,1,1);
        nodes.push(node2);
 
        node3.edgesTo.push(node2,node4,node7,node8,node9);
        node3.edgesCost.push(1,1,1,1,1);
        nodes.push(node3);
 
        node4.edgesTo.push(node3,node5,node8,node9,node10);
        node4.edgesCost.push(1,1,1,1,1);
        nodes.push(node4);
 
        node5.edgesTo.push(node4,node9,node10);
        node5.edgesCost.push(1,1,1);
        nodes.push(node5);
 
        node6.edgesTo.push(node1,node2,node7,node11,node12);
        node6.edgesCost.push(1,1,1,1,1);
        nodes.push(node6);
 
        node7.edgesTo.push(node1,node3,node6,node8,node11,node12,node13);
        node7.edgesCost.push(1,1,1,1,1,1,1);
        nodes.push(node7);
 
        node8.edgesTo.push(node2,node3,node4,node7,node9,node12,node13,node14);
        node8.edgesCost.push(1,1,1,1,1,1,1,1,1);
        nodes.push(node8);
 
        node9.edgesTo.push(node3,node4,node5,node8,node10,node13,node14,node15);
        node9.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node9);
 
        node10.edgesTo.push(node4,node5,node9,node15);
        node10.edgesCost.push(1,1,1,1);
        nodes.push(node10);
 
        node11.edgesTo.push(node6,node7,node12,node16,node17);
        node11.edgesCost.push(1,1,1,1,1);
        nodes.push(node11);
 
        node12.edgesTo.push(node6,node7,node8,node11,node13,node16,node17,node18);
        node12.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node12);
 
        node13.edgesTo.push(node7,node8,node9,node12,node14,node17,node18,node19);
        node13.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node13);
 
        node14.edgesTo.push(node8,node9,node10,node13,node15,node18,node19,node20);
        node14.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node14);
 
        node15.edgesTo.push(node9,node10,node14,node19,node20);
        node15.edgesCost.push(1,1,1,1,1);
        nodes.push(node15);
 
        node16.edgesTo.push(node11,node12,node17,node21,node22);
        node16.edgesCost.push(1,1,1,1,1);
        nodes.push(node16);
 
        node17.edgesTo.push(node11,node12,node13,node16,node18,node21,node22,node23);
        node17.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node17);
 
        node18.edgesTo.push(node12,node13,node14,node17,node19,node22,node23,node24);
        node18.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node18);
 
        node19.edgesTo.push(node13,node14,node15,node18,node20,node23,node24,node25);
        node19.edgesCost.push(1,1,1,1,1,1,1,1);
        nodes.push(node19);
 
        node20.edgesTo.push(node14,node15,node19,node24,node25);
        node20.edgesCost.push(1,1,1,1,1);
        nodes.push(node20);
 
        node21.edgesTo.push(node16,node17,node22);
        node21.edgesCost.push(1,1,1);
        nodes.push(node21);
 
        node22.edgesTo.push(node16,node17,node18,node21,node23);
        node22.edgesCost.push(1,1,1,1,1);
        nodes.push(node22);
 
        node23.edgesTo.push(node17,node18,node19,node22,node24);
        node23.edgesCost.push(1,1,1,1,1);
        nodes.push(node23);
 
        node24.edgesTo.push(node18,node19,node20,node23,node25);
        node24.edgesCost.push(1,1,1,1,1);
        nodes.push(node24);
 
        node25.edgesTo.push(node19,node20,node24);
        node25.edgesCost.push(1,1,1);
        nodes.push(node25);
 
        var startNode = nodes[1]; // スタートノードの設定
        startNode.cost = 0; // スタートノードのコストに0を設定
        startNode.done = true; // スタートノードを訪問済みにする
 
        var goalNode = nodes[23]; // ゴールノードを設定
        var prevNode = null;
        var minCost = 0;
        var minScore = 0;
 
        // 最短ルートを探索
        function setSearchRoute(){
            minCost = 9999;
            minScore = 9999;
            for(var i=0; i<nodes.length; i++){
                // ノードが訪問済みの場合に実行
                if(nodes[i].done===true){       
                    for(var j=0; j<nodes[i].edgesTo.length; j++){
                        // 接続したノードが未訪問の場合に実行
                        if(nodes[i].edgesTo[j].done===false){
                            // 接続したノードまでの最短コストを計算
                            var dx = goalNode.x - nodes[i].edgesTo[j].x;
                            var dy = goalNode.y - nodes[i].edgesTo[j].y;
                            if(dx>dy){
                                var score = dx;
                            }
                            else{
                                score = dy;
                            }
                            // score = dx+dy; // 移動が左右前後のみの場合
                            
                            if(minScore>score+nodes[i].cost+nodes[i].edgesCost[j]){
                                setCalcCostScore();
                            }
                        }
                    }
                }
            }
 
            function setCalcCostScore(){
                // 接続したノードのコスト
                minCost = nodes[i].cost+nodes[i].edgesCost[j];
                minScore = score+nodes[i].cost+nodes[i].edgesCost[j];
                // 最短コストの始点のノード
                prevNode = nodes[i];
                // 最短コストの最終のノード
                nodes[i].nextNode = nodes[i].edgesTo[j].node;
                // 最短コストで決まった接続ノード
                nodeDone = nodes[i].edgesTo[j];
            }
        }
 
        var count = 0;
        while(goalNode.done==false){
            count++;
            setSearchRoute();
            // 最短に接続したノードを訪問済みにする
            nodeDone.done = true;
            // 最短に接続したノードのコストに最短コストを設定
            nodeDone.cost = minCost;
            nodeDone.score = minScore;
            // 最短コストの始点のノードを接続したノードに設定
            nodeDone.previousNode = prevNode;
        }
        console.log("count",count); 
 
        var path = '最短経路: Start ';
        var currentNode = goalNode;
        var route = [];
        while(currentNode.previousNode) {
            var nextNode = currentNode.previousNode;
            currentNode = nextNode;
            route.unshift(nextNode.node);
        }
 
        for(var i=0; i<route.length; i++){
            path += route[i] + ' -> ';
        }
        path += 'Goal(' + goalNode.node + ')';
 
        console.log('最短コスト: ' + goalNode.cost);
        console.log(path);
 
        window.onload = function() {
            var element = document.getElementById("result");
            element.innerHTML = "最短コスト: " +  goalNode.cost + "<br />" + path + "<br />探索回数: " + count;
        }
    </script>
</head>
<body>
    <img style="width:500px;" src="A.png" alt="A*法">
    <p id="result"></p>
</body>
</html>

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です