Mona Lisa TSPでモナリザの顔を表示させる -その2-

前回：
http://d.hatena.ne.jp/xyz600/20121028/1351428339

前回swapする方法だと上手く行かなかったからKD-Treeを作って近傍に線を引いていこうと思ってたんだけど、どうやらinverseの法を高速化して工夫すると十分良いらしい(研究室の先輩談)。

inverseさせる方法というのは、単にランダムに2点を選択して2点間の経路を反転させるというもので、２点をswapさせる方法より辺の変化数が少ない(inverse = 2, swap = 4)分優秀とのこと。
頂点の数をnとするとナイーブに計算すると経路反転にO(n)かかるから、データ構造を作ることになるけど、経路反転を高速に出来るデータ構造は知らない...
しばらく探してたら、こんなのが見つかった。

http://www.slideshare.net/iwiwi/2-12188757/1

Treapって聞いたことなかったけど、スライドがわかりやすいから実装はそんなにムズくなかった。多分反転の操作にO(log n)かかるように見えるんだけど、どうなんだろう。
コードはこんな感じになった。ずいぶん投げやりだけど。

import random, math

class Point:
    def __init__(self, y, x):
        self.x = x
        self.y = y
        #ランダムに割り振られる優先度
        self.priority = random.random()

    def toString(self):
        return "(%d, %d)" % (self.y, self.x)
        
class Node:
    def __init__(self, lst):
        self.reverse = False
        self.size = len(lst)
        if len(lst) == 0:
            pass
        else:
            self.size = len(lst)
            max_value = max(lst, key = (lambda x: x.priority))
            index = lst.index(max_value)
            self.location = lst[index]
            self.left = Node(lst[:index])
            self.right = Node(lst[index+1:])

    def get(self, index):
        self.push()
        if index < self.left.size:
            return self.left.get(index)
        elif self.left.size < index:
            return self.right.get(index - self.left.size - 1)
        else:
            return self.location
            
    def is_null(self):
        return self.size == 0
            
    def is_leaf(self):
        return self.right.is_null() and self.left.is_null()
            
    def update(self):
        if not self.is_null():
            self.size = self.left.size + self.right.size + 1
        return self

    def push(self):
        if self.reverse and not self.is_null():
            self.left, self.right = self.right, self.left
            self.reverse = False
            self.right.reverse ^= True
            self.left.reverse ^= True

    def toString(self):
        self.push()
        if self.is_null():
            return "(NULL)"
        else:
            return "[%s{%s}%s]" % (self.left.toString(), self.location.toString(), self.right.toString())

    def toList(self):
        self.push()
        if self.is_null():
            return []
        elif self.is_leaf():
            return [self.location]
        else:
            return self.left.update().toList() + [self.location] + self.right.update().toList()
            
def merge(node_l, node_r):
    node_l.push()
    node_r.push()
    if node_l.is_null():
        return node_r
    elif node_r.is_null():
        return node_l
    elif node_l.location.priority > node_r.location.priority:
        node_l.right = merge(node_l.right, node_r).update()
        return node_l.update()
    else:
        node_r.left = merge(node_l, node_r.left).update()
        return node_r.update()
    
# [0, n) -> [0, k) + [k, n)
def split(node, k):
    node.push()
    if node.is_null():
        return (node, node)
    if k == node.size:
        return (node, Node([]))
    elif k == 0:
        return (Node([]), node)
    elif node.left.size < k:
        (node_rl, node_rr) = split(node.right, k - node.left.size - 1)
        node.right = node_rl.update()
        return (node.update(), node_rr.update())
    else:
        (node_ll, node_lr) = split(node.left, k)
        node.left = node_lr.update()
        return (node_ll.update(), node.update())

def reverse(node, frm, to):
    node.push()
    if node.is_null():
        return node
    else:
        left, middle_tmp = split(node, frm)
        middle, right = split(middle_tmp, to - frm + 1)
        middle.reverse ^= True
        return merge(left, merge(middle, right))

updateで木のサイズを再計算していて(ただし再帰的に計算するわけではなく、左右の部分木のサイズが正しく計算されているという仮定が必要)、pushでinverseの操作を実際に行っている。
updateとpushのタイミングがよく分からなかったんだけど、とりあえずオブジェクトに破壊的な操作をする時は終了したタイミングでupdateをかけて、オブジェクトのデータにアクセスする時にpushしてるんだけど、もう少し上手くできないものか。
これをpypyで3時間程度動かすと、1700万〜1800万程度の経路長が出てくる。これで実際の既知最良解の3、４倍程度か。前回より10倍近く短くなったからまぁいいや。
今回は割とモナリザっぽくなった！

次はどうしようかな。最近傍ってどの程度精度出るのか興味あるし、やっぱりKD-treeかなぁ。工夫すればinverseでももっといけるっぽいけど、悩み中。