traveling-salesman-problem.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "traveling-salesman-problem.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xOWvi0SVg-2R"
      },
      "source": [
        "Traveling Salesman Problem (TSP)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xnpqYxrW9GY1"
      },
      "source": [
        "* Set use_input_txt = 1 if you want to use input from file, or set use_input_txt = 0 to auto generate input data.\n",
        "* Upload input.txt to current directory at the \"Files\" bar on the left \n",
        "* Click \"Runtime\" and \"Run all\" and see the output file BF.txt and BB.txt in current directory\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cYoojZe9hZAl"
      },
      "source": [
        "use_input_txt = 0#@param\n",
        "min_input_size = 5#@param\n",
        "max_input_size = 15#@param\n",
        "max_brute_force_input_size = 10#@param\n",
        "sample_size = 3#@param"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9G3k1sW3hIBt"
      },
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "import timeit\n",
        "from itertools import permutations, count\n",
        "from queue import PriorityQueue"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xHa4XLARWfny"
      },
      "source": [
        "def brute_force(cost_matrix):\n",
        "  n = cost_matrix.shape[0]\n",
        "  min_cost = np.inf\n",
        "  min_cost_cycle = []\n",
        "  for cycle in permutations(range(1, n)):\n",
        "    # print(cycle)\n",
        "    cost = cost_matrix[0, cycle[0]] + cost_matrix[cycle[-1], 0]\n",
        "    for i in range(n-2):\n",
        "      cost += cost_matrix[cycle[i], cycle[i + 1]]\n",
        "      # print(cost)\n",
        "    if cost < min_cost:\n",
        "      min_cost = cost\n",
        "      min_cost_cycle = cycle\n",
        "  return min_cost_cycle, min_cost"
      ],
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "skZhQRgQghQs"
      },
      "source": [
        "def branch_and_bound(cost_matrix):\n",
        "  # print(cost_matrix)\n",
        "  n = cost_matrix.shape[0]\n",
        "  pq = PriorityQueue()\n",
        "  tiebreaker = count()\n",
        "\n",
        "  # (lower_bound, index, cost, with arc, cost_matrix)\n",
        "  pq.put((0, next(tiebreaker), 0, set(), cost_matrix))\n",
        "\n",
        "  current_best_cycle = None\n",
        "  upper_bound = np.inf\n",
        "\n",
        "  while not pq.empty():\n",
        "    # print(\"//////////////////////////////////////////\")\n",
        "    # print(pq.queue[0])\n",
        "    # get smallest lower bound in queue\n",
        "    lower_bound, index, cost, with_arc, new_cost_matrix = pq.get()\n",
        "    if lower_bound >= upper_bound:\n",
        "      # lower bound is higher then the current best solution, discard this child.\n",
        "      continue\n",
        "    # print(new_cost_matrix)\n",
        "\n",
        "    def get_reduce_matrix(new_cost_matrix):\n",
        "      # calculate cost and reduce matrix\n",
        "      row_min = np.nan_to_num(new_cost_matrix.min(axis=1), posinf=0)\n",
        "      # print(row_min)\n",
        "      reduce_row = new_cost_matrix - row_min[:, np.newaxis]\n",
        "      # print(reduce_row)\n",
        "      column_min = np.nan_to_num(reduce_row.min(axis=0), posinf=0)\n",
        "      # print(column_min)\n",
        "      reduce_column = reduce_row - column_min\n",
        "      # print(reduce_column)\n",
        "      added_cost = row_min.sum() + column_min.sum()\n",
        "      # print(cost)\n",
        "      return reduce_column, added_cost\n",
        "    reduce_column, added_cost = get_reduce_matrix(new_cost_matrix)\n",
        "    cost += added_cost\n",
        "\n",
        "    # find best arc to branch\n",
        "    branch_arc = None\n",
        "    highest_cost_increment_without_arc = -1\n",
        "    for arc in np.argwhere(reduce_column == 0):\n",
        "      # set this arc to inf temporary\n",
        "      reduce_column[arc[0], arc[1]] = np.inf\n",
        "      increment = reduce_column[arc[0], :].min() + reduce_column[:, arc[1]].min()\n",
        "      # print(increment)\n",
        "      if increment > highest_cost_increment_without_arc:\n",
        "        highest_cost_increment_without_arc = increment\n",
        "        branch_arc = tuple(arc)\n",
        "      # set this arc back to 0\n",
        "      reduce_column[arc[0], arc[1]] = 0\n",
        "    # print(highest_cost_increment_without_arc)\n",
        "    cost_without_arc = cost + highest_cost_increment_without_arc\n",
        "    # print(branch_arc)\n",
        "    # print(cost_without_arc)\n",
        "\n",
        "    with_arc_update = with_arc.copy()\n",
        "    with_arc_update.add(branch_arc)\n",
        "    \n",
        "    if len(with_arc_update) >= n:\n",
        "      # found one feasible solution\n",
        "      if cost < upper_bound:\n",
        "        # current best solution\n",
        "        upper_bound = cost\n",
        "        current_best_cycle = with_arc_update\n",
        "    else:\n",
        "      # not enough arc to form a solution\n",
        "      if cost < upper_bound:\n",
        "        # add with arc to queue\n",
        "        with_arc_cost_matrix = reduce_column.copy()\n",
        "        with_arc_cost_matrix[branch_arc[0], :] = np.inf\n",
        "        with_arc_cost_matrix[:, branch_arc[1]] = np.inf\n",
        "        with_arc_cost_matrix[branch_arc[1], branch_arc[0]] = np.inf\n",
        "\n",
        "        # find infeasible arc and set it to inf\n",
        "        arc_dict = {}\n",
        "        for from_city, to_city in with_arc_update:\n",
        "          arc_dict[from_city] = to_city\n",
        "        # print(arc_dict)\n",
        "        def find_last_city_in_route(from_city):\n",
        "          to_city = arc_dict.get(from_city)\n",
        "          if to_city is None:\n",
        "            return from_city\n",
        "          return find_last_city_in_route(to_city)\n",
        "        if len(with_arc_update) < n-1:\n",
        "          for from_city in arc_dict:\n",
        "            last_city = find_last_city_in_route(from_city)\n",
        "            # print(last_city, from_city)\n",
        "            with_arc_cost_matrix[last_city, from_city] = np.inf\n",
        "        \n",
        "        reduce_matrix, added_cost = get_reduce_matrix(with_arc_cost_matrix)\n",
        "        # print(added_cost)\n",
        "        cost_with_arc = cost + added_cost\n",
        "        if cost_with_arc < upper_bound:\n",
        "          pq.put((cost_with_arc, next(tiebreaker), cost_with_arc, with_arc_update, reduce_matrix))\n",
        "      if cost_without_arc < upper_bound:\n",
        "        # add without arc to queue\n",
        "        without_arc_cost_matrix = reduce_column.copy()\n",
        "        without_arc_cost_matrix[branch_arc[0], branch_arc[1]] = np.inf\n",
        "        pq.put((cost_without_arc, next(tiebreaker), cost, with_arc, without_arc_cost_matrix))\n",
        "    # print(pq.queue)\n",
        "    # print(upper_bound)\n",
        "  \n",
        "  # get start from 0 cycle\n",
        "  cycle = []\n",
        "  arc_dict = {}\n",
        "  for from_city, to_city in current_best_cycle:\n",
        "    arc_dict[from_city] = to_city\n",
        "  # print(arc_dict)\n",
        "  def get_cycle(from_city):\n",
        "    to_city = arc_dict[from_city]\n",
        "    # if len(cycle) >= n:\n",
        "    #   return\n",
        "    if to_city != 0:\n",
        "      cycle.append(to_city)\n",
        "      get_cycle(to_city)\n",
        "  get_cycle(0)\n",
        "  # print(cycle)\n",
        "\n",
        "  return cycle, upper_bound\n",
        "# branch_and_bound(cost_matrix)"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "d5SntVTpbcQm",
        "outputId": "c6c06f06-9003-4aa7-8c09-d1e49d943f23"
      },
      "source": [
        "def print_cycle(cycle, cost, time, file_name):\n",
        "  if cost == np.inf:\n",
        "    print(\"\\tno cycle found\")\n",
        "  else:\n",
        "    solution = '0 - '\n",
        "    for vertice in cycle:\n",
        "      solution += '{} - '.format(vertice)\n",
        "    solution += '0'\n",
        "    print(f\"Solution : {solution}\")\n",
        "    print(f\"Cost \\t: {cost}\")\n",
        "    print(f\"Time \\t: {time} s\")\n",
        "    with open(file_name, \"w\") as text_file:\n",
        "      print(f\"Solution : {solution}\", file=text_file)\n",
        "      print(f\"Cost \\t: {cost}\", file=text_file)\n",
        "      print(f\"Time \\t: {time} s\", file=text_file)\n",
        "    \n",
        "\n",
        "def gen_cost_matrix(n):\n",
        "  cost_matrix = np.random.randint(1, 100, size=(n, n)).astype(np.float32)\n",
        "  # some test case\n",
        "  # cost_matrix[0,:] = np.inf\n",
        "  # cost_matrix[0,1] = -1\n",
        "  # cost_matrix = np.ones((n, n))\n",
        "  np.fill_diagonal(cost_matrix, np.inf)\n",
        "  cost_matrix[cost_matrix < 0] = np.inf\n",
        "  return cost_matrix\n",
        "\n",
        "brute_force_time = []\n",
        "branch_and_bound_time = []\n",
        "np.set_printoptions(formatter={'float': '{: 0.0f}'.format})\n",
        "\n",
        "if use_input_txt:\n",
        "  brute_force_time = [0]\n",
        "  input = np.loadtxt('input.txt', skiprows=1)\n",
        "  # print(input)\n",
        "  min_input_size = input.shape[0]\n",
        "  max_input_size = min_input_size\n",
        "\n",
        "for n in range(min_input_size, max_input_size + 1):\n",
        "  print(\"_____________________________________\")\n",
        "  print(\"n:\", n)\n",
        "  if use_input_txt:\n",
        "    cost_matrix = input\n",
        "    np.fill_diagonal(cost_matrix, np.inf)\n",
        "    cost_matrix[cost_matrix < 0] = np.inf\n",
        "  else:\n",
        "    cost_matrix = gen_cost_matrix(n)\n",
        "  print(\"cost_matrix:\\n\", cost_matrix)\n",
        "  print(\"\")\n",
        "  print(\"brute force\")\n",
        "  if n <= max_brute_force_input_size:\n",
        "    start = timeit.default_timer()\n",
        "    cycle, brute_force_cost = brute_force(cost_matrix)\n",
        "    stop = timeit.default_timer()\n",
        "    if use_input_txt:\n",
        "      time = stop - start\n",
        "    else:\n",
        "      run_time_samples = timeit.repeat(stmt='brute_force(matrix)', setup='from __main__ import gen_cost_matrix, brute_force, n; matrix = gen_cost_matrix(n)', repeat=sample_size, number=1)\n",
        "      time = np.average(run_time_samples)\n",
        "      print(\"run_time_samples: \", run_time_samples)\n",
        "    print_cycle(cycle, int(brute_force_cost), time, \"BF.txt\")\n",
        "    \n",
        "    brute_force_time.append(time)\n",
        "  else:\n",
        "    print(f\"n > {max_brute_force_input_size}, too many!\")\n",
        "    time = brute_force_time[-1] * n\n",
        "    print(f\"Time (estimated): {time} s\")\n",
        "    brute_force_time.append(time)\n",
        "  print(\"\")\n",
        "  print(\"branch and bound\")\n",
        "  start = timeit.default_timer()\n",
        "  cycle, branch_and_bound_cost = branch_and_bound(cost_matrix)\n",
        "  stop = timeit.default_timer()\n",
        "  if use_input_txt:\n",
        "    time = stop - start\n",
        "  else:\n",
        "    run_time_samples = timeit.repeat(stmt='branch_and_bound(matrix)', setup='from __main__ import gen_cost_matrix, branch_and_bound, n; matrix = gen_cost_matrix(n)', repeat=sample_size, number=1)\n",
        "    time = np.average(run_time_samples)\n",
        "    print(\"run_time_samples: \", run_time_samples)\n",
        "  print_cycle(cycle, int(branch_and_bound_cost), time, \"BB.txt\")\n",
        "  \n",
        "  branch_and_bound_time.append(time)\n",
        "  if n <= max_brute_force_input_size:\n",
        "    assert brute_force_cost == branch_and_bound_cost, \"Cost is different!\""
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "_____________________________________\n",
            "n: 5\n",
            "cost_matrix:\n",
            " [[ inf  28  42  5  68]\n",
            " [ 81  inf  49  1  46]\n",
            " [ 54  47  inf  28  95]\n",
            " [ 69  1  4  inf  63]\n",
            " [ 57  19  73  20  inf]]\n",
            "\n",
            "brute force\n",
            "run_time_samples:  [0.00011044800021409173, 0.0001144510001722665, 0.00011534499981280533]\n",
            "Solution : 0 - 4 - 1 - 3 - 2 - 0\n",
            "Cost \t: 146\n",
            "Time \t: 0.00011341466673305452 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.0013633879998451448, 0.001921960999879957, 0.001292846000069403]\n",
            "Solution : 0 - 4 - 1 - 3 - 2 - 0\n",
            "Cost \t: 146\n",
            "Time \t: 0.0015260649999315017 s\n",
            "_____________________________________\n",
            "n: 6\n",
            "cost_matrix:\n",
            " [[ inf  25  63  58  16  12]\n",
            " [ 59  inf  18  6  82  99]\n",
            " [ 38  89  inf  60  47  53]\n",
            " [ 30  36  7  inf  60  11]\n",
            " [ 22  87  81  26  inf  76]\n",
            " [ 42  74  55  16  51  inf]]\n",
            "\n",
            "brute force\n",
            "run_time_samples:  [0.00033424299999751383, 0.0003190049997101596, 0.0003233899997212575]\n",
            "Solution : 0 - 5 - 3 - 1 - 2 - 4 - 0\n",
            "Cost \t: 151\n",
            "Time \t: 0.00032554599980964366 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.0014950629997656506, 0.0014451789998020104, 0.0022197680000317632]\n",
            "Solution : 0 - 5 - 3 - 1 - 2 - 4 - 0\n",
            "Cost \t: 151\n",
            "Time \t: 0.0017200033331998081 s\n",
            "_____________________________________\n",
            "n: 7\n",
            "cost_matrix:\n",
            " [[ inf  38  79  20  20  61  72]\n",
            " [ 8  inf  48  2  91  80  24]\n",
            " [ 49  20  inf  14  43  36  70]\n",
            " [ 22  20  60  inf  37  77  16]\n",
            " [ 18  34  62  33  inf  59  64]\n",
            " [ 47  7  57  92  19  inf  79]\n",
            " [ 65  48  46  1  75  39  inf]]\n",
            "\n",
            "brute force\n",
            "run_time_samples:  [0.0022445029999289545, 0.0021347270003388985, 0.0021318469998732326]\n",
            "Solution : 0 - 4 - 2 - 3 - 6 - 5 - 1 - 0\n",
            "Cost \t: 166\n",
            "Time \t: 0.0021703590000470285 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.00236223499996413, 0.006239815999833809, 0.002249473000119906]\n",
            "Solution : 0 - 4 - 3 - 6 - 2 - 5 - 1 - 0\n",
            "Cost \t: 166\n",
            "Time \t: 0.0036171746666392814 s\n",
            "_____________________________________\n",
            "n: 8\n",
            "cost_matrix:\n",
            " [[ inf  37  3  70  73  77  16  89]\n",
            " [ 67  inf  12  13  60  25  36  26]\n",
            " [ 40  79  inf  59  34  65  60  47]\n",
            " [ 63  85  51  inf  25  24  67  71]\n",
            " [ 12  75  73  91  inf  79  42  28]\n",
            " [ 91  93  7  76  24  inf  64  87]\n",
            " [ 77  58  36  56  44  30  inf  80]\n",
            " [ 85  40  78  49  76  21  95  inf]]\n",
            "\n",
            "brute force\n",
            "run_time_samples:  [0.017877960999612696, 0.018586128000151803, 0.018193310999777168]\n",
            "Solution : 0 - 6 - 5 - 2 - 7 - 1 - 3 - 4 - 0\n",
            "Cost \t: 190\n",
            "Time \t: 0.018219133333180555 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.0024988430000121298, 0.00203899400003138, 0.002899789999901259]\n",
            "Solution : 0 - 6 - 5 - 2 - 7 - 1 - 3 - 4 - 0\n",
            "Cost \t: 190\n",
            "Time \t: 0.0024792089999815894 s\n",
            "_____________________________________\n",
            "n: 9\n",
            "cost_matrix:\n",
            " [[ inf  88  84  32  25  55  64  29  2]\n",
            " [ 7  inf  33  24  70  34  61  14  63]\n",
            " [ 33  11  inf  38  39  45  94  28  68]\n",
            " [ 15  41  64  inf  52  93  88  4  58]\n",
            " [ 77  32  43  73  inf  4  95  48  92]\n",
            " [ 65  2  66  34  99  inf  65  87  24]\n",
            " [ 4  71  87  65  88  81  inf  15  30]\n",
            " [ 97  44  25  32  27  61  81  inf  55]\n",
            " [ 89  51  76  61  35  57  86  70  inf]]\n",
            "\n",
            "brute force\n",
            "run_time_samples:  [0.16083243999992192, 0.16668010300008973, 0.16230418400027702]\n",
            "Solution : 0 - 8 - 4 - 5 - 3 - 7 - 2 - 1 - 6 - 0\n",
            "Cost \t: 180\n",
            "Time \t: 0.16327224233342955 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.003679556999941269, 0.003466038999704324, 0.004613122000137082]\n",
            "Solution : 0 - 8 - 4 - 5 - 3 - 7 - 2 - 1 - 6 - 0\n",
            "Cost \t: 180\n",
            "Time \t: 0.003919572666594225 s\n",
            "_____________________________________\n",
            "n: 10\n",
            "cost_matrix:\n",
            " [[ inf  23  18  81  77  70  5  84  58  33]\n",
            " [ 82  inf  23  70  17  12  84  96  72  79]\n",
            " [ 25  8  inf  61  1  67  19  38  98  93]\n",
            " [ 62  63  34  inf  14  33  99  88  66  35]\n",
            " [ 77  72  97  19  inf  5  89  68  12  85]\n",
            " [ 20  43  12  73  1  inf  82  21  65  81]\n",
            " [ 65  77  62  64  81  11  inf  20  61  74]\n",
            " [ 17  2  49  73  63  4  75  inf  28  38]\n",
            " [ 71  29  76  98  16  66  55  39  inf  91]\n",
            " [ 93  69  46  10  52  29  3  38  78  inf]]\n",
            "\n",
            "brute force\n",
            "run_time_samples:  [1.6014453620000495, 1.5934535789997426, 1.585506377999991]\n",
            "Solution : 0 - 6 - 7 - 9 - 3 - 4 - 8 - 1 - 5 - 2 - 0\n",
            "Cost \t: 177\n",
            "Time \t: 1.5934684396665943 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.00869079399990369, 0.005571700000018609, 0.006720322000091983]\n",
            "Solution : 0 - 6 - 7 - 9 - 3 - 4 - 8 - 1 - 5 - 2 - 0\n",
            "Cost \t: 177\n",
            "Time \t: 0.00699427200000476 s\n",
            "_____________________________________\n",
            "n: 11\n",
            "cost_matrix:\n",
            " [[ inf  80  99  6  13  43  98  78  63  12  77]\n",
            " [ 15  inf  55  43  76  74  94  43  1  64  25]\n",
            " [ 70  43  inf  49  68  27  12  59  69  30  20]\n",
            " [ 22  86  9  inf  49  16  77  69  87  87  26]\n",
            " [ 47  15  53  37  inf  56  50  9  36  67  93]\n",
            " [ 21  11  93  81  23  inf  34  92  76  68  10]\n",
            " [ 94  14  36  25  55  99  inf  68  41  75  81]\n",
            " [ 36  89  4  1  77  93  30  inf  15  50  34]\n",
            " [ 77  67  24  95  31  33  19  83  inf  85  55]\n",
            " [ 58  3  46  3  95  54  97  60  40  inf  85]\n",
            " [ 10  72  17  96  39  37  18  34  96  65  inf]]\n",
            "\n",
            "brute force\n",
            "n > 10, too many!\n",
            "Time (estimated): 17.528152836332538 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.005555609000111872, 0.006126867000148195, 0.007864295999752358]\n",
            "Solution : 0 - 9 - 1 - 8 - 4 - 7 - 2 - 6 - 3 - 5 - 10 - 0\n",
            "Cost \t: 133\n",
            "Time \t: 0.006515590666670808 s\n",
            "_____________________________________\n",
            "n: 12\n",
            "cost_matrix:\n",
            " [[ inf  96  48  41  63  63  8  83  87  80  86  66]\n",
            " [ 29  inf  40  89  57  15  83  65  43  32  81  80]\n",
            " [ 43  29  inf  31  95  7  86  41  39  88  31  94]\n",
            " [ 19  76  70  inf  67  28  40  56  90  41  76  46]\n",
            " [ 44  22  84  15  inf  37  22  32  51  21  41  99]\n",
            " [ 67  69  3  95  4  inf  70  4  3  44  15  96]\n",
            " [ 85  36  59  23  84  63  inf  2  77  8  7  82]\n",
            " [ 25  59  5  29  98  11  30  inf  51  64  15  92]\n",
            " [ 29  23  37  98  7  99  60  2  inf  40  77  94]\n",
            " [ 76  34  19  18  79  95  23  88  41  inf  71  83]\n",
            " [ 65  22  56  74  89  10  22  83  1  47  inf  97]\n",
            " [ 27  75  9  8  66  71  3  80  78  36  75  inf]]\n",
            "\n",
            "brute force\n",
            "n > 10, too many!\n",
            "Time (estimated): 210.33783403599045 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.0037985560002198326, 0.010195691000262741, 0.0035440239998933976]\n",
            "Solution : 0 - 6 - 9 - 3 - 11 - 2 - 5 - 7 - 10 - 8 - 4 - 1 - 0\n",
            "Cost \t: 174\n",
            "Time \t: 0.005846090333458657 s\n",
            "_____________________________________\n",
            "n: 13\n",
            "cost_matrix:\n",
            " [[ inf  31  96  32  11  59  96  78  81  60  63  10  80]\n",
            " [ 93  inf  45  48  57  9  26  49  37  6  59  39  5]\n",
            " [ 8  60  inf  27  13  5  68  69  29  1  36  11  63]\n",
            " [ 16  31  97  inf  20  15  27  63  19  94  54  76  96]\n",
            " [ 56  30  42  64  inf  30  86  83  11  5  35  81  91]\n",
            " [ 37  32  44  65  79  inf  79  49  34  61  4  75  12]\n",
            " [ 42  9  12  77  16  24  inf  62  46  33  3  85  11]\n",
            " [ 90  17  14  21  49  10  72  inf  72  37  37  30  59]\n",
            " [ 33  73  64  95  18  31  3  61  inf  3  73  26  30]\n",
            " [ 72  68  94  69  88  36  98  83  5  inf  53  17  70]\n",
            " [ 1  41  14  55  27  76  63  40  7  87  inf  63  41]\n",
            " [ 65  67  86  17  25  5  11  57  54  67  61  inf  86]\n",
            " [ 19  19  19  55  36  66  29  70  28  6  31  52  inf]]\n",
            "\n",
            "brute force\n",
            "n > 10, too many!\n",
            "Time (estimated): 2734.391842467876 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.019014537000202836, 0.044280106000314845, 0.0038591789998463355]\n",
            "Solution : 0 - 11 - 5 - 10 - 7 - 3 - 4 - 9 - 8 - 6 - 1 - 12 - 2 - 0\n",
            "Cost \t: 154\n",
            "Time \t: 0.02238460733345467 s\n",
            "_____________________________________\n",
            "n: 14\n",
            "cost_matrix:\n",
            " [[ inf  64  85  95  6  96  58  14  22  37  19  52  41  78]\n",
            " [ 27  inf  82  12  6  43  84  85  67  94  64  94  13  24]\n",
            " [ 97  31  inf  59  79  23  98  75  79  80  57  34  17  34]\n",
            " [ 97  27  81  inf  38  46  28  99  43  47  2  65  2  99]\n",
            " [ 48  1  35  56  inf  61  19  13  58  83  69  61  43  86]\n",
            " [ 1  82  25  33  20  inf  12  56  92  18  98  77  90  44]\n",
            " [ 3  99  13  87  17  6  inf  15  30  95  54  74  2  78]\n",
            " [ 94  35  45  72  12  54  80  inf  94  51  23  34  61  31]\n",
            " [ 63  42  24  39  11  51  25  52  inf  89  71  75  36  7]\n",
            " [ 32  39  10  48  39  33  56  95  67  inf  39  80  15  75]\n",
            " [ 69  62  80  78  27  37  64  55  60  8  inf  21  91  1]\n",
            " [ 73  56  73  50  13  26  69  89  49  17  96  inf  11  23]\n",
            " [ 99  89  17  85  76  3  30  84  64  72  85  69  inf  11]\n",
            " [ 47  40  29  66  2  19  11  13  31  6  66  68  10  inf]]\n",
            "\n",
            "brute force\n",
            "n > 10, too many!\n",
            "Time (estimated): 38281.48579455026 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.012034243000016431, 0.019745202000194695, 0.0088077489999705]\n",
            "Solution : 0 - 8 - 13 - 6 - 7 - 4 - 1 - 3 - 10 - 9 - 2 - 11 - 12 - 5 - 0\n",
            "Cost \t: 149\n",
            "Time \t: 0.013529064666727209 s\n",
            "_____________________________________\n",
            "n: 15\n",
            "cost_matrix:\n",
            " [[ inf  15  6  36  53  12  50  98  78  21  90  16  92  73  2]\n",
            " [ 36  inf  90  92  3  11  22  28  99  27  87  19  85  16  17]\n",
            " [ 62  56  inf  42  4  6  29  98  39  88  92  14  26  10  47]\n",
            " [ 9  72  6  inf  46  2  13  58  54  45  99  40  40  34  18]\n",
            " [ 19  63  1  9  inf  81  35  19  48  53  76  63  20  73  9]\n",
            " [ 68  74  35  56  62  inf  31  46  5  90  52  44  84  31  45]\n",
            " [ 41  37  79  11  96  5  inf  57  54  68  70  90  84  50  62]\n",
            " [ 83  68  82  2  65  20  3  inf  64  92  47  16  13  95  77]\n",
            " [ 52  70  19  46  22  12  11  7  inf  3  56  3  19  61  56]\n",
            " [ 51  64  68  38  1  3  14  36  94  inf  7  36  39  65  7]\n",
            " [ 6  36  77  83  29  8  91  18  54  67  inf  94  74  61  83]\n",
            " [ 25  20  38  93  27  80  66  16  15  18  53  inf  30  18  80]\n",
            " [ 58  42  33  52  45  39  85  39  39  23  93  56  inf  77  45]\n",
            " [ 95  15  85  87  57  90  88  84  93  21  33  93  16  inf  46]\n",
            " [ 70  11  1  5  88  63  73  5  37  64  94  41  58  61  inf]]\n",
            "\n",
            "brute force\n",
            "n > 10, too many!\n",
            "Time (estimated): 574222.2869182539 s\n",
            "\n",
            "branch and bound\n",
            "run_time_samples:  [0.020111967000048026, 0.018180413000209228, 0.00479494799992608]\n",
            "Solution : 0 - 14 - 7 - 6 - 3 - 5 - 8 - 11 - 1 - 4 - 2 - 13 - 12 - 9 - 10 - 0\n",
            "Cost \t: 117\n",
            "Time \t: 0.014362442666727778 s\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sgX7qZCQ4szk",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 295
        },
        "outputId": "71b4efad-3b4b-4439-fb00-be742289902c"
      },
      "source": [
        "# x = np.arange(min_input_size, max_input_size + 1)\n",
        "bf_time = brute_force_time[:max_brute_force_input_size - min_input_size + 1]\n",
        "plt.plot(np.arange(min_input_size, min_input_size + len(bf_time)), bf_time)\n",
        "plt.plot(np.arange(min_input_size, min_input_size + len(branch_and_bound_time)), branch_and_bound_time)\n",
        "plt.xlabel('n')\n",
        "plt.ylabel('run time(sec)')\n",
        "plt.title('run time vs n')\n",
        "plt.legend(['brute force', 'branch and bound'])\n",
        "# plt.xticks(x)\n",
        "plt.show()"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEWCAYAAABrDZDcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3de3wU5b3H8c8vm0C4BEEIeAENKlBALmKAilZRUalVlNa24qWirbY9tfactlZrW23tuWjt6alVWosVbX0p4qUqpwcrtdVSq1aDUitgAipiqFkCctkEAkn2d/7YTVxCLhuSySS73/frta+dyzMzv1nI/nbmeeZ5zN0REZHslRN2ACIiEi4lAhGRLKdEICKS5ZQIRESynBKBiEiWUyIQEclySgQibTCzKjM7Kuw4RIKiRCCSwsyeM7MvpC5z9/7u/nZYMYkETYlAeiwzyw07BpFMoEQgPYqZbTCz68zsdaDazHLNzM3smJQy95nZvyenZ5pZuZl9w8w2m9n7ZnZ5C/v+D+BjwJ3J20F3Jpc37j+575+b2VPJMn81s0PM7Kdmts3M3jSz41L2eZiZPWZmlWb2jpld08Kxp5tZhZlFUpbNTZ4nZjbNzErMbKeZRc3sJy3sJ+3zFWmgRCA90TzgE8BAd69Lo/whwEHA4cDngQVmNqhpIXf/DvAX4Ork7aCrW9jfZ4DvAkOAPcCLwKvJ+UeBnwCYWQ7wv8Dfk8c+HfhXMzurmWP/DagGTktZfBHwYHL6duB2dx8AHA083NHzFWmgRCA90c/c/T13351m+VrgZnevdfdlQBUwpgPHf9zdV7p7DfA4UOPuv3H3emAJ0HBFMBUodPeb3X1vsp7hbuDCFva7mESSw8wKgLOTyxrO4RgzG+LuVe7+Uivxdfb5SoZTIpCe6L12lt/a5MphF9C/A8ePpkzvbma+Yd9HAoeZ2faGF3ADMKyF/T4IfNLMegOfBF5193eT6z4PjAbeNLNXzOycVuLr7POVDKfKNumJmnaZuwvomzJ/CFDeSfvuiPeAd9x9VFoHdl9jZu8CH2ff20K4+zpgXvJ20yeBR81ssLtXd2K8kqV0RSCZYBVwkZlFzGw2cEoH9hUFOuuZgZeBWLJyu08yvmPNbGor2zwIfA04GXikYaGZXWJmhe4eB7YnF8c7KU7JckoEkgm+BpxL4gvyYuCJDuzrduCCZAugn3UkqGSdwTnAZOAdYAvwKxIVuS1ZTCKR/cndt6Qsnw2sNrOqZIwXtqOORKRVpoFpRESym64IRESynBKBiEiWUyIQEclySgQiIlmuxz1HMGTIEC8qKgo7DBGRHmXlypVb3L2wuXU9LhEUFRVRUlISdhgiIj1K8mHFZunWkIhIllMiEBHJckoEIiJZrsfVEYhIempraykvL6empibsUKQL5efnM3z4cPLy8tLeJrBEYGaLSPSzstndj22hzEzgp0AesMXdO9JZmIikKC8vp6CggKKiIsws7HCkC7g7W7dupby8nJEjR6a9XZC3hu4j0VFWs8xsIPBzYI67jwc+HWAsIlmnpqaGwYMHKwlkETNj8ODB7b4KDCwRuPsK4INWilwE/NbdNybLbw4qFpFspSSQfQ7k3zzMyuLRwCAze87MVprZ51oqaGZXJQfuLqmsrOzCEEXSs2tvHf/11FrWvr8z7FBE2i3MRJALHE9iEPKzgO+Z2ejmCrr7QncvdvfiwsJmH4wTCdW6aBW//PPbbPxgV9ihdBsbNmzg2GObrR5M26pVq1i2bFm7t7v22msZP3481157bYeOny3CbDVUTmJs1Wqg2sxWAJOAshBjEjkgpdEYAKOHFYQcSc9TX19PJBJpdt2qVasoKSnh7LPPbtc+Fy5cyAcffNDifpuqq6sjNzd7G1GGeUXwJHCSmeWaWV9gOrA2xHhEDlhZRYzeuTkccXDftgtnkbq6Oi6++GLGjh3LBRdcwK5diSumoqIirrvuOqZMmcIjjzzCzJkzG7uO2bJlC0VFRezdu5cbb7yRJUuWMHnyZJYsWUJ1dTVXXHEF06ZN47jjjuPJJ5/c75hz5syhqqqK448/niVLlrBhwwZOO+00Jk6cyOmnn87GjRsBmD9/Pl/60peYPn063/rWt1i/fj2zZs1i0qRJTJkyhbfeeguA2267jalTpzJx4kRuuummLvrkulaQzUcXAzOBIWZWDtxEopko7n6Xu681s98Dr5MYe/VX7v5GUPGIBKk0GmPUsP5Ecrpn5ewP/nc1a/7ZufUX4w4bwE3njm+1TGlpKffccw8nnngiV1xxBT//+c/55je/CcDgwYN59dVXAbjrrrv227ZXr17cfPPNlJSUcOeddwJwww03cNppp7Fo0SK2b9/OtGnTmDVrFv369WvcbunSpfTv359Vq1YBcO6553LZZZdx2WWXsWjRIq655hqeeCIxmml5eTkvvPACkUiE6dOnc/311zN37lxqamqIx+MsX76cdevW8fLLL+PuzJkzhxUrVnDyySd3/APsRoJsNTTP3Q919zx3H+7u9yQTwF0pZW5z93Hufqy7/zSoWESCti5apdtCzRgxYgQnnngiAJdccgnPP/9847rPfvaz7d7f8uXLueWWW5g8eTIzZ86kpqam8Rd+S1588UUuuugiAC699NJ9Yvj0pz9NJBIhFouxadMm5s6dCyQeyurbty/Lly9n+fLlHHfccUyZMoU333yTdevWtTvu7i57b4qJdJIdu2qp2FnDmG6cCNr65R6Upk0ZU+dTf8Xn5uYSj8cBWm0D7+489thjjBkzplPiS42hpeN9+9vf5otf/GKnHK+7Ul9DIh1UtjlZUXxI900EYdm4cSMvvvgiAA8++CAnnXRSs+WKiopYuXIlAI8++mjj8oKCAmKxWOP8WWedxR133IG7A/Daa6+1GcOMGTN46KGHAHjggQf42Mc+tl+ZgoIChg8f3njLaM+ePezatYuzzjqLRYsWUVVVBcCmTZvYvDnzHnlSIhDpoNKKxBdVd74iCMuYMWNYsGABY8eOZdu2bXz5y19uttw3v/lNfvGLX3DcccexZcuWxuWnnnoqa9asaaws/t73vkdtbS0TJ05k/PjxfO9732szhjvuuIN7772XiRMncv/993P77bc3W+7+++/nZz/7GRMnTmTGjBlUVFRw5plnctFFF3HCCScwYcIELrjggn0SU6awhszaUxQXF7sGppHu5MYn3+DxVzfx+vfP7FZP8q5du5axY8eGHYaEoLl/ezNb6e7FzZXXFYFIB5VWxBh9SEG3SgIi7aFEINIB7k5ZNKYWQ9KjKRGIdEBl1R627aplzLD+YYcicsCUCEQ6oKwi0ZpELYakJ1MiEOkA9TEkmUCJQKQDyipiDO7XiyH9e4cdisgBUyIQ6YCyzaoobklndEPdXqmd1wWlpfN67rnnOOeccwI9dlPz58/f5wG8A6VEIHKA3J2yihhjVD/QIfX19WGHkPWUCEQO0Kbtu6neW68rglak2w313XffzdSpU5k0aRKf+tSnGsvNnz+fa665hhkzZnDUUUft8+v31ltvZcKECUyaNInrr7++cfkjjzzCtGnTGD16NH/5y1/2i6mqqorTTz+dKVOmMGHChMaurDds2MDYsWO58sorGT9+PGeeeSa7d+8GYOXKlUyaNIlJkyaxYMGCFs93586dfOITn2DMmDF86Utfauw/afHixUyYMIFjjz2W6667rrF8//4ftjZ79NFHmT9/fqvn7e5cffXVjBkzhlmzZnVadxfqdE7kAJUlK4rHHNIDmo4+dT1U/KNz93nIBPj4La0WSbcb6q1bt3LllVcC8N3vfpd77rmHr371qwC8//77PP/887z55pvMmTOHCy64gKeeeoonn3ySv/3tb/Tt25cPPvhwePS6ujpefvllli1bxg9+8AOeeeaZfWLKz8/n8ccfZ8CAAWzZsoWPfvSjzJkzB4B169axePFi7r77bj7zmc/w2GOPcckll3D55Zdz5513cvLJJ7c66tnLL7/MmjVrOPLII5k9eza//e1vmTFjBtdddx0rV65k0KBBnHnmmTzxxBOcf/75rX52zZ33448/TmlpKWvWrCEajTJu3DiuuOKKVveTDl0RiByg0mTT0VG6ImhRut1Qv/HGG3zsYx9jwoQJPPDAA6xevbpx3fnnn09OTg7jxo0jGo0C8Mwzz3D55ZfTt29iIKCDDz64sfwnP/lJAI4//ng2bNiwX0zuzg033MDEiROZNWsWmzZtatzvyJEjmTx58j7bb9++ne3btzeOQXDppZe2eL7Tpk3jqKOOIhKJMG/ePJ5//nleeeUVZs6cSWFhIbm5uVx88cWsWLGizc+uufNesWIF8+bNIxKJcNhhh3Haaae1uZ906IpA5ACVRWMcdlA+A/Lzwg6lbW38cg9Kut1Qz58/nyeeeIJJkyZx33338dxzzzWu6937wxZZ6fSN1lA+EolQV1e33/oHHniAyspKVq5cSV5eHkVFRY1dX6ceKxKJNN4aSldr59tW+abdb7f3vDsisCsCM1tkZpvNrNVRx8xsqpnVmdkFQcUiEoSGPoakZel2Qx2LxTj00EOpra3lgQceaHO/Z5xxBvfee29jXULqraG27Nixg6FDh5KXl8ezzz7Lu+++22r5gQMHMnDgwMarmdbie/nll3nnnXeIx+MsWbKEk046iWnTpvHnP/+ZLVu2UF9fz+LFiznllFMAGDZsGGvXriUej/P444+3GfvJJ5/MkiVLqK+v5/333+fZZ59N+7xbE+StofuA2a0VMLMIcCuwPMA4RDpdXX2c9ZVV6nq6Del2Q/3DH/6Q6dOnc+KJJ/KRj3ykzf3Onj2bOXPmUFxczOTJk/nxj3+cdkwXX3wxJSUlTJgwgd/85jdpHe/ee+/lK1/5CpMnT2711/nUqVO5+uqrGTt2LCNHjmTu3Lkceuih3HLLLZx66qlMmjSJ448/nvPOOw+AW265hXPOOYcZM2Zw6KGHthnH3LlzGTVqFOPGjeNzn/scJ5xwQtrn3ZpAu6E2syLgd+7ebGNiM/tXoBaYmizXZoNYdUMt3cFblVWc/t9/5r8/PYlPHT887HCapW6os1eP6YbazA4H5gK/SKPsVWZWYmYllZWVwQcn0oayCnUtIZkjzFZDPwWuc/d4WwXdfaG7F7t7cWFhYReEJtK60mgMMzhmaA9oOirShjBbDRUDDyVrzYcAZ5tZnbs/EWJMImkpi8Y48uC+9OkVCTuUVrm7BszJMgdyuz+0RODuIxumzew+EnUESgLSI5RFq7r9baH8/Hy2bt3K4MGDlQyyhLuzdetW8vPz27VdYInAzBYDM4EhZlYO3ATkAbj7XUEdVyRoe+rqeWdLNR8/9pCwQ2nV8OHDKS8vR/Vq2SU/P5/hw9vXgCGwRODu89pRdn5QcYh0trcrq6mPe7e/IsjLy2PkyJFtF5Sspy4mRNrpwz6GunciEEmXEoFIO5VWxMiLGEWD+7VdWKQHUCIQaaeyaIyjhvSnV67+fCQz6H+ySDuVRtXHkGQWJQKRdqjeU8d7H+xmzDA9SCaZQ4lApB3WbU6MQdDdWwyJtIcSgUg7qI8hyURKBCLtUBqNkZ+Xw4iD+4YdikinUSIQaYeyaIxRQwuI5KjLBskcSgQi7VAWjem2kGQcJQKRNG3ftZfozj2MOUQthiSzKBGIpKksqhZDkpmUCETSVKo+hiRDKRGIpKmsIkZBfi6HDGhfX+8i3Z0SgUiaSqMxxgwr0CAvknGUCETS4O6JFkO6LSQZKLBEYGaLzGyzmb3RwvqLzex1M/uHmb1gZpOCikWkoypje9i+q5YxqiiWDBTkFcF9wOxW1r8DnOLuE4AfAgsDjEWkQxoqikepsznJQEEOVbnCzIpaWf9CyuxLQPsG2RTpQqXJPoZ0RSCZqLvUEXweeKqllWZ2lZmVmFmJBuKWMJRFYwzp34vB/XuHHYpIpws9EZjZqSQSwXUtlXH3he5e7O7FhYWFXRecSFJZtEoPkknGCjURmNlE4FfAee6+NcxYRFoSjzvr1MeQZLDQEoGZHQH8FrjU3cvCikOkLZu276Z6b72eKJaMFVhlsZktBmYCQ8ysHLgJyANw97uAG4HBwM+TD+jUuXtxUPGIHKiyqAajkcwWZKuheW2s/wLwhaCOL9JZShsTgZqOSmYKvbJYpLsrq4hx+MA+FOTnhR2KSCCUCETaUBqt0tWAZDQlApFW1NXHeWtzlfoYkoymRCDSig1bd7G3Pq4niiWjKRGItEIthiQbKBGItKK0IoYZHDNUdQSSuZQIRFqxbnOMosH9yM+LhB2KSGCUCERaUVoRU4shyXhKBCItqKmtZ8PWXaooloynRCDSgrcrq6mPu5qOSsZTIhBpQUOLIV0RSKZTIhBpQWk0Rl7EKBrSL+xQRAKVVqdzZpYDTAIOA3YDb7j75iADEwlbWUWMowv7kxfR7yXJbK0mAjM7msTIYbOAdUAlkA+MNrNdwC+BX7t7POhARbpaaTTGlCMGhR2GSODauiL4d+AXwBfd3VNXmNlQ4CLgUuDXwYQnEo6qPXWUb9vNvGlHhB2KSOBaTQStjSmQvDX0006PSKQbWJesKB6lJ4olC6R189PMvmJmA1PmB5nZv7SxzSIz22xmb7Sw3szsZ2a23sxeN7Mp7QtdJDiNLYbUdFSyQLq1YFe6+/aGGXffBlzZxjb3AbNbWf9xYFTydRWJW1Ai3UJpRRX5eTmMGNQ37FBEApduIohYcmBhADOLAL1a28DdVwAftFLkPOA3nvASMNDMDk0zHpFArdscY/SwAnJyrO3CIj1cuong98ASMzvdzE4HFieXdcThwHsp8+XJZfsxs6vMrMTMSiorKzt4WJG2JfoY0m0hyQ7pJoLrgGeBLydffwS+FVRQTbn7QncvdvfiwsLCrjqsZKlt1XvZHNujJ4ola6T1QJm7x83sPuBP7l7aScfeBIxImR+eXCYSqsbBaFRRLFki3VZDc4BVJG8HmdlkM1vawWMvBT6XbD30UWCHu7/fwX2KdJj6GJJsk9YVAXATMA14DsDdV5nZyNY2MLPFwExgiJmVJ/eRl9z+LmAZcDawHtgFXN7+8EU6X2k0xoD8XIYN6B12KCJdIt1EUOvuO1IaDgF4S4Wh9YfRkusd+EqaxxfpMmUVVYw5pIAm/99FMla6lcWrzewiEs1IR5nZHcALAcYlEgp3pzSqFkOSXdJNBF8FxgN7SDQd3Qn8a1BBiYRlc2wPO3bX6oliySrpthraBXwH+E7yYbJ+7l4TaGQiISitaOhjSIlAske6rYYeNLMBZtYP+AewxsyuDTY0ka7X2HRUA9ZLFkn31tA4d98JnA88BYwk0f20SEYpi8YY0r83g/urxZBkj3QTQZ6Z5ZFIBEvdvZY2Wg2J9ESl0SrGHKKrAcku6SaCXwIbgH7ACjM7kkSFsUjGiMeddWoxJFkorUTg7j9z98Pd/exk+/+NwKnBhibStTZt382uvfV6oliyTquJwMwuSQ5cv49k19F1Zna0mZ0UXHgiXaehxZD6GJJs01bz0cHAa2a2EljJh4PXHwOcAmwBrg80QpEuUqrhKSVLtTVm8e1mdidwGnAiMBHYDawFLnX3jcGHKNI1yqIxDh/Yh4L8vLBDEelSbT5Q5u71wB+SL5GMVVoR0xPFkpXSfaBstJn9sWEgejObaGbfDTY0ka5TWx/n7cpqtRiSrJRu89G7gW8DtQDu/jpwYVBBiXS1d7dWs7c+rmcIJCulmwj6uvvLTZbVdXYwImEpragC1MeQZKd0E8EWMzua5NPEZnYBoNHEJGOURmPkGByjFkOShdJNBF8h8XTxR8xsE4kuqL/c1kZmNtvMSs1svZnt18zUzI4ws2fN7DUze93Mzm5X9CKdZF00RtHgfuTnRcIORaTLpdsN9dvArGTvoznuHmtrm2R31QuAM4By4BUzW+rua1KKfRd42N1/YWbjSAxfWdTOcxDpMA1GI9ksrURgZgOBz5H4ks5tGMLP3a9pZbNpwPpkEsHMHgLOA1ITgQMDktMHAf9sR+winaKmtp4NW6o5Z+JhYYciEop0xyxeBrxEYiyCeJrbHA68lzJfDkxvUub7wHIz+yqJDu1mNbcjM7sKuArgiCOOSPPwIul5q7KKuKM+hiRrpZsI8t396wEcfx5wn7v/t5mdANxvZse6+z7Jxt0XAgsBiouL1f21dKqGwWjUdFSyVbqVxfeb2ZVmdqiZHdzwamObTcCIlPnhyWWpPg88DODuL5Lox2hImjGJdIrSiip6RXI4cnC/sEMRCUW6iWAvcBvwIonO51YCJW1s8wowysxGmlkvEg+gLW1SZiNwOoCZjSWRCCrTjEmkU5RFYxxV2I+8SLp/DiKZJd1bQ98AjnH3LenuONlN9dXA00AEWOTuq83sZqDE3Zcm93u3mf0biYrj+cnxDkS6TGlFjOKiQWGHIRKadBPBemBXe3fu7stIVDSnLrsxZXoNiV5NRUIRq6ll0/bdXDRMjRAke6WbCKqBVWb2LLCnYWEbzUdFur11mxNdS+gZAslm6SaCJ5IvkYxSlhyVTE1HJZul+2Txr4MORCQMZdEq+uRFGD6oT9ihiISm1URgZg+7+2fM7B8kO5xL5e4TA4tMpAuURWOMHtafnBwLOxSR0LR1RfC15Ps5QQciEobSaIyZowvDDkMkVK02nHb3hq6m/8Xd3019Af8SfHgiwfmgei+VsT0anlKyXrpP0JzRzLKPd2YgIl2toWsJtRiSbNdWHcGXSfzyP8rMXk9ZVQD8NcjARIL2YR9DSgSS3dqqI3gQeAr4LyB1YJmYu38QWFQiXaC0IsZBffIYWtA77FBEQtVqInD3HcAOEr2EimSUsmiMMcMKaBhfQyRbqZctyUruTmlFjNHqelpEiUCyU3TnHnbW1OmJYhGUCCRLlSYrikcpEYiklwjM7JNmts7MdpjZTjOLmdnOoIMTCUpDH0NqOiqSfqdzPwLOdfe1QQYj0lXKojEKC3pzcL9eYYciErp0bw1FDyQJmNlsMys1s/Vmdn0LZT5jZmvMbLWZPdjeY4gciIYWQyKS/hVBiZktIdEVdep4BL9taQMziwALSDyVXA68YmZLk4PRNJQZBXwbONHdt5nZ0AM4B5F2icedsmgV86ZpMBoRSD8RDCAxQtmZKcscaDERANOA9e7+NoCZPQScB6xJKXMlsMDdtwG4++Y04xE5YOXbdrO7tp4xajoqAqQ/HsHlB7Dvw4H3UubLgelNyowGMLO/khjX+Pvu/vumOzKzq4CrAI44Qr/ipGNK1ceQyD7SSgRmdi/Nj0dwRSccfxQwExgOrDCzCe6+vclxFgILAYqLizW4vXRImZqOiuwj3VtDv0uZzgfmAv9sY5tNwIiU+eHJZanKgb+5ey3wjpmVkUgMr6QZl0i7lVbEGD6oD/17p/vfXySzpXtr6LHUeTNbDDzfxmavAKPMbCSJBHAhcFGTMk+Q6MfoXjMbQuJW0dvpxCRyoNRiSGRfB/pk8Sig1RY+7l4HXA08DawFHnb31WZ2s5nNSRZ7GthqZmuAZ4Fr3X3rAcYk0qba+jhvVVYxWl1PizRKt44gxr51BBXAdW1t5+7LgGVNlt2YMu3A15MvkcBt2FJNbb0zephaDIk0aDMRWKKP3vHuvrEL4hEJlFoMieyvzVtDyV/t/9cFsYgErixaRY7B0YW6IhBpkG4dwatmNjXQSES6QFlFjKIh/cjPi4Qdiki3kW77uenAxWb2LlANGImLhYmBRSYSgLJoTGMUizSRbiI4K9AoRLpATW09G7ZWc+6kw8IORaRbSfc5gneDDkQkaOs3VxF3dEUg0oRGKJOsUaYWQyLNUiKQrFEajdErkkPR4L5hhyLSrSgRSNYoq4hx9ND+5Eb0314klf4iJGuURasYoyeKRfajRCBZIVZTy6btu9XHkEgzlAgkK5RFqwAYPVSJQKQpJQLJCg0thtR0VGR/SgSSFcqiMfr2inD4wD5hhyLS7SgRSFYoi8YYNayAnBwLOxSRbkeJQLJCaYVaDIm0JNBEYGazzazUzNab2fWtlPuUmbmZFQcZj2SnrVV72FK1R08Ui7QgsERgZhFgAfBxYBwwz8zGNVOuAPga8LegYpHs1tBiSBXFIs0L8opgGrDe3d92973AQ8B5zZT7IXArUBNgLJLFGlsM6YpApFlBJoLDgfdS5suTyxqZ2RRghLu3OgKamV1lZiVmVlJZWdn5kUpGK43GGNg3j8KC3mGHItIthVZZbGY5wE+Ab7RV1t0XunuxuxcXFhYGH5xklLKKGKOHFZAYfltEmgoyEWwCRqTMD08ua1AAHAs8Z2YbgI8CS1VhLJ3J3SmNxnRbSKQVQSaCV4BRZjbSzHoBFwJLG1a6+w53H+LuRe5eBLwEzHH3kgBjkixTsbOGWE0do9V0VKRFgSUCd68DrgaeBtYCD7v7ajO72czmBHVckVSlFRqMRqQt6Y5ZfEDcfRmwrMmyG1soOzPIWCQ7rWvobE6JQKRFerJYMlppNMbQgt4M6tcr7FBEui0lAsloZdGYHiQTaYMSgWSseNwpi8Z0W0ikDUoEkrHe27aLmtq4mo6KtEGJQDJWY4sh3RoSaZUSgWSshj6GRg3VMwQirVEikIxVGq1ixMF96Nc70FbSIj2eEoFkrLIKdS0hkg4lAslIe+vivFVZpRZDImlQIpCMtGFrNXVxVyIQSYMSgWQk9TEkkj4lAslI66IxIjnGUYX9wg5FpNtTIpCMVBqNUTS4L/l5kbBDEen2lAgkI5VFq9THkEialAgk49TU1rNha7XqB0TSpEQgGWf95irc0TMEImkKNBGY2WwzKzWz9WZ2fTPrv25ma8zsdTP7o5kdGWQ8kh3Ux5BI+wSWCMwsAiwAPg6MA+aZ2bgmxV4Dit19IvAo8KOg4pHsURaN0Ss3hyMP7ht2KCI9QpBXBNOA9e7+trvvBR4Czkst4O7Puvuu5OxLwPAA45EsURqNcUxhf3IjuvMpko4g/1IOB95LmS9PLmvJ54GnmlthZleZWYmZlVRWVnZiiJKJyio0KplIe3SLn0xmdglQDNzW3Hp3X+juxe5eXFhY2LXBSY+ys6aWf+6oUYshkXYIsn/eTcCIlPnhyWX7MLNZwBIvf6wAAApVSURBVHeAU9x9T4DxSBZYF23oWkJjEIikK8grgleAUWY20sx6ARcCS1MLmNlxwC+BOe6+OcBYJEuURasA9TEk0h6BJQJ3rwOuBp4G1gIPu/tqM7vZzOYki90G9AceMbNVZra0hd2JtOnVjdu496/vUNA7l8MH9gk7HJEeI9Chm9x9GbCsybIbU6ZnBXl8yQ6bYzXc+lQpj71azrABvfmfz04mJ8fCDkukx9AYftJj1dbH+fULG7j9mXXU1NXz5ZlHc/Wpx2hoSpF20l+M9Eh/Xb+F7y9dzbrNVcwcU8iN54zjqEJVEIscCCUC6VE2bd/Nf/zfGpb9o4IjDu7Lrz5XzOljh2KmW0EiB0qJQHqEmtp67l7xNgueWw/AN84YzZUnH6XxBkQ6gRKBdGvuzjNrN/PD361h4we7OHvCIXznE+PUKkikEykRSLf1dmUVN/9uDc+VVjJqaH8e+MJ0TjxmSNhhiWQcJQLpdqr31HHHn9Zzz/Nvk58b4bufGMtlM4rIUydyIoFQIpBuw91Z+vd/8l/L3qRiZw0XHD+cb80ew9CC/LBDE8loSgTSLax9fyc3LV3Ny+98wITDD2LBxVM4/shBYYclkhWUCCRUO3bV8pM/lHL/S+9yUJ88/nPuBD47dQQRPRks0mWUCCQU8bjzcMl7/OjpUrbv2sslHz2Sr58xmoF9e4UdmkjWUSKQLvfaxm3ctHQ1r5fvYGrRIH4wZzrjDhsQdlgiWUuJQLpMZWwPP/r9mzyyspyhBb25/cLJzJl0mJ4KFgmZEoEErrY+zv0vvsv//KGMmrp6vnjKUXz1tFH0V+dwIt2C/hIlUC+8legcrixaxcmjC7np3HEcrc7hRLoVJQLpdPVxZ9O23dz69Jv83+vvM+LgPiy89HjOGDdMt4EkPbW7Yfd2qNmeeN+97cPpmuS8xyGvD+T2gbz85HvylZsPeX1Tlifnc/M/XJ+bDzl6SBECTgRmNhu4HYgAv3L3W5qs7w38Bjge2Ap81t03BBmTpGdvXZwdu2vZsbuWnTXJ9937vjeu3123T9lYTR0AvXNz+LdZo/niKeocLivV7d3/y7ulL/emX/R1Na3s2CD/ILCcRMKo233gMTYkhMYE0jRpNJNgcnsntnUH/MP35pbt886H7y2WaWN/x5wB4xoGeOw8gSUCM4sAC4AzgHLgFTNb6u5rUop9Htjm7seY2YXArcBnAwnIPfELoumy5gs3v31HyjUcf59Xc8taL+NeTzweJx6P4/F6PB7HPZ54j9cT9zg0rPd66urjVO+tZ9feOFV76qneW//h+9441cnp2J7E8sR7nJq6OI6R+O9nTV7QOzdC3/w8+vXOY2h+Hkf1zaP/oDz65efRP78PBfl5nDRqMIcOyIEd7yQ/g5TzaXGeVtY3t63vX9bj4PUQT7489b0uOR1veVm8LmWb5pbVQzze/LIGTa98Guetk+ebLrN9y1oz61ss23Q6jbLuULOj+S/62mpa1XsA5A+EPgcl3oeMhj4Dk8sGpUwn5xumex+07y95d6jbk0gItclXXQ3U1kDtruT07g+TRm1NM2Wbmd61pUnZ5HT93n0/+xY/n1be9/lcW9umybqBR7b+mR6gIK8IpgHr3f1tADN7CDgPSE0E5wHfT04/CtxpZube4jf0AVv9x98w/vlrOnu3Xc5IXF615/f14PYeJN0D1CZfVS2sf6G9B+4mLAcsAjmR5Htu4ountWU5uYntMPb9NUdw802XedOy3mR9M79GU8u2uF0z+22YtuSv84Yv6UFFrX+JN0znHwSRTvr6MUv+is9P7D9oDeedQYJMBIcD76XMlwPTWyrj7nVmtoPE99aW1EJmdhVwFcARRxxxYNEUjuV/D758/+Ut/oNaM5PNlbXmF+9XLAfISX7J5ODWMG2Ny/Z55TSsiyTuqzd8OZlhyfdEmRwsuY0lv5isoUyOEcmJ0K9XhP69cujXOyc5HaFPrxwixoe/pFP/4PdZlvKe+st8n2U0Uz6e/GxSzrHhc2icb7o+dd72nW+1bMO8fTjf+GUdSX6ekSbLIonPLye3yRd8JOP+yKWTZeD/jx5RWezuC4GFAMXFxQd0tTB+0jTGT5rWqXGJiGSCIKvMNwEjUuaHJ5c1W8bMcoGDSFQai4hIFwkyEbwCjDKzkWbWC7gQWNqkzFLgsuT0BcCfgqgfEBGRlgV2ayh5z/9q4GkSVY+L3H21md0MlLj7UuAe4H4zWw98QCJZiIhIFwq0jsDdlwHLmiy7MWW6Bvh0kDGIiEjr9FidiEiWUyIQEclySgQiIllOiUBEJMtZT2utaWaVwLthx3EAhtDkieksoHPOfNl2vtBzz/lIdy9sbkWPSwQ9lZmVuHtx2HF0JZ1z5su284XMPGfdGhIRyXJKBCIiWU6JoOssDDuAEOicM1+2nS9k4DmrjkBEJMvpikBEJMspEYiIZDklgoCZ2UAze9TM3jSztWZ2QtgxBc3M/s3MVpvZG2a22Mzyw46ps5nZIjPbbGZvpCw72Mz+YGbrku9dMG5i12nhnG9L/t9+3cweN7OBYcbY2Zo755R13zAzN7MhYcTWmZQIgnc78Ht3/wgwCVgbcjyBMrPDgWuAYnc/lkQX5JnYvfh9wOwmy64H/ujuo4A/JuczyX3sf85/AI5194lAGfDtrg4qYPex/zljZiOAM4GNXR1QEJQIAmRmBwEnkxh3AXff6+7bw42qS+QCfZKjzvUF/hlyPJ3O3VeQGEMj1XnAr5PTvwbO79KgAtbcObv7cnevS86+RGIkwozRwr8zwP8A3yI50ndPp0QQrJFAJXCvmb1mZr8ys35hBxUkd98E/JjEL6X3gR3uvjzcqLrMMHd/PzldAQwLM5gQXAE8FXYQQTOz84BN7v73sGPpLEoEwcoFpgC/cPfjgGoy73bBPpL3xc8jkQQPA/qZ2SXhRtX1kkOuZsSvxXSY2XeAOuCBsGMJkpn1BW4AbmyrbE+iRBCscqDc3f+WnH+URGLIZLOAd9y90t1rgd8CM0KOqatEzexQgOT75pDj6RJmNh84B7g4C8YcP5rEj5y/m9kGErfCXjWzQ0KNqoOUCALk7hXAe2Y2JrnodGBNiCF1hY3AR82sr5kZiXPO6AryFEuBy5LTlwFPhhhLlzCz2STulc9x911hxxM0d/+Huw919yJ3LyLxY29K8m+9x1IiCN5XgQfM7HVgMvCfIccTqOTVz6PAq8A/SPwfy7xH8s0WAy8CY8ys3Mw+D9wCnGFm60hcGd0SZoydrYVzvhMoAP5gZqvM7K5Qg+xkLZxzxlEXEyIiWU5XBCIiWU6JQEQkyykRiIhkOSUCEZEsp0QgIpLllAhERLKcEoGISJZTIhDpIDMrSo41cXdyHIblZtYn7LhE0qVEINI5RgEL3H08sB34VMjxiKRNiUCkc7zj7quS0yuBohBjEWkXJQKRzrEnZbqeRBfkIj2CEoGISJZTIhARyXLqfVREJMvpikBEJMspEYiIZDklAhGRLKdEICKS5ZQIRESynBKBiEiWUyIQEcly/w9mKzz5FBmwggAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    }
  ]
}