新しい七分割 - 西尾泰和のはてなダイアリー

帰りの電車でひらめいてしまった。点対称！

しかし12個の頂点を美しく配置する必要があり、人力でできる気がしないのでコードを書く。辺の長さが最少になるようにしたいので二次関数の最適化問題だから共役勾配法を使うべきだな。うん。

まずこれが辺の長さを最小化すべきグラフ、固定点が座標、移動点が添字でかいてある。

edges = [
    (0, (1, 0)),
    (0, (1, 0)),
    (0, 1),
    (1, (2, 0)),
    (1, 3),
    (2, (3, 0)),
    (2, (4, 1)),
    (2, 4),
    (3, 4),
    (3, 5),
    (4, (2, 2)),
    (5, (0, 2)),
    (5, (0, 3)),
]

距離を求める関数を作る

from math import sqrt
def calc_dist(xs):
    ret = 0.0
    for (v1, v2) in edges:
        x1 = xs[v1]
        if isinstance(v2, tuple): # v2 fixed 
            x2 = v2
        else:
            x2 = xs[v2]
        ret += sqrt((x1[0] - x2[0]) ** 2 + (x1[1] - x2[1]) ** 2)
    return ret

突然変異をさせる関数とランダムな初期値を作る

from random import gauss, random

def mutate(xs):
    ret = []
    for i in range(6):
        ret.append(
            (xs[i][0] + gauss(0, 1), xs[i][1] + gauss(0, 1)))

    return ret


cur = [(random() * 4, random() * 4) for i in range(12)]
cur = [(calc_dist(cur), cur)]

あとはコンピュータがひたすら頑張るだけ。

for i in range(1000):
    children = [mutate(cur[0][1]) for i in range(1000)]
    cur.extend((calc_dist(xs), xs) for xs in children)
    cur.sort()
    cur = [cur[0]]
    print cur

実行すると
[(10.066974460981866, [(1.0093958273824633, -0.10241337817317504), (1.67596128193252, -0.088355447743802051), (3.2439881038316933, 1.0639891791625744), (2.1424292236222975, 0.594492140279546), (2.3347757185495399, 1.4530289576181918), (0.010060747437447629, 2.2030633802780248)])]
あたりで収束した。突然変異の大きさを抑えてここから再スタートしてみよう。

こう書き換えるだけ。

def mutate(xs):
    sigma = 0.1
    ret = []
    for i in range(6):
        ret.append(
            (xs[i][0] + gauss(0, sigma), xs[i][1] + gauss(0, sigma)))

    return ret


cur = [(10.066974460981866, [(1.0093958273824633, -0.10241337817317504), (1.67596128193252, -0.088355447743802051), (3.2439881038316933, 1.0639891791625744), (2.1424292236222975, 0.594492140279546), (2.3347757185495399, 1.4530289576181918), (0.010060747437447629, 2.2030633802780248)])]