category: 未分類
DATE : 2010/08/28 (Sat)
DATE : 2010/08/28 (Sat)
Google Developer Day 2010のDevQuizで出題された「Shiritori」レベル3を解いた際に使用したソースコードです。言語にはPythonを使用しました。サーバの回答を入力すると、自分が答えるべき単語を出力するというスクリプトです。出力までには1～3分ほど時間がかかります。辞書は、スクリプトと同じディレクトリに以下の形式でdata.txtを置くことで設定します。
* （単語1）
* （単語2）
* （単語3）
* （以下同様）
本ソースコードでは、アルファベータ法を実装してみました。しかし、初めに作成したコードでは、レベル1やレベル2は突破できたものの、レベル3は単語の候補が多くなりすぎて、プログラムから全く回答が返ってこないという状態になってしまいました。
そこで先読みの深さを制限するほかに、枝刈りを行いました。例えば、axxb, ayyb, bxxa, byya
という辞書があったとし、サーバがaxxbを回答したとします。プレイヤーの候補はbxxaもしくはbyyaとなります。ところがそのどちらを選んでも、辞書の中にayybという、プレイヤーに再びbのつく単語を選ばせることのできる単語が存在するため、サーバはその単語を回答してくると予測できます。すると、プレイヤーの候補としてbxxa, byyaのそれぞれを候補としてその先の手を読むのではなく、どちらか一方、例えばbxxaだけの先の手を読むだけで十分です。このように、プレイヤーが前回と同じ文字を先頭に持つ単語を回答しなければならない状況になりうる単語が複数ある場合は、そのうちの1つのみを先読みの候補とし、それ以外は無視することで枝刈りを行いました。特にレベル3はこのような状況になる単語が大量にあるため、この枝刈りを行うことで、答えが全く返ってこなくなる状況から、1～3分待てば回答が返ってくるほどまでに進歩しました。
#!/usr/bin/env python
# coding: UTF-8
import re
import sys
import bisect
# 辞書のパス
DICTIONARY_FILE = u'data.txt'
# 辞書から単語を取り出すための正規表現。
WORD_PATTERN = re.compile(ur'\s*\*\s*(\w+)\s*')
# 探索を行う深さ
FIRST_DEPTH = 10
MAX_SCORE = sys.maxint
MIN_SCORE = -sys.maxint - 1
# 自分が勝ったことを表す
MY_WIN = MAX_SCORE - 1
# サーバが勝ったことを表す
SERVER_WIN = MIN_SCORE + 1
# ターンを表す定数
MY_TURN = 0
SERVER_TURN = 1
def compress_word(word):
u"""
単語を2文字に圧縮する。
"""
if 2 < len(word):
return word[0] + word[len(word) - 1]
else:
return word
class CompressedDictionary(list):
u"""
圧縮された単語からなる辞書。
"""
def __init__(self, source_dictionary):
self.extend([compress_word(a_word) for a_word in source_dictionary])
self.sort()
def __contains__(self, item):
index = bisect.bisect_left(self, item)
return index < len(self) and self[index] == item
def clone(self):
u"""
本辞書を複製する。
"""
return CompressedDictionary(self)
def get_word(self, compressed_word, source_dictionary):
u"""
圧縮された辞書から元の単語を取り出す。
"""
if compressed_word in self:
for a_word in source_dictionary:
if a_word[0] == compressed_word[0] and \
a_word[len(a_word) - 1] == compressed_word[1]:
return a_word
else:
raise ValueError()
def remove(self, x):
u"""
辞書から単語を削除する。
"""
index = bisect.bisect_left(self, x)
if index < len(self) and self[index] == x:
del self[index]
else:
raise ValueError()
def remove_word(self, word):
u"""
辞書から単語を、未圧縮の単語を指定して削除する。
"""
first_character = word[0]
last_character = word[len(word) - 1]
index = bisect.bisect_left(self, word)
if index < len(self):
candidate_word = self[index]
if candidate_word[0] == first_character and \
candidate_word[1] == last_character:
self.remove(candidate_word)
else:
raise ValueError()
def load_dictionary(dictionary_file):
u"""
辞書をファイルから読み込む。
"""
dictionary = []
with open(dictionary_file, 'r') as f:
for a_line in f:
match = WORD_PATTERN.match(a_line)
if match:
dictionary.append(match.group(1))
return dictionary
def input_server_word(previous_word, dictionary):
u"""
サーバからの回答を入力する。
"""
while True:
print "Please input server's word."
source_word = raw_input('---> ')
word = compress_word(source_word)
if word in dictionary:
if previous_word:
if previous_word[1] == word[0]:
return word
else:
print '%s is invalid word. Please retry.' % (source_word)
else:
return word
else:
print '%s is not in dictioary. Please retry.' % (source_word)
def get_candidate_words(previous_word, current_dictionary):
u"""
回答の候補となる単語を返す。
"""
previous_last_character = previous_word[1]
return [a_word for a_word in current_dictionary
if a_word[0] == previous_last_character]
def has_win_word(candidate_words, current_dictionary):
u"""
勝利できる単語が候補中にあるか否かを返す。
勝利できる単語とは、末尾の文字を先頭に持つ単語が
辞書の中にないような単語のことである。
"""
for a_candidate in candidate_words:
last_candidate_character = a_candidate[1]
for next_candidate in current_dictionary:
if next_candidate[0] == last_candidate_character:
break
else:
return True
else:
return False
def get_dead_rate_in_bad_loop(candidate_words, current_dictionary):
u"""
ループになる可能性を返す。
"""
dead_count = 0
for my_candidate_word in candidate_words:
alive = True
my_candidate_first_character = my_candidate_word[0]
for opponent_word in get_candidate_words(
my_candidate_word, current_dictionary):
if opponent_word[1] == my_candidate_first_character:
dead_count += 1
return float(dead_count) / len(candidate_words)
def get_frame_rate(previous_word, candidate_words):
u"""
ループにはめられている可能性を返す。
"""
frame_count = 0
target_character = previous_word[0]
for my_candidate_word in candidate_words:
if my_candidate_word[1] == target_character:
frame_count += 1
return float(frame_count) / len(candidate_words)
def calculate_score(turn, previous_word, current_dictionary):
u"""
スコアを計算する。
"""
candidate_words = get_candidate_words(previous_word, current_dictionary)
if 0 < len(candidate_words):
if has_win_word(candidate_words, current_dictionary):
if turn == MY_TURN:
return MY_WIN
elif turn == SERVER_TURN:
return SERVER_WIN
else:
print u'失敗'
else:
score = 0
dead_score = 50
dead_rate = get_dead_rate_in_bad_loop(
candidate_words, current_dictionary)
if dead_rate == 1:
if turn == MY_TURN:
return SERVER_WIN
elif turn == SERVER_TURN:
return MY_WIN
else:
print u'失敗'
score -= int(dead_score * dead_rate)
frame_score = 100
frame_rate = get_frame_rate(previous_word, candidate_words)
score += int(frame_score * frame_rate)
score *= len(candidate_words)
if turn == MY_TURN:
return score
elif turn == SERVER_TURN:
return -score
else:
print u'失敗'
else:
if turn == MY_TURN:
return SERVER_WIN
elif turn == SERVER_TURN:
return MY_WIN
else:
print u'失敗'
def get_server_candidate_list(my_word, current_dictionary):
u"""
サーバが回答する可能性のある単語のリストを返す。
"""
candidate_words = list(set(get_candidate_words(my_word, current_dictionary)))
candidate_words.sort(lambda x, y: cmp(
calculate_score(MY_TURN, x, current_dictionary),
calculate_score(MY_TURN, y, current_dictionary)))
return candidate_words
def is_loop(opponent_word, candidate_word, current_dictionary):
u"""
指定の単語でループに入るかどうかを返す。
"""
last_loop_character = opponent_word[1]
opponent_candidates = get_candidate_words(candidate_word, current_dictionary)
for a_opponent_candidate in opponent_candidates:
if a_opponent_candidate[1] == last_loop_character:
return True
else:
return False
def select_server_word(history, dictionary, limit, depth):
u"""
サーバ側の回答を予測する。
"""
my_word = history[len(history) - 1]
current_dictionary = dictionary.clone()
current_dictionary.remove(my_word)
if depth == 0:
return calculate_score(SERVER_TURN, my_word, current_dictionary), None
score = MAX_SCORE
word = None
candidate_words = get_server_candidate_list(my_word, current_dictionary)
if 0 < len(candidate_words):
loop_candidates = [a_candidate for a_candidate in candidate_words
if is_loop(my_word, a_candidate, current_dictionary)]
for a_loop_candidate in loop_candidates:
candidate_words.remove(a_loop_candidate)
if 0 < len(loop_candidates):
a_loop_candidate = loop_candidates[0]
current_history = history[:] + [a_loop_candidate]
candidate_score, _ = select_my_word(
current_history, current_dictionary, score, depth - 1)
score = candidate_score
word = a_loop_candidate
if score != SERVER_WIN and limit <= score:
for a_candidate_word in candidate_words:
current_history = history[:] + [a_candidate_word]
candidate_score, _ = select_my_word(
current_history, current_dictionary, score, depth - 1)
if candidate_score < score:
score = candidate_score
word = a_candidate_word
if score == SERVER_WIN or score <= limit:
break
return score, word
else:
return MY_WIN, None
def get_my_candidate_list(server_word, current_dictionary):
u"""
自分が回答できる単語のリストを返す。
"""
candidate_words = list(set(get_candidate_words(server_word, current_dictionary)))
candidate_words.sort(lambda x, y: cmp(
calculate_score(SERVER_TURN, x, current_dictionary),
calculate_score(SERVER_TURN, y, current_dictionary)))
candidate_words.reverse()
return candidate_words
def select_my_word(history, dictionary, limit, depth):
u"""
自分の回答を予測する。
"""
server_word = history[len(history) - 1]
current_dictionary = dictionary.clone()
current_dictionary.remove(server_word)
if depth == 0:
return calculate_score(MY_TURN, server_word, current_dictionary), None
score = MIN_SCORE
word = None
candidate_words = get_my_candidate_list(server_word, current_dictionary)
if 0 < len(candidate_words):
loop_candidates = [a_candidate for a_candidate in candidate_words
if is_loop(server_word, a_candidate, current_dictionary)]
for a_loop_candidate in loop_candidates:
candidate_words.remove(a_loop_candidate)
if 0 < len(loop_candidates):
a_loop_candidate = loop_candidates[0]
current_history = history[:] + [a_loop_candidate]
candidate_score, _ = select_server_word(
current_history, current_dictionary, score, depth - 1)
score = candidate_score
word = a_loop_candidate
if score != MY_WIN and score <= limit:
for a_candidate_word in candidate_words:
current_history = history[:] + [a_candidate_word]
candidate_score, _ = select_server_word(
current_history, current_dictionary, score, depth - 1)
if score < candidate_score:
score = candidate_score
word = a_candidate_word
if candidate_score == MY_WIN or limit <= score:
break
return score, word
else:
return SERVER_WIN, None
def calculate_my_word(server_word, dictionary, max_depth):
u"""
次に出すべき単語を求める。
"""
score, my_word = select_my_word([server_word], dictionary, MAX_SCORE, max_depth)
return my_word
def main():
source_dictionary = load_dictionary(DICTIONARY_FILE)
dictionary = CompressedDictionary(source_dictionary)
server_word = input_server_word(None,dictionary)
current_dictionary = dictionary.clone()
depth = FIRST_DEPTH
turn = 1
while True:
my_word = calculate_my_word(server_word, current_dictionary, depth)
current_dictionary.remove_word(server_word)
select_word = current_dictionary.get_word(my_word, source_dictionary)
print 'Select %s' % (select_word)
print '\n'
current_dictionary.remove(my_word)
server_word = input_server_word(my_word, current_dictionary)
turn += 1
if __name__ == '__main__':
main()
PR
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まですべて解けたので良しとしたいところではあります。
category: 未分類
DATE : 2010/08/24 (Tue)
DATE : 2010/08/24 (Tue)
Google Developer Day 2010のDevQuizで出題された「2-legged OAuth」を解いた際に使用したソースコードです。一部、xxxxと伏せてある部分があります。言語にはPythonを使用しました。
OAuthでのアクセスを実現するために、oauth2モジュールを使用しました。
どのような署名を求めていたのかが失敗時のレスポンスのbodyに書かれていたため、その内容とOAuth 1.0のRFCとをにらめっこした結果、なんとか解けました。
#!/usr/bin/env python
import oauth2 as oauth
import time
import urllib2
uri = 'http://gdd-2010-quiz-japan.appspot.com/oauth/xxxxxxxxxxxxxxxxxxxxx'
params = {
'oauth_timestamp': int(time.time()),
'oauth_nonce': oauth.generate_nonce(),
'hello': 'world'
}
consumer = oauth.Consumer(
key = 'xxxxxxxxxxxxxxxxxxxxxxxx', secret = 'xxxxxxxxxxxxxxxxxxxxxxxx')
params['oauth_consumer_key'] = consumer.key
request = oauth.Request(method = 'POST', url = uri, parameters = params)
signature_method = oauth.SignatureMethod_HMAC_SHA1()
request.sign_request(signature_method, consumer, None)
header = request.to_header('devquiz')
http_request = urllib2.Request(uri, 'hello=world', header)
try:
response = urllib2.urlopen(http_request)
except urllib2.HTTPError, e:
print e.read()
print response.info()
category: Python
DATE : 2010/04/04 (Sun)
DATE : 2010/04/04 (Sun)
subprocessモジュールを使うと、Pythonからコマンドを実行できて便利です。以下のように指定すると、シェルスクリプトも実行できます。
import subprocess
subprocess.call("""
<command1> <argument1 ...>
<command2> <arguemnt2 ...>
""", shell = True)
しかし、シェル組み込みのコマンド（sourceなど）を使用する場合は、executable引数を指定しないと、実行時にエラーとなる可能性があります。executable引数を指定しない場合、subprocessモジュールは、Unix系の環境では/bin/shをシェルとして使用します。
ディストリビューションによって/bin/shにリンクされているシェルが異なります。例えば、Red Hat系ではbashなことが、Debian系ではdashなことが多いようです。
そのため、executable引数にそのシェルのパスを指定しないと、他のディストリビューションにPythonスクリプトを移行した際に急に動かなくなるという現象が起こります(；´Д｀)実際に体験しました
先程のスクリプトをexecutable引数を用いたものに書き直すと、次のようになります（以下の例では、bashに依存するスクリプトの場合です）。実際には、ディストリビューションによってシェルの場所も/bin配下にあったり/usr/bin配下にあったりする場合があるので、executable引数に渡す文字列は定数扱いにしておいた方がメンテナンスしやすいかと思います。
import subprocess
BASH = '/bin/bash'
subprocess.call("""
<command1> <argument1 ...>
<command2> <arguemnt2 ...>
""", shell = True, executable = BASH)
category: Java
DATE : 2010/01/13 (Wed)
DATE : 2010/01/13 (Wed)
ある日、大文字が含まれているかもしれない文字列を全て小文字に統一したいという目的からJava SE 6のAPIドキュメントをなんとなく眺めていました。すると、String.toLowerCase()の解説に次のような記述がありました。
注: このメソッドはロケールに依存するため、ロケールが単独で解釈されるような文字列に使用すると、予期せぬ結果を引き起こすことがあります。例として、プログラミング言語識別子、プロトコルキー、HTML タグがあります。たとえば、トルコ語ロケールの "TITLE".toLowerCase() は "t?tle" を返します。ここで、「?」は点のないラテン小文字の I の文字です。ロケールに依存しない文字列の正しい結果を取得するには、toLowerCase(Locale.ENGLISH) を使用します。
つまりトルコ語ロケールの環境下では、小文字変換で「TITLE」は「title」にならず、大文字変換でも「title」は「TITLE」になりません。トルコ語(Wikipedia)に掲載されているトルコ語でのアルファベッドによると、トルコ語では「i」が「İ」（上に点のあるI）、「I」が「ı」（点のないi）に変換されます。
するとロケールによって変換結果が異なっては困る処理でString.toLowerCase()およびString.toUpperCase()を使用すると、ロケールによっては正しく動作しないという現象が発生します。この問題を解決するには、APIドキュメントにもあるとおり、引数にLocale.ENGLISHを指定して、変換対象のロケールを指定できるString.toLowerCase(Locale)やString.toUpperCase(Locale)を使用します。
それでは大文字・小文字を区別せずに比較するString.equalsIgnoreCase(String)はどうなのでしょうか。結論から言えば、String.equalsIgnoreCase(String)はどのロケールであっても結果が同じとなります。
String.equalsIgnoreCase(String)のAPIドキュメントには以下のような記述があります。
この String とほかの String を比較します。大文字と小文字は区別されません。長さが同じで、2 つの文字列内の対応する文字が大文字と小文字の区別なしで等しい場合、2 つの文字列は大文字と小文字の区別なしで等しいと見なされます。
次のどれかに該当する場合に、c1 と c2 という 2 つの文字は大文字小文字の区別なしで等しいと見なされます。
- 2 つの文字が等しい (== 演算子による比較)
- Character.toUpperCase(char) メソッドをそれぞれの文字に適用すると同じ結果になる
- Character.toLowerCase(char) メソッドをそれぞれの文字に適用すると同じ結果になる
String.equalsIgnoreCase(String)で用いられているのは、String.toLowerCase(), String.toUpperCase()ではなくCharacter.toLowerCase(char), Character.toUpperCase(char)です。
Character.toLowerCase(char)のAPIドキュメントには以下のように書かれています。
UnicodeData ファイル内のケースマッピング情報を使用して、文字引数を小文字に変換します。
（中略）
通常、String.toLowerCase() は、文字を小文字にマップするときに使用する必要があります。String ケースマッピングメソッドは、Character ケースマッピングメソッドと比べて複数の利点があります。String ケースマッピングメソッドは、ロケール依存のマッピング、コンテキスト依存のマッピング、および 1:M 文字マッピングを実行できるのに対し、Character ケースマッピングメソッドはそのようなマッピングを実行できません。
ここで重要なのは「通常、String.toLowerCase() は」で始まる部分です。ここにString.toLowerCase()とCharacter.toLowerCase(char)の違いが明記されています。
つまりCharacter.toLowerCase(char), Character.toUpperCase(char)はロケールに依存せず、どのようなロケールでも同じ結果となります。そのためString.equalsIgnoreCase(String)も同様にロケールに依存せず、どのようなロケールでも同じ結果となると言えます。
初めはメソッド名が同じなので、String.toLowerCase(), String.toUpperCase()とCharacter.toLowerCase(char), Character.toUpperCase(char)とが同じと勘違いしてしまいました。
（；^ω^）クラス名やメソッド名が似ているからと言って処理が同じだと判断せずに、ドキュメントはきちんと読むべきでした。
忍者ブログ [PR]
