3Dプログラミング講座・その13:経路探索(A*:A-STAR)&巡回セールスマン問題:巨大サイズ



経路探索(A*:A-STAR)&巡回セールスマン問題
経路探索(A*:A-STAR)&巡回セールスマン問題:くろにゃんこ
ファイルはこちら



始点
終点


変更地点:英数字 変更経路:英数字 経路コスト:数字
レート:数字 経由地点:英数字:トークン('-')



prg3d009.htm

...省略...

<script>

var route = [
['A', 0,  [55,   53], 3, [1, 1.2, [80, 40]], [5, 1,   [5,   90]], [6,  1.7,[135, 95]]  ],
['B', 1,  [213,  50], 2, [0, 1.2, [-1, -1]], [7, 1.7, [235,125]] ],
['C', 2,  [396,  59], 2, [3, 1.2, [425,50]], [7, 1,   [325,105]] ],
['D', 3,  [565,  49], 3, [2, 1.2, [-1, -1]], [4, 1.2, [625, 50]], [8,  1,  [485,110]]  ],
['E', 4,  [746,  63], 2, [3, 1.2, [-1, -1]], [9, 1,   [685,110]] ],
['F', 5,  [48,  155], 3, [0, 1,   [-1, -1]], [6, 1.2, [80, 135]], [10, 1,  [5,   210]] ],
['G', 6,  [228, 168], 3, [0, 1.7, [-1, -1]], [5, 1.2, [-1,  -1]], [11, 1,  [150, 220]] ],
['H', 7,  [386, 162], 4, [1, 1.7, [-1, -1]], [2, 1,   [-1,  -1]], [8,  1.2,[450, 145]], [11, 1.7, [270, 210]] ],
['I', 8,  [569, 167], 4, [3, 1,   [-1, -1]], [7, 1.2, [-1,  -1]], [12, 1.7,[425, 215]], [13, 1,   [525, 240]] ],
['J', 9,  [749, 168], 3, [4, 1,   [-1, -1]], [13,1.7, [628,213]], [14, 1,  [700, 255]] ],
['K', 10, [53,  282], 2, [5, 1,   [-1, -1]], [15,1,   [5,  330]] ],
['L', 11, [210, 284], 5, [6, 1,   [-1, -1]], [7, 1.7, [-1,  -1]], [12, 1.2,[292, 274]], [15, 1.7, [78,  333]], [16, 1,   [163, 373]] ],
['M', 12, [393, 290], 4, [8, 1.7, [-1, -1]], [11,1.2, [-1,  -1]], [17, 1,  [330, 350]], [18, 1.7, [455, 316]] ],
['N', 13, [566, 305], 3, [8, 1,   [-1, -1]], [9, 1.7, [-1,  -1]], [18, 1,  [495, 350]] ],
['O', 14, [740, 295], 3, [9, 1,   [-1, -1]], [18,1.7, [627,340]], [19, 1,  [684, 387]] ],
['P', 15, [53,  415], 4, [10,1,   [-1, -1]], [11,1.7, [-1,  -1]], [20, 1,  [5,   485]], [21, 1.7, [110, 440]] ],
['Q', 16, [216, 414], 4, [11,1,   [-1, -1]], [17,1.2, [275,390]], [21, 1,  [150, 480]], [22, 1.7, [240, 510]] ],
['R', 17, [390, 408], 3, [12,1,   [-1, -1]], [16,1.2, [-1,  -1]], [22, 1,  [317, 480]] ],
['S', 18, [563, 429], 5, [12,1.7, [-1, -1]], [13,1,   [-1,  -1]], [14, 1.7,[-1,   -1]], [22, 1.7, [420, 484]], [24, 1.7, [625, 450]] ],
['T', 19, [740, 425], 2, [14,1,   [-1, -1]], [24,1,   [680,480]] ],
['U', 20, [55,  555], 2, [15,1,   [-1, -1]], [21,1.2, [95, 545]] ],
['V', 21, [198, 556], 3, [15,1.7, [-1, -1]], [16,1,   [-1,  -1]], [20, 1.2,[-1,   -1]] ],
['W', 22, [386, 550], 4, [16,1.7, [-1, -1]], [17,1,   [-1,  -1]], [18, 1.7,[-1,   -1]], [23, 1.2, [465, 545]] ],
['X', 23, [564, 557], 2, [22,1.2, [-1, -1]], [24,1.2, [608,536]] ],
['Y', 24, [752, 557], 3, [18,1.7, [-1, -1]], [19,1,   [-1,  -1]], [23, 1.2,[-1,   -1]] ] ];
var answer = "";
var answercost = 1e12;
var answerhcost = 1e12;
var answerV = "";
var answercostV = 1e12;
var answerhcostV = 1e12;
var rate = 81;
var img;
var readed = false;
var eps = 5e-14;
var via = new Array();
var gST;
var gED;
var data;
var elm;

function calc(){
  var stelm = document.getElementById('ST');
  var edelm = document.getElementById('ED');
  gST = Number(stelm.value.substr(6));
  gED = Number(edelm.value.substr(6));
  answerV = "";
  answercostV = 1e12;
  answerhcostV = 1e12;

  var num = via.length;
  data = permutation(via, num);
  var dnum = data.length;
  var strroute = "";
  var str = "";
  var ret = false;
  var brk;
  var r;
  var i;
  var j;
  var h;
  var nextst;
  var nexted;
  var cost = 0;
  var hcost = 0;
  if(0 < dnum){
    for(i = 0; i < dnum; i ++){
      str = strroute;
      brk = false;
      cost = 0;
      hcost = 0;
      hh = 0;
      nextst = gST;
      nexted = gST;
      for(j = 0; j < num; j++){
        nextst = nexted;
        nexted = data[i][j];
        h = heuristic(nextst, nexted);
        if(cost + h < answercostV){
          if(h < hcost) h = hcost;
          r = calcastar(nextst, nexted);
          ret = (ret || r);
          if(r == true){ 
            if(j == 0) str = answer;
            else str = str + '-' + answer.substr(2);
            cost = cost + answercost;
            if(h < answerhcost) h = answerhcost;
          }
          else {
            brk = true;
            break;
          }
        }
        else {
          brk = true;
          break;
        }
      }
      if(brk) continue;
      nextst = nexted;
      nexted = gED;
      h = heuristic(nextst, nexted);
      if(cost + h < answercostV){
        if(h < hcost) h = hcost;
        r = calcastar(nextst, nexted);
        ret = (ret || r);
        if(r == true){ 
          cost = cost + answercost;
          str = str + '-' + answer.substr(2) + ":cost:" + cost.toFixed(3);
          if((cost < answercostV)||(answercostV - eps < cost)&&(cost < answercostV + eps)&&(h < answerhcost)){
            answerV = str;
            answercostV = cost;
            answerhcostV = h;
          }
        }
      }
    }
  }
  else {
    str = strroute;
    cost = 0;
    hcost = 0;
    hh = 0;
    nextst = gST;
    nexted = gED;
    h = heuristic(nextst, nexted);
    if(cost + h < answercostV){
      if(h < hcost) h = hcost;
      r = calcastar(nextst, nexted);
      ret = (ret || r);
      if(r == true){
        cost = cost + answercost;
        str = answer + ":cost:" + cost.toFixed(3);
        if((cost < answercostV)||(answercostV - eps < cost)&&(cost < answercostV + eps)&&(h < answerhcost)){
          answerV = str;
          answercostV = cost;
          answerhcostV = h;
        }
      }
    }
  }

  var elm = document.getElementById('OUTTXT');
  if(!ret) answerV = "Can't solve.";
  elm.value = answerV;
  updatecanvas();
}

function calcastar(st, ed){
  answer = "";
  answercost = 1e12;
  answerhcost = 1e12;
  var ret = astar("", st, ed, 0, 0, 15, 0);

  return ret;
}

//strroute:経路文字列
//now:現在位置
//end:終了位置
//cost:経路コスト
//hcost:推計経路コスト
//maxdepth:最大ネスト深度
//depth:現在のネスト数
//answer:解答経路文字列
//answercost:解答経路コスト
//ret:解決できたか?
function astar(strroute, now, end, cost, hcost, maxdepth, depth){
  var ret = false;
  if(0 < depth) strroute = strroute  + "-" + String.fromCharCode(65 + now);
  else strroute = String.fromCharCode(65 + now);
  if(now == end) {
    if((cost < answercost)||((answercost - eps < cost)&&(cost < answercost + eps)&&(hcost < answerhcost))){
      answercost = cost;
      answerhcost = hcost;
      answer = strroute;
      return true;
    }
  }
  if(maxdepth < depth) return false;
  var num = route[now][3];
  var i = 0;
  while(i < num){
    var next = route[now][4+i][0];
//    if(isGone(strroute, next) == false){
      var h = heuristic(next, end);
      if(cost + h < answercost){
        if(h < hcost) h = hcost;
        var r = astar(strroute, next, end, cost + route[now][4 + i][1], h, maxdepth, depth + 1);
        ret = (ret || r);
      }
//    }
    i++;
  }
  return ret;
}

function heuristic(now, end){
  var p0 = route[now][2];
  var p1 = route[end][2];
  var sub = [p1[0] - p0[0], p1[1] - p0[1]];
  var ret = Math.sqrt(sub[0] * sub[0] + sub[1] * sub[1]) / rate;
  return ret;
}

function permutation(nums, k){
  var ans = [];
  var i;
  var j;
  if(nums.length == 0){
    return ans;
  }
  if((k <= 0)||(nums.length < k)){
    k = nums.length;
  }
  if(k == 1){
    for(i = 0; i < k; i++){
      ans[i] = [nums[i]];
    }
  }
  else {
    for(i = 0; i < k; i++){
      var parts = nums.slice(0);
      parts.splice(i, 1)[0];
      var row = permutation(parts, k - 1);
      for(j = 0; j < row.length; j++){
        ans.push([nums[i]].concat(row[j]));
      }
    }
  }
  return ans;
}

function isGone(strroute, now){
  var ch;
  var str = strroute;
  while(str != ""){
    ch = Number(str.charCodeAt(0) - 65);
    if(ch == now) return true;
    str = str.substr(2);
  }
  return false;
}

function chgdata(){
  var stelm = document.getElementById('ST');
  var edelm = document.getElementById('ED');
  gST = Number(stelm.value.substr(6));
  gED = Number(edelm.value.substr(6));
  var nowelm = document.getElementById('TXTNOW');
  var numelm = document.getElementById('TXTNUM');
  var costelm = document.getElementById('TXTCOST');
  var rateelm = document.getElementById('TXTRT');
  var viaelm = document.getElementById('TXTVIA');
  var lowerUpper = "A".charCodeAt(0);
  var upperUpper = "Z".charCodeAt(0);
  var lowerLower = "a".charCodeAt(0);
  var upperLower = "z".charCodeAt(0);
  var i;
  var j;
  var bbb;
  var work;
  var ch;
  via = new Array();
  via.length = 0;
  var strs = viaelm.value.split('-');
  for(i = 0; i < strs.length; i++){
    work = Number(strs[i]);
    if((Number.isNaN(work))||(work < 0)||(24 < work)){
      ch = strs[i].charCodeAt(0);
      if((lowerUpper <= ch)&&(ch <= upperUpper)){
        work = Number(ch - lowerUpper);
      }
      else if((lowerLower <= ch)&&(ch <= upperLower)){
        work = Number(ch - lowerLower);
      }
    }
    if((strs[i] != "")&&(0 <= work)&&(work <= 24)){
      if((work != gST)&&(work != gED)){
        bbb = true;
        for(j = 0; j < via.length; j++){
          if(work == via[j]) bbb = false;
        }
        if(bbb) via.push(work);
      }
    }
  }

  var now = Number(nowelm.value);
  ch = nowelm.value.charCodeAt(0);
  if((lowerUpper <= ch)&&(ch <= upperUpper)){
    now = Number(ch - lowerUpper);
  }
  else if((lowerLower <= ch)&&(ch <= upperLower)){
    now = Number(ch - lowerLower);
  }
  if((now < 0)||(24 < now)) return;
  var cost = Number(costelm.value);
  if((Number.isNaN(cost))||(cost < 0)) return;
  var num = Number(numelm.value);
  ch = numelm.value.charCodeAt(0);
  work = -1;
  if((lowerUpper <= ch)&&(ch <= upperUpper)){
    work = Number(ch - lowerUpper);
  }
  else if((lowerLower <= ch)&&(ch <= upperLower)){
    work = Number(ch - lowerLower);
  }
  if(0 <= work){
    num = -1;
    for(i = 0; i < route[now][3]; i++){
      if(route[now][4 + i][0] == work){
        num = i;
        break;
      }
    }
  }
  if((num < 0)||(route[now][3] <= num)) return;
  route[now][4 + num][1] = cost;
  for(i = 0; i < route[route[now][4 + num][0]][3]; i++){
    if(route[route[now][4 + num][0]][4 + i][0]  == now){
      route[route[now][4 + num][0]][4 + i][1] = cost;
      var r = Number(rateelm.value);
      if(r < 0) retrun;
      rate = r;
      calc();
      updatecanvas();
      return;
    }
  }
}

function updatecanvas(){
  elm = document.getElementById('cnv0');
  if(!readed){
    img = new Image();
    img.src = "./img/astarL.jpg";
    img.onload = () => {
      readed = true;
      updatecanvas();
      return;
    };
  }
  var ctx = elm.getContext("2d");
  ctx.fillStyle = "rgb(0, 0, 0)" ;
  ctx.strokeStyle = 'rgb(0, 0, 0)';
  ctx.clearRect(0, 0, 800, 600);
  ctx.drawImage(img, 0, 0);
  var strs;
  var str;
  var now;
  var num;
  var i;
  var p0;
  var p1;
  for(now = 0; now < 25; now++){
    num = route[now][3];
    for(i = 0; i < num; i++){
      if(route[now][4 + i][2][0] < 0) continue;
      drawcost(ctx, now, i);
    }
  }

  if((answerV == "")||(answerV == "Can't solve.")) return;

  strs = answerV.split(':');
  str = strs[0];
  now = Number(str.charCodeAt(0) - 65);
  num = now;
  p0 = route[now][2];
  p1 = p0;
  ctx.beginPath();
  ctx.arc(p0[0], p0[1], 10, 0, 2 * Math.PI) ;
  ctx.fillStyle = "rgb(32, 192, 128)" ;
  ctx.strokeStyle = 'rgb(32, 192, 128)';
  ctx.fill();
  ctx.closePath()
  ctx.fillStyle = "rgb(32, 128, 255)" ;
  ctx.strokeStyle = 'rgb(32, 128, 255)';
  for(i = 0; i < via.length; i++){
    ctx.beginPath();
    p0 = route[via[i]][2];
    p1 = p0;
    ctx.arc(p0[0], p0[1], 10, 0, 2 * Math.PI) ;
    ctx.fill();
    ctx.closePath()
  }
  p0 = route[num][2];
  p1 = p0;
  ctx.beginPath();
  ctx.fillStyle = "rgb(32, 192, 128)" ;
  ctx.strokeStyle = 'rgb(32, 192, 128)';
  ctx.lineWidth = 6;
  ctx.moveTo(p0[0], p0[1]);
  str = str.substr(2);
  while(str != ""){
    p0 = p1;
    now = Number(str.charCodeAt(0) - 65);
    p1 = route[now][2];
    ctx.lineTo(p1[0], p1[1]);
    str = str.substr(2);
  }
  if(Number.isNaN(p1[0]) == false){
    var sub = [p1[0] - p0[0], p1[1] - p0[1]];
    if((sub[0] != 0)||(sub[1] != 0)){
      var th = Math.atan2(sub[1], sub[0]);
      var add = Math.PI / 180.0 * 150.0;
      var head = [30, 0];
      var work0 = [head[0] * Math.cos(th + add) - head[1] * Math.sin(th + add) + p1[0], head[0] * Math.sin(th + add) + head[1] * Math.cos(th + add) + p1[1]];
      var work1 = [head[0] * Math.cos(th - add) - head[1] * Math.sin(th - add) + p1[0], head[0] * Math.sin(th - add) + head[1] * Math.cos(th - add) + p1[1]];
      ctx.lineTo(work0[0], work0[1]);
      ctx.moveTo(p1[0], p1[1]);
      ctx.lineTo(work1[0], work1[1]);
    }
  }
  ctx.moveTo(route[num][2][0], route[num][2][1]);
  ctx.closePath()
  ctx.stroke();
}

function drawcost(ctx, now, i){
  var cost = route[now][4 + i][1];
  var pnt = route[now][4 + i][2];
  ctx.font = "24px Sans-serif";
  ctx.fillText(cost.toFixed(2), pnt[0], pnt[1]);
}

</script>

...省略...


route:経路配列
要素:[経路名の文字列, 経路番号, [x座標, y座標], この経路から他の経路につながる数, [他の経路への経路番号, 経路コスト, [コスト表示x座標, コスト表示y座標]], ...]

function calc()
は巡回経由地も含めた計算
巡回経由地の経由の列挙と経由毎にastarを計算

function heuristic(now, end)
はend - nowのxy座標の距離をrateで割ったものを推計値としています

//strroute:経路文字列
//now:現在位置
//end:終了位置
//cost:経路コスト
//hcost:推計経路コスト
//maxdepth:最大ネスト深度
//depth:現在のネスト数
//answer:解答経路文字列
//answercost:解答経路コスト
//ret:解決できたか?
function astar(strroute, now, end, cost, hcost, maxdepth, depth)
の解説をします

if(0 < depth) strroute = strroute + "-" + String.fromCharCode(65 + now);
else strroute = String.fromCharCode(65 + now);
で現在の経路を登録しています

if(now == end) {
 if((cost < answercost)||((answercost - eps < cost)&&(cost < answercost + eps)&&(hcost < answerhcost))){
終了判定と良解答判定です
良解答ならば経路文字列などを解答に保存してリターンします

if(maxdepth < depth) return false;
最大ネストより深く潜った場合、解答不能としてリターンします

while(i < num){
この経路から他の経路につながる数の検索を繰り返します

//if(isGone(strroute, next) == false){
 var h = heuristic(next, end);
 if(cost + h < answercost){
次の探索がまだ行っていない場所で(だったんだけれど、巡回経由地問題は複数回踏破しても良いのでコメントアウト)
終点までの推計コストが解答コストよりも小さいのならば

if(h < hcost) h = hcost;
最大推計コストを保存

var r = astar(strroute, next, end, cost + route[now][4 + i][1], h, maxdepth, depth + 1);
ret = (ret || r);
+1ネストして次の検索を再帰呼び出しをします
戻り値をorして解答できたかを保存します

このようにして最短経路を求めます

このアルゴリズムの解説

経路探索は
再帰的全検索で解こうとすると
日が暮れてしまいます

なのでおらはどうしたかというと
設定した最大ネスト深度まで潜ったら
一旦リターンして最大ネスト深度までの解答を検索します

(深追いは禁物ということでネストを深く潜りすぎるのならば
それ以上の計算を諦めて処理を高速化します)

要するに再帰的全検索に最大ネスト深度を設定してネスト制御をしただけです

で、詳細な正解は多分出ないかと思いますが
大体の良解答は出るのではと思います

で巡回セールスマン問題は
巡回地点の全組み合わせを列挙して
その経路探索を行っているだけです









3Dプログラミング入門講座
NAS6LIB
ポリゴンテスト解説・x3dom使い方
その1:ベクトル
その2:行列
その3:クォータニオン
その4:基本総復習・実践
その5:応用その1・メッシュアニメーション、動的テクスチャ
その6:応用その2・GLSL、カスタムシェーダー、キーボード、ファイル
その7:応用その3・ゲームプログラミング、タグの動的追加
その8:応用その4・GLSL、シェーダー、その2
その9:物理演算その1・電卓で相対性理論を解く方法
その10:物理演算その2・相対性理論的ニュートン力学
その11:物理演算その3・ケプラー方程式で惑星軌道シミュレーターを作る
その12:物理演算その4・ルンゲクッタ法で作った 相対性理論的ニュートン力学物理エンジンで惑星軌道シミュレーターを作る
その13:経路探索(A*:A-STAR)&巡回セールスマン問題 : 巨大サイズ : くろにゃんこ
その14:プログラミングにおける配列テーブルテクニック
その15:javascriptのクラス活用法
その16:透視射影公式テスト


 ■■■ THREE.JSプログラミング講座 ■■■ 
THREE.JSテスト解説・THREE.JS使い方
THREE.JS examplesをいじってみた(フレネル反射透過シェーダー)
THREE.JS (半透明シェーダー)
THREE.JS 3D演算で必要な計算(具体例)★とても重要★
THREE.JS THREE-VRM をいじってみた


<<prev ルンゲクッタ法で作った 相対性理論的ニュートン力学物理エンジンで惑星軌道シミュレーターを作る  : プログラミングにおける配列テーブルテクニック next>>





戻る