...省略... <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> ...省略...