grbl1.1+Arduino CNCシールドV3.5+bCNCを使用中。
BluetoothモジュールおよびbCNCのPendant機能でスマホからもワイヤレス操作可能。
その他、電子工作・プログラミング、機械学習などもやっています。
MacとUbuntuを使用。

CNCマシン全般について:
国内レーザー加工機と中国製レーザー加工機の比較
中国製レーザーダイオードについて
CNCミリングマシンとCNCルーターマシンいろいろ
その他:
利用例や付加機能など:
CNCルーター関係:



*CNCマシンの制作記録は2016/04/10〜の投稿に書いてあります。


2019年2月8日金曜日

最小全域木(MST: minimum spanning tree)、Christofides algorithmによるTSP初期経路生成

TSP(巡回セールスマン問題)について調べていくと、派生的に色々なアルゴリズムに出くわします。それと、ここしばらくはPythonを使っていますが、Python自体の書き方においてもいまだに発見があります(便利というか奥が深いというか)。

TSPにおいては、初期経路生成のアルゴリズムとその後の経路最適化アルゴリズムの二段階に分かれます。まずは、初期経路生成について色々試しています。
前回は凸包(convex hull)による初期経路を試してみましたが、単純な貪欲法よりはまともな初期経路ができあがりました。結論的には、凸包の挿入法による初期経路形成のほうが今回のMST(minimum spanning tree)による方法よりもいいような気がしますが、実際どうなのかまだ検証していないので分かりません(追記:その後簡単な比較検証してみた結果、MSTを用いたほうが優れていました)。いずれにせよMSTは様々な分野において応用が効きそうなので勉強してみようかと。

今回は、最小全域木(MST: minimum spanning tree)を使って初期経路を生成しようと思います。MSTはそれ自体では枝分かれしたグラフであり、そのままではTSPの巡回路としては使えないのですが、MSTを生成することで様々なことに応用できるようです。枝分かれしたそれぞれの辺は最小値になるように選択しているため、TSPにおける経路の上限値と下限値などがわかるようです。MSTの生成アルゴリズムとしては、主にクラスカル法とプリム法の二つがあるようです。


クラスカル法:
全ての辺の組み合わせを計算して最短の辺から順番にリストに加えていきます。

統合:
リストに加えて行く際に、すでに選択した辺に繋がる場合は統合します。辺は二つのノード(点)なので、新たに加える辺のどちらか一方のノードが、すでに選択した辺のノードと一致する場合は同じグループとみなします。今回の場合はリスト内にグループごとの子リストをつくって仕分けしていきます。

グループ追加:
加えようとする辺の二つのノードが、既に選択されている辺のどれにも一致しない場合は統合されないため、新たな子グループ(リスト)として親リスト内に追加します。

却下:
グループに新たな辺を加える際には閉路ができないようにします。加えようとする辺のノードが二つともすでに選択した辺と一致してしまう場合は閉路とみなすことができるので選択を却下します。

このように統合、グループ追加、却下を繰り返していくと、全てのノードが繋がって一つのグループになります。

set()関数:
ある数値(ノードの番号)が、あるリスト内の数値に一致するかどうかは、集合関数であるset()を使うといいようです。

A = [1, 2, 3, 4, 5]
B = [0, 2]
set(A) & set(B):

とすれば、

{2}

という出力があり(2がどちらにも共通という)、リストAに対してリストBの部分一致を確かめることができます。つまりBのどちらか一方がAに所属するということがわかるというわけです。

set(A) >= set(B)

なら、Bの全てがAに含まれるかどうかがわかります。
ということで、この一連の流れをコーディングしてみました。実際は計算量を軽減するための工夫も必要ですが、今回は結果だけを求めています。

def kruskal(path):
    dist = []
    idx = []
    for i in range(len(path)):
        for j in range(i+1, len(path)):
            dist.append(np.abs(XY[i] - XY[j]))
            idx.append([i,j])
    arg = np.argsort(dist)
    edge_list = [idx[a] for a in arg]
    
    plist = []
    group = []
    for edge in edge_list:
        if set(edge) & set(sum(group, [])):     # either in all groups
            merge_list = []
            for i in range(len(group)):
                if set(edge) <= set(group[i]):  # both in one group
                    continue
                elif set(edge) & set(group[i]): # either in one group
                    merge_list.append(i)
            if len(merge_list) > 0:
                group[merge_list[0]] = list(set(sum([group[m] for m in merge_list] + [edge], [])))
                [group.pop(i) for i in merge_list[1:]]
                plist.append(edge)                
        else:
            group.append(edge)
            plist.append(edge)
    return plist
最初に全ての辺の組み合わせを計算しなければいけないので、ノード数が増えるとかなりきつくなりそうです。この部分に工夫が必要そうです。今回はベタに計算しています。
ノード50個の場合。
このように最短の辺で構成された枝分かれのグラフができあがります。
すべてのノードへ訪問可能にするために必要な経路の合計が最短ということです。
この段階では、
[[4,15],[23,45]...]
というような二つのノードを組にした辺のリストとして順序は無関係に並んでいます。


プリム法:
もう一つのMST生成アルゴリズムであるプリム法です。
プリム法では、まず任意のノードを選び、それに最も近いノードを次に選びます。選んだノードはリストに加えていきますが、一組の数値(辺:[a, b])として加えていきます。次は、選択した二点のノードのそれぞれに近いノードを残りのノードから選びだし、より小さいほうだけをリストに加えます。このようにリストに加えたノードに最も近いノードを残りのノードから一つずつ選んで辺として加えていきます。
クラスカル法に比べアルゴリズムは単純ですが、毎回選択したノード数分の距離を総当たりで計算させているため計算量がかさんでしまいます。あらかじめ距離の総当たりテーブルを用意しておけばいいのかもしれません。
def nearest_node_dist(path, index):
    best_dist = np.inf
    best_node = None
    for p in path:
        if p != index:
            d = abs(XY[p] - XY[index])
            if d < best_dist:
                best_dist = d
                best_node = p
    return best_node, best_dist

def prim(path):
    copy = list(path)
    if path[0] == path[-1]:
        copy = list(path[:-1])
    node, _ = nearest_node_dist(copy, path[0])
    plist = [[path[0], node]]
    copy.remove(path[0])
    copy.remove(node)
    
    while len(copy):
        best_dist = np.inf
        best_edge = None
        for p in set(np.ravel(plist)):
            node, dist = nearest_node_dist(copy, p)
            if dist < best_dist:
                best_dist = dist
                best_edge = [p, node]
        plist.append(best_edge)
        copy.remove(best_edge[1])
    return plist
今回は毎回各ノードに対して最も近いノードとの距離計算をさせているためnearest_node_dist()という関数を別途用意してあります。


グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム
浅野 孝夫
近代科学社
売り上げランキング: 444,789


TSP初期経路生成:
MSTを元にTSPのための初期経路を生成します。主には2種類あり、今回はDouble TreeアルゴリズムとChristofidesアルゴリズムをコーディングしてみました。大まかな内容を理解してから勝手にアルゴリズムを組み立てているので、厳密なアルゴリズムにはなっていません。

オイラー閉路:すべての辺を通り開始点に戻ることができる。
ハミルトン閉路:すべてのノードを通り開始点に戻ることができる。

Double Treeアルゴリズム:
このアルゴリズムではMSTの上にもう一つ同じ経路を重ね合わせて二重経路にします。MSTを経路というよりは壁と見立てて、その周囲を壁沿いに移動していくイメージです。そうすることで、どの経路も往復路になり、行き止まりになる枝の先端部分であっても戻ることができるため全てのノードに到達可能となります。TSPでは同じノードを二回通ることはできませんが、まずはグラフ理論におけるオイラー路(すべての辺を通るグラフ、同じノードを複数回訪れてもよい)として考え、さらに循環する場合はオイラー閉路とみなしてすべてのノードへの経路を考えます。そのため単純計算すれば、最大でMSTの二倍の距離になります。最終的にはTSPの経路に変換するため同じノードをスキップします。

結果的にはあまりきれいな経路にはなりませんが、このあとの最適化によってまともな経路になることに期待します。

Christofidesアルゴリズム:
このアルゴリズムはやや複雑で、Double Treeでは2倍長の経路であったのに対し、グラフ理論における最適マッチングを適用することで加える経路を半分に減らすことができ、合計1.5倍の経路で巡回可能になるようです。

次数が奇数のノードを選択する:
まず、MST上で接続されている辺の数が奇数のノードをすべてピックアップします。例えば三つに分岐しているノードなどです。枝の先端も接続されている辺の数は一本だけなので奇数ノードとみなします(ノードにおける辺の接続数のことを「次数」という)。
ノードにおける奇数と偶数の違いは、そこにたどり着く経路とそこから出ていく経路の数として見るといいようです。同じ経路を二回通らないという設定であれば、三分岐点の場合は、その地点から出発して戻ってきたあと再度出発すれば二度と戻ってこれないということになり、往復経路のどちらか一方が足りないということになります。そのためこれら奇数のノードに対してもう一本経路を追加してあげれば往復可能、通過可能、巡回可能なノードになります。

最適マッチング(minimum weight perfect matching):
奇数ノードだけを抜き出し、それらだけで最適マッチングによる辺(サブ経路:M)の追加を行います。サブ経路Mが追加されることで、行き止まりとなる枝の先端ノードや分岐点が巡回可能になります。
左図(上図)はノード数20個のMST。この中から次数が奇数のノードを選択します。この場合、三又の分岐点(3箇所)以外に枝の先端(5箇所)も含め8箇所あります。そして最適マッチングによりそれらの8点を4本(8ノードの半数)の辺としてつなぎます(右図/下図)。最適マッチングによる辺は互いに接続せず離れ離れに配置されます。連結した辺というよりは破線のように一つ飛ばしで辺を構成していく感じです。この4辺をMとして、MSTの辺と重ね合わせます。これで全てのノードにおいて偶数の経路と接続されたこととなります。
このときminimum-weightになるように、合計の辺の長さが短くなるような組み合わせを選びます。8点あるので組み合わせの数は7*5*3*1=105パターンになります。もし10点ある場合は9*7*5*3*1=945というように数が増えるほど計算量が膨大になっていきます。今回の場合そのまま計算させるとかなり時間がかかってしまったので(ベタに計算させたコードはこちら)、グラフ理論ライブラリであるNetworkXmax_weight_matching()関数を利用しました(短時間で計算してくれます)。ただし、NetworkXにはminimum_weight_matchingの関数はないので、パラメータをマイナス反転して結果だけを利用しています。
尚、最適マッチングの計算方法としては、Blossom algorithmやHungarian algorithmを参考にするといいようです。
def min_weight_perfect_matching(edges):
    # find odd-degree nodes from MST(edges)
    odd = []
    for i in range(num):
        cnt = 0
        for e in np.ravel(edges):
            if i == e:
                cnt += 1
        if cnt % 2 == 1:
            odd.append(i)
    print('Odd-Degree Edges:', odd)
    
    # get combinations of edges from the odd-degree nodes
    combs = list(combinations(odd, 2))
    
    # calculate weights on the edges
    weight = [abs(XY[c[0]]-XY[c[1]]) for c in combs]
    
    # negating the weights to get minimum-weight from the max_weight_matching function
    edge_weight = [(combs[i][0], combs[i][1], {'weight': -weight[i]}) for i in range(len(combs))]
    
    # find minimum-weight perfect matching(negative max_weight_matching) by NetworkX library 
    G = nx.Graph(edge_weight)
    M = nx.max_weight_matching(G, True, 'weight')
    M = [list(m) for m in M]
    G.clear()
    return M

最適マッチングによって辺Mが追加された結果、枝の先端は行き止まりになることなく、また三又の分岐点も巡回可能なノードになります。この状態から新たにTSP用に経路を構築していきます。


初期経路生成:
MSTを元に、Double TreeやChristofidesアルゴリズムを経てTSPに合わせた経路に変換します。前段階まではオイラー閉路(全ての辺を通る、同じノードを数回通ってもよい)であったので、同じノードを一回しか通ることができない経路にするため、複数回通るノードをスキップします。

MSTや最適マッチングによって生成された辺の集合は、
[[12,20],[4,8],[6,22]...]
などと順序は無関係に並んでいるので、これらを
[[12,20],[20,23],[23,5]...]
というように前後の番号がつながるように並び替えます。
そして最終的には、
[0,12,20,23...18,15,0]
というような重複しないノードのリストに変換してTSP経路をつくります。

# T, M=False: Double Tree Algorithm
# T, M=M    : Cristofides Algorithm 
def tsp_tour(T, M=False):
    if M:
        TM = (T + M).copy()
    else:
        TM = (T + T).copy()
    
    tour = [TM[0]]
    TM.remove(TM[0])

    while len(TM):
        for tm in TM:
            if tour[-1][1] == tm[0]:   # tour(n,0) == TM(0,m) 
                tour.append(tm)
                TM.remove(tm)
            elif tour[-1][1] == tm[1]: # tour(n,0) == TM(m,0)
                tour.append(tm[::-1])
                TM.remove(tm)
        if tour[0][0] == tour[-1][1]:  # when meets deadend
            tour = [tour[-1]] + tour[:-1]

    newtour = []
    for t in tour:
        if not t[0] in newtour:
            newtour.append(t[0])    
    zero = newtour.index(0)
    newtour = newtour[zero:] + newtour[:zero] + [0]
    return newtour
MSTで生成した経路をT、最適マッチングによって追加された経路をMとしています。なお引数にMを渡さなければ、Double Treeアルゴリズムで経路生成します。その場合はTを2倍にした経路が初期状態となります。
基本的には、各辺は[a,b]というような一組のノード番号によってリストに入っており、次につながる辺は[b,c]もしくは[c,b]となるため前後を逆にした二通りを検索し、つながる辺が見つかれば追加していきます。
しかし、そのまま各辺を追加してくと、開始点によっては途中で道が途絶えてしまうことがあります。これは、開始点と現在地とで局所的ループが発生して、それ以外の経路へ移動できない状態になっているということです。局所的ループによって行き止まりになったら、現在加えた辺を経路リストの最後から先頭に移動して現在地を一つ手前に戻します。それでも接続可能な辺を見つけられなければ、接続可能な辺が見つかるまでこの手順を繰り返します。
こうすることで、どの地点から開始しても現在地と開始点をずらしながら通り過ぎてしまった分岐点に遡ることが可能となり、見逃していた辺(経路)を追加していくことができます。
そして順路ができあがったらノード0を起点に並べ替えて、最後に再度ノード0を付け足して巡回路とします。

 
ノード数20の場合。左(上)がDouble Tree。右(下)がChristofides。
最終的に重複するノードをスキップさせるためか経路が部分的に交差してしまうことがあります。二つを何回か比較すると、Christofidesのほうがより安定した経路を形成します。
そして最適化させると以下のようになります。交差している部分は解消されほぼ厳密解に近い経路になります。


比較結果(追記):
その後、前回の凸包・挿入法と今回のMSTによる初期経路生成について、TSPライブラリのPyconcordeの結果を元に100回分のスコアを比較しました。

Pyconcorde  :100.0000 %
凸包・挿入法:103.3175 %
Double Tree :105.5888 %
Christofides:102.7978 %

それぞれのアルゴリズムで経路生成したあとに最適化アルゴリズムを通して得られたスコアです。Pyconcordeのスコアを100%とした場合の経路長の率で、%が低いほど短距離でいい結果ということです。今回は簡単な最適化しか行っていないためもう少し改善することはできましたが、Pyconcordeより短い距離を出すことはほぼ無理。何回かに一回はPyconcordeと同じスコアになるときはあります。
凸包・挿入法は一見よさそうだったのですが、結果的にはChristofidesのほうがわずかながら優れています。凸包とはいえ仕組み的には貪欲法なので、やはりMSTを構築したほうが結果がよくなるという感じでしょうか。MSTは最短の辺で全体をつなぎとめるので、全体的な構成や骨格が最小で済み、あとは局所的な最適化さえすればいいという感じで理にかなっているのかもしれません。

関連:



驚きの数学 巡回セールスマン問題
ウィリアム・J・クック
青土社
売り上げランキング: 255,242

2019年1月25日金曜日

convex hull:凸包/ギフト包装法/Graham scanアルゴリズム

引き続きTSP(巡回セールスマン問題)についてというか、下準備の派生アルゴリズムについてです。
前回、初期経路生成に「欲張り法(貪欲法)」を用いてスタート地点から最も近い都市を次々とつないでいきましたが、その他の方法として「挿入法」というものもあるらしい。
「挿入法」では、最初に簡単な初期経路つくっておき、コストが最小になるような地点を徐々に加えていくようです。しかし、初期経路を何にするかという問題があり、通常は「凸包」で都市全体を外側から包み込む経路を初期経路とするといいようです(参照)。

今回はTSPの下準備となる、この凸包アルゴリズムについて試してみました。
凸包には「ギフト包装法」や「グラハムスキャン」などあるようです。この手のアルゴリズムは計算コストの工夫も同時に考慮しなければいけないようですが、今回はとりあえず解を求めることを目標に自分なりにコーディングしてみました。

追記:
グラハムスキャン、ならびに挿入法(経路生成)も追加しました。

これはランダムに配置した20個(0〜19)の点の場合。
全体を包み込むような経路(黄色)を生成します。
TSPに利用する場合は、ここからコストが最小になるような点を加えていき徐々に複雑な経路にしていきます。
赤点「0」はTSPにおけるスタート地点であり、今回はあまり意味はありません。


ギフト包装法アルゴリズム:
コード:
def giftwrap():
    lowest_y = np.where(Y==min(Y))[0][0]
    plist = [lowest_y]
    prev_theta = np.inf
    
    for _ in range(NUM): 
        best_theta = -np.inf
        best_idx = None
        for i in range(NUM):
            if i not in  plist:
                theta = np.arctan2(Y[i]-Y[plist[-1]], X[i]-X[plist[-1]])
                if theta >= best_theta and theta <= prev_theta:
                    best_idx = i
                    best_theta = theta
                    
        if best_idx is not None:
            theta_to_start = np.arctan2(Y[plist[0]]-Y[best_idx], X[plist[0]]-X[best_idx])
            if best_theta >= theta_to_start:
                plist.append(best_idx)
                prev_theta = best_theta
            else:
                break
        else:
            break

    plist.append(plist[0])
    
    return plist
・まずは点群の中でY座標値が最小となる点を選びます(複数ある場合はXも最小値)。
 上記の場合であれば「14」。これを開始点にしリストに加えておきます。
・「14」を起点に、その他のすべての点に向けての角度を比較します。
・角度については(時計で例えるなら)最小値→最大値は半時計回りになっています。
 9時:-180度
 6時:-90度
 3時:0度
 12時:90度
 9時:180度
・「14」を起点に角度が最大となる点を選びます。この場合「8」を選択。
 次回この(14, 8)の辺の角度を利用するので記録しておきます。
・「8」をリストに加えておき、次の起点を「8」にします。
・先程と同様に起点「8」からその他の点に向けての角度を比較します。
 この際、リストに加えた点以外という条件設定にしておきます。
・基本的にはこれを繰り返していくだけです。

ただし、もう少し条件を加えないと循環経路として閉じてくれません。
リストに加えていく候補点の条件としては:
(1)リスト以外の点
(2)起点からの角度が最大の点
(3)前回の辺の角度以下の角度となる点
(4)候補点から開始点(「14」)に向けた角度以上の角度となる点
という感じでしょうか。
最後に開始点をリストに加えて終了します。
各辺の角度は囲い込んでいくにつれ減少していく特徴があるので、その部分を条件式として利用しています。


今回は自前でコーディングしたので、正当な「ギフト包装法」のコードとは違うかもしれません。しかしながらこのようなアルゴリズムはTSPの初期経路生成に利用するだけでなくいろんな分野でも活用できそうです。



グラハムスキャン(Graham Scan):(追記)
もうひとつの凸包アルゴリズムであるグラハムスキャンも試してみました。計算量はグラハムスキャンの方が少ないらしいのですが、実際どうなのか?
アルゴリズムは、各点をスキャンして行く際に行ったり来たりする挙動なので最初わかりにくかったのですが、処理の順番を理解すればそれほど難しいものでもありませんでした。

コード:
def graham_scan():
    lowest_y = np.where(Y==min(Y))[0][0]
    plist = [lowest_y]
    
    theta_list = [] 
    for i in range(NUM):
        theta = np.arctan2(Y[i]-Y[plist[-1]], X[i]-X[plist[-1]])
        theta_list.append(theta)
        
    sorted_index = np.argsort(theta_list)
    
    for i in range(1,NUM):
        plist.append(sorted_index[i])
        if i > 1:
            v1 = [X[plist[-2]] - X[plist[-3]], Y[plist[-2]] - Y[plist[-3]]]
            v2 = [X[plist[-1]] - X[plist[-2]], Y[plist[-1]] - Y[plist[-2]]]
            while np.cross(v1, v2) <= 0:
                plist.pop(-2)
                v1 = [X[plist[-2]] - X[plist[-3]], Y[plist[-2]] - Y[plist[-3]]]
                v2 = [X[plist[-1]] - X[plist[-2]], Y[plist[-1]] - Y[plist[-2]]]
        
    plist.append(plist[0])
    return plist
・Y座標が最小の点を選択し起点とします。
・最終的な経路リストを用意して、起点を入れておきます。
・起点から全ての点に対する角度のリストをつくります。
・角度のリストをソートしなおして角度順のリストをつくります。
・角度順リストを元に角度の小さい方から各点を経路リストに加えていきます。
・その際に現在の辺と一つ前の辺の外積を求め、以下をチェックします。
  外積=0:一つ手前の辺と現在の辺が平行(延長線上にある)
  外積<0:一つ手前の辺からみて現在の辺が右曲がり
  外積>0:一つ手前の辺からみて現在の辺が左曲がり
・外積<0の際は一つ手前の点を経路リストから削除します(外積>=0になるまで繰り返す)。
・次のノードへ移動し、上記を繰り返す。
・最後に経路を閉じるため経路リストの最初の値を加えて終了。

起点を中心とすると、起点の左側から反時計周りに角度が小→大となります。
循環経路なので追加される各辺は常に左曲がりとなります。つまり徐々に角度の値が大きくなっていくということです。
左曲/右曲の判定は外積(現在の辺と一つ手前の辺による)を使います。np.cross(v1, v2)を利用しましたが、x1*y2-x2*y1でも求められます。
もし途中で現在の辺が右曲がりなら、その手前の点を経路リストから削除します。そうすると、二つ手前の辺が繰り上がって一つ手前の辺になります。再度、現在の辺と一つ手前の辺(繰り上がった二つ手前の辺)の外積を調べて左曲/右曲の判定をします。現在の辺が右曲であるかぎり、この外積の左曲/右曲判定と点の削除をwhile文で繰り返します。現在の辺が左曲がりになれば次の点へ移動していきます。

以下の動画が分かりやすかったです。


ということで、ギフト包装法とグラハムスキャンの二つのコード(以下)。
100000点で比較してみると、
ギフト包装法:6.80秒
グラハムスキャン:4.76秒
という結果になりました。


挿入法によるTSP初期経路生成(追記):
TSPに適用するには、凸包上のノードAとBからなる任意の辺、加えようとするノードをCとし、
L=AC+BC-AB
という長さを各辺において比較し最小値のノードを加えていきます。一点加えるごとに形が変化していくので、辺と点のすべての組み合わせの二重forループで一点追加していきます。その分計算量は多くなりますが、貪欲法でありながらも無駄な経路は少なくなります。
要は外側から徐々に内部の方に侵食していくように経路を形成していきます。
def hull_insert(path, hull):
    Path = list(path[:-1].copy())
    Hull = list(hull[:-1].copy())
    for h in Hull:
        Path.remove(h)
        
    def tri_length(p0, p1, pt): 
        d0t = abs(XY[p0]-XY[pt])
        d1t = abs(XY[p1]-XY[pt])
        d01 = abs(XY[p0]-XY[p1])
        L = d0t + d1t - d01
        return L
       
    while len(Path):
        best_len = np.inf
        best_node = None
        for i in range(len(Hull)):
            for p in Path:
                if i == len(Hull)-1:
                    L = tri_length(Hull[i], Hull[0], p)
                else:
                    L = tri_length(Hull[i], Hull[i+1], p)
                if L < best_len:
                    best_len = L
                    best_node = [Hull[i], p]
                        
        Hull.insert(Hull.index(best_node[0])+1, best_node[1])
        Path.remove(best_node[1])

    zero = Hull.index(0)
    tour = Hull[zero:] + Hull[:zero] + [0]
    return tour
最終的には2-OPTなどによる最適化も必要ですが、単純な貪欲法よりは整った経路ができあがります。しかしながら、その後の最適化によって改善しやすいかどうかは分かりません。
ノード20個の場合。

ノード100個の場合。
交差している箇所も少しありますが、最終型に近い経路になります。

追記:
以下は経路生成(ノード:50)のアニメーション。下のGistの最後にコードを追加しました。
外側から内側へ向かって一つずつ最短距離の点を加えていくので一見無駄がなさそうですが、まだ選択されていない点によって形成される最短経路を無視して繋いでいくため、必ずしも最終的な最短経路になるとは限りません。



人気の投稿