TSP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.cluster import KMeans\n",
    "import os\n",
    "import imageio\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class TSP:\n",
    "\n",
    "    def __init__(self, city_pos : list, city_dist : list):\n",
    "        \"\"\"\n",
    "        tsp_n = number for tsp algorithm(DP), O(2^n * n^2)\n",
    "        cluster_division_n = divide each cluster that has cities > this param\n",
    "        path_tsp_n = number for path_tsp algorithms(Bruteforce), O(n!)\n",
    "        kmeans_k = sklearn KMeans's cluster_n param\n",
    "        kmeans_r = sklearn KMeans's random_state param\n",
    "        \"\"\"\n",
    "        # private\n",
    "        self.__city_pos = np.array(city_pos)\n",
    "        self.__city_dist = np.array(city_dist)\n",
    "\n",
    "        # public\n",
    "        # stage 1: kmeans clustering\n",
    "        self.kmeans_cluster_pos = None\n",
    "        self.kmeans_cluster_cities = None\n",
    "        self.kmeans_cluster_labels = None\n",
    "\n",
    "        # stage 2: tsp path of kmeans clusters\n",
    "        self.tsp_path = None\n",
    "        \n",
    "        # stage 3: new cluster_pos, cluster_cities sets, dividing each clusters that has too many cities\n",
    "        # last element = best\n",
    "        self.dividing_cluster_infos = []\n",
    "\n",
    "        # stage 4: cluster path -> city path using path-tsp algorithm\n",
    "        # last element = best\n",
    "        self.path_tsp_process = [] # for plot\n",
    "        self.path_tsp_path = []\n",
    "        self.path_tsp_dist = 0\n",
    "        \n",
    "        # last stage: untangling city path using path-tsp algorithm\n",
    "        self.final_process = [] # for plot\n",
    "        self.final_path = None\n",
    "        self.final_dist = 0\n",
    "\n",
    "\n",
    "    def __get_pos_dist(self, a, b):\n",
    "        return ((b[0] - a[0])**2 + (b[1] - a[1])**2)**0.5\n",
    "    \n",
    "    def __get_dist_table(self, pos):\n",
    "        return np.array([[self.__get_pos_dist(pos[i], pos[j]) for j in range(pos.shape[0])] for i in range(pos.shape[0])])\n",
    "\n",
    "    def __get_tsp(self, pos):\n",
    "        def is_in(i, A):\n",
    "            if ((A & (1 << (i-2))) != 0):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def diff(A, j):\n",
    "            t = 1 << (j - 2)\n",
    "            return (A & (~t))\n",
    "\n",
    "        def count(A, n):\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                if ((A & (1 << i)) != 0):\n",
    "                    count += 1\n",
    "            return count\n",
    "\n",
    "        def travel(W):\n",
    "            n = len(W) - 1\n",
    "            size = 2 ** (n - 1)\n",
    "            D = [[0] * size for _ in range(n + 1)]\n",
    "            P = [[0] * size for _ in range(n + 1)]\n",
    "            for i in range(2, n + 1):\n",
    "                D[i][0] = W[i][1]\n",
    "            for k in range(1, n - 1):\n",
    "                for A in range(1, size):\n",
    "                    if (count(A, n) == k):\n",
    "                        for i in range(2, n + 1):\n",
    "                            if (not is_in(i, A)):\n",
    "                                D[i][A], P[i][A] = minimum(W, D, i, A)\n",
    "            A = size - 1\n",
    "            D[1][A], P[1][A] = minimum(W, D, 1, A)\n",
    "            return D, P\n",
    "\n",
    "        def minimum (W, D, i, A):\n",
    "            minValue = 99999999\n",
    "            minJ = 1\n",
    "            n = len(W) - 1\n",
    "            for j in range(2, n + 1):\n",
    "                if (is_in(j, A)):\n",
    "                    m = W[i][j] + D[j][diff(A, j)]\n",
    "                    if (minValue > m):\n",
    "                        minValue = m\n",
    "                        minJ = j\n",
    "            return minValue, minJ\n",
    "        \n",
    "        padding_pos = np.zeros((1,2))\n",
    "        padding_pos = np.append(padding_pos, pos, axis=0)\n",
    "        W = self.__get_dist_table(padding_pos)\n",
    "        D, P = travel(W)\n",
    "        \n",
    "        tsp_path = [0]\n",
    "        start, A = 1, len(P[1]) - 1\n",
    "        while A != 0:\n",
    "            start = P[start][A]\n",
    "            tsp_path.append(start - 1)\n",
    "            A = diff(A, start)\n",
    "\n",
    "        return tsp_path\n",
    "\n",
    "    def __get_center(self, *positions):\n",
    "        points = []\n",
    "        for i in range(len(positions[0])):\n",
    "            points.append(sum([pos[i] for pos in positions]) / len(positions))\n",
    "        return points\n",
    "\n",
    "    def __make_func(self, point1, point2):\n",
    "        m = (point2[1] - point1[1]) / (point2[0] - point1[0])\n",
    "        return lambda x : m * (x - point1[0]) + point1[1]\n",
    "\n",
    "    def __get_path_dist(self, path, pos_dist):\n",
    "        ret = 0\n",
    "        for i in range(len(path) - 1):\n",
    "            ret += pos_dist[path[i]][path[i+1]]\n",
    "        ret += pos_dist[path[-1]][path[0]]\n",
    "        return ret\n",
    "        \n",
    "    def __find_end_city(self, path, c_idx, start, city_pos, cluster_pos, cluster_cities):\n",
    "        return max([[c, self.__get_pos_dist(cluster_pos[c_idx], city_pos[c])] for c in cluster_cities[path[c_idx + 1]]], key=lambda x: x[1])[0]\n",
    "    \n",
    "    def __get_line_pos_dist(self, line_pos1, line_pos2, point_pos):\n",
    "        area = abs((line_pos1[0]-point_pos[0]) * (line_pos2[1]-point_pos[1]) - (line_pos1[1]-point_pos[1]) * (line_pos2[0] - point_pos[0]))\n",
    "        AB = ((line_pos1[0]-line_pos2[0])**2 + (line_pos1[1]-line_pos2[1])**2) **0.5\n",
    "        if AB < 0.0000001:\n",
    "            return 99999999\n",
    "        distance = area/AB\n",
    "        return distance\n",
    "\n",
    "    def __get_cross_point(self, p1, p2, p3, p4):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        x4, y4 = p4\n",
    "\n",
    "        if (x1-x2)*(y3- y4) - (y1-y2)*(x3-x4) == 0:\n",
    "            return None\n",
    "\n",
    "        X = ((x1*y2 - y1*x2)*(x3-x4) - (x1-x2)*(x3*y4 - y3*x4))\n",
    "        X /= ((x1-x2)*(y3- y4) - (y1-y2)*(x3-x4))\n",
    "        Y = ((x1*y2 - y1*x2)*(y3-y4) - (y1-y2)*(x3*y4 - y3*x4))\n",
    "        Y /= ((x1-x2)*(y3- y4) - (y1-y2)*(x3-x4))\n",
    "\n",
    "        return [X, Y]\n",
    "\n",
    "    def __find_end_city2(self, path, c_idx, start, pos, c_pos, cluster_cities):\n",
    "        \n",
    "        cities = cluster_cities[path[c_idx+1]]\n",
    "        \n",
    "        dot_a = pos[start]\n",
    "        dot_b = c_pos[path[c_idx]]\n",
    "        \n",
    "\n",
    "        dot_c = c_pos[path[(c_idx+1) % len(path)]]\n",
    "        dot_d = c_pos[path[(c_idx+2) % len(path)]]\n",
    "\n",
    "        close_rank = sorted(cities, key=lambda c: self.__get_line_pos_dist(dot_a, dot_b, pos[c]))\n",
    "        far_rank = sorted(cities, key=lambda c: self.__get_line_pos_dist(dot_c, dot_d, pos[c]), reverse=True)\n",
    "        \n",
    "        score_table = {c: 0 for c in cities}\n",
    "        \n",
    "        for i in range(len(cities)):\n",
    "            score_table[close_rank[i]] += len(cities) - i\n",
    "            score_table[far_rank[i]] += len(cities) - i\n",
    "            \n",
    "        max_score = max(score_table.values())\n",
    "        max_cities = [c for c, v in score_table.items() if v == max_score]\n",
    "  \n",
    "        cross_point = self.__get_cross_point(dot_a, dot_b, dot_c, dot_d)\n",
    "\n",
    "        if cross_point == None:\n",
    "            return max_cities[0]\n",
    "    \n",
    "        max_cities.sort(key=lambda city: self.__get_pos_dist(pos[city], cross_point))\n",
    "   \n",
    "        return max_cities[0]\n",
    "        \n",
    "    def __DFS_path_tsp(self, start, end, cities, pos_dist):\n",
    "        # 우선 스타트시티가 들어있는 군집의 모든 도시들 나열 스타트시티 제외하고\n",
    "        cities = [c for c in cities if c != start]\n",
    "        \n",
    "        global glob_path\n",
    "        global glob_dist\n",
    "            \n",
    "        glob_path = [start] + cities + [end]\n",
    "        glob_dist = self.__get_path_dist(glob_path, pos_dist)\n",
    "        \n",
    "        def dfs(npath, extra, pos_dist, accum_dist):\n",
    "            global glob_path\n",
    "            global glob_dist\n",
    "            \n",
    "            # promising\n",
    "            if accum_dist > glob_dist:\n",
    "                return\n",
    "            if len(npath) == len(cities) + 1:\n",
    "                new_dist = self.__get_path_dist(npath + [end], pos_dist)\n",
    "                if glob_dist > new_dist:\n",
    "                    glob_path = npath + [end]\n",
    "                    glob_dist = new_dist\n",
    "                    # print(glob_dist)\n",
    "            else:\n",
    "                for e in extra:\n",
    "                    npath.append(e)\n",
    "\n",
    "                    new_extra = [e for e in extra if e != npath[-1]]\n",
    "                    dfs(npath, new_extra, pos_dist, accum_dist + pos_dist[npath[-2]][npath[-1]])\n",
    "\n",
    "                    npath.pop()\n",
    "\n",
    "        dfs([start], cities, pos_dist, 0)\n",
    "\n",
    "        return glob_path[:-1]\n",
    "\n",
    "    def set_params(self, tsp_n = 20, cluster_division_n = 8 ,path_tsp_n = 10, kmeans_k = -1, kmeans_rseed = 0):\n",
    "        self.__tsp_n = tsp_n\n",
    "        self.__cluster_division_n = cluster_division_n\n",
    "        self.__path_tsp_n = path_tsp_n\n",
    "        self.__kmeans_k = kmeans_k\n",
    "        self.__kmeans_rseed = kmeans_rseed\n",
    "\n",
    "    def run(self, tsp_n = 20, division_bound = 8, path_tsp_n = 9,kmeans_k = -1, kmeans_rseed = 0):\n",
    "        # just do only tsp algorithm\n",
    "        if self.__city_pos.shape[0] < 20:\n",
    "            return self.__get_tsp(self.__city_pos)\n",
    "\n",
    "\n",
    "        # stage 1: kmeans clustering\n",
    "        print('s1 kmeans clustering', flush=True)\n",
    "        if kmeans_k == -1:\n",
    "            K = min((self.__city_pos.shape[0] // division_bound) + 1, tsp_n)\n",
    "        else:\n",
    "            K = kmeans_k\n",
    "        \n",
    "        model = KMeans(K, random_state=kmeans_rseed)\n",
    "        model.fit(self.__city_pos)\n",
    "        \n",
    "        self.kmeans_cluster_pos = model.cluster_centers_\n",
    "        self.kmeans_cluster_labels = model.labels_\n",
    "        self.kmeans_cluster_cities = [[c for c, label in enumerate(model.labels_) if label == C] for C in range(model.cluster_centers_.shape[0])]\n",
    "        print(' done     ')\n",
    "\n",
    "        # stage 2: do tsp with clusters\n",
    "        print('s2 tsp finding', flush=True)\n",
    "        self.tsp_path = self.__get_tsp(self.kmeans_cluster_pos)\n",
    "        print(' done     ')\n",
    "\n",
    "        # stage 3: dividing clusters that has too many cities (until <= cluster_division_n)\n",
    "        print('s3 cluster dividing', flush=True)\n",
    "        d_cluster_pos = self.kmeans_cluster_pos.copy()\n",
    "        d_cluster_labels = self.kmeans_cluster_labels[:]\n",
    "        d_cluster_cities = self.kmeans_cluster_cities[:]\n",
    "        d_path = self.tsp_path[:]\n",
    "        \n",
    "        most_cluster_cities = max(self.kmeans_cluster_cities, key=lambda x: len(x))\n",
    "\n",
    "        remaining = sum([max(len(cities) - division_bound, 0) for cities in d_cluster_cities])\n",
    "\n",
    "        divisior = len(most_cluster_cities) - division_bound\n",
    "        while len(most_cluster_cities) > division_bound:\n",
    "            print(f' {((remaining - sum([max(len(cities) - division_bound, 0) for cities in d_cluster_cities])) * 100) / remaining:.2f}%\\r', end='')\n",
    "            C_divide = d_cluster_cities.index(most_cluster_cities)\n",
    "            d_path_idx = d_path.index(C_divide)\n",
    "\n",
    "            # 얘네를 가까운 도시 위치로 하는것도\n",
    "            b_center, f_center = d_cluster_pos[d_path[d_path_idx-1]], d_cluster_pos[d_path[(d_path_idx+1)%len(d_path)]]\n",
    "            \n",
    "            b_cities, f_cities = [], []\n",
    "\n",
    "            center = self.__get_center(b_center, f_center)\n",
    "            f = self.__make_func(center, d_cluster_pos[C_divide])\n",
    "\n",
    "            for c in d_cluster_cities[C_divide]:\n",
    "                # m = (dividing_cluster_pos[C_divide][1] - center[1]) / (dividing_cluster_pos[C_divide][0] - center[0])\n",
    "                if f(self.__city_pos[c][0]) >= self.__city_pos[c][1]:\n",
    "                    b_cities.append(c)\n",
    "                else:\n",
    "                    f_cities.append(c)\n",
    "\n",
    "            # print(b_cities, f_cities)\n",
    "            b_cluster_centroid = self.__get_center(*[self.__city_pos[c] for c in b_cities])\n",
    "            f_cluster_centroid = self.__get_center(*[self.__city_pos[c] for c in f_cities])\n",
    "            \n",
    "            # 새로 센트로이드까지 구했으니, 서로 센트로이드 기준으로 먼거 맞교환\n",
    "            \n",
    "            f_to_b = []\n",
    "            for fc in f_cities:\n",
    "                if self.__get_pos_dist(self.__city_pos[fc], f_cluster_centroid) > self.__get_pos_dist(self.__city_pos[fc], b_cluster_centroid):\n",
    "                    f_to_b.append(fc)\n",
    "            \n",
    "            for c in f_to_b:\n",
    "                f_cities.remove(c)\n",
    "                b_cities.append(c)\n",
    "            \n",
    "            b_to_f = []\n",
    "            for bc in b_cities:\n",
    "                if self.__get_pos_dist(self.__city_pos[bc], b_cluster_centroid) > self.__get_pos_dist(self.__city_pos[bc], f_cluster_centroid):\n",
    "                    b_to_f.append(bc)\n",
    "                    \n",
    "            for c in b_to_f:\n",
    "                b_cities.remove(c)\n",
    "                f_cities.append(c)\n",
    "            \n",
    "            b_cluster_centroid = self.__get_center(*[self.__city_pos[c] for c in b_cities])\n",
    "            f_cluster_centroid = self.__get_center(*[self.__city_pos[c] for c in f_cities])\n",
    "        \n",
    "\n",
    "            bf_pos = [d_cluster_pos[d_path[d_path_idx-1]], b_cluster_centroid, \n",
    "                f_cluster_centroid, d_cluster_pos[d_path[(d_path_idx+1)%len(d_path)]]]\n",
    "            bf_dist = self.__get_pos_dist(bf_pos[0], bf_pos[1]) + self.__get_pos_dist(bf_pos[1], bf_pos[2]) + self.__get_pos_dist(bf_pos[2], bf_pos[3])\n",
    "            \n",
    "            fb_pos = [d_cluster_pos[d_path[d_path_idx-1]], f_cluster_centroid, \n",
    "                b_cluster_centroid, d_cluster_pos[d_path[(d_path_idx+1)%len(d_path)]]]\n",
    "            fb_dist = self.__get_pos_dist(fb_pos[0], fb_pos[1]) + self.__get_pos_dist(fb_pos[1], fb_pos[2]) + self.__get_pos_dist(fb_pos[2], fb_pos[3])\n",
    "            \n",
    "            if bf_dist < fb_dist:\n",
    "                d_cluster_cities[C_divide] = f_cities\n",
    "                d_cluster_cities.append(b_cities)\n",
    "\n",
    "                d_cluster_pos[C_divide] = f_cluster_centroid\n",
    "                d_cluster_pos = np.append(d_cluster_pos, np.array([b_cluster_centroid]), axis=0)\n",
    "                for i in range(len(d_cluster_labels)):\n",
    "                    if i in b_cities:\n",
    "                        d_cluster_labels[i] = len(d_path) - 1\n",
    "            else:\n",
    "                d_cluster_cities[C_divide] = b_cities\n",
    "                d_cluster_cities.append(f_cities)\n",
    "\n",
    "                d_cluster_pos[C_divide] = b_cluster_centroid\n",
    "                d_cluster_pos = np.append(d_cluster_pos, np.array([f_cluster_centroid]), axis=0)\n",
    "\n",
    "                for i in range(len(d_cluster_labels)):\n",
    "                    if i in f_cities:\n",
    "                        d_cluster_labels[i] = len(d_path) - 1\n",
    "            \n",
    "            d_path.insert(d_path_idx, len(d_path))\n",
    "            \n",
    "            sub_cluster_dist = self.__get_dist_table(d_cluster_pos)\n",
    " \n",
    "            d_path_q = deque(d_path)\n",
    "            d_path_q.rotate(len(d_path) - 2 - d_path_idx)\n",
    "            d_path = list(d_path_q)\n",
    "            \n",
    "            d_path_idx = len(d_path) - 2\n",
    "            s, e = d_path_idx - min(len(d_path) - 2, path_tsp_n - 2), (d_path_idx + 1)\n",
    "            \n",
    "            sub_path = d_path[s:e + 1]\n",
    "            new_path = self.__DFS_path_tsp(d_path[s], d_path[e], sub_path[:-1], sub_cluster_dist) + [d_path[e]]\n",
    "\n",
    "            for i in range(s, e + 1):\n",
    "                d_path[i] = new_path[i - s] \n",
    "                \n",
    "            d_path_q.rotate(-(len(d_path) - 2))\n",
    "            d_path = list(d_path_q)\n",
    "            d_path_idx = 1\n",
    "            \n",
    "            s, e = d_path_idx - 1, d_path_idx + min(len(d_path) - 2, path_tsp_n - 2)\n",
    "            sub_path = d_path[s:e + 1]\n",
    "            new_path = self.__DFS_path_tsp(d_path[s], d_path[e], sub_path[:-1], sub_cluster_dist) + [d_path[e]]\n",
    "\n",
    "            for i in range(s, e + 1):\n",
    "                d_path[i] = new_path[i - s] \n",
    "\n",
    "            self.dividing_cluster_infos.append([d_cluster_pos.copy(), d_cluster_cities[:], d_cluster_labels[:], d_path[:]])\n",
    "            most_cluster_cities = max(d_cluster_cities, key=lambda x: len(x))\n",
    "        \n",
    "        print(' done     ')\n",
    "\n",
    "        # stage 4: path-tsp\n",
    "        print('s4 path-tsp finding', flush=True)\n",
    "        cluster_pos = self.dividing_cluster_infos[-1][0]\n",
    "        cluster_cities = self.dividing_cluster_infos[-1][1]\n",
    "        cluster_labels = self.dividing_cluster_infos[-1][2]\n",
    "        path = self.dividing_cluster_infos[-1][3]\n",
    "\n",
    "        start = max([[c, self.__get_pos_dist(self.__city_pos[c], cluster_pos[path[1]])] for c in cluster_cities[path[0]]], key=lambda x: x[1])[0]\n",
    "\n",
    "        first = start\n",
    "        for i in range(len(path) - 1):            \n",
    "            print(f' {(i / len(path)) * 100:.2f}%\\r', end='')\n",
    "            end = self.__find_end_city2(path, i, start, self.__city_pos, cluster_pos, cluster_cities)\n",
    "            sub_path_tsp_path = self.__DFS_path_tsp(start, end, cluster_cities[path[i]], self.__city_dist)\n",
    "            self.path_tsp_path += sub_path_tsp_path\n",
    "            self.path_tsp_process.append(self.path_tsp_path[:])\n",
    "            start = end\n",
    "        self.path_tsp_path += self.__DFS_path_tsp(start, first, cluster_cities[path[-1]], self.__city_dist)\n",
    "        self.path_tsp_dist = self.__get_path_dist(self.path_tsp_path + [self.path_tsp_path[-1]], self.__city_dist)\n",
    "\n",
    "        print(' done     ')\n",
    "\n",
    "        # last stage: untangling\n",
    "        print('s5 path untangling', flush=True)\n",
    "\n",
    "        self.final_path = self.path_tsp_path[:]\n",
    "        s, e = 0, path_tsp_n - 1\n",
    "        gap = 0\n",
    "        while e < len(self.final_path):\n",
    "            print(f' {(e / len(self.final_path)) * 100:.2f}%\\r', end='')\n",
    "            sub_path = self.final_path[s:e + 1]\n",
    "            new_path = self.__DFS_path_tsp(self.final_path[s], self.final_path[e], sub_path[:-1], self.__city_dist) + [self.final_path[e]]\n",
    "            # sd = self.__get_path_dist(sub_path, self.__city_dist)\n",
    "            # nd = self.__get_path_dist(new_path, self.__city_dist)\n",
    "            # gap += sd - nd\n",
    "            # # print(sub_path, new_path, f'{sd:7.2f}, {nd:7.2f}', f'|| gap: {gap:.2f}', e)\n",
    "            for i in range(s, e + 1):\n",
    "                self.final_path[i] = new_path[i - s] \n",
    "\n",
    "            if self.final_path not in [e[0] for e in self.final_process]:\n",
    "                self.final_process.append([self.final_path[:], self.__get_path_dist(self.final_path + [self.final_path[0]], self.__city_dist)])\n",
    "            s += 1\n",
    "            e += 1\n",
    "        \n",
    "        self.final_dist = self.__get_path_dist(self.final_path + [self.final_path[0]], self.__city_dist)\n",
    "        print(' done      ')\n",
    "        \n",
    "\n",
    "def draw_path(path : list, pos : np.ndarray, dist : int = None, city_pos: list = [], mod = None, save = None, figsize : tuple = None, color='r', dot=True):\n",
    "\n",
    "    if figsize != None:\n",
    "        plt.figure(figsize=figsize)\n",
    "    \n",
    "    if not dot:\n",
    "        plt.scatter([pos[0] for pos in city_pos], [pos[1] for pos in city_pos], edgecolors='none', s=1, c='none')\n",
    "    else:\n",
    "        plt.scatter([pos[0] for pos in city_pos], [pos[1] for pos in city_pos], s=10, alpha=0.2, edgecolors='none', c='black')\n",
    "  \n",
    "    if dist != None:\n",
    "        plt.text(0, 0, f'Len: {dist:.2f}')\n",
    "\n",
    "    if mod != None:\n",
    "        plt.plot([pos[c][0] for c in path[mod[1] + 1:]], [pos[c][1] for c in path[mod[1] + 1:]], c=color)\n",
    "        plt.plot([city_pos[c][0] for c in mod[0]], [city_pos[c][1] for c in mod[0]], c=color)\n",
    "    else:\n",
    "        plt.plot([pos[c][0] for c in path + [path[0]]], [pos[c][1] for c in path + [path[0]]], c=color)\n",
    "\n",
    "    if save != None:\n",
    "        plt.savefig(os.path.join(f'{save[0]}', f'{save[0]}_{save[1]:05}.png'))\n",
    "        plt.close()\n",
    "\n",
    "def make_gif(tsp_obj : TSP, file_name : str, coords : list = [], figsize : tuple = None, color='r', dot=True, interval=0.1):\n",
    "    image_num = 0\n",
    "\n",
    "    os.mkdir(file_name)\n",
    "\n",
    "\n",
    "    draw_path(path=tsp_obj.tsp_path, pos=tsp_obj.kmeans_cluster_pos, city_pos=coords, \n",
    "        save=[file_name, image_num], figsize=figsize, color=color, dot=dot)\n",
    "    image_num += 1\n",
    "\n",
    "    for i in range(20):\n",
    "        draw_path(path=tsp_obj.dividing_cluster_infos[0][-1], pos=tsp_obj.dividing_cluster_infos[0][0], city_pos=coords, \n",
    "            save=[file_name, image_num], figsize=figsize, color=color, dot=dot)\n",
    "        image_num += 1\n",
    "\n",
    "    for i in range(len(tsp_obj.dividing_cluster_infos)):\n",
    "        draw_path(path=tsp_obj.dividing_cluster_infos[i][-1], pos=tsp_obj.dividing_cluster_infos[i][0], city_pos=coords, \n",
    "            save=[file_name, image_num], figsize=figsize, color=color, dot=dot)\n",
    "        image_num += 1\n",
    "\n",
    "    for i in range(len(tsp_obj.path_tsp_process)):\n",
    "        draw_path(path=tsp_obj.dividing_cluster_infos[-1][-1], pos=tsp_obj.dividing_cluster_infos[-1][0], city_pos=coords, \n",
    "            save=[file_name, image_num], mod=[tsp_obj.path_tsp_process[i], i + 1], figsize=figsize, color=color, dot=dot)\n",
    "        image_num += 1\n",
    "\n",
    "    for i in range(len(tsp_obj.final_process)):\n",
    "        draw_path(path=[int(c) for c in tsp_obj.final_process[i][0]], pos=coords, city_pos=coords, \n",
    "            dist = tsp_obj.final_process[i][1], save=[file_name, image_num], figsize=figsize, color=color, dot=dot)\n",
    "        image_num += 1\n",
    "\n",
    "    for i in range(30):\n",
    "        draw_path(path=tsp_obj.final_process[-1][0], pos=coords, city_pos=coords, dist = tsp_obj.final_process[-1][1], \n",
    "            save=[file_name, image_num], figsize=figsize, color=color, dot=dot)\n",
    "        image_num += 1\n",
    "\n",
    "    imgs = []\n",
    "    for file_n in os.listdir(file_name):\n",
    "        if file_n.endswith(f'.png'):\n",
    "            file_path = os.path.join(file_name, file_n)\n",
    "            imgs.append(imageio.imread_v2(file_path))\n",
    "    imageio.mimsave(f'{file_name}.gif', imgs, **{'duration':interval})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.collections.PathCollection at 0x28f5694dc10>"
      ]
     },
     "execution_count": 211,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAD4CAYAAADsKpHdAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAY8UlEQVR4nO3dfYxc13nf8e/PNC2vZStrRSuVWtIhAxBq9ZKI1oKls0XgSLFFu4ZFqLDBFI4YgAEBQYXltlC6RIAa+UMQUxdGmrYSSjiOqCS2zNoyRegltEDGCGqolpehHOuNMR0x0i4ZceNKsdoKAkU/+WPOhqPl7O7M7Mydc+78PsBg7pydu/Psy8xzz3POPVcRgZmZ2TsGHYCZmeXBCcHMzAAnBDMzS5wQzMwMcEIwM7PknYMOYDmXXXZZrF+/ftBhmJkV5ejRo38XEWOd7JN9Qli/fj3T09ODDsPMrCiS/qbTfVwyMjMzwAnBzMwSJwQzMwOcEMzMLHFCMDMzoIBZRmZmdXTg2CxfOHScU6+9wZWjI9x181Vs2zQ+0JicEMzMKnbg2Cy7H/oBb5w9B8Dsa2+w+6EfAAw0KbhkZGZWsS8cOv6PyWDeG2fP8YVDxwcUUYMTgplZxU699kZH7VVxQjAzq9iVoyMdtVfFCcHMrGJ33XwVI6tXva1tZPUq7rr5qgFF1OBBZTOzis0PHBc5y0jSSeB14BzwVkRMSLoU+BqwHjgJfDoiXk3P3w3sTM//bEQcSu03APcDI8BjwJ3hizqb2RDatml84AlgoU5KRr8SEddHxER6PAUcjoiNwOH0GElXA9uBa4CtwL2S5vtG9wG7gI3ptnXlP4KZmfXCSsYQbgH2pe19wLam9gcj4s2IeBE4AWyWtAa4JCKeTL2CB5r2MTOzAWs3IQTwLUlHJe1KbVdExGmAdH95ah8HXm7adya1jafthe0XkLRL0rSk6bm5uTZDNDOzlWh3UHkyIk5Juhx4QtILSzxXLdpiifYLGyP2AnsBJiYmPMZgZlnLcRmKbrSVECLiVLo/I+mbwGbgFUlrIuJ0KgedSU+fAdY17b4WOJXa17ZoNzMrVq7LUHRj2ZKRpIslvW9+G/go8AxwENiRnrYDeDhtHwS2S7pI0gYag8dPpbLS65K2SBJwW9M+ZmZFynUZim6000O4Avhm4zOcdwJfiYg/lfQ9YL+kncBLwKcAIuJZSfuB54C3gDsiYv63dTvnp50+nm5mZsXqdBmKnMtLyyaEiPhr4BdbtP8YuGmRfe4G7m7RPg1c23mYZmZ5unJ0hNkWH/6tlqHIvbzkpSvMzFagk2Uoci8veekKM7MV6GQZilxXOZ3nhGBmtkLtLkOxXHlp0OMLLhmZmVVkqfLS/PjC7GtvEJwfXzhwbLay+JwQzMwqsm3TOPfceh3joyMIGB8d4Z5br2PbpvEsxhdcMjIzq9Bi5aUcxhfcQzAzy0AOV1FzQjAzy0Cr8QUBv/JPxyqLwQnBzCwD2zaN869uGH/bKqABfOPobGUDy04IZmaZ+LMX5i5YArrKgWUPKpuZ9dBKziUY9MCyewhmZj2y0nMJBj2w7IRgZtYjnZxLcODYLJN7jrBh6lEm9xzhwLHZjtZF6gcnBDOzHmm35LNYTwJY9MS1KngMwcysR9pdCnupnsR3pm4c2FLY7iGYmfVIuyWfQQ8eL8YJwcysR5Zaq6jZoAePF+OSkZlZD7WzFPZdN1/1tiunQbWDx4txQjAzq1gnF9WpkhOCmdkAtHtRnSp5DMHMzAAnBDMzS5wQzMwMcEIwM7PECcHMzAAnBDMzS5wQzMwMcEIwM7PECcHMzIAOEoKkVZKOSXokPb5U0hOSfpju39/03N2STkg6LunmpvYbJP0gfe33JanVa5mZWfU66SHcCTzf9HgKOBwRG4HD6TGSrga2A9cAW4F7Jc2vB3sfsAvYmG5bVxS9mVlhWl0pLRdtJQRJa4F/CXypqfkWYF/a3gdsa2p/MCLejIgXgRPAZklrgEsi4smICOCBpn3MzGpvpddc7rd2ewi/B/wW8NOmtisi4jRAur88tY8DLzc9bya1jafthe0XkLRL0rSk6bm5uTZDNDPLWyfXXB6EZROCpE8AZyLiaJvfs9W4QCzRfmFjxN6ImIiIibGxsTZf1swsb7leKW1eO8tfTwKflPRx4N3AJZL+GHhF0pqIOJ3KQWfS82eAdU37rwVOpfa1LdrNzIZCu9dcHpRlewgRsTsi1kbEehqDxUci4jPAQWBHetoO4OG0fRDYLukiSRtoDB4/lcpKr0vakmYX3da0j5lZ7bV7zeVBWckFcvYA+yXtBF4CPgUQEc9K2g88B7wF3BER80Wz24H7gRHg8XQzMxsKuV4pbZ4aE37yNTExEdPT04MOw8ysKJKORsREJ/v4EppmZitw4Nhstkf8nXJCMDPr0vx5BfNTSefPKwCKTApOCGZmXVrqvIKlEkKuvQonBDOzLnVzXkHOvQqvdmpm1qXFzh9Y6ryCnM9WdkIwM+tSN+cV5Hy2shOCmVmXtm0a555br2N8dAQB46Mj3HPrdUuWfrrpVVTFYwhmZiuwbdP4srX/5kHk0fesZvU7xNmfnj8HLJezlZ0QzKwyuc6u6aeFg8iv/v+zrF4lRkdW8/dvnM3q9+CEYGaVyHl2TT+1GkQ+ey64+KJ38vTnPzqgqFrzGIKZVSLn2TX9lPMg8kJOCGZWiZI+GHsp50HkhZwQzKwSJX0w9lLuS143c0Iws0qU9MHYS91MTR0UDyqbWSVyvxZAP7UzNTUHTghmVplSPhiHlROCWWaGca6+5cEJwSwjwzpX3/LghGC1UvrRdbfr65v1ghOC1UYdjq6Hda6+5cHTTq026nAmbNVz9Q8cm2VyzxE2TD3K5J4jHDg225fXsTI4IVht1OHousq5+vM9qtnX3iA436NyUuiPEpKvE4LVRh3OhK3yJKY69KhKUUry9RiC1cZdN1/1tjEEKPNM2Krm6tehRwVlTCQoZbKAE4LVxjCfCduNK0dHmG3x4V9Sj6qUiQSlJF8nBKsVnwnbvjr0qEo58i4l+XoMwWxIlbTo2mJKOfIuZWE/9xDMhljpPapSjrxLKWc6IZhZsUoqe5WQfJ0QzKxYpRx5l2LZhCDp3cCfAxel5389Ij4v6VLga8B64CTw6Yh4Ne2zG9gJnAM+GxGHUvsNwP3ACPAYcGdERG9/JDMbJis58i5hymqV2hlUfhO4MSJ+Ebge2CppCzAFHI6IjcDh9BhJVwPbgWuArcC9kuZHU+4DdgEb021r734UM7P2lXKyWJWWTQjR8H/Tw9XpFsAtwL7Uvg/YlrZvAR6MiDcj4kXgBLBZ0hrgkoh4MvUKHmjax8ysUj5T+0JtTTuVtErS08AZ4ImI+C5wRUScBkj3l6enjwMvN+0+k9rG0/bC9lavt0vStKTpubm5Dn4cM7P2lDJltUptJYSIOBcR1wNraRztX7vE09XqWyzR3ur19kbERERMjI2NtROimVlH6rD2Va91dGJaRLwGfJtG7f+VVAYi3Z9JT5sB1jXtthY4ldrXtmg3syE1yBVASzlZrErLJgRJY5JG0/YI8KvAC8BBYEd62g7g4bR9ENgu6SJJG2gMHj+VykqvS9oiScBtTfuYVaaEZYiHwaAHdetwpnavtXMewhpgX5op9A5gf0Q8IulJYL+kncBLwKcAIuJZSfuB54C3gDsiYn7k5nbOTzt9PN2sxzyVbnGlLIY2DHJYh2gQJ4vl/P5cNiFExF8Cm1q0/xi4aZF97gbubtE+DSw1/mAr5A+8peXwIWQNwziom/v704vb1Yyn0i1tGD+EcjWMg7q5vz+dEGrGH3hLG8YPoVwN46Bu7u9PJ4Sa8Qfe0obxQyhXwziom/v7s5aL2+U8aNNvJa3+OAh1WAytTv/f3Q7qlvo7yP39WbuEkPugTb/V4QOv30pYhngxw/7/DWX/DnJ/fyr3xUYnJiZienq67edP7jnS8oIZ46MjfGfqxl6GZlY5/3/7d9AuSUcjYqKTfWrXQ8h90MZsJQb5/51Lmcbv8f6p3aBy7oM2ZisxqP/vQZ9V3Mzv8f6pXULwLBKrs0H9f+c0f97v8f6pXcko90Ebs5UY1P93TmUav8f7p3aDymbWex7ILU83g8q1KxmZWe+5TDMcalcyMrPec5lmODghmFlbSj6hz9rjkpGZmQFOCGZmljghmJkZ4DEEs4HIZRkIs2ZOCGYVK3m1Tqs3l4zMKpbTMhBmzdxDMKtYTstAWP+UWBasZUIo8Q9hw+PK0ZGWy0B4tc76KLUsWLuSUU7L9Jq1ktsyEAeOzTK55wgbph5lcs8Rv1d6oNSyYO0SQql/CBseOV1c3gdQ/VFqWbB2JaNS/xA2XHJZBmKpA6gc4mtWUim41LJg7XoIvpqSWftKOYAqrSeTW1mwXbVLCKX+IcwGoZQDqNJKwTmVBTtRu5JRacv0ltQNtvq56+ar3jYbBvI8gCqlJ9Msl7JgJ2qXEKCcP0SpU9Osev06cCjlAKrUmnxplk0IktYBDwD/BPgpsDci/oukS4GvAeuBk8CnI+LVtM9uYCdwDvhsRBxK7TcA9wMjwGPAnZH7NTz7qKQBPRucfh84lHAAVUpPpnTtjCG8Bfz7iPhnwBbgDklXA1PA4YjYCBxOj0lf2w5cA2wF7pU0X9S/D9gFbEy3rT38WYpTYjfYqlda/bwfSq3Jl2bZHkJEnAZOp+3XJT0PjAO3AB9OT9sHfBv4D6n9wYh4E3hR0glgs6STwCUR8SSApAeAbcDjvftxyuJucGeGdbzFBw4NJfRkStfRLCNJ64FNwHeBK1KymE8al6enjQMvN+02k9rG0/bC9lavs0vStKTpubm5TkIsimdEta+0aYe9VMpMICtf2wlB0nuBbwCfi4ifLPXUFm2xRPuFjRF7I2IiIibGxsbaDbE47ga3b5jLJj5wqIaX8GhzlpGk1TSSwZ9ExEOp+RVJayLitKQ1wJnUPgOsa9p9LXAqta9t0T7U3A1uzzCXTUqZCVQyz/hraGeWkYA/AJ6PiC82fekgsAPYk+4fbmr/iqQvAlfSGDx+KiLOSXpd0hYaJafbgP/as5/Eam3Yx1t84NBfnvHX0E7JaBL4deBGSU+n28dpJIKPSPoh8JH0mIh4FtgPPAf8KXBHRMz/pm8HvgScAH7EEA8oW2dcNrF+GuYeaLN2Zhn9L1rX/wFuWmSfu4G7W7RPA9d2EqAZuGxi/TXsPdB5tTxT2erJZRPrF5/41uCEYGZDzz3QBicEMzPcA4UaLn9tZmbdcQ/BijSsy1iY9ZMTghXHJxGZ9YdLRlacYV7Gwqyf3EMYciWWXnwSkVl/uIcwxEpdQdSrf5r1hxPCECu19OJlLMz6wyWjIVZq6cUnEZn1hxPCECt5/RafRGTWey4ZDTGXXmwY+UI4i3MPYYi59GLdKnF2GvgcluU4IQw5l16sUyV/qPpCOEtzycjMOlLq7DQodyJFVZwQzKwjJX+o+hyWpTkhmFlHSv5Q9USKpTkhmFlHSv5Q3bZpnHtuvY7x0REEjI+OcM+t13n8IPGgspl1pPTZaf2YSFHqrKuFnBDMrGOenXZeybOuFnLJyMxsBUqedbWQewhmmatLOaKuSp51tZB7CGYZK3WJ8mFS8qyrhZwQzDJWp3JEXZU862ohl4zMMlanckQ7SiyPlT7rqpkTglnGSl6ivFMlz9apy6wrl4zMMlancsRyXB4bPPcQzDJWp3LEcoatPJajZROCpC8DnwDORMS1qe1S4GvAeuAk8OmIeDV9bTewEzgHfDYiDqX2G4D7gRHgMeDOiIje/jjVKrHeaeWpSzliOcNUHstVOyWj+4GtC9qmgMMRsRE4nB4j6WpgO3BN2udeSfP93fuAXcDGdFv4PYvi6YBmvTVM5bFcLZsQIuLPgf+zoPkWYF/a3gdsa2p/MCLejIgXgRPAZklrgEsi4snUK3igaZ8iud5p1lteeG7wuh1DuCIiTgNExGlJl6f2ceB/Nz1vJrWdTdsL21uStItGb4IPfOADXYbYX653mvXesJTHctXrWUZq0RZLtLcUEXsjYiIiJsbGxnoWXC/V6exEMzPoPiG8kspApPszqX0GWNf0vLXAqdS+tkV7sVzvNLO66TYhHAR2pO0dwMNN7dslXSRpA43B46dSeel1SVskCbitaZ+sHDg2y+SeI2yYepTJPUcWHSR2vdPM6qadaadfBT4MXCZpBvg8sAfYL2kn8BLwKYCIeFbSfuA54C3gjoiYH3m9nfPTTh9Pt6x0eqak651mVifK/VSAiYmJmJ6eruS1JvccaTkPenx0hO9M3VhJDGZmvSDpaERMdLKPz1Ru4plDZfIJgma94bWMmnjmUHl8gqBZ7zghNPHMofL4BEGz3nHJqMkwLSRWFy7zmfWOE8ICnjlUFi+IVi8eDxosl4ysaC7z1YfHgwbPCcGK5hME68PjQYPnkpEVz2W+evB40OC5h2BmWfC078FzQjCzLHg8aPBcMjKzLHja9+A5IZhZNjweNFguGZmZGeCEYGZmiROCmZkBTghmZpY4IZiZGeCEYGZmiROCmZkBTghmZpY4IZiZGeCEYGZmiROCmZkBTghmZpZ4cTuzGvM1iq0TTghmNTV/jeL5y1LOX6MYcFKwllwyMqspX6PYOuWEYFZTvkaxdcoJwaymfI1i61TlCUHSVknHJZ2QNFX169vKHDg2y+SeI2yYepTJPUc4cGx20CHZInyNYutUpYPKklYB/x34CDADfE/SwYh4rso4rDsepCyLr1Fsnap6ltFm4ERE/DWApAeBWwAnhAIsNUjpD5k8+RrF1omqS0bjwMtNj2dS29tI2iVpWtL03NxcZcHZ0jxIaVZvVScEtWiLCxoi9kbERERMjI2NVRCWtcODlGb1VnVCmAHWNT1eC5yqOAbrkgcpzeqt6jGE7wEbJW0AZoHtwL+uOAbrkgcpzeqt0oQQEW9J+jfAIWAV8OWIeLbKGGxlPEhpVl+Vr2UUEY8Bj1X9umZmtjSfqWxmZoATgpmZJU4IZmYGOCGYmVmiiAvOC8uKpDngb7rc/TLg73oYTi85tu7kHBvkHZ9j607OscHi8f1cRHR0Zm/2CWElJE1HxMSg42jFsXUn59gg7/gcW3dyjg16G59LRmZmBjghmJlZUveEsHfQASzBsXUn59gg7/gcW3dyjg16GF+txxDMzKx9de8hmJlZm5wQzMwMqGlCkLRV0nFJJyRNVfSaX5Z0RtIzTW2XSnpC0g/T/fubvrY7xXdc0s1N7TdI+kH62u9LanVRoU5jWyfpzyQ9L+lZSXfmEp+kd0t6StL3U2y/k0tsTd93laRjkh7JMLaT6fs+LWk6p/gkjUr6uqQX0v/eh3KITdJV6fc1f/uJpM/lEFvT9/236f3wjKSvpvdJ/+OLiFrdaCyr/SPg54F3Ad8Hrq7gdX8Z+CDwTFPbfwKm0vYU8Ltp++oU10XAhhTvqvS1p4AP0bi63OPAx3oQ2xrgg2n7fcBfpRgGHl/6Pu9N26uB7wJbcoitKcZ/B3wFeCSnv2v6vieByxa0ZREfsA/4zbT9LmA0l9iaYlwF/C3wc7nERuOywi8CI+nxfuA3qoivJ7/UnG7phz/U9Hg3sLui117P2xPCcWBN2l4DHG8VE43rQ3woPeeFpvZfA/5HH+J8GPhIbvEB7wH+AvjnucRG46p+h4EbOZ8Qsogtfa+TXJgQBh4fcAmNDzXlFtuCeD4KfCen2Dh/7flLaVyi4JEUZ9/jq2PJaP6XOW8mtQ3CFRFxGiDdX57aF4txPG0vbO8ZSeuBTTSOxLOIL5VkngbOAE9ERDaxAb8H/Bbw06a2XGKDxjXJvyXpqKRdGcX388Ac8Iep3PYlSRdnEluz7cBX03YWsUXELPCfgZeA08DfR8S3qoivjgmhVY0st7m1i8XY19glvRf4BvC5iPjJUk9dJI6+xBcR5yLiehpH45slXZtDbJI+AZyJiKPt7rJIDP38u05GxAeBjwF3SPrlJZ5bZXzvpFFCvS8iNgH/j0aZI4fYGi8ovQv4JPA/l3vqIjH0JbY0NnALjfLPlcDFkj5TRXx1TAgzwLqmx2uBUwOK5RVJawDS/ZnUvliMM2l7YfuKSVpNIxn8SUQ8lFt8ABHxGvBtYGsmsU0Cn5R0EngQuFHSH2cSGwARcSrdnwG+CWzOJL4ZYCb19gC+TiNB5BDbvI8BfxERr6THucT2q8CLETEXEWeBh4BfqiK+OiaE7wEbJW1IRwDbgYMDiuUgsCNt76BRu59v3y7pIkkbgI3AU6kb+LqkLWk2wG1N+3Qtfa8/AJ6PiC/mFJ+kMUmjaXuExpvhhRxii4jdEbE2ItbT+D86EhGfySE2AEkXS3rf/DaNOvMzOcQXEX8LvCzpqtR0E/BcDrE1+TXOl4vmY8ghtpeALZLek77vTcDzlcTXq8GZnG7Ax2nMpPkR8NsVveZXadT7ztLIzDuBn6UxIPnDdH9p0/N/O8V3nKaRf2CCxpv6R8B/Y8GgXJex/QsaXcW/BJ5Ot4/nEB/wC8CxFNszwH9M7QOPbUGcH+b8oHIWsdGo038/3Z6d/1/PKL7rgen0tz0AvD+j2N4D/Bj4maa2LGJL3/d3aBwYPQP8EY0ZRH2Pz0tXmJkZUM+SkZmZdcEJwczMACcEMzNLnBDMzAxwQjAzs8QJwczMACcEMzNL/gGPfezJx2O6oAAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# prepare x, y pos list (n by 2) [[0, 0], [2, 3.2] ... ]\n",
    "file_name = 'att48'\n",
    "coords = []\n",
    "with open(file_name + '.txt') as f:\n",
    "    for line in f.readlines():\n",
    "        coords.append(list(map(float, [line.split()[-2], line.split()[-1]])))\n",
    "\n",
    "#print(coords)\n",
    "# prepare Euclidian distance table\n",
    "# [[0, 1, 3]\n",
    "#  [1, 0, 7]\n",
    "#  [3, 7, 0]] ... \n",
    "\n",
    "coord_dist = [[((coords[i][0] - coords[j][0]) ** 2 + (coords[i][1] - coords[j][1]) ** 2) ** 0.5 \n",
    "for j in range(len(coords))] for i in range(len(coords))]\n",
    "\n",
    "plt.scatter([pos[0] for pos in coords], [pos[1] for pos in coords])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s1 kmeans clustering\n",
      " done     \n",
      "s2 tsp finding\n",
      " done     \n",
      "s3 cluster dividing\n",
      " done     \n",
      "s4 path-tsp finding\n",
      " done     \n",
      "s5 path untangling\n",
      " done      \n"
     ]
    }
   ],
   "source": [
    "# run tsp\n",
    "tsp_obj = TSP(coords, coord_dist)\n",
    "tsp_obj.run(tsp_n=17, division_bound=5, path_tsp_n=12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAD4CAYAAADsKpHdAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAABB3klEQVR4nO2dd3hUVfPHvxMSAgSQlkAoEkCkBCFAlGJAAZGACr4KUkSwIIooKvoq6IuKiqI/C6KIIopU6VJUug1ESmgKISRBWgAJYIHQQpL5/TF3yQIh2d3s3Xt3M5/nuc/dPXvvPbPtzD0zc2aImaEoiqIoQVYLoCiKotgDVQiKoigKAFUIiqIoioEqBEVRFAWAKgRFURTFINhqAQqiUqVKHBUVZbUYiqIofsWmTZuOMXO4O+fYXiFERUUhISHBajEURVH8CiLa5+45ajJSFEVRAKhCUBRFUQxUISiKoigAVCEoiqIoBqoQFEVRFACqEBRFURQDVQiKoigKAFUIiqIo1nHgADBpktVSXEAVgqIoihWsWwfExgIPPghkZFgtDQBVCIqiKL5nxgzg5puB9HQgPBwoXdpqiQCoQlAURfEdOTnAiBHAvfcCLVoADRrIZhNUISiKoviC06eBnj2B118XM9GKFTJDqF/fasku4JJCIKK9RPQ7EW0logSjrQIRrSCiFGNf3un44USUSkS7iKiTU3tz4zqpRDSWiMj7b0lRFMVmHDwItG0LzJsHvPMOMHEicOIEcPy4/ykEg3bMHMPMscbzYQBWMXNdAKuM5yCihgB6AYgGEA/gYyIqZpwzHsBAAHWNLb7wb0FRFMXGbNoE3HADsGsXsGgR8MwzABGwc6e8HiAmo24AJhuPJwO406l9JjOfY+Y9AFIB3EBEkQDKMvOvzMwApjidoyiKEnjMnQu0aQMEBwO//ALcfnvua0lJsvfDGQIDWE5Em4hooNFWmZkPA4CxjzDaqwE44HRumtFWzXh8aftlENFAIkogooSjR4+6KKKiKIpNYBZfQY8eQEwMsGED0LjxxcckJQElSwJXX22JiHnhaoGcG5n5EBFFAFhBREn5HJuXX4Dzab+8kXkCgAkAEBsbm+cxiqIotuTsWeChhyS09N57xV9QosTlx+3cCdSrBwTZJ7bHJUmY+ZCxTwfwNYAbABwxzEAw9unG4WkAajidXh3AIaO9eh7tiqIogcGRI0C7dqIMRo0Cpk7NWxkAMkOwkbkIcEEhEFEYEZVxPAZwK4DtABYB6G8c1h/AQuPxIgC9iCiUiGpBnMcbDLPSSSJqaUQX9XM6R1EUxb85fFicx9u2ie/ghRfEeZwXZ84Ae/faTiG4YjKqDOBrI0I0GMAMZl5KRBsBzCaihwDsB9ADAJh5BxHNBpAIIAvAYGbONq41CMCXAEoCWGJsiqIo/s+6dcD+/cD8+cB//pP/scnJ4mewUYQR4IJCYOY/ADTJo/04gA5XOGcUgFF5tCcAaOS+mIqiKDYnOlr2//5b8LE2jDACdKWyoiiKd6hTBwgLA7ZsKfhYxxqEqlXNlclNVCEoiqJ4g2LFJLR069aCjw0Pl310NPDhh8C5c6aK5iqqEBRFUbxFTIwoBC4gWn7wYGDtWqBhQ2DIEDEdTZkCZGfnf57JqEJQFEXxFk2bSo6ivXsLPrZVK+D774Fly4CKFYH+/YEmTYAFCwpWKCahCkFRFMVbxMTI3hWzESBhqbfeCmzcCMyZA2RlSYRS375mSZgvqhAURVG8RaNGsvLYFceyM0RA9+7A9u2yynnWLEuqqKlCUBRF8RYlS4o/wNUZwqUEBwP33CO+hF9/9aporqAKQVEUxZs4HMue0qqVzDJ+/tlbErmMKgRFURRv0rQpcOCAFL/xhDJlgGbNVCEoiqL4PQ7H8rZtnp2fnQ2UKwesX+/zaCNVCIqiKN6kiZHpx13HMiCO5DvvBFauBJ566srJ8UzC1XoIiqIoiiuEhwPVqrnvRzh8WCqqbd0KjBsHPPaYGdLliyoERVEUb9O0qXsKYft24LbbxO+waJE8tgA1GSmKonib8uWBf/5x7diVK4EbbwTOnxdHskXKAFCFoCiK4n1SU4G6dQs+bsUKoHNnoGZNcSI3a2a+bPmgCkFRFMXbJCcD115b8HFz5kiY6erVQI0aBR9vMqoQFEVRvMlff4kvwJUZQkqKrGy+6irz5XIBVQiKoijeJCVF9q7MEFJSXFMcPkIVgqIoijdJTpZ9QQrh9Gng4EFVCIqiKAFLSorkIqpVK//jUlNlrwpBURQlQElOFmVQvHj+xzlMS6oQFEVRAhRXI4xUISiKogQwzK47ilNSgMqVJezUJqhCUBRF8RZ//ikJ6lydIVxzjfkyuYEqBEVRFG/hiDByZYbg6mpmH6IKQVEUxVu4ugYhI0Oym6pCUBRFCVCSk4HQ0ILTUNgw5BRQhaAoiuI9kpOBOnWAYsXyP86GEUaAKgRFURTvkZLiXsipvzqViagYEW0hom+M5xWIaAURpRj78k7HDieiVCLaRUSdnNqbE9HvxmtjiXxcH05RFMUssrNddxSnpACRkUDp0ubL5QbuzBCeBLDT6fkwAKuYuS6AVcZzEFFDAL0ARAOIB/AxETnmT+MBDARQ19jiCyW9oiiKXdi/H8jM9Mukdg5cUghEVB3AbQAmOjV3AzDZeDwZwJ1O7TOZ+Rwz7wGQCuAGIooEUJaZf2VmBjDF6RxFURT/xo+znDpwdYYwBsBzAHKc2ioz82EAMPYRRns1AAecjksz2qoZjy9tvwwiGkhECUSUcPToURdFVBRFsRBX1yCcOAGkp/unQiCi2wGkM/MmF6+Zl1+A82m/vJF5AjPHMnNseHi4i90qiqJYSHKy+ASqVMn/uBMnZG+TojjOBLtwzI0AuhJRFwAlAJQlomkAjhBRJDMfNsxB6cbxaQCcg3CrAzhktFfPo11RFMX/cUQYFRQrU6UKEBwsPgebUeAMgZmHM3N1Zo6COIu/Z+a+ABYB6G8c1h/AQuPxIgC9iCiUiGpBnMcbDLPSSSJqaUQX9XM6R1EUxb9JTnbNDBQcDFSvDuzbZ75MblKYdQijAXQkohQAHY3nYOYdAGYDSASwFMBgZs42zhkEcUynAtgNYEkh+lcURbEHmZnA3r2uOZQBICpKjrcZrpiMLsDMPwL40Xh8HECHKxw3CsCoPNoTADRyV0hFURRb88cfQE6O647iqChg+XJTRfIEXamsKIpSWFyto+wgKkqS2507Z5pInqAKQVEUpbC4k/YaEIXADBw4UOChvkQVgqIoSmHZsQOoWBGoUMG142vWlL3N/AiqEBRFUQrDH38AM2YAt9/u+jlRUbJXhaAoihJAPPssEBICjLosjubKVK8uKbJtFnqqCkFRFMVTvv8e+PprYPhwoFqemXjyZuFCiUoKstcQbC9pFEVR/IWsLOCpp8T8M3So6+f9+CPQpw/QogXw/PMmCecZbq1DUBRFUQwmTgR+/x2YOxcoWdK1c7ZtA7p1k6pq33wDlCplroxuojMERVEUd/n7b+B//wNuugm46y7XztmzB4iPB8qWBZYtk6gkm6EzBEVRFHcZOVKUwpgxBSezA4BTp4BOnWQh2sqVQI0aBZ9jAaoQFEXxHTk5krKBGejc2WppPGPnTmDcOGDAACAmxrVzkpMlG+rEiUB0tKniFQZVCIqimM+xY8AXXwCffipx+6VKARkZrt1d242hQ4GwMOD1110/x7EQ7d9/zZHJS6gPQVEUc2AGfv0VuO8+ibt//nkxlfTqBZw+DRw5YrWE7vPdd8DSpcDLLwPuFO+qUAEoVw7Yvds00byBKgRFUbxLRgYwYQLQrBnQurXE3D/8MLB9u4Rc9usnx/3xh6Viuk1mJvD005LAbvBg98+/5hogNdX7cnkRNRkpiuIdEhOB8eOBKVOkTGTjxmIi6tNHSks6qF1b9rt3i8LwFz76SHwB334LFC/u/vl16gAJCd6Xy4uoQlAUxXMyM4EFC4CPPwZ++kkGynvuAQYNAlq1yttHULOmtPvTDCE9HXj1VQkb7dLFs2vUqQPMmycL2oLtOfTaUypFUezNgQNiFvrsM/EF1KoFvPUW8MADBdvWS5SQNA/+pBBGjJDQ0ffe8/wadeqIMti/P3eWZDNUISiKXcjKAk6elC0nJzcjpl3IyZEY+o8/BhYvFqfxbbfJbKBTJ0nW5iq1a/uPQti6VRTfk08CDRp4fp06dWSfmqoKQVECjuxsGbwzMnIH8ry2gl53HHP27MXXX7pUBlqrOX4c+PJL8Q/s3i0zgOefBwYO9Fxp1a5tyxKSl8Es+YoqVABeeqlw13IoBBtHGqlCUIoOOTl5D86eDuhnzrjWLxFQpkzuVrq07KOiLm533v77X2D6dOsUAjOwYYMogZkzZYVtXBzw2muSqiE0tHDXr10bOHRIPkNX8wBZwbx54hsZPx4oX75w16paVcxlqhAUxYd88gnw1VeXD+anTrl+Dceg7bzVqJF3e16DvfNWqpT7C7DWrJG0yufOFX7wdYdTp+SzGz8e2LxZ3s+DD4pZ6LrrvNePw2Syd2/hzDBmcuaMKObrrpNVyYUlKEjetyoERfEha9cCP/8sd7T16l15oL7SYB4WZn2e+h49xEyzapXnUS3ukJQkSmDyZFlN26iR+Ar69pXPxNs4FMIff9hXIbz3niisVau8FxVUp46t1yKoQlACj+efB6ZNA268ERg92mppPKNDB+Cqq4A5c8xXCGPGyIKrkBCge3fgscfkszMzrYSzQrAjBw8Cb7wh5rH27b133Tp1RMEw2zJth65UVgKP6GhZDDV2LPDnn1ZL4xmhoUDXrhLjn5lpbl8hIbKfP19qA8fFmT9YRUSIKc2uCmH4cIn6+r//8+51a9eWtB3p6d69rpdQhaAEJi+/LAPpm29aLYnn9OgB/POPlGk0k/vvF4fp5Mnm9uMMkX1DT9etA6ZOBZ55xvvhoZGRsrdpHidVCEpgUreuDHSffCKLqPyRjh3Ffj93rrn9hIUBjzwiM4Q9e8ztyxlvKoQxY4D335fggcKQkyNhplWqyCzB20REyF5nCIriY0aMEFutO2mK7USJEmI2+vpr4Px5c/t6/HFxpI8da24/zjgUAnPhrnPuHPDss5KWukYNGcgPH/bsWtOnA+vXi+/JDGe6YxX30aPev7YXUIWgBC41a8qd7xdf2DrUL1+6dwf++kuyhJpJtWqSlnriRDFT+QJv2dNTUmSR4LBhwK23Am+/LWs8Hn4Y2LXL9etkZEhAwvXXS8puM9AZgqJYyAsvSMjgq69aLYlndOok4bBmm40AucPOyBCl4AscK3cLazbasUP2vXoBs2eLEnjoIYk0a9AAuPNOCUUuiNGjZWbxwQfmhR2XLy8pPlQhKIoFREaKOWTaNCl96G+ULAncfrvY97OyzO2raVOgXTsxG5ltogK8F3qamCgDeL168vyaa2QNxb59YjZcvVrCaOPigEWLxE9wKXv2AO+8A9x7r2RpNYugIKBSJf81GRFRCSLaQETbiGgHEY002isQ0QoiSjH25Z3OGU5EqUS0i4g6ObU3J6LfjdfGEtkwEFcJPJ57TkIcX3nFakk8o3t3KUH588/m9zV0qDjh580zvy9HHiRvKIQ6dcTn4kxEBDBypGQXHTsWSEsDunWTsOTPPxffg4P//lfu3H2xbiUiwq9nCOcAtGfmJgBiAMQTUUsAwwCsYua6AFYZz0FEDQH0AhANIB7Ax0TkSIM4HsBAAHWNLd57b0VRrkB4uESOzJ4tmSv9jc6dRaH5wmzUpYtUBHv33cI7ewvCW2mwd+wAGja88uthYcATT8gK4a++klnXgAGikEaPlopu8+aJD6J69cLJ4gr+rBBYyDCehhgbA+gGwBG4PBnAncbjbgBmMvM5Zt4DIBXADUQUCaAsM//KzAxgitM5imIuzzwjNW0Lm7HSCkqVkjTT8+eL89RMgoJk1XJCguRTMpvChp5mZopTOTq64GODg8XPsGkTsGKF5CgaPlx8DFdfLZFKviA83H9NRgBARMWIaCuAdAArmHk9gMrMfBgAjL3hPkc1AM6B32lGWzXj8aXtefU3kIgSiCjhqE0/OMXPKFdO/vCLF0tYob/Ro4csZvLFIN2vH1CxYuGKwbhKYZO9paSIbyW/GcKlEAG33CLptzdvBh59VBbl+Srrqj/PEACAmbOZOQZAdcjdfqN8Ds/LL8D5tOfV3wRmjmXm2PCCqi8piqsMGSIOvREjrJbEfTp3lgFrzhzz+ypVSrKbLlxofiK22rUlb9CltSBcJTFR9q7MEPKiaVNJ6nfzzZ6d7wnh4VJz2tmHYRPcijJi5n8A/Aix/R8xzEAw9g6VlwaghtNp1QEcMtqr59GuKL6hTBmxE69YITnu/YnSpUUpzJuXd5SMtxk8WHIcffCBuf04p8H2hMREueN3RBj5A461CDa0frgSZRROROWMxyUB3AIgCcAiAP2Nw/oDWGg8XgSgFxGFElEtiPN4g2FWOklELY3oon5O5yiKbxg0SEJRHauY/YkePSRZ3y+/mN9XlSqSIPCLL4C//zavn8KGnu7YIdewc5GdS7Hx4jRXZgiRAH4got8AbIT4EL4BMBpARyJKAdDReA5m3gFgNoBEAEsBDGZmhydsEICJEEfzbgBLvPheFKVgSpUCXnxRYtNXrLBaGve47TbJguqLaCNAnMunTwOffmpeH9dcI/stWzw7PzHRc3ORVTjM4DZUCMQ2v0uKjY3lhIQEq8VQAolz58TEEBEhZSL9if/8B9i4UWLrfVHEp2NHGXT37AGKFzenj7ZtZeaza5d7abfPn5eQ0mee8a+stikpEto7ZYp5KTIAENEmZo515xxdqRyI/PMP0Ls3sH271ZLYk9BQiUqxceWqK9K9uzhh163zTX/PPCO1j2fPNq+PAQNkkHR34V1qqigFf5shOExGixZZK0ceqEIIRB57TAqjT5tmtST2ZO1aYMkSGez8jdtvlzt1X5mNOnUS5fnee+b5XLp3l+pwn33m3nmOCCN3Qk7tgCOiylffoRuoQgg0ZsyQ1ZghIb6JWfc3mCXSqEoVWb3sb1x1lQzSc+f6JtqISHwJW7aYF5lVqpTkEJo71z0H9o4dIl/9+ubIZRbLl8vehqZwVQiBxL59Mjto3VoSum3c6Hl8d6Dy3XfiUH7pJbE/+yPdu0u+oY0bfdPfvfeKI/Tdd83r4+GHxbfjzqw2MRGoVUsUij+xZImYjZo2tVqSy1CFEChkZwP9+8t+6lRZaJOZacu7EMvIyZFUBXXqiN3aX+naVWaAvjI5lCwpNxrffONefQF3iIkBmjcXs5GrpqmCchjZkexsmSF06uSboAA3sZ9E3mLyZElne+aM1ZL4hnfekSn9hx9KXHbr1tKuZqNcZswAfv9dKqg5Csv7I+XKAR06yKplX0UJPvaYOOPHjDGvj4cflu/HlZlPVpYoJ39TCJs2AcePA/H2zOsZuArh3Xclpa0jvMsX9lar2LxZFlp17y6zBEBSNDRooArBwblz8hk1bQrcc4/V0hSOefOkglrx4r5TCBEREiI5ebKk4jaD3r3F/ONKgZ59+yTCyN/8B0uXit/j1lutliRPAlchhIbKjyUyUgbJ2Fhg1SqrpfI+p0/n2ng/+eTiOO64OFnVGsjK0FU+/VTSI4webcupukswA//3f7JiOSZGlL0v38tTT8mM26yFamXLAj17SlBERkb+xzpChh0L2/yFpUulRGelSlZLkid++s9wgdBQoGpVideeMUPq0t5yi6z2dJTcCwSeew5ISgK+/FIyVDoTFydrEhzheUWVkyfFTNSunSy08kfOn5esnM89JzPB77/PjWf3FdHRQMuW4qMyiwEDRBnMmpX/cSkpsq9b1zxZvM1ff0mmXZuai4BAVgglSkiETVCQTEWTkuTu6pdfgMaNpfj6n39aLWXh+O47YNw4CQvMa6CLi5N9UTcbvfeeJBIbPdq9lbB24d9/5UZmwgRxis+caU3unk2bxL7fpo15fbRqJX6BgtYkpKZKwr/Klc2TxdusWCGzdRsrBDCzrbfmzZuzR3TpwpzXuceOMT/5JHNwMHNYGPPIkcwZGZ71YSXp6cyVKzNfdx3zmTN5H5OTwxwZydynj29lsxNHjjCXLs18991WS+IZe/cyR0fL73XiROvkOHeOuXFj5qpVmf/+29y+3nuPGWD+7bcrH9OlC3NMjLlyeJv772cuX545K8sn3QFIYDfH28CfIVxKxYoSKbFzp6QTfvllmXZ+8YX51ai8BbNMrf/+G5g+/fJasg6IZJZQlGcIb7whdu9Ro6yWxH02bgRatJBawEuXAg89ZJ0sb70F/Pab1A4oV87cvu67Txzm+TmXU1P9y3/ALN/hrbdK7WabErgKITQ0/wIU11wjYXu//ALUrCl/tqZNgWXLfCejp0ycKHlQRo+WMoD5ERcnidD27/eNbHZi714ZwB54wL/y5QPA118DN90kpqG1ayXM1CoSE4HXXpPyk127mt9fpUqSxG/q1Lxv6rKyJF22P/kPtm0TE7WdzUUIZIVQooRrFYlat5Y/3Jw5wKlT8oV16iR3Q3YkJUWiPW65BXjyyYKPd/gRfJFD32689JL4kF55xWpJXIdZQqbvvluU/bp11sbaZ2cDDz4oKTPGjvVdvw8/LDPg+fMvf23/flEK/jRDWLpU9p06WStHAQSuQggNdT1tA5FEbiQmAu+/L1P1mBj5Ixw8aKqYbnH+vISYhoZKVJErIYeNG4vzraiZjX77TdIgDBkCVMuzdLf9yMqSBWDPPgvcdRfwww/WO03HjpXImLFjc/P4+4J27SQtRV5mI0eEkb8phJgYCYO3MYGtENytWRoaKnffu3cDQ4eKfb5uXbnTPHnSFDHd4rXXRFlNmOD6IBccLJEbRU0hvPii3NUOG2a1JK5x4gRwxx2yluS55yTdtNU5enbvls/xjjvEXORLgoLET/bDD5enKXc89xeT0YkTMkO3ubkICGSFcCWnsiuULy+pIJKSgG7dZCCuW1cW5GRleVdOV1m7Vhyj/fvLbMYd4uIkJcA//5gimu1Ys0by7jz/vHyXdufAAfmOVqwQZf/WW9YvnmMWs01IiPhhrAjXvf9+ccB+/vnF7SkpkpiwShXfy+QJq1bJuKEKwUJCQyW5W2GW9teqJasm16+XFBiPPiommG+/9W093hMngL59xfntiR03Lk7k/fVX78tmN5hFEVStKuYiu7Npk0QS7dsnWTAffthqiYTPPpO783fesc7kVrWqrL+YNEnMpQ4cEUb+sqZk6VKgTJnc/GI2JnAVgiMU012zUV7ccIMkjvv6a9H0t98uUR+bNxf+2q7w5JMyYEydKsv73aVFCzEdFQWz0eLFMpt6+WXrTS4FsXChlI8MCRGTgl1WUaeliR+jfXvrs8IOGAAcOSI3YQ5SUvzHf+AIN73lFr9IqBi4CiE0VPbeUAiA3I3ceaekvfjwQzHBNG8O9Otnbkjn3LniQH7hBeDGGz27RlgY0KxZ4CuE7Gz5nK69VgIC7MyZM5Jkj0i+l0aNrJZIYJaZcHa2zBKsvgvv3FlmCo6Vy1lZUt/ZX/wHSUkyPviBuQgIZIXgzRmCMyEhUnwmNVUclrNnywA0fLikGPAmBw8CAwdKMqyXXircteLipKC8tz8POzFtmijs11+XGZGdKVlSvtNTp4BBgyRJoR2YMUPuxkeNkjTqVhMcLMp96VLxtezfL+Yjf5khLFkie1UIFuOYIZhVMeyqq4A33wSSk+VOb/Ro+ZGOG3exvdNTcnLEqeaoIlXY6WZcnHwWvjJz+ZqzZ2WAjY113+luFS++KA7b776TFazulI80g/R0MU+2agU88YS1sjjz4IPyf5g0yf8ijJYulXUkV19ttSQuEbgKwawZwqVcfbXUW0hIkIVEjz8u0/8FCwrneB47Fli5UtJsXHtt4eV0mJsC1Ww0frzcPfpbArtHH5VZ5saN4k84dMg6WYYMkfDqiRPtlV6hVi3xr3z+eW7FNrvPELKz5bf4/fdAly5WS+M67iY/8vXmcXK7+fMlQdaGDZ6d7wk5OczffMPcoIH03aYN8/r17l/nt9+YQ0OZu3aVa3qLa6+VawYa//7LXLEi8y23WC2J56xcKUn4atZkTk72ff8LFshv9rXXfN+3K8yaJfJFRzOXKuXd/4W32bePuW1bkbdHD+Z//rFEDHiQ3M7yAb+gzWOFsH+/vL133vHs/MJw/jzzJ58wR0SIDL16Mf/xh2vnnjkjGUwrV5aMpt7kwQdl4MzO9u51rWbECPmcExKslqRwbNzIXKkSc3g486ZN5vd39Cjz118zP/WU/C6aNGHOzDS/X084e1Y+G0CyrtqVGTOYr7pKlPuXX1qquFQhXEp0NHOHDp6fX1hOnJDBqmRJ5uLFmZ99lvmvv/I/Z+hQ+Vq++8778nzxhVw7MdH717aKP/+UNOb33GO1JN5h1y7mq69mLlOGedUq71770CHmmTOZBw2S/4YYNZlLlGBu3555xw7v9udtHP8NO6Yy/+cf5nvvFflatWLevdtqiVQhXMazz8pAfPKk59fwBmlpzA88wEzEXKEC85gxkl/+UlaskK9k8GBz5EhOlutPmGDO9a1g8GDmYsWsMbOYRVqaDNjFizPPnev5dfbuZZ48mfmhh5jr1s1VAKVLM3fqxPzGG8xr1sjdtz+QmCjyDxtmtSQX8/PPYuorVkzqq5w/b7VEzKwK4XJWrpS3uHix59fwJlu3MnfsKDLVqcM8Z07ulPL4cSk+Ur8+86lT5vSfkyNmrH79zLm+r9m9WwrHPPKI1ZJ4n+PH5U4zKIj5008LPj4nR2YXn33G3LevzDIcCqB8efEdvfOOmKVsMmB5xIIFMtOxA5mZzC+8IN9RnTrMv/5qtUQXoQrhUs6eFXPCY495fg0zWLqUuVEjvjC9XLuWuXt35pAQ823Hd93FXKuWuX34ij59xBx38KDVkphDRgZz587yO3n99Yvt0dnZEnzw0UdiLqtSJVcBRETI7+nDD5m3bQs8n5EdSEpijo2Vz/vBB8U8bDNMUQgAagD4AcBOADsAPGm0VwCwAkCKsS/vdM5wAKkAdgHo5NTeHMDvxmtjAVBB/RdKITAz33GHDIB2i0rIypKSiJGRuX/k0aPN79dRnjAtzfy+zGTLFnkfw4dbLYm5ZGbm2qYfe0y+v27dxPTo+N1Ury7HfPop886d9vutBxI5ORIwUqqUfAfz5lkt0RUxSyFEAmhmPC4DIBlAQwBvAxhmtA8D8JbxuCGAbQBCAdQCsBtAMeO1DQBaASAASwB0Lqj/QiuEcePkbdrVxpyRwfzqq/Jn90Wt1Q0b5POYNcv8vsykc2cxhZhd39cOZGdLHXCHAqhTR3xSkyZJ9JoqAN+Qni6mN0BCnG1+U+UTkxGAhQA6Gnf/kZyrNHZx7uxguNPxywwlEAkgyam9N4BPC+qv0Aph9255mx98ULjrBAqZmXJ388QTVkviOT/+KN/p229bLYnvyMkRc+KBA1ZLUjT57jsJBS9eXGZpfmCG80QhuLVSmYiiADQFsB5AZWY+bCxuOwwgwjisGoADTqelGW3VjMeXtufVz0AiSiCihKNHj7oj4uXUri0rfR0l7Io6ISFAy5b+u2KZjfTW1avLqvCiApEkKKxe3WpJihZnzkgajy5dpGLcxo3A009bX6/CJFx+V0RUGsA8AE8x84n8Ds2jjfNpv7yReQIzxzJzbLg3yvbFxwM//ihfriJ5jbZtkzoL/sY330h9ildekQRximIWW7dKbqyPPpIcTxs3Sj2UAMYlhUBEIRBlMJ2ZHVWvjxBRpPF6JIB0oz0N4oh2UB3AIaO9eh7t5hMfL8pg9WqfdGd74uIkWdi6dVZL4j47d8q+Wzdr5VACl5wcKQzUogXw11/AsmWSU8yRHy2AKVAhEBEB+BzATmZ+z+mlRQD6G4/7Q3wLjvZeRBRKRLUA1AWwwTArnSSilsY1+zmdYy433yxfpiMVbVGnZUuZ8vqj2ahpU9lv22atHEpg8vffknn2v/8VM9Hvv8vzIoIrM4QbAdwHoD0RbTW2LgBGA+hIRCkQJ/NoAGDmHQBmA0gEsBTAYGbONq41CMBESNjpbkikkfmULAncdJP6ERyUKQPExPinQmjeXPYbN1orhxKYrF8vNZAffBCYPx+oVMlqiXxKgVVEmHkN8rb/A0CHK5wzCsCoPNoTAFhTGio+XpxBe/cCUVGWiGAr4uKkCtX5835R2u8CFSoAdepIunFF8Ta33ir1IBYvltlChQpWS+RTAtNVnhedO8teZwlCXJz4VbZssVoS94mNVYWgmENQkNTW+OsvKcdaxCg6CuHaa2VmoApB8OeCObGxwL59QGFDkhUlL5o0kWJBEyaICakIUXQUApGYjVatAjIzrZbGeqpWlTUa/qoQAGDTJmvlUAKXkSOByEipd52VZbU0PqPoKARAzEYZGcAvv1gtiT1o00YUAhei1KcVNGsmezUbKWZRpoyEmm7ZIiakIkLRUgjt2okDVc1GQlycmF1SUqyWxD3KlgXq1VOFoJhL9+7iZP7f/4DDh62WxicULYVQpowMgqoQhLg42fur2UhDTxUzIQLGjQPOnQOeecZqaXxC0VIIgPgRfvsNOHjQakmsp149oGJF/1EIWVnA8ePA7t2SV+bQIdkUxSyuuQYYNgz46itg5UqrpTEdYpvbj2NjYznBm6aB33+XfCSffy6LT4o6d94JJCYCycnm95WVBfz7L/DPP55tGRmXX3PDBuD6682XXSm6nD0LNGoEFCsmN5OhoVZL5BJEtImZY905p8CFaQFHo0YSYbN0qSoEQMxGCxcCR44AlSvnf2xWliTEcwzQf/9d+AHdmaAg4KqrgHLlcre6dS9+7rxVrZq7cllRzKJECTEdxccD//d/4lMIUIqeQnCEn86fLwNccNH7CC7C4UcYMQKoUiX/Af3kyfyvRXT5oJ3fgH7pVrp0wKYVVvycTp2AHj2AUaOAPn0kZDsAKXomIwCYO1e+3DVrchdoFVUyMyXH/tGjeQ/o7mw6oCuBzMGDQP36QNu2koadrpTRxx6oychVbrlF7IFLl6pCKF5c8jtlZemArij5Ua0a8OqrwNChwIIFwH/+Y7VEXqdo/vvLlZMU0JoOWyhVSmL7VRkoSv488YQEpQwZUrBPzA8puiNA586S+iA9veBjFUVRAPE5jh8PpKXJbCHAKLoKIT5e9suXWyuHoii+5cwZoEMHSYHy5pvAH3+4d37r1sBDDwHvvw9s326OjBZRdBVC06ZARISajRTFVZiBPXuAKVOAAQNk/ccrrxQcfWYnmIGHHwa+/16cwi+8IPU1rr9eymbu3+/add56S0KkBw3yv1xg+VB0FUJQkISSLVsGZGcXfLyiFDVycmQh58cfA717AzVqSLhl//7AvHnyHxo5UgbUsWMlxYPdefttYPp04LXXxGS8d6+sLQCkbGbNmlIgZ8yY/LMZVKwoSmHNGmDyZF9I7huY2dZb8+bN2TSmT2cGmDdsMK8PRfEXzp1jXruW+a23mG+/nbl8efl/AMxVqzL37Mn80UfM27YxZ2fLORs2MLdvL8dERTFPnZr7mt1YvJiZSN5HTs7lr6emMr/xBnNMTO77jotj/vBD5sOHLz8+O5u5dWvmSpWYjx83X343AZDAbo63lg/4BW2mKoSjR+UH8uqr5vWhKHbl5EnmFSuYR4xgvvlm5pIlcwfCa69lfugh5i+/ZN69O+8B1EFODvOyZcxNm8q5jRszf/tt/uf4mu3bmcuUERlPnSr4+KQkGReio+U9BQUxt2vH/MknzOnpucdt28ZcrBjzwIHmye4hniiEorkwzZkWLWRNwtq15vWhKHbg2DExcaxeLdvmzWIuDQoCYmKkPkabNrJ6vaA0JnmRkwPMni2pHXbvlgVco0eLCcZKjh8HbrgBOHVKMuTWqOHe+Tt2yPuaNQvYtUvGi/btgZ49ZS3CqFHiYF67VsLZbYInC9MsnwEUtJk6Q2Bmfukl0f42nPIpSqHYu1dMOAMHMjdokHv3HxrK3LYt84svMi9dyvzvv97t99w55nHjmCtXlv66dWPescO7fbhKZqaYtIoXF3NYYcjJYd66lXn4cObateW9BQczt2kjj2NimM+f947cXgBqMvKAtWvlY5g1y9x+FMVMcnJk0B0/nrlPH+YaNXIVQNmyzJ07M7/5JvOaNcxnz/pGppMnmV97TUw1QUHMDzzAvH+/b/p28Pjj8hlMmuTd6+bkMCckMP/3v8w1a+Z+1pMne7efQuCJQlCTUXa25Nbv1g2YNMm8fhTFm5w/L+UdHeafNWvENAJIkkKH+adNG+C668TMYRXHjgFvvCEZQ4mAxx8Hhg+XSB0zmTABeOQRSTXx7rvm9cMMrF8PfPst0KsXEB1tXl9u4InJSBUCIF/iTz9JsRWbJ6xSijCrV0v8/OrVwK+/AqdPS/s111ysAOrUsefveN8+4OWXZR1D2bLAc88BTz4JhIV5v6+ff5bFZx06SCK6IpjVWBWCp3z5JfDAA8DWrUCTJub2pSiesGGDBEAQyW/U2QEcGWm1dO6xfbssCFu8WGYzL78sK39DQrxz/b17ZaFZhQpy516unHeu62d4ohCK7sI0Zzp1kr2uWlbsSsOGkoTwwQfFVDR2rKRw9zdlAEiRqkWLZKZTp46s9o2OlkienJzCXTsjQ8y/589LH0VUGXiKKgRA/lQxMZIOW1HsSOnSwN13Sy2Ps2etlsY7xMWJUli0SNKw9+wp4aGe1i7OyQH69ZMZyKxZUjNccQtVCA7i44FffpESkYpiR/r1k5rUixdbLYn3IALuuAPYtk1Mt0ePAh07As884/61Ro4Evv5achI5Zv2KW6hCcBAfL0ViVq2yWhJFyZt27aRIy5QpVkvifYoVkxxJycniG3E3C/GcOZKO+v77gaeeMkPCIkGBCoGIviCidCLa7tRWgYhWEFGKsS/v9NpwIkolol1E1MmpvTkR/W68NpbIZmEQrVsDZcqo2UixL8WKAffeK76uQK3jERoqjuasLNfP2bJFlEmrVsAnn9gzwspPcGWG8CWA+EvahgFYxcx1AawynoOIGgLoBSDaOOdjInIEQI8HMBBAXWO79JrWEhIipTWXLg2odLZKgHHffbJ2ZuZMqyUxj+Bg1zMQHzkiTuSKFYH580WhKB5ToEJg5p8B/HVJczcAjpyvkwHc6dQ+k5nPMfMeAKkAbiCiSABlmflXYwXdFKdz7EN8vORD37nTteNTU8XRd8cd8lhRzKZRIynsEohmIwfFirk2Qzh3DrjrLln4tnChzCyUQuGpD6EyMx8GAGMfYbRXA3DA6bg0o62a8fjS9jwhooFElEBECUePHvVQRA9wVFEryGyUkSErLaOjxdb500/yR339df/ICa/4N/36SS7/HTuslsQcXJkhMEu46tq14oxu1swnogU63nYq52W843za84SZJzBzLDPHhoeHe024Arn6aon3vpJCYJbiGvXqSRbHXr3ECZaUBHTtCowYIeGrP/3kO5mVokfv3nIXPXWq1ZKYgyszhLFjJdXM//4H3HOPb+QqAniqEI4YZiAYe4eHKw2Ac27Z6gAOGe3V82i3H/HxMqCfOnVx++bNEv3Qt6+sW1i7ViolRUYCVavKoppvv5UY8ZtvlgVEx45Z8haUACciQn6n06cHZrW/gmYIy5dLfqI775RQU8VreKoQFgHobzzuD2ChU3svIgololoQ5/EGw6x0kohaGtFF/ZzOsRedOwOZmcCPP8rzo0clQVZsrMwGJk6UNAJ55Xjv0kWm8c8/L3dv9evLdFad1Iq36dcPSEvL/Z0GEsHBV54hJCfLArboaPmPBWnkvDdxJez0KwC/AqhHRGlE9BCA0QA6ElEKgI7GczDzDgCzASQCWApgMDM7VP0gABMhjubdAOyZJyIuTlIEfPMN8OGHwLXXAp9/LrHNycmScyW/H2GpUmJO2rxZzn3gAYkfT0ry2VtQigB33CFF3gPRuXwlk9E//4hpNjhYVjeXLu1z0QIed/Nl+3ozvR5CXtx2W25+81tu8by4R3Y286efMpcrxxwSIqUKz5zxrqxK0WXAAOawMOaMDKsl8S5DhzKXLn1xW1YWc3y8FKT58Udr5PIz4EE9BJ1v5cXAgUDz5hLXvHy5OJo9IShIrpWUJInIXntNctN7mqtFUZzp1098XV9/bbUk3iWvGcKwYRLs8dFHwE03WSNXEUAVQl507QokJEi9VG+seqxcWRyAjuX4HTuKc/rIkcJfWym63HgjUKtW4JmNLnUqT54s+YkGDxZ/nmIaqhB8SceOwO+/S3jq7NnidJ4wofApfxWxL69eXbTWgQQFycrllSuBgwetlsZ7OM8Q1q2TWXa7dlLIXjEVVQi+pkQJScK1bZsUOnnkEQln/f13qyXzXzZulM+ybVsJybzvPnE6Bkqa6Pzo2zd3fUygEBws7+nAAQktrV5dktd5q4COckVUIVhFgwbADz/I4ppdu2Sl5bBhuWURlYJhBsaPl8gwQD7Lu++W9SDduoly6NsXWLAgcJVD3boSAj1lSuCENzvqP3ftKj6SRYvMr7+sAFCFYC1Ekq43KUnuat96S+Krv/vOasnsz6lT8pk99pjUzd28WT7LL74Q38ySJbKCdckS8QWFhwN9+ogD9swZq6X3Lv36yfqXrVutlsQ7OOofb9sGzJhhm6L1RQFVCHagUiUZyH78UUxKt90mg9khey7mtpykJKmsNWOGRG59883Fd5AhIbKSd+JE4M8/gWXLJM3I8uWSDC0iQtI/zJ8fGMrhnnuk4ligOJcdGUvfeEPWWyi+w904VV9vlqxDsJKzZ5lfe405NJS5bFnmDz+UGGxFmDVLYtQrVWJescK9czMzmZcvZ374YTkfkDj+nj2Z58xhPnXKHJl9wV13MUdEMJ8/b7UkhefPP5mnTWPOybFaEr8GHqxDsHzAL2grcgrBQUqKLIoDmK+/nnnzZqslspZz55iHDJHPo1Ur5gMHCne98+eZV65kfuQR5vBwuW6pUsw9ejDPnu1/i70WLJD38O23Vkui2ARPFIKajOzKNdeIiWP6dGDfPsmlNHSopN4uahw4IIuRxo4FnnxSTGvVqxd4Wr4EB4vv4ZNPxDS3apXY4n/6SUwwERGymHD2bP/4zDt3FrNZoJiNFEtQhWBniMQRmpQEPPywxGE3aCBRM0WFFSskAmv7dhmcx4wRe7k3CQ4G2reXiKVDh4Dvv5eSjKtXSyK1iAiJXpo5077KoXhx8YssWCBrMhTFA1Qh+APly8ud7C+/AOXKSdTMnXfKnXOgkpMj6zU6dZKV3gkJcsduNsWKySKojz+WxV4//iipzNeulQE3PFwc0199BZw8ab487nDffbIwb+5cqyVR/BRim8cux8bGckJCgtVi2Ifz52Wm8MorslL11VeBIUNyQ/UCgWPHZP3AsmVSVP7TT4GwMGtlys4WhTxnDjBvHnD4sETDdO4siur224GyZa2VkVlmkJUra5EmBUS0iZlj3TlHZwj+RkgI8NxzQGKi2NWfeQa4/nqp0RAIbNggiQV/+EFMOFOnWq8MAJk5tG0rKdHT0sSc9MgjIu+994pZqVs3YNo04MQJa2QkEj/Izz8De/ZYI4Pi16hC8FeioiT+fs4cID0daNkSePxx4N9/rZbMM5jFTBMXJwPbmjXAo496J7mgtwkKEjk/+EDMdg5ZN20Ss014uKyynTrV999H376ynzbNt/0qAYGajAKBEyektuxHHwFVqshA1b27PQfTvMjIkLvtGTPEBDN1qn+mKsjJkWRsc+aIHT8tTZy9t94qZqWuXcUHZDbt2on/Y9cu//kNKF5HTUZFlbJlJSRz/XpRCPfcI6ud/cFssHMn0KKFOGnzWnXsTwQFAa1bi49n3z7g119l1vbbbxK1FBEh38uXXwJ//22eHP36ASkp8ntQFDdQhRBIOHwJ778vNu7oaCnnef681ZLlzaxZIvPRo7Lm4n//C5wauUFBYsZ7911g716ZOQwZIjmHHnhAHL9dukhCvr/+8m7fd98NlCypaxIUtwmQf59ygeBgqf+cmCghm8OHA02bSoSMXcjMlMGxVy9JW715M3DLLVZLZR5EMgt65x2ZtW3YIN/Rzp0S0lq5suRe+vxz4PjxwvdXtqyEJs+cWbTqQyiFRhVCoFKjhmT2XLhQfAxxcVJoxNt3o+5y4EButM5TT3ln1bE/QSSzorffBv74Q2o5DB0KJCcDAwaIya9TJ0nMd+yY5/3cd5+YpTRzruIG6lQuCmRkyLqFMWOAChWA996TUElfOxyXL5eV1+fOSXZXXyw08xeYZaY0Z45sf/whoa7t28vndOedEr3kKllZclPQsmXg1VxWXEKdykrelC4t5oqEBKnBe999Us4zJcU3/efkACNHilmkShXfrTr2J4hk/cXo0UBqqiiH554TE9PAgUBkpJjVPv1UfC4FERwsSv/bbws301CKFKoQihIxMZKCYdw4MVVcd52sdDbTznzsmDhPX3lFYuTXrwfq1TOvv0CASPw+b7whpqQtW4Dnnwf275f1DlWq5CbmS0+/8nX69ZOAglmzfCe74teoyaiocvgw8PTTMljUqyeDy803e7eP9etlJnDkiITFDhyocfGFgVlqbzvMSrt2STTTTTfJ5/yf/4iycKZJE4k4WrfOGpkVy1CTkeI6kZEShbJkiUT9tGsnJSi9YV5glkVybdrIgPXLL7LwTJVB4SACGjeW9Ro7d8r6hhdfFOX+2GNA1aqi1MeNk0pxgMwS1q8X5aEoBRDwCqF06dKmXv+hhx5CkyZN0LhxY3Tv3h0ZRnrkhQsXonHjxoiJiUFsbCzWrFlz4Zz3338f0dHRaNSoEXr37o2zRgH4ESNGXDjn1ltvxSGjhObx48fRrl07lC5dGo8//vgVZenZsydiYmIQExODqKgoxMTEAAA2bNhwob1Jkyb42tnJGB8vqaWHD5faC/XqSWy8pzPHjAxxHD/xhKzQ3bxZajko3oUo1+SXmCgzhxEjxIT0+OOiHG66KXcB3NSp1sqr+AfuVtTx9VbYimlhYWGFOr8g/v333wuPn376aX7zzTeZmfnkyZOcY5QA3LZtG9erV4+ZmdPS0jgqKopPnz7NzMw9evTgSZMmXXatDz74gB955BFmZs7IyODVq1fz+PHjefDgwS7JNXToUB45ciQzM586dYrPG6UVDx06xOHh4ReeX8T27cw33iiVt9q2ZU5MdPVjEBITmRs0YA4KYh41ijk7273zFe+wYwfzK68wR0fLdwkw16pltVSKj4FWTHON3bt3Iz4+Hs2bN0ebNm2QlJQEALj//vsxZMgQtG7dGrVr18ZcF/LKlzVSHjMzzpw5AzLMIqVLl77w+NSpUxceA0BWVhbOnDmDrKwsnD59GlWrVr3oWpeeExYWhri4OJQoUcKl98fMmD17Nnr37g0AKFWqFIKN9Nhnz569SJaLiI6WTJmffSZ3nE2ayOphVwrRz5wp8fXHjkl46QsvBM6qY3+jYUPg5Zdl5peYKBFe99xjtVSKP+CuBvH1ZsYMoX379pycnMzMzOvWreN27doxM3P//v25e/funJ2dzTt27OA6depcOKdJkyZX7OP+++/niIgIvvnmm/mUU6H2+fPnc7169bh8+fK8du3aC+1jxozhsLAwrlSpEvfp0+eia73wwgtcvXp1jo6O5vT09ItemzRpkkszhJ9++okv/dzWrVvHDRs25LCwMJ4/f36B1+AjR5jvu0/uLuvUkeL0eXHuHPPjj8txrVszp6UVfG1FUUwHHswQfD7AA4gHsAtAKoBhBR3vbYVw8uRJLlGiBDdp0uTCVr9+fWYWhTBt2rQLx5YuXdrlfrKysnjQoEH8xRdfXPbaTz/9xB06dGBm5r/++ovbtWvH6enpnJmZyd26deOpU6deds4bb7zBL7300kVtriqERx99lN955508X0tMTOTrr7+ez5w548rbYl61irluXfmp9O7NfPhw7mv79jG3aCGvPf00c2ama9dUFMV0PFEIPp3TE1ExAOMAdAbQEEBvImroSxlycnJQrlw5bN269cK2c+fOC6+HhoZeeCyfqWsUK1YMPXv2xLx58y57rW3btti9ezeOHTuGlStXolatWggPD0dISAjuuusurF279rJz+vTpk+e1CiIrKwvz589Hz54983y9QYMGCAsLw/bt2127YPv2Es3y8stSKax+fVkctWSJ1DpOTJQQyPfek+I9iqL4Lb428t4AIJWZ/2DmTAAzAXTzpQBly5ZFrVq1MGfOHAAy6G/bts2jazEzUlNTLzxevHgx6tevDwBITU29oFA2b96MzMxMVKxYEVdffTXWrVuH06dPg5mxatUqNGjQAACQ4rRyeNGiRReu5Q4rV65E/fr1Ud0pP9CePXuQlZUFANi3bx927dqFqKgo1y9aooQsLPvtN1ECjz4qi80iI2XVcffubsupKIr98HUh3moAnCvDpwFocelBRDQQwEAAuPrqqwvV4enTpy8aHIcOHYrp06dj0KBBeP3113H+/Hn06tULTZo0yfc6MTEx2Lp160VtzIz+/fvjxIkTYGY0adIE48ePBwDMmzcPU6ZMQUhICEqWLIlZs2aBiNCiRQt0794dzZo1Q3BwMJo2bYqBAwcCAIYNG4Zdu3YhKCgINWvWxCeffHKhr6ioKJw4cQKZmZlYsGABli9fjoYNG2LAgAF49NFHEWuEds6cOfOCM9nBmjVrMHr0aISEhCAoKAgff/wxKlWq5P6HWa8esGqVhKfu2CEOZzuUt1QUxSv4dKUyEfUA0ImZBxjP7wNwAzM/caVzdKWyoiiK+/jDSuU0ADWcnlcHcMjHMiiKoih54GuFsBFAXSKqRUTFAfQCsMjHMiiKoih54FMfAjNnEdHjAJYBKAbgC2be4UsZFEVRlLzxtVMZzPwdAC3jpCiKYjM0t4CiKIoCQBWCoiiKYqAKQVEURQGgCkFRFEUxsH0JTSI6CmCfh6dXAmDXCuMqm2fYWTbA3vKpbJ5hZ9mAK8tXk5nD3bmQ7RVCYSCiBHdX6vkKlc0z7CwbYG/5VDbPsLNsgHflU5ORoiiKAkAVgqIoimIQ6AphgtUC5IPK5hl2lg2wt3wqm2fYWTbAi/IFtA9BURRFcZ1AnyEoiqIoLqIKQVEURQEQoAqBiOKJaBcRpRLRMB/1+QURpRPRdqe2CkS0gohSjH15p9eGG/LtIqJOTu3Nieh347WxRERekK0GEf1ARDuJaAcRPWkX+YioBBFtIKJthmwj7SKb03WLEdEWIvrGhrLtNa67lYgS7CQfEZUjorlElGT89lrZQTYiqmd8Xo7tBBE9ZQfZnK77tPF/2E5EXxn/E/PlY+aA2iBptXcDqA2gOIBtABr6oN+2AJoB2O7U9jaAYcbjYQDeMh43NOQKBVDLkLeY8doGAK0AEIAlADp7QbZIAM2Mx2UAJBsyWC6fcZ3SxuMQAOsBtLSDbE4yDgUwA8A3dvpejevuBVDpkjZbyAdgMoABxuPiAMrZRTYnGYsB+BNATbvIBik1vAdASeP5bAD3+0I+r3yodtqMN7/M6flwAMN91HcULlYIuwBEGo8jAezKSyZIfYhWxjFJTu29AXxqgpwLAXS0m3wASgHYDKmzbQvZIFX9VgFoj1yFYAvZjGvtxeUKwXL5AJSFDGpkN9kukedWAL/YSTbk1p6vAClR8I0hp+nyBaLJyPFhOkgz2qygMjMfBgBjH2G0X0nGasbjS9u9BhFFAWgKuRO3hXyGSWYrgHQAK5jZNrIBGAPgOQA5Tm12kQ0AGMByItpERANtJF9tAEcBTDLMbROJKMwmsjnTC8BXxmNbyMbMBwG8A2A/gMMA/mXm5b6QLxAVQl42MrvF1l5JRlNlJ6LSAOYBeIqZT+R36BXkMEU+Zs5m5hjI3fgNRNTIDrIR0e0A0pl5k6unXEEGM7/XG5m5GYDOAAYTUdt8jvWlfMEQE+p4Zm4K4BTEzGEH2aRDKePbFcCcgg69ggymyGb4BrpBzD9VAYQRUV9fyBeICiENQA2n59UBHLJIliNEFAkAxj7daL+SjGnG40vbCw0RhUCUwXRmnm83+QCAmf8B8COAeJvIdiOArkS0F8BMAO2JaJpNZAMAMPMhY58O4GsAN9hEvjQAacZsDwDmQhSEHWRz0BnAZmY+Yjy3i2y3ANjDzEeZ+TyA+QBa+0K+QFQIGwHUJaJaxh1ALwCLLJJlEYD+xuP+ENu9o70XEYUSUS0AdQFsMKaBJ4mopREN0M/pHI8xrvU5gJ3M/J6d5COicCIqZzwuCfkzJNlBNmYezszVmTkK8jv6npn72kE2ACCiMCIq43gMsTNvt4N8zPwngANEVM9o6gAg0Q6yOdEbueYihwx2kG0/gJZEVMq4bgcAO30in7ecM3baAHSBRNLsBvCij/r8CmLvOw/RzA8BqAhxSKYY+wpOx79oyLcLTp5/ALGQP/VuAB/hEqech7LFQaaKvwHYamxd7CAfgMYAthiybQfwktFuuWyXyHkzcp3KtpANYqffZmw7HL91G8kXAyDB+G4XAChvI9lKATgO4CqnNlvIZlx3JOTGaDuAqZAIItPl09QViqIoCoDANBkpiqIoHqAKQVEURQGgCkFRFEUxUIWgKIqiAFCFoCiKohioQlAURVEAqEJQFEVRDP4fDWRkDQlSxDEAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# draw plot\n",
    "# path = [1, 7, 0, ...]\n",
    "# pos = [[0, 0], [2, 3] ...]\n",
    "# dist = int\n",
    "# color='royalblue'\n",
    "draw_path(tsp_obj.final_path, coords, tsp_obj.final_dist, color='r', dot=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {},
   "outputs": [],
   "source": [
    "make_gif(tsp_obj=tsp_obj, file_name=file_name, coords = coords, dot=True, interval=0.1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.12 ('py38_64')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "1f4b4a3d02725ab5ebe0e8d7d442878c2537616f6c1170cc112a3aa33d99e98b"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}