category: 未分類
DATE : 2010/08/28 (Sat)
DATE : 2010/08/28 (Sat)
Google Developer Day 2010のDevQuizで出題された「Google Maps API」を解いた際に使用したソースコードです。言語にはJavaScriptを使用しました。動作確認はWindows版Firefox 3.6.8で行っています。APIキーは、xxxxと伏せてあります。
この時点で、もう一方の選択問題である「2-legged OAuth」はすでに解けていました。しかし「2-legged OAuth」は詰まりつつも2時間ほどで解けてしまったので競争率が高そうなこと、「Google Maps API」の方が3問あって得点がより高そうなことから、本問題にも取り組んでみました。
Google Maps APIを使うのは初めてだったので、Google Maps APIから辿れる「Google Maps JavaScript API V2 Reference」をなんとなく見てみると、GDirectionsがなんとなく使えそうなことを発見しました。使えそうなサンプルコードはないかとGoogle Maps API Examplesを覗くと、Processing DirectionsがGDirectionsを使っていたので、そのサンプルコードを改変しながら本問題に取り組み始めました。
入力1、2は以下のソースコードを使いました。なんとなくA*アルゴリズムっぽいものを実装してみました（クローズリストを全然活用してないので、A*ではありません）。移動時間の計算でGoogle Maps APIに問い合わせると非同期で答えが返ってくるため、グローバル変数を多用したかなり見づらいコードになってしまいました。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:v="urn:schemas-microsoft-com:vml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8"/>
<title>Dev Quiz Google Maps 入力1、2用</title>
<script src=" http://maps.google.com/?file=api&v=2.x&key=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
type="text/javascript"></script>
<script type="text/javascript">
// GDirections
var gdir
// 経由地のリスト
var wayPoints
// 開始地点
var startPoint
// 調査対象のリスト
var openList
// 現在で最も小さな移動時間
var currentLowestCost
// 現在で最も低い移動コストを持つノードのリスト
var currentLowestCostNodes
// 現在のノード
var currentNode
// 現在の隣接ノードのリスト
var currentNeighborhoodNodes
// 現在調査中のノード
var currentTargetNode
// 移動時間のキャッシュ
var durationCache = []
// 計算中の始点ノード
var calculatingStartNode
// 計算中の終点ノード
var calculatingEndNode
// ノードを生成する
function Node(point, previousNode) {
this.point = point
this.previous = previousNode
this.cost = 0
}
// 指定の要素の子要素としてテキストを設定する。
function setText(text, elementId) {
var textNode = document.createTextNode(text)
var element = document.getElementById(elementId)
element.replaceChild(textNode, element.firstChild)
}
// 結果を設定する。
function setResult(resultString) {
setText(resultString, "result")
}
// ログを表示する。
function log(logString) {
var logTextArea = document.getElementById("log")
logTextArea.value += logString + "\n"
}
// Google Maps APIを呼び出した回数を表示する。
function setRequestLog(value) {
setText(value, "request_count")
}
// Google Maps APIを呼び出した際に呼び出す。
function requestLog() {
var value = parseInt(document.getElementById("request_count").firstChild.nodeValue, 10)
setText(value + 1, "request_count")
}
// ログを消去する。
function clearLog() {
var logTextArea = document.getElementById("log")
logTextArea.value = ""
setRequestLog(0)
}
// ノードのリストをログに出力する。
function logNodeList(name, nodeList) {
var logString = name + ": ["
for (var i = 0; i < nodeList.length; i++) {
if (0 < i) {
logString += ", "
}
logString += nodeList[i].point.name
}
logString += "]"
log(logString)
}
// 「(緯度,経度)」の形式の文字列を作成する。
function createPointString(point) {
return "(" + point.latitude + "," + point.longitude + ")"
}
// Google Maps APIへのクエリ文字列を作成する。
function createQuery(start, end) {
return "from: " + createPointString(start) + " to: " + createPointString(end)
}
// 移動時間の計算が終わると呼び出される。
function handleLoading() {
if (gdir.getStatus().code == 200) {
var durationSeconds = gdir.getDuration().seconds
durationCache.push({
start: calculatingStartNode.point,
end: calculatingEndNode.point,
duration: durationSeconds})
durationCalculated(durationSeconds)
} else {
setResult("error: " + gdir.getStatus().code + " on " +
startPoint.name + " to " + endPoint.name)
}
}
// 最も低い移動コストを返す。
function getLowestCost() {
var lowestCost = Number.MAX_VALUE
for (var i = 0; i < openList.length; i++) {
if (openList[i].cost < lowestCost) {
lowestCost = openList[i].cost
}
}
return lowestCost
}
// 最も小さな移動コストを持つノードのリストを返す。
function getLowestCostNodes() {
lowestCost = getLowestCost()
var lowestCostNodes = []
for (var i = 0; i < openList.length; i++) {
if (openList[i].cost == lowestCost) {
lowestCostNodes.push(openList[i])
}
}
return lowestCostNodes
}
// 出発点に戻ってきたか否かを返す。
function isGoal(node) {
return node.previous != null && node.point == startPoint
}
// ノードから経由地のリストを生成する。
function getPoints(node) {
var points = []
do {
points.push(node.point)
node = node.previous
} while (node != null)
return points
}
// 結果を表示する。
function finish(node) {
route = getPoints(node)
route.reverse()
resultString = ""
for (var i = 0; i < route.length; i++) {
if (0 < i) {
resultString += " "
}
resultString += route[i].name
}
setResult(resultString)
}
// 計算済みのリストへ移動する。
// しかし計算済みのリストを活用しないため、ただ計算対象のリストから除くのみ。
function moveToCloseList(node) {
for (var i = 0; i < openList.length; i++) {
if (openList[i] === node) {
openList.splice(i, 1)
break
}
}
}
// 各経由地をすべて含むリストを作成する。
function createAllPoints() {
var points = []
for (var i = 0; i < wayPoints.length; i++) {
points.push(wayPoints[i])
}
return points
}
// 指定のノードの隣接ノードのリストを返す。
function getNeighborhoodNodes(startNode) {
points = getPoints(startNode)
neighborhoodPoints = createAllPoints()
for (var i = 0; i < points.length; i++) {
for (var j = 0; j < neighborhoodPoints.length; j++) {
if (points[i].name == neighborhoodPoints[j].name) {
neighborhoodPoints.splice(j, 1)
j -= 1
}
}
}
var neighborhoodNodes = []
if (0 < neighborhoodPoints.length) {
for (var i = 0; i < neighborhoodPoints.length; i++) {
neighborhoodNodes.push(new Node(neighborhoodPoints[i], startNode))
}
} else if (points.length == wayPoints.length) {
neighborhoodNodes.push(new Node(startPoint, startNode))
}
return neighborhoodNodes
}
// キャッシュから距離を返す。
// キャッシュ内に見つからない場合はnullを返す。
function getDurationFromCache(startPoint, endPoint) {
for (var i = 0; i < durationCache.length; i++) {
if (startPoint.latitude == durationCache[i].start.latitude &&
startPoint.longitude == durationCache[i].start.longitude &&
endPoint.latitude == durationCache[i].end.latitude &&
endPoint.longitude == durationCache[i].end.longitude) {
return durationCache[i].duration
}
}
return null
}
// 移動時間が求まると呼び出される。
function durationCalculated(duration) {
log("duration is " + duration)
currentTargetNode.cost = currentNode.cost + duration
log("(tartget)" + currentTargetNode.point.name + " cost : " + currentTargetNode.cost)
calculateOnNeighborhoodNodes()
}
// 移動コストを計算する。
function calculateCost(startNode, endNode) {
calculatingStartNode = startNode
calculatingEndNode = endNode
log("Calculate duration from " + startNode.point.name + " to " + endNode.point.name)
var duration = getDurationFromCache(startNode.point, endNode.point)
if (duration != null) {
durationCalculated(duration)
} else {
// 最終的に、非同期にdurationCalculatedを呼び出す。
gdir.load(createQuery(startNode.point, endNode.point),
{travelMode: G_TRAVEL_MODE_DRIVING})
requestLog()
}
}
// 隣接ノードのコストを計算する。
function calculateOnNeighborhoodNodes() {
if (0 < currentNeighborhoodNodes.length) {
currentTargetNode = currentNeighborhoodNodes.pop()
calculateCost(currentNode, currentTargetNode)
openList.push(currentTargetNode)
} else {
calculateOnLowestCostNodes()
}
}
// 最も低い移動コストを持つノードの移動コストを計算する。
function calculateOnLowestCostNodes() {
if (0 < currentLowestCostNodes.length && currentLowestCost == getLowestCost()) {
currentNode = currentLowestCostNodes.pop()
log("Current node is " + currentNode.point.name)
if (isGoal(currentNode)) {
finish(currentNode)
} else {
moveToCloseList(currentNode)
currentNeighborhoodNodes = getNeighborhoodNodes(currentNode)
logNodeList("Neighborhood nodes", currentNeighborhoodNodes)
calculateOnNeighborhoodNodes()
}
} else {
calculate()
}
}
// 最も移動時間の短い経路を計算する。
function calculate() {
if (openList.length != 0) {
currentLowestCost = getLowestCost()
currentLowestCostNodes = getLowestCostNodes()
calculateOnLowestCostNodes()
} else {
setResult("失敗")
}
}
// 経路を計算する。
function calculateRoute() {
setResult("Calculating...")
startPoint = wayPoints[0]
var startNode = new Node(startPoint, null)
log("Start node is " + startNode.point.name)
openList = [startNode]
calculate()
}
// 各経由地を取得する。
function getWayPoints() {
var inputTextArea = document.getElementById("input")
var inputText = inputTextArea.value
var wayPoints = []
data = inputText.split(/\r?\n/)
for (var i = 0; i < data.length; i++) {
var elements = data[i].split(" ")
if (elements.length == 3) {
wayPoints.push({
name: elements[0],
latitude: elements[1],
longitude: elements[2]})
}
}
for (var i = 0; i < wayPoints.length; i++) {
log(wayPoints[i].name + " " +
wayPoints[i].latitude + " " +
wayPoints[i].longitude)
}
return wayPoints
}
// 初期化を行う。
function initialize() {
setResult("Initializing...")
clearLog()
log("Get waypoints...")
wayPoints = getWayPoints()
gdir = new GDirections(null, null)
GEvent.addListener(gdir, "error", handleErrors)
GEvent.addListener(gdir, "load", handleLoading)
log("Start calculate...")
calculateRoute()
}
// Google Maps APIからエラーが返ってきた場合に呼び出される。
// 本関数は、以下のサンプルのままである。
// http://code.google.com/intl/ja/apis/maps/documentation/javascript/v2/examples/directions-advanced.html
function handleErrors(){
if (gdir.getStatus().code == G_GEO_UNKNOWN_ADDRESS)
alert("No corresponding geographic location could be found for one of the specified addresses. This may be due to the fact that the address is relatively new, or it may be incorrect.\nError code: " + gdir.getStatus().code);
else if (gdir.getStatus().code == G_GEO_SERVER_ERROR)
alert("A geocoding or directions request could not be successfully processed, yet the exact reason for the failure is not known.\n Error code: " + gdir.getStatus().code);
else if (gdir.getStatus().code == G_GEO_MISSING_QUERY)
alert("The HTTP q parameter was either missing or had no value. For geocoder requests, this means that an empty address was specified as input. For directions requests, this means that no query was specified in the input.\n Error code: " + gdir.getStatus().code);
else if (gdir.getStatus().code == G_GEO_BAD_KEY)
alert("The given key is either invalid or does not match the domain for which it was given. \n Error code: " + gdir.getStatus().code);
else if (gdir.getStatus().code == G_GEO_BAD_REQUEST)
alert("A directions request could not be successfully parsed.\n Error code: " + gdir.getStatus().code);
else alert("An unknown error occurred.");
}
</script>
</head>
<body onunload="GUnload()">
<h1>Input:</h1>
<div>
<textarea id="input" rows="12" cols="50"></textarea>
<button type="button" onclick="initialize()">OK</button>
<h1>Output:</h1>
<div>
<p id="result">Please input.</p>
</div>
<h1>Log:</h1>
<div>
<p>Request count: <span id="request_count">0</span></p>
<textarea id="log" rows="20" cols="70"></textarea>
</div>
</body>
</html>
入力3には以下のソースコードを使いました。入力3を前述のソースコードで解こうとすると、Google Maps APIの1日のリクエスト可能数を越えてしまいました。どうも、前述のソースコードではキャッシュがうまく働いていないようでした。またこの時点で、本問題が巡回セールスマン問題に相当していることにようやく気付きました。そこで遺伝的アルゴリズムを使用して入力3の問題を解こうと思いつきました。
しかし単純に遺伝的アルゴリズムを導入してしまうと、Google Maps APIに大量にリクエストしてしまいます。なにしろ、遺伝的アルゴリズムではランダムに大量に生成した回答から優秀なものを選び出したり組み合わせたり一部を変化させたりして新しい回答を生み出し、それを何度も繰り返すわけですから。
そこで、次のような戦略を考えました。まず、遺伝的アルゴリズムで生成した回答から距離を計算します。この計算は、Google Maps APIを使わずに行います。その計算から得られた回答を元に、Google Maps APIを使って移動時間を計算します。つまり遺伝的アルゴリズムで距離による近似解を生成して、Google Maps APIで厳密解を得ようという寸法です。
距離の計算にはヒュベニの公式を使用しました。詳しくは「二地点の緯度・経度からその距離を計算する」を参照してください。Google Maps APIの測地系は世界測地系なので、ヒュベニの公式で用いられる定数も世界測地系のものを選択しました。
遺伝的アルゴリズムで用いられる遺伝子の構造は次のようにしました。基本的には、出発点・終点を除いた経由地からなるリストを用意し、そのリスト内の番号のリストです。しかし、次のような工夫を行いました。まず、終点の一歩手前の経由地は、それまでの経由地が決まれば一意に決まるため除きます。さらにリスト内の番号については、出発点・終点を除いて同じ経由地が出てくることはないため、これまでの経由地をリストから除いた状態での番号としました。こうすることで、同じ経由地を2度回るような明らかに非効率的な遺伝子を排除できました。
これまでの考えを取り込んだソースコードは以下のとおりです。
なお、後ほど確認してみたのですが本コードに入力1、2を使用すると、エラーで停止してしまいます。修正しようとも思ったのですが、問題を解いた時点のソースコードからの修正は最小限にしたかったためそのままにしてあります。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:v="urn:schemas-microsoft-com:vml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8"/>
<title>Dev Quiz Google Maps 入力3用</title>
<!-- 参考: http://groups.google.com/group/google-maps-api/browse_thread/thread/58f5a3503da859e1 -->
<script type="text/javascript">
tick = function() { }
</script>
<script src=" http://maps.google.com/?file=api&v=2.x&key=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
type="text/javascript"></script>
<script type="text/javascript">
// GDirections
var gdir
// 経由地の配列
var wayPoints
// 距離を格納した配列
var distances
// 遺伝子の配列
var genes
// 移動時間の配列
var durations = []
// Google Mapsによって移動時間の計算が終わった遺伝子を格納する配列
var calculatedGene
// 距離計算に使うための定数など
// 参考 : http://yamadarake.web.fc2.com/trdi/2009/report000001.html
var a = 6378137.000
var b = 6356752.314140
var e = Math.sqrt((Math.pow(a, 2) - Math.pow(b, 2)) / Math.pow(a, 2))
var mNumerator = a * (1 - Math.pow(e, 2))
// 度からラジアンへの変換
var toRad = 180 / Math.PI
// GAに関する設定
// 遺伝子の数
var POP_SIZE = 2000
// 世代数
var MAX_ITERATION = 100
// エリートの数
var ELETE_RATE = 0.2
// 突然変異が発生する可能性
var MUTATION_PROBABILITY = 0.1
// Google Maps APIにリクエストする最大数
var MAX_REQUEST = 100
// 指定のElementにTextノードを設定する。
function setText(text, elementId) {
var textNode = document.createTextNode(text)
var element = document.getElementById(elementId)
element.replaceChild(textNode, element.firstChild)
}
// 結果を設定する。
function setResult(resultString) {
setText(resultString, "result")
}
// ログを表示する。
function log(logString) {
var logTextArea = document.getElementById("log")
logTextArea.value += logString + "\n"
}
// Google Mapsに対してリクエストした回数を設定する。
function setRequestLog(value) {
setText(value, "request_count")
}
// Google Mapsに対してリクエストしたことを記録する。
function requestLog() {
var value = parseInt(document.getElementById("request_count").firstChild.nodeValue, 10)
setText(value + 1, "request_count")
}
// ログを削除する。
function clearLog() {
var logTextArea = document.getElementById("log")
logTextArea.value = ""
setRequestLog(0)
}
// startからendまでの距離を計算する。
function getDistance(start, end) {
x1 = start.latitude * toRad
y1 = start.longitude * toRad
x2 = end.latitude * toRad
y2 = end.longitude * toRad
dx = x1 - x2
dy = y1 - y2
muy = (y1 + y2) / 2
w = Math.sqrt(1 - (Math.pow(e, 2) * Math.pow(Math.sin(muy), 2)))
m = mNumerator / Math.pow(w, 3)
n = (a / w)
return Math.sqrt(Math.pow(dy * m, 2) + Math.pow(dx * n * Math.cos(muy), 2))
}
// 指定の遺伝子が表現する経路全体の距離を計算する。
function calculateDistance(gene, wayPoints) {
var currentWayPoints = wayPoints.slice(1, wayPoints.length)
var distance = 0
var start = wayPoints[0]
for (var i = 0; i < gene.length; i++) {
var geneIndex = gene[i]
var end = currentWayPoints[geneIndex]
distance += getDistance(start, end)
currentWayPoints.splice(geneIndex, 1)
start = end
}
end = currentWayPoints[0]
distance += getDistance(start, end)
start = end
end = wayPoints[0]
distance += getDistance(start, end)
return distance
}
// 遺伝子の各要素の値を範囲に収まるように調節する。
function tidyGene(gene, wayPoints) {
var max_number = wayPoints.length - 1
for (var i = 0; i < gene.length; i++) {
gene[i] %= max_number
max_number--
}
}
// 遺伝子を作成する。
function createInitialGenes(wayPoints, popSize) {
var geneLength = wayPoints.length - 2
var genes = []
for (var i = 0; i < popSize; i++) {
var a_gene = []
for (var index = 0; index < geneLength; index++) {
a_gene.push(Math.floor(Math.random() * (geneLength - 1)))
}
tidyGene(a_gene, wayPoints)
genes.push(a_gene)
}
return genes
}
// 「(緯度,経度)」の形式の文字列を生成する。
function createPointString(point) {
return "(" + point.latitude + "," + point.longitude + ")"
}
// Google Mapsのルート計算が終わると呼び出される。
function handleLoading() {
if (gdir.getStatus().code == 200) {
var durationSeconds = gdir.getDuration().seconds
durations.push({gene: calculatedGene, duration: durationSeconds})
calculateDurations()
} else {
setResult("error: " + gdir.getStatus().code + " on " +
startPoint.name + " to " + endPoint.name)
}
}
// テキストボックスから出発点・経由地を取得する。
function getWayPoints() {
var inputTextArea = document.getElementById("input")
var inputText = inputTextArea.value
wayPoints = []
data = inputText.split(/\r?\n/)
for (var i = 0; i < data.length; i++) {
var elements = data[i].split(" ")
if (elements.length == 3) {
wayPoints.push({
name: elements[0],
latitude: elements[1],
longitude: elements[2]})
}
}
for (var i = 0; i < wayPoints.length; i++) {
log(wayPoints[i].name + " " +
wayPoints[i].latitude + " " +
wayPoints[i].longitude)
}
return wayPoints
}
// 距離を比較する。
function compareDistance(x, y) {
return x.distance - y.distance
}
// 遺伝子に突然変異を起こす。
function mutate(source_gene, wayPoints) {
var gene = []
gene = gene.concat(source_gene)
gene[Math.random() * (gene.length - 1)] = Math.random() * 9
tidyGene(gene, wayPoints)
return gene
}
// 遺伝子を交叉させる。
function crossover(source_gene1, source_gene2, wayPoints) {
var gene = []
// 以下の式の-3は、交叉の結果生まれた遺伝子が、source_gene1, source_gene2の
// いずれかと一致しないようにするためである。
// それぞれの-1の内訳は、以下のとおりである。
// 1) インデックスの範囲を超えないようにするため。
// 2) 生成された遺伝子がsource_gene2と等しくならないようにするため。
// 3) （+1も含む）生成された遺伝子がe1source_genと等しくならないようにするため。
var gene1SeparatePoint = Math.floor((Math.random() * (source_gene1.length - 3)) + 1)
gene = gene.concat(
source_gene1.slice(0, gene1SeparatePoint))
gene = gene.concat(
source_gene2.slice(gene1SeparatePoint, source_gene2.length))
tidyGene(gene, wayPoints)
return gene
}
// 遺伝子から距離を計算し、昇順に並べる。
// 戻り値は、プロパティにdistance, geneを持つオブジェクトのリストである。
function rankDistances(genes, wayPoints) {
var currentDistances = []
for (var i = 0; i < genes.length; i++) {
var a_gene = genes[i]
currentDistances.push({
distance: calculateDistance(a_gene, wayPoints),
gene: a_gene})
}
currentDistances.sort(compareDistance)
return currentDistances
}
// エリートな遺伝子を1つ取得する。
function getEleteGene(distances, eleteCount) {
return distances[Math.floor(Math.random() * (eleteCount - 1))].gene
}
// 遺伝子同士が等しいか否かを返す。
function isGeneEquals(gene1, gene2) {
for (var i = 0; i < gene1.length; i++) {
if (gene1[i] != gene2[i]) {
return false
}
}
return true
}
// 遺伝子の、重複を含まないリストを返す。
function filterGene(distances) {
var currentGenes = []
var index = 0
while (currentGenes.length < MAX_REQUEST && index < distances.length) {
var currentDistance = distances[index]
var inserted = false
for (var i = 0; i < currentGenes.length; i++) {
if (isGeneEquals(currentDistance.gene, currentGenes[i])) {
inserted = true
break
}
}
if (!inserted) {
currentGenes.push(currentDistance.gene)
}
index++
}
return currentGenes
}
// 移動時間を比較する。
function compareDurations(x, y) {
return x.duration - y.duration
}
// 遺伝子を出力値に変換する。
function decodeGene(gene) {
var first = true
var currentWayPoints = wayPoints.slice(1, wayPoints.length)
var decodedString = wayPoints[0].name
for (var i = 0; i < gene.length; i++) {
var wayPointIndex = gene[i]
decodedString += " " + currentWayPoints[wayPointIndex].name
currentWayPoints.splice(wayPointIndex, 1)
}
decodedString += " " + currentWayPoints[0].name + " " + wayPoints[0].name
return decodedString
}
// すべての遺伝子について移動時間を計算し終えると呼び出される。
function durationCompleted() {
durations.sort(compareDurations)
setResult(decodeGene(durations[0].gene))
}
// 移動時間を計算する。
function calculateDurations() {
var index = durations.length
if (genes.length <= index) {
durationCompleted()
return
}
var aGene = genes[index]
var targetWayPoints = [createPointString(wayPoints[0])]
var currentWayPoints = wayPoints.slice(1, wayPoints.length)
for (var i = 0; i < aGene.length; i++) {
var wayPointIndex = aGene[i]
targetWayPoints.push(
createPointString(currentWayPoints[wayPointIndex]))
currentWayPoints.splice(wayPointIndex, 1)
}
targetWayPoints.push(createPointString(currentWayPoints[0]))
targetWayPoints.push(createPointString(wayPoints[0]))
calculatedGene = aGene
gdir.loadFromWaypoints(targetWayPoints, {travelMode: G_TRAVEL_MODE_DRIVING})
requestLog()
}
// 最短の移動時間となる経由地の順序を計算する。
function calculate(wayPoints) {
var currentGenes = createInitialGenes(wayPoints, POP_SIZE)
var eleteCount = POP_SIZE * ELETE_RATE
for (var iteration = 0; iteration < MAX_ITERATION; iteration++) {
var currentDistances = rankDistances(currentGenes, wayPoints)
currentGenes.splice(0, currentGenes.length)
var index = 0;
while (currentGenes.length < eleteCount) {
var currentElete = currentDistances[index].gene
var inserted = false
for (var listIndex = 0; listIndex < currentGenes.length; listIndex++) {
if (isGeneEquals(currentGenes[listIndex], currentElete)) {
inserted = true
break
}
}
if (!inserted) {
currentGenes.push(currentDistances[index].gene)
}
index++
}
for (var i = 0; i < (POP_SIZE - currentGenes.length); i++) {
if (Math.random() < MUTATION_PROBABILITY) {
currentGenes.push(
mutate(getEleteGene(currentDistances, eleteCount),
wayPoints))
} else {
var gene1 = getEleteGene(currentDistances, eleteCount)
var gene2 = getEleteGene(currentDistances, eleteCount)
currentGenes.push(crossover(gene1, gene2, wayPoints))
}
}
log("iteration: " + iteration +
", best distance: " + currentDistances[0].distance +
" gene: " + currentDistances[0].gene.length)
}
distances = rankDistances(currentGenes, wayPoints)
log("iteration end. best distance: " + distances[0].distance)
genes = filterGene(distances)
calculateDurations()
}
// 初期化する。
function initialize() {
setResult("Initializing...")
clearLog()
log("Get waypoints...")
var wayPoints = getWayPoints()
gdir = new GDirections(null, null)
GEvent.addListener(gdir, "error", handleErrors)
GEvent.addListener(gdir, "load", handleLoading)
log("Start calculate...")
calculate(wayPoints)
}
// Google Maps APIからエラーが返ってきた場合に呼び出される。
// 本関数は、以下のサンプルのままである。
// http://code.google.com/intl/ja/apis/maps/documentation/javascript/v2/examples/directions-advanced.html
function handleErrors(){
if (gdir.getStatus().code == G_GEO_UNKNOWN_ADDRESS)
alert("No corresponding geographic location could be found for one of the specified addresses. This may be due to the fact that the address is relatively new, or it may be incorrect.\nError code: " + gdir.getStatus().code);
else if (gdir.getStatus().code == G_GEO_SERVER_ERROR)
alert("A geocoding or directions request could not be successfully processed, yet the exact reason for the failure is not known.\n Error code: " + gdir.getStatus().code);
else if (gdir.getStatus().code == G_GEO_MISSING_QUERY)
alert("The HTTP q parameter was either missing or had no value. For geocoder requests, this means that an empty address was specified as input. For directions requests, this means that no query was specified in the input.\n Error code: " + gdir.getStatus().code);
else if (gdir.getStatus().code == G_GEO_BAD_KEY)
alert("The given key is either invalid or does not match the domain for which it was given. \n Error code: " + gdir.getStatus().code);
else if (gdir.getStatus().code == G_GEO_BAD_REQUEST)
alert("A directions request could not be successfully parsed.\n Error code: " + gdir.getStatus().code);
else alert("An unknown error occurred.");
}
</script>
</head>
<body onunload="GUnload()">
<h1>Input:</h1>
<div>
<textarea id="input" rows="12" cols="50"></textarea>
<button type="button" onclick="initialize()">OK</button>
<h1>Output:</h1>
<div>
<p id="result">Please input.</p>
</div>
<h1>Log:</h1>
<div>
<p>Request count: <span id="request_count">0</span></p>
<textarea id="log" rows="20" cols="70"></textarea>
</div>
</body>
</html>
さて、これまで長々としたソースコードを展開してきたわけですが、本問題への取り組みはさまざまな反省点を残しました。
まずは、Google Maps APIのドキュメントをあまりよく見ていなかったことです。DevQuiz終了後に公開されたさまざまな回答を見ると、Google Maps API Web ServicesのGoogle Directions APIを使用しているコードを見かけました。ざっとAPIドキュメントを眺めた時点ではGoogle Maps JavaScript APIが目に飛び込んできたのでJavaScriptを使用したわけですが、Google Maps API Web Serviceを使用していればPythonなどのいつも自分が慣れ親しんだ言語を使用することもできました。
また実際には遺伝的アルゴリズムを使用するほどではなかったことも反省すべき点です。各経由地同士の行き帰りの移動時間をあらかじめGoogle Maps APIに問い合わせてメモリに保存しておけば良かったのです。入力1、2用のコードではキャッシュの仕組みがうまく動いていなかったこと、またこの時点で大量のJavaScriptコードを書いていて、コードの規模を縮小する方向に考えが及ばなかったことが遺伝的アルゴリズムの導入を促してしまったように思います。
このようにさまざまな反省点を残しましたが、なんとか入力3まですべて解けたので良しとしたいところではあります。
PR
●この記事にコメントする
忍者ブログ [PR]
