．．．省略．．．

＜script＞

var route = [
['A', 0, [63, 63], 3, [1, 2, [144, 40]], [2, 1, [0, 105]], [3, 1.2, [110, 100]]],
['B', 1, [224, 63], 3, [0, 2, [-1, -1]], [3, 1.2, [180, 140]], [4, 1.2, [250, 100]]],
['C', 2, [46, 152], 2, [0, 1, [-1, -1]], [5, 1, [5, 210]]],
['D', 3, [151, 143], 3, [0, 1.2, [-1, -1]], [1, 1.2, [-1, -1]], [5, 1.2, [80, 180]]],
['E', 4, [248, 165], 3, [1, 1.2, [-1, -1]], [5, 1.2, [170, 230]], [6, 1, [260, 220]]],
['F', 5, [101, 227], 4, [2, 1, [-1, -1]], [3, 1.2, [-1, -1]], [4, 1.2, [-1, -1]], [6, 2, [140, 270]]],
['G', 6, [264, 254], 2, [4, 1, [-1, -1]], [5, 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)||(6 ＜ 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 ＜= 6)){
      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)||(6 ＜ 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/astar.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, 320, 320);
  ctx.drawImage(img, 0, 0);
  var strs;
  var str;
  var now;
  var num;
  var i;
  var p0;
  var p1;
  for(now = 0; now ＜ 7; 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＞

．．．省略．．．