mirrornerror/TSP_DP.ipynb

## TSP_DP.ipynb
{
  "cells": [
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# TSP DP:  \n### Travelling Salesman Problem with Dynamic Programming"
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Import Libraries"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-19T19:29:32.261496Z",
          "end_time": "2019-05-19T19:29:32.935612Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "import numpy as np\nimport matplotlib.pyplot as plt\nseed = 42\nnp.random.seed(seed=seed)\n%matplotlib inline",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Generate Parameters"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-19T19:29:33.495523Z",
          "end_time": "2019-05-19T19:29:33.502700Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "def gen_param(num):\n    path = list(range(num)) + [0]\n    X, Y= np.random.random([2, num])\n    XY = X + Y * 1j\n    S = set(list(range(num)))\n    return num, path, X, Y, XY, S",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Plot Path"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-19T19:29:36.945044Z",
          "end_time": "2019-05-19T19:29:36.965125Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "def plot_path(path, size=6):\n    plt.figure(figsize=(size, size))\n    cmap = plt.get_cmap(\"tab10\")\n    plt.axis('equal')\n    plt.plot(X[path], Y[path], alpha=0.0)\n    plt.scatter(X[0], Y[0], s=80, c='r', marker='o')\n    for i in range(len(path)-1):\n        plt.arrow(X[path[i]], Y[path[i]], \n                  X[path[i+1]]-X[path[i]], Y[path[i+1]]-Y[path[i]], \n                  head_width=0.02, head_length=0.02, length_includes_head=True, \n                  fc=cmap(0), ec=cmap(0))\n    \n    for i in range(num):\n        plt.text(X[i], Y[i]+0.01, s=i, fontsize=10, color='gray')",
      "execution_count": 3,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Distance Matrix"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-19T19:29:38.263475Z",
          "end_time": "2019-05-19T19:29:38.270407Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "def dist_mx(num):\n    mx = []\n    for i in range(num):\n        mx.append([])\n        for j in range(num):\n            mx[i].append(abs(XY[i] - XY[j]))\n    return mx",
      "execution_count": 4,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "end_time": "2019-05-19T01:03:29.351856Z",
          "start_time": "2019-05-19T01:03:29.349122Z"
        }
      },
      "cell_type": "markdown",
      "source": "## TSP without DP (Slow)\n10 nodes: 0.97 sec  \n11 nodes: 9.49 sec"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-20T03:36:16.734339Z",
          "end_time": "2019-05-20T03:36:16.739187Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "# Generate new parameters\nnum, path, X, Y, XY, S = gen_param(11)\ndist = dist_mx(num)",
      "execution_count": 221,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-20T03:36:22.557134Z",
          "end_time": "2019-05-20T03:36:31.823966Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "def TSP(a, S, b):\n    if len(S) == 0:\n        return dist[a][b]\n\n    d_min = float('inf')\n    for s in S - {a}:\n        d = dist[a][s] + TSP(s, S - {a, s}, b)\n        if d < d_min:\n            d_min = d\n\n    return d_min\n\n%time print('Total Distance:', TSP(0, S, 0))",
      "execution_count": 222,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Total Distance: 2.834259735803878\nCPU times: user 9.23 s, sys: 9.97 ms, total: 9.24 s\nWall time: 9.25 s\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## TSP DP with memo (Faster)\n10 nodes: 34.5 ms  \n11 nodes: 65.3 ms"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-20T03:36:36.195167Z",
          "end_time": "2019-05-20T03:36:36.347015Z"
        },
        "scrolled": false,
        "trusted": true
      },
      "cell_type": "code",
      "source": "memo = {}\n\ndef TSP_DP(a, S, b):\n    if len(S) == 0:\n        memo[(a, tuple(S - {a}), b)] = dist[a][b]\n        return dist[a][b]\n\n    d_min = float('inf')\n    for s in S - {a}:\n        if (s, tuple(S - {a, s}), b) not in memo:\n            memo[(s, tuple(S - {a, s}), b)] = TSP_DP(s, S - {a, s}, b)\n        d = dist[a][s] + memo[(s, tuple(S - {a, s}), b)]  \n        if d < d_min:\n            d_min = d\n\n    return d_min\n\n%time print('Total Distance:', TSP_DP(0, S, 0))",
      "execution_count": 223,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Total Distance: 2.834259735803878\nCPU times: user 90.2 ms, sys: 3.44 ms, total: 93.6 ms\nWall time: 102 ms\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-20T03:36:43.550302Z",
          "end_time": "2019-05-20T03:36:43.647613Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "# another memoization option\nmemo = {}\n\ndef TSP_DP(a, S, b):\n    S = S - {a}\n    if len(S) == 0:\n        memo[(a, tuple(S), b)] = dist[a][b]\n        return dist[a][b]\n    \n    if (a, tuple(S), b) in memo:\n        return memo[(a, tuple(S), b)]\n    \n    d_min = min([dist[a][s] +  TSP_DP(s, S - {s}, b) for s in S])\n    memo[(a, tuple(S), b)] = d_min\n\n    return d_min\n\n%time print('Total Distance:', TSP_DP(0, S, 0))",
      "execution_count": 224,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Total Distance: 2.834259735803878\nCPU times: user 72.4 ms, sys: 3.42 ms, total: 75.8 ms\nWall time: 75 ms\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "end_time": "2019-05-19T01:05:03.958125Z",
          "start_time": "2019-05-19T01:05:03.955156Z"
        }
      },
      "cell_type": "markdown",
      "source": "## Generate Tour"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-20T03:03:59.080476Z",
          "end_time": "2019-05-20T03:04:00.448316Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "P = [0]  # starting from to \"0\"\n\nfor i in range(num - 2, -1, -1):\n    d_min = np.inf\n    p_min = None\n    for m in memo:\n        if len(m[1]) == i and  set(P) | {m[0]} | set(m[1]) == S:\n            d = dist[P[-1]][m[0]] + memo[m]\n            if d < d_min:\n                d_min = d\n                p_min = m[0]\n    P.append(p_min)\n\nprint('Tour:', P + [0])\nplot_path(P + [0])",
      "execution_count": 218,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Tour: [0, 8, 10, 5, 15, 11, 4, 13, 12, 7, 3, 6, 2, 9, 14, 1, 0]\n",
          "name": "stdout"
        },
        {
          "output_type": "display_data",
          "data": {
            "text/plain": "<matplotlib.figure.Figure at 0x112eab470>",
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAFpCAYAAABnHGgVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJzs3Xd4VNXWx/HvmZZeSUILJPQOofdeBCwoCPauXMXesSs2riioV7G9VuwKCiod6UV6rwFCLwmkT5Jp5/1jkhCahDCTM2dmfZ6HBzOZzPwiyZo9+6y9t6KqKkIIIfyLQesAQgghPE+KuxBC+CEp7kII4YekuAshhB+S4i6EEH5IirsQQvghKe5CCOGHpLgLIYQfkuIuhBB+SIq7EEL4IZNWTxwXF6cmJydr9fRCCKFLa9asyVBVNf5C99OsuCcnJ7N69Wqtnl4IIXRJUZR95bmfTMsIIYQfkuIuhBB+SIq7EEL4ISnuQgjhh6S4CyGEH5LiLoQQfkiKuxBC+CEp7kII4YekuAshhB+S4i6EEH5IirsQQvghzfaWEUJ4ztSpU9m5cydhYWGMGjVK6zjCB8jIXQg/kJKSws0336x1DOFDpLgL4QeSkpIICQnROobwIRcs7oqifKEoynFFUTaf5/OKoijvK4qSqijKRkVR2ng+phBCiItRnjn3r4APgG/O8/lBQIPiPx2Bj4r/FsInpKamMnPmTFwuF23atKFbt25aRxLC6y44cldVdRFw8l/uMgT4RnVbAUQrilLdUwGFuBQul4vp06dz0003cf/997N582bS09O1jiWE13lizr0mcKDMxweLbxNCc4cOHSI2NpaYmBiMRiPNmjVj+/btWscSwus8UdyVc9ymnvOOijJSUZTViqKsltGTqAy5ublERkaWfhwZGUlubq6Gibxj8uTJfP7555w4cYLx48ezdu1arSMJjXmiz/0gUKvMx4nA4XPdUVXVT4FPAdq1a3fOFwAhPElVA+PHbNiwYVpHED7GEyP3acCtxV0znYBsVVWPeOBxhbhkkZGR5OTklH6ck5NDRESEhomEqBwXHLkrivID0AuIUxTlIPASYAZQVfVjYDowGEgFrMAd3gorRLnk5sJvv8HRo9SsWpUTmZlkZmYSGRnJli1bGDp0qNYJK0RVVQrtLrIL7GQV2Mi22knPLaJzvSpUCQ/SOp7wMRcs7qqq3nCBz6vA/R5LJERFqSqMHQuvvgpGIxQWYggOZnBSEt9mZ+OIiua4pRqPTdvLt3cnaBbT4XQXaHeRdv+dkVvEgZNW9p2wsicjn/0nrWQX2Mv1eP2bJPDZbe29nFrojewtE2DOtQdJQUEBv/76K1lZWURHR3Pttdfqc7Xj2LHw2mtQUHDqtrw86mzdRsSMDbzV63bsRhNGw7919paPqqrkFTnIstpLC3Wm1cahzAL2nbSSlpFP2ol8DmcVVvg5gk0GEmNDqVMljOS4UGpXCaPI7mTO1mOs3Z8JqopBURjWttaFH0wEHCnuASYlJYUOHTrw22+/ld62ZMkS6tSpQ7du3ViyZAlLliyhf//+GqasgNxc94i9bGEH/klsxlODHyY9LAYrRnCqOJwqTpeK0aBQaHeSU2YEnWW1cyynkP3FBXpvRj4HMq0U2l0VjlYjOpjkKmEkVQkjqUooiTEhxIRaiAoxu/+Emgm3mDAYztV45n4hmb/jOO/O3cXOY7nYHC5cxdeJLUaFtkkxFc4m/JcU9wCTlJREVlbWabft2LGD2267DYBWrVrx9ddf66+4//abeyqm2M7YRMb2uoNlya0oNAefdlcVqPfs9It6+KgQM7VjQ6kTF0ZylVBqxYYSFxFEVIiZ6OIiHRlixmz0/HZNeUUO7vpq9Tn7iyNDTMRHyHy7OJsUd0FeXl5pB0lERAT5+fkaJ6qAo0eh8NQUyIC7JoKiYHY6zrqryaBwZasatK4dTdXIYKJDzESXGUkHmw0oyrlH0VqICDbzf7e148Ef1mG1OU/7nIzaxflIcRf+oVo1CA6GvDz3xwYD9TL20y91Jd+1HoSKQn5QKAAhZiO3d0mmVa1oDQNfnL5NqjLxpjbc/uUqzEYFu1Ml2Gyge4M4raMJHyVb/grCw8NLV23m5uYSFhamcaIKuOYacJ4+qnUajDyz8CvWvn8Tb8z6gEYZ+wgxGSiwO8vdieIr8osc3P7lKgBaJkYTYjaioNAuOVbjZMJXSXEXNGzYkA0bNgCwYcMGGjVqpHGiCoiIgBdegNDQ0psKTRYALC4HQ/atZla9bH4d1YU7uibTpHrk+R5JM1OnTmXcuHFMnDjxtNtdLpWb3pjEHSGrmfNgR34a2YmhbWoSHmSiQYIsyBLnJtMyAWby5MmkpaVhtVoZP348vXr1olu3bvz666+sW7eOqKgohg8frnXMihk92v33q68CUGQKgvBw94j++edh9GiaKQrNakRpGPL8ztXJBPDQN0tJULMICg2nZkwoJqOB169pwWtXN/epawPCt0hxDzDn24Pk1ltvreQkXqAo8Mwz8MAD8PoiikLDYOJE95RNeLjW6S7oXJ1MP/yzn/w9a2napjPmtBWnfU4Ku/g3Mi0TwKw2B4t2pvP6X1t58Ie1OJwV7+X2KcWdP0UGE9xyiy4K+7lsPJjFxKmLCQkL48mrO2kdR+iMjNwDSKHdydr9mSzZlcG8bcfZk5FHkMmI1eYgyGTEeJ5FNHpkUMDp0u+OkOm5RVzzwSIGBR3hzQdGaR1H6JAU9wCxcu8JRnyygmCTAbvThbO47tmL+8Cb1Yj0q7f5FpPhklaVakkF2r8+lxiliNphKp9/9ing3tHyk08+4Z577iFcp+9GROWR4h4gDmW5l+WrqKWFvYQCbDyYzdT1h+hQJ5bqUTrcV+YMQSajLou7qqrsO+FeRPbDw5fRuNqprp53332XkSNHElqmI0iI85HiHiBCzO6l+d/d3Ym7v15NXpEDR/G0hdlkwOZw8fCP60/7mtu7JDO4RXVa1IwixGI86zF9WbDZQHbxNjPLly9n3bp1AFStWpUhQ4ZgMvnej/7kyZPZvCOVEGcRI2O2Yj1cHaq10TqW0Cnf+wkXXmExua+dN6keyexHe3DrFytJO5FPod2FqqpseGkABsU9gv993SF+WXOQr5al8dWytNLHaJAQzu1dk+lSL47kKqE+PY0TZHK/GOXk5LBy5UpGjRqF2Wzml19+YfPmzaSkpGic8GwRjbvy5apghrdN5JXhrc76/COPPKJBKqFXUtwDRMmGVnani4TIYKY+0JXRkzfx18bDxIS591UB6Fo/jq714xg3vBWqqnIws4Dle07w9bI0thzO4bnfNp/2uFe1qsGwtomk1IoufQxfEGw+1QjmcrlwOBwYjUbsdrtPnsS0Jz2PkZPWEBdu4a1rW2odR/gBKe4BwlJc3G0O9zx0kMnIhOtSaJcUg9l07o5YRVGoFeveAXFEO/ee4YV2J1sO5zB7y1G+WLqXaRsOM23DqSNz48It3NmtDr0aJtCwajgmL+ySWB7BxdNQkZGRdO7cmQkTJmA2m6lXrx716tXTJNP55BU56PPOQgAWP9XHp98RCf2Q4h4gSqZlihynX2S8qVPSRT1OsNlI26QY2ibF8MzgJgAczylk9b5MfvhnP4tTM3hr5g7emrmj9Gu614/jho61aZccQ0JE8Pke+pKt25/JHxuOYHe62HgwG4CHvl1B+KHVVG1zJQ/0b8ovv/zCxo0badnSd0bHq9NOogD/u7G17q5tCN8lxT1AlBR3mxcWKiVEBjO4RXUGt6gOuI+R23ksjwU7j/PFkr0sTs1gcWpG6f3NRoU7u9ZhQLNqNKsRWTrKvlTzth3jq2V7KdvevnHrLmoaFTbtyubhgUaaNGnCgQMHfKq4p+cWYTIqPPnLRuLDg+hYt4rWkYQfkOIeICxl5ty9zWQ00LRGJE1rRDKqV30AsgvsrD+QxeQ1B5m24TCfLNrDJ4v2lH5NsxqR3NYlmU51qlArNqRCUxP39KjHF0vTTtvzPE+1UNWYzz396qKqKnv37qV69eqX/k160O70PBxOFbvTye1fruLrOzvQoY7s9igujRT3AFE6cndo0/sdFWKmZ8N4ejaM5/0bWqOqKmknrCzbncGXS90Xa5/6deNpXzO8bSJXt65Jq1rRhAdd+Ec1KsTMvT3rMnHB7tIe9ww1nCxLApvnTWHrfAPVq1enbdu2XvkeK2rrkZzSU5YK7E5u+2KlFHhxyaS4Bwiti/uZFEWhTlwYdeLCuKmje96/wOZk8+Fs/tp4hK+WpfHLmoP8suZg6dfUiA7mzq516NEwnvrx4ec8c/Tu7nX5bPHe0uIeajFy3ZCBXNasWuV8YxWwN/30k68K7E5u/9Jd4NvLfu2igqS4B4jSbhkf3hwsxGKkfXIs7ZNjefmqZgAcyS5g5d6TfPfPflbuPclrf22Dv7aVfk2/JgmMaFeLtkkxVAkPItRi4tF+DRg3aycFdicxoRb6N6mq1bd0Qaqqciyn6KzbC+xO7v9uLSuf66dBKuEPpLgHCLOPjdzLq3pUCENSajIkpSbgvmaw/Ugu87Yd44ule5m77Thztx0vvX94kIlbO9fGZACTAZ4Y0PCcI3xfkZ5bRMnlBaMBnC6oEmZhSIp7/YAQFSXFPUCc2eeuV2ajgRaJUbRIjOKR/g0BOJlvY93+TH5efYBZW44xcYH7Qm2o2ciVrWpoGfeCTuTbKHK4iAt3F/TPl6Txn551GdnDt3rxhf5IcQ8QepiWqajYMAt9m1Slb/H0i8ulsicjj4hgs2aLqMqrSfVIlo3uQ/WoYBRF4fMlabwxfbsUd3HJfPsnX3hMydSEtch5gXvqn8GgUD8hgqqR3lsw5Uk1ok+1fr5xTQsAsqw2LSMJPyDFPcDkFTm0jiD+xRWt3D34k8t0CQlREQExLTN16lR27txJWFgYo0a5T7VZsGABa9euLd0bu2/fvjRo0EDLmJVCirtviwx2b7726l/buKt7XY3TCD0LiOJ+vlPlO3XqRJcuXTRKpY18Ke4+79UhzXhh6hayrXaiQn1np02hLwExLZOUlERIiP5PF/KEXCnuPu+q4rbPKetkakZUXEAU9/NZuXIlH330EVOnTqWgoEDrOJUiv1CKu68r2Rf/lT+2apxE6FnAFvd27drx0EMPce+99xIeHs7s2bO1jlQpcgrtWkcQ5fDylU0B94ZrQlREwBb38PBwDAYDiqLQtm1bDh06pHWkSiEXVPXhmtbu1am/y9SMqKCALe65ubml/71t2zYSEhI0TFN5pLjrQ8mF1JemydSMqJiA6JaZPHkyaWlpWK1Wxo8fT69evdi3bx9Hjx4FIDo6miuuuELjlJUjT+bcdePFK5ow5s9t5BTaS1skhSivgCjuw4YNO+u2Nm3aaJBEezJy14+hbRIZ8+c2pq0/zM0XeRyiEAE5LeNyqexOz2P70Ryto1S6sqcUCd8WHWoB4PnfN2ucROhRQIzcT+bb2HAgi9X7Mlm2O4PtR3JxulTCgoyse3GA1vEqjUE5+4Bs4dueG9yY16dvJ7fQToRMzYiL4NfFffnuDG75fCWgEmw2YbU5Tjs8uWPNwDrlJtRikmkZnbm2bS1en76dPzce4YYOtbWOI3TEr6dlYsIsOFwqTpd7rrlsYQ82GejRIE67cBoICzJqHUFcpJgw99TMM1M2aZxE6I1fF/fG1SJ5e3hLVMB0xmk8hQ4Xr0/fTvLovxg6cSmzthwl188X+JTnkGnhe54Z1BjA738+hWf5dXEH99vafk0ScLhULMZTBT4i2MTEm9rQrEYka/dn8Z9Ja2jx8mySR//FbV+sZNHOdAr87OJjmBR3XRrerhYA0zcd0TiJ0JOA+G3/5JZ21Ht2OjanSpBJocih0qlOFQa3qM7gFu79s9Nzi1i4M5335+1i4c50Fu5ML/36K1pW55ZOSbSuHYPFpN/XQxm561Ns8dTM05M3cV370+fdV6xYwdq1awF3e2+nTp0qPZ/wTQHx2240KKx7oT+tX51DkUMlKtjElSmnn60ZHxHEtW0Tubb4UOLDWQXM23aMd+fu4s+NR/hz46lR040dajGifW2a14j0+WPcypKFMPr19MBG/HfmDvKLHKXvwI4fP87atWu55557MBqNfPvttzRo0IAqVaponFb4Av1UpksUE2Zh6v1dAWhVK5qrLnBwco3oEG7pnMyaF/qz983BLHiiF08PbESQycD3Kw9w9YdLqf/cDJJH/8Ub07ex9XAOrrJXbH1QRHBAvJb7pRHFUzN/lZmaSU9PJzExEbPZjMFgICkpie3bt2sVUfiYgPptb1UrmmcGNebNGdv5ceV+ri9na5miKCTHhXFfr/rc16s+qqqy63ge09Yf5oP5qXy6aA+fLtoDuHvJH+nXkMtbVqduXFjp2Zi+oOyc+7vvvktQUBCKomAwGBg5cqSGycSFVAkPAuDpXzeWFvqEhAT+/vtvrFYrZrOZ1NRUqlevrmVM4UMCqrgD/KdnPf7YcJjRUzbRJimGhlUjLvoxFEWhYdUInrisEU9c1ginS2Xr4Rwmrz3IV8vSGD9nJ+Pn7ATc89yP9m/IgKZVqRUb6ulv56KcOed+2223lR4zKHzfEwMa8vbsnaVTM/Hx8XTt2pVJkyZhsVioWrUqBkPAvBkXFxBwxR1g8qguNHp+JgMmLGLjywMueS7aaFBokRhFi8QoXr6qGXaniw0Hsvh+5X6mrD3Eq39u5dU/3bv7VY8K5uG+DejdOIGqkcGe+HbKLVymZXTtuva1eXv2TmZuPsqw4mtDbdq0Kd0nad68eURGRmoZUfiQgPxtDzIZWf5MHzq/+TcdX5/Hllcuw2Dw3PSJ2WigXXIs7ZJjGT8ihUK7k7X7MvlyWRpzth5jdJkFKQ0SwnmgT316NIgvXbDiLWWnZRRFYdKkSaX72bdt29arzy0uXXxE8dTM5I2lxT0/P5+wsDCys7PZtm0bd911l5YRhQ9RVFWbi4Dt2rVTV69erclzl1i8K51bPl/Jde1r8d9hLSvtefOKHKzce4JPF+1hxZ6Tp32uTe1o7u1Zj871qnhkL5GVe0/w4A/rsDtVrDYHhXYXFpMBi7MIxRLC/Ec68+tP3zNo0CCSkmTnQV/33tydTJi7i61jLiPUYuLLL7/EarViNBoZMGAAdevW1Tqi8DJFUdaoqtruQvcLyJF7ie4N4rmjazJfLk2jb+MEBjSrVinPGx5kok/jqvRpXBWAbKudJakZTFyQytr9WYyctKb0vr0axnNntzq0T44lxHLx2wdEhpg5kWfDUaaTx+ZwYcNMo5gQqkRH0LhxYw4dOiTFXQdu6FibCXN3MWvLUa5pncgdd9yhdSThowK6uAO8eEVTpq0/zMhJa1j8VG9NLnpGhZq5vGV1Lm959oKqBTvTWVBmQdWVLatz80UsqGpcLZL+Tasye8tRnMX13YSTUIuRJwY0wm63s3v3bnr27OmV7014VkKE+zrN6MmbSo/iE+JcAnpapkR+kYNmL80CYPurAwk2+9YGW4fKLKg6mW877XPlWVB14KSVfuMXlm73G64UMTBkN/XiI1BVF82bN6dHjx5e/z6EZ4yfvYP3/05l25iBFXo3J/StvNMyUtyL7UnPo887C6kTF8bfj/f0qf70slRVZd8JKzM2H2HC3F3Yztif/T896jIkpSaNq0WcdpH42Smb+HXNAWxOlVCLkTFDmnFt21qVHV94wF8bD/HA9+uZ9UgPGla7+FZeoW9S3Ctg6rpDPPzTeh7qW5/H+jfSOk65nLmgqiyDAo/2b8jgFtWJDDbR/a35FNpdRIeaWfVcP8w62jpBuG08mMX1n67A4VT5+JY2pddtROCQ4l5B9327hhmbj/LLvZ1pn6y/wzxKFlT9uuYgXy9PO+1zFqMBm9PF85c34e7u0lWhN7vT87j6g6XkFjkwGtwroR/s00DrWKKSSXGvIKdLpd6z0wFY9Vy/0t5ivTpzQRXAllcGEBYkm4jpyZHsAi5/fwmZ+TZKfmN7Nozn6zs7aJpLVL7yFvdyvS9XFGWgoig7FEVJVRRl9Dk+X1tRlPmKoqxTFGWjoiiDKxLaFxgNCutf7A9A+9fn4nDq+8zRkgVV40ekkDb2ctLGXi6FXWcy821c+9Eysq12yg7Fth0JvAPeRfldsLgrimIEPgQGAU2BGxRFaXrG3Z4HflZVtTVwPTDR00ErU3SohT8e6AbArV+s1DiNCHR3f7OaI9mFOM94l30y34bVJmfiinMrz8i9A5CqquoeVVVtwI/AkDPuowIlm1pEAYc9F1EbLRKjeP7yJizbfYLvVuzTOo4IYLd1TiKlVjQWo4Gyu2QEm41sP5qrXTDh08pT3GsCB8p8fLD4trJeBm5WFOUgMB140CPpNHZ397q0Soziud83s/2ovAUW2rgqpSZTRnXll3s741Khf5OqxIZZyCtycDirQOt4wkeVp7ifq+H7zKuwNwBfqaqaCAwGJimKctZjK4oyUlGU1YqirE5PTz/z0z7pl3u7ADDw3cXkyAHFQkM/r3aPsT6+pS1rnu/Hwid7cXkL2b9dnFt5ivtBoOxql0TOnna5C/gZQFXV5UAwEHfmA6mq+qmqqu1UVW0XHx9fscSVzGIy8M+zfQFo9+pcnz9tSfiv7/7ZT0SwCaNBQVEUkqr41mEwwreUp7ivAhooilJHURQL7gum0864z36gL4CiKE1wF3d9DM3LoWpkMN/d3RGb08UTv27QOo4IQCXvGp8b3ETjJEIvLljcVVV1AA8As4BtuLtitiiKMkZRlKuK7/Y4cI+iKBuAH4DbVa0a6L2ka/047ulehylrDzFz85ELf4EQHvT3tuMAlbZzqdA/WcR0EVRVpdOb8ziWU6TZDpIiMHV8Yy7HcopIG3u51lGExjy6iEm4KYrC/Cd6AdD9rfkU2JzaBhIBQVVVjuUUcXXKmU1qQpyfFPeLFGoxsaC4wA+YsBA/m30SPmjLYXcb7p3dkrUNInRFinsFJMeF8b8bWnMgs4C3Z+/QOo7wc18tSwOgeY0obYMIXZHiXkFXtqrBFS2r8+H83azYc0LrOMKP/brmIHHhFo8e4i78nxT3S/D+9a0BuP7TFRzPLdQ4jfBHWVb3yVvPDJIWSHFxpLhfAoNBYcOLAwDo8Po87DrfQVL4ntlbjwHQr4kcyiEujhT3SxQVaubPB907SN702T8apxH+5o3p2wD3z5kQF0OKuwc0rxnFy1c2ZWXaSb4uvvglxKVyuVSyrHauay9n3YqLJ8XdQ27vWoe2STG8NG0LWw/LDpLi0m06lA3AbZ2TtQ0idEmKuwf9cE8nAAa/v5jsgn/fQXLq1KmMGzeOiRNPnWuyZcsWJk6cyCuvvMLhw7rfEl9cov9bsgeAJtUjNE4i9EiKuwdZTAZWFu8g2XrM7H/dQTIlJYWbb775tNsSEhIYMWIESUlJXs0p9OGPDUeoER0sOz+KCpHi7mEJkcH8cE8nXCo8+vP6894vKSmJkJCQ026Lj48nLu6snZJFADqRVwTAaGmBFBUkxd0LOterwr096zF1/WH+2uieXtmbkc9Nn62QQ41FuczcchSA3o30ce6B8D0mrQP4q6cHNuKPDYe5//t1ZFptvDF9O4V2J/O3H6dJ9cgLP4AIaK//5W6BjAiWFkhRMTJy9xJFUZj9aA8Anv99C1abE5cKy2WrAnEBTpeK1eaULhlxSaS4e0mW1cadX60ixHz6/+LNxe1tQpzP+gOZANzUqbbGSYSeybSMl9z2xUo2HcrmzIaZvCIHGXlFLJz1J2lpaVitVsaPH0+vXr0ICQlhxowZWK1Wvv/+e6pVq3ZWR43wf58sdLdANkgI1ziJ0DMp7l7y5GWNeX36VtIyrBTYTx3qEWQysulgNsOGDTvn1zVpIt0RgW721mPUiZPDr8WlkWkZL+nWII4ZD/fgm7s60KFOLMFmAwYFrDYH6/Znah1P+KDs7Gw++/xLrgnazCDDRlasWKF1JKFjUty9rH1yLD//pzNT7utK3yZVcanw1yY5YFuczWAw4KrRgt+KmnPP3XexatUq0tPTtY4ldEqKeyVpWiOSz25tR2yomd3p+VrHET4oIiKCcYuPAxATGUZ8fDw5ObIuQlSMFPdKVGh3ctJq565udbSOInyQw+nC4VIZ2b0uWVlZHDlyhMTERK1jCZ2SC6qVaO4298ELUtzFuazZ574WM7R1VX7++WcGDhxIUFCQxqmEtxQWFjJt2jSOHz+OoihcddVV1Krlue2dpbhXoid/2QhAjeiQC9xTBKKJC3aj4GLVvL9o0aKFdE75uZkzZ1K/fn1GjBiB0+nEbv/3nWQvlkzLVBKrzUGB3clDfeprHUX4qIU7j3N55CHi4+Pp3Lmz1nGEFxUVFbFv3z5at3afw2w0GgkODvboc8jIvZL8tdHdIXOLLCkX53A0u5AEQx7x9mPs3avy8ccfA9C2c3diqidRXxY0+ZXMzExCQ0OZOnUqx44do3r16gwcOBCLxeKx55DiXkme/NU9JRMfIXOo4mzTNhziuCuCp555nhCLkV3Hcnn/7128/dM+qoQf4Z9n+2kdUXiQy+XiyJEjDBo0iMTERGbMmMGSJUvo06ePx55DinslyCl0z6U9M6ixxkmEr3pj+nYANhzMYsKcnWw4kIXdqeJUVUwGWanqbyIjI4mMjCzthmratClLly716HNIca8Ev609CCAHHYtzsjlcAESHmLjzq1VYbc7TPq8C24/mEGwyEmIxEmwyEmwxYDEaZIsCnQoPDycqKoqMjAzi4uLYu3evxw/qkeJeCV6athWA6FDPzacJ/2FQoEZ0MEezC8/aaA7gcFYhA99dXOHHjgwxEx1iJjrUQmyY+09MqPvj6FAzUSFmQsxGQsxGgsxGgs0GQsxGgotvCzYbCTIZMMg7CI8aNGgQU6ZMwel0EhMTw5AhQzz6+FLcvexkvg2AV4c00ziJ8FUmo4GlT/dh7rZjvDR1C1kF9tNG781qRPLudSkU2l0U2J0U2p0U2J1YbQ6yrHYyrXayrDYy822ctNrIzLeTabWRU2An3+Yky2ony2qHE1avfy/hQSaiQ81Eh5qJCS15ISn+E+Z+IQm1mE57AQk2G4r/PvWCYgyAF5Jq1aoxcuRIrz3UEf4IAAAgAElEQVS+FHcv+2nVfgCubl1T4yTClymKQv+m1ejdKIGfVh/gvzO2Y3O6KLS7iA4106BqhNee2+lSKXI4KbA5KXS43H/bncW3uSi0O7HanWQX2MnKt7lfTApsnMx3/8m02si22skpdJBX5P5zMLPAa3lLBJsNRIeYiQq1EFvyQhLmflGJCnH/HRZkKp7Kcr+AlJ3WCja7/9tsVPxyekuKu5f9d+YOQI5LE+VjMhq4qWMS17SuyccLdvPxwj1Eh3h3Os9oUAi1mAi1eL8cqKpKkcNV+u6j0F72v0v+uMgpsJe+iGTl2zlpLX4hybeRXWAnu8BOod3FUXsRR3OKvJ7bbFRKp7diykxvRRW/Q4kJNRMRbC6e2jp7Wqvk3UmQqfKuk0hx96LjOYUAvDO8lcZJhN6EWkw8NqARt3VJJizIf35NFUUpnX6J9vJzqaqK3alSYHdSVPyiUXZaq+SFJK/I4Z7Wstrc01xlpreyCtzvSgodLk7k2TiRZwMufeO/BU/0Ijku7NK/yX/hPz81Puib5fsAGNyiusZJhF5VCZd1ERWlKAoWk4LFZIAQ779zdjhdFJa8K7GVmdZyuF9ITubbGDtjO0eyC9l3Il+Ku559MD+VMIt7nk8I4d9MRgPhRgPh53inlVto59qPl3Miz0aQycC+k96/uC3F3UsOZbkvKI2TKRkhAlpekYPhHy9nb3o+Nqd7TcOOo7lef17ZOMxLPlvkPuS4b5MEjZMIIbTiLuzL2JNxqrBD5RR3Gbl7yVfL0qgaGUSQSaZkhAhEqqpy3SfLST2eh915+uq0ypiWkZG7F6RluK+mjx3aUuMkQgitKIpC85pRmAxnz8OfzLfhKDOS9wYp7l7wwfxUALo18OxeEUIIffnvsJZseGkAt3dJBiDEbCQsyIiqql5f6CXTMl7w65qD1IsPw2yU104hAp3FZODH4pXqG14awLLdGfyz5yQJkd5tc5Xi7mElF0pevbq5xkmEEL6gyOEkI8/GnV2TsZgM9GqUQK9G3m+0kKGlh02YsxOAjnWqaJxECOELFu5IB+COrnUq9XmluHuQqqrM3HKUlFrRAbGrnRDiwp77fTMAtWJDK/V5pbh70OZDOQC8cEVTjZMIIXyBzeEiPbeI27skVfpzy5y7B42duQ2ANrW9vSWSqIipU6eyc+dOwsLCGDVqFACzZ89m586dGI1GYmNjGTJkiMdPoReBa/Eu95TMXd3qVvpzy8jdQ1RVZWnqCbrVj/PLvaH9QUpKCjfffPNpt9WrV49Ro0Zx3333ERsby+LFFTvxSIhzeV6jKRmQ4u4xa/dnAjBaDsH2WUlJSYSEhJx2W7169TAY3L8GiYmJ5OZ6f1m4CAx2p4sj2YXc0qnyp2RAirvHvFJ8TmqzGpEaJxEVtX79eurXr691DOEnSqZk7ule+VMyIMXdI5wulY2HshncvJpMyejUokWLMBgMtGjRQusowk+UTMnUrlL5UzIgxd0jVuw5AcCj/RtqnERUxPr169m1axdDhw6VF2fhEXani8NZhdzYobZmGaS4e8ALxa/Q3jzEWHhHamoqS5cu5frrr8dslnNuhWcsSc0AYGQPbaZkQFohL5nd6WJPRj4j2tXSOoq4gMmTJ5OWlobVamX8+PH06tWLJUuW4HQ6mTRpEuC+qHrFFVdonFTo3UtTtwB4/Si9fyPF/RIt2um+aHJ/73oaJxEXMmzYsLNua9OmjQZJhD+zO13sP2nluvbaDvhkWuYSjZ6yCYCkKtq9QgshfMey3e5rcPf21HbAJ8X9EhQ5nKTnFnFn12StowghfMSLU93X4OpoOCUDUtwvydytxwG4W6M+VnFheUUObvxsBZdNWOT1k2+EcDhd7DthZXjbRK2jlK+4K4oyUFGUHYqipCqKMvo89xmhKMpWRVG2KIryvWdj+qYnf90AQI3okAvcU2hh2e4Mer41n+W7T7DjWC593lmIy6Ve+AuFqKDlxW3R9/XS/hrcBYu7oihG4ENgENAUuEFRlKZn3KcB8AzQVVXVZsAjXsjqU6w2B1abkwf7yIpGX2O1OXhmykbu/GoVJ/JthFiM3NIpif0nrQz9aBmqKgVeeMfL09xdMnXjwzVOUr6RewcgVVXVPaqq2oAfgSFn3Oce4ENVVTMBVFU97tmYvmf6pqMA3No5Wdsg4jSr0k7Sa9wCpqw9RKHdPQ1jUBS61q/Cm0NbsP5AFnd/vVrjlMIfOZwudqfnM6xNTa2jAOUr7jWBA2U+Plh8W1kNgYaKoixVFGWFoigDPRXQVz3xi3tKJj7Cu+cgivL7ZlkaN362guO5RRQ5Ts2vKwqEBZm4oUNtRg9sxLztx3mqeEpNCE9ZseckAPf18o138+Xpcz/Xeuwz39eagAZALyARWKwoSnNVVbNOeyBFGQmMBKhdW7tluZcqp9AOyA6QvqZeQhhhQSYK7c7SUXuJsCD3j/q9veqTabXzyaI9xIYFyb+h8JiX/3BPydRP0H5KBso3cj8IlO3GTwQOn+M+U1VVtauquhfYgbvYn0ZV1U9VVW2nqmq7+Pj4imbW3O9rDwFwvcaLFMTputaPZ/novgxv6/53MRcfdaiqEB50ahzzzOAmDG+byMcLd/Pxwt2aZBX+xelSST2ex9UpNbSOUqo8xX0V0EBRlDqKoliA64FpZ9znd6A3gKIocbinafZ4MqgvebH4okl0qEXjJOJMIRYjf2x0jz0GtqhGsMlAgd1ZOnIv8da1LendKJ6xM7bz48r9WkQVfuSfve4umQd8qMHigtMyqqo6FEV5AJgFGIEvVFXdoijKGGC1qqrTij83QFGUrYATeFJV1RPeDK6VzHwbAK8OaaZxEnEuq9NOkmW18/bwllzbthabD2UzfdMR4sNPvzaiKApf3N6eqz9cyugpm4gKMTOoRXWNUgu9G/OH+zyH+gm+s3lgufaWUVV1OjD9jNteLPPfKvBY8R+/9uMq9yjv6ta+cUVcnKKqKtd+vByAYW3ci0ia14yiec2oc95fURR+G9WVnm/P577v1jLprg50b6Df6UKhDadLZfvRXK5o6VuDA1mhepH+O3MHABHBsj2sr/m+eHpl6v1dy70vu8GgMP/xXoQHmbjl85Ws2ZfpzYjCD63c6+6SeajvWZcZNSXF/SIczy0E4O3hrTROIs5UaHfy3G+bqREdTKta0Rf1tSajgTUv9ANg2EfL2HYkxxsRhZ969U/3NbiGPnaegxT3izBp2T4ABreopnEScaaSzZqm3Ne1Ql8fZDKybYx7ecag9xazNyPfY9mE/3K5VLYeyeVyH7xeI8X9IvxvfiphFiOhFtkG35cczy3k59UHGZJSg2pRwRV+nBCLkY0vDwCg99sLOJxV4KmIwk+tSvPNKRmQ4l5uh4p/0cfJlIzPuf7TFQC8OfTSD7eODDaz9oX+AHQZ+zfpuUWX/JjCf7321zYAGlb1jYVLZUlxL6f/W+xu2+/bJEHjJKKsLYez2ZOez0tXNPXYO6rYMAv/PNsXgPavzyXLavPI4wr/4XA4+Oyzz6ibsYybI7ezYMECrSOdRYp7OX25NI2EiCCCTEato4hiqqpy+ftLALitS7JHH7tqZDCLn+oNQMqYOeQVOTz6+ELfjEYjzXpeydSiZtxw253s3r2bgwcPah3rNFLcyyGt+OLa2GGX/rZfeM6fxStRf7inEwZD+VofL0at2FDmPtYTgOYvzaLQ7vT4cwh9UhSF/85OBaBBfBhOp+/9bEhxL4cP5rv/EWWBi++wOVw8+MN6QsxGOter4rXnqZ8Qzp8PdgOg2YszsctpTgJ3l8zGg1ncFLWTt99+m7p165KYqP3pS2VJcS+HX9ccpG5cGGaj/O/yFe/Mdi8mm/VID68/V/OaUfw0shNOFTq9MQ+nnOYU8NYdyERF4abb7uKxxx7j8OHDHD/uW8dYSLW6gJ3HcgF47ermGicRJbKsNj5ZtIceDeKoXSW0Up6zY90qfH5bO07k2xj47iI5ri/AvV7cJdOkegTBwcEkJSWRmpqqcarTSXG/gAlzdgLuX27hG+76ahUAH9zUplKft2+Tqrx3XQq7judx42cr5Li+AOVyqWzZn06/hjEoioLdbmfv3r3ExcVpHe00shrnX6iqyozNR2mVGIXRCxfsxMXbnZ7Hmv1ZPNKvAZEa7O8zpHVNsgvsvDhtC/d/v5aJN7Wt9AxCW+sOZBGq2GluXc9HH21AVVWaNWtGw4YNtY52Ginu/2LLYfceIy9e2fQC9xSVpe87CwF4oLd2+2bf2iWZrAI74+fs5IXfN/OqTNkFlLEztpGphvLw/feVe4M6LUhx/xdjZ2wHoE3tGI2TCID5O9wXrP7v1naYNL64/VDfBpzML+KrZfuIDbPwaH/fGrUJ71BVlVVpmfRuFO/ThR2kuJ+XqqosSc2gW/04n/9HDAROl8odX7rn2vs1rapxGreXr2rOyXw7783bRXSomTu61tE6kvCy9Qfcx0I/PqCRxkkuTIr7eazd797XWw5Q9g2fFJ91OvtR77c+Xoz3rk8hI6+IV/7YSlSImaFtfKvXWXjW18vSAGhWI1LbIOUg3TLnUXJslh7+Ef1dXpGDt2btoEXNKJ/bM1tRFL67uyONqkXw2M8bmLP1qNaRhJcU2p0s3JlOkFEhp8D3t6OQ4n4OTpfKhoPZDGxWTaZkfMAjP64D4Os7O2ic5NwURWH6Q91JiAjinm/WsHy3Xx4fHPC+WZ5God2Foih8vXyv1nEuSIr7Ofyzx/3L+fgAuUimtQMnrczddpzbuyQTG2bROs55GQ0KS0f3wWxUuOGzFWw8mKV1JOFBOYXuaysFdieFDhefLd7r83sNSXE/h+d/d5/q08DHpgAC0ZX/c+/6+Mxg37/2YTYa2PTyZQBc9cFSdhWvbhb698HfqTicpxatOV0qv672rV0gzyTF/Qx2p4s9GfkMbysXxrS2Ku2ku598RCvdbLUcbDay5RV3ge8/YRH7T1g1TiQu1fGcQr5ZnkaR49SmcVabk/f/3uXT+wxJcT/D4l3pADzQR7tFMsK9xHv4x8sBuKZ1TY3TXJywIBMbXnQf19dj3HyOZhdqnEhcirdm7Tht1F4iv8jBzM1HNEhUPlLczzB68iYAkqqEaZwksP2wcj8A0x7oqsuL2lGhZlY/3w+ATm/O40SeHNenV0V2J1EhZiKDT3WOGxTItzlZlZapYbJ/J33uZRQ5nBzPLeKOrslaRwlohXYnz/2+mZrRIbRMjNY6ToXFhQex/Jk+dH7zb9q+NpeNLw/QZD8ccWn+d+OpDeqSR/9F1/pV+O7uTjhdKr487JCRexlzt7qXt9/Tva7GSQLbC8UXtKeM6qJxkktXPSqEBU/0AqDly7Ox2ny/P1r8u6gQ9wu00aB45QQwT5HiXsZTv24AoEZ0iMZJAtfxnEJ+WXOQq1vXoGpksNZxPCI5LoyZj3QHoOmLclyf3unl3ZcU92JWm4N8m5MHNdxtUMCIT9wXUd+4xr/Oq21cLZLfit+JtB4zR47r07GIYH3MZktxLzZ9k3vZ+C1dkjROErg2H8om7YSVl69sSqhFH79AF6N17Ri+v7sjBXYnvcYtkNOcdCpCRu768sQv7imZhAj/mArQG1VVuaJ4wdKtnZO1DeNFXerH8cnNbTiUVcBVHy6V05x0KDxIHwMPKe5AbqEdgKcH+v42nv7qjw2HAfhxZCefvkjlCZc1r864a1uy+VA2t3+5Ugq8zsi0jI78tvYQANe3r61xksBkc7h46Mf1hFqMdAqQs2qHt6vF85c3YeHODB4vftcofFvJatQwnYzc9ZHSy16ctgWAGB/emMqfjZvlPvFq5sO+tVe7t93dvS6Z+TY+XLCb2DALz18uxzn6Mlvx9gNBJn2MiQO+uGfm2wAYc1UzjZMEpsx8G58t3kvPhnHUrhKqdZxK9+TAxpy02vi/xXuJDbUwSrq1fNap4q6PfY4Cvrj/tPoAANe00df+Jf7irq/dR+eVXQUYaN4c2pITeTbemrWD6FAzN3aUji1fVORwr0+w6GTkro+UXlRyCLZe2pv8SerxPNbuz+LRfg11szDEWz65pS1tk2J49rfNpReXhW8p2RVSirsOHM9179b39vBWGicJTP3GLwTg/t71NE6iPUVR+OU/nakTF8aDP6xjwY7jWkcSZyjS2Zy7PlJ6yaTl+wAY3KKaxkkCz/zt7uL1+W3tMBkD+sewlMGgMOfRHkSFmLn9y1WsTjupdSRRhk1G7vrxv79TCTEb/XI1pC9zulTu+Mo91963SVWN0/gWk9HAqufcWwVf+/FythzO1jiRKFEy5y4jdx93OKsAkCkZLXy8cDcAcx4NrNbH8rKYDGwbMxCAy99fwu70PI0TCZCRu258tngPAP2aJmicJLDkFtoZN2sHLROj5IzafxFiMbLpZfdpTn3fWcjBTDmuT2tFOmuFDNji/uXSNOIjgnTzD+UvHv5xPQBf3dFB4yS+LyLYzLoX+gPQ7b/zSxsAhDb0tohJHyk9LC0jH4CxQ/1rW1lfd+Cklb+3H+eOrsnEymrgcokJs7Dy2b4AdHh9HllWm8aJAldhSZ+7ThoA9JHSwz6cnwpAj4bxGicJLJe/vxiA0YMaa5xEXxIig1nydG8AUsbMIa9ITnPSQn7x/3e9bGwXkMX9lzUHqRsXhlknr8D+YOXek+QUOpgwopVMhVVAYkwo8x7vCUDzl2ZRYJPTnCpbbqG+XlQDrrrtPJYLwGtXN9c4iX+bOnUq48aNY+LEibhcKiM+WU5r0yGO/vMHH3/8MZMmTSI3N1frmLpSLz6cvx7qBkCTF2eWzgGLyiHF3ce9O2cnAB0DZGtZraSkpHDzzTcD8N0/7sViL9x5Nffddx/33nsvDRs2ZOHChVpG1KVmNaL49d7OAHR4fS4OOa6v0khx92GqqjJ981FaJkZh1Mm8mV4lJSUREhKCqsILU7dQKyaENnVPtZ3abHJhsKLaJcfy1e3tySqw03/CIjmur5KUHOqjFwFV3LcczgHgpStl3+zKcqy4fe/X+9yHQ8+bN48JEyawadMmevfurWU0XevVOIH/3dCavRn5jPhkuZzmVAlypLj7rpIdINvUjtE4SWBIzy0ip8DONa1rUjXSfTZt3759efTRR2nRogUrV67UOKG+XdmqBm9c05zV+zK599s1WsfxezkFMi3jk1RVZUlqBl3rV0FRZEqmMtz/3VoA3rjm7PUELVq0YNu2bZUdye/c2DGJJy9ryKwtx3h2yiat4/g1Gbn7qLX7swB4ZlATjZMEhs2HsjmcXUBCRDAhFnfr44kTJ0o/v2PHDuLi4rSK51fu792Au7rV4fuV+3l71g6t4/gtvRX3gNkO8dU/twLQrEakxkn8n6qqjPv4Gy4PysVZ4GT8+PH06tWL1NRUMjIyUBSF6OhoLr/8cq2j+o0XrmhKZr6ND+anEh1q5u7udbWO5HfydNYtExDF3elSWX8gi4HNqsmUTCWYtv4wC+11+emOTqe1nLZpE7hH6VWGd0a0IiO/iNf+2kZUiJnh7WppHcmv6G1lcEBMy/yz1z0d8PiAhhon8Q+Fdud5uzNsDhcP/7Se8CCTrCWoZIqi8PUdHWheI5Inf93IrM1HtI7kV+xOFbNRP4PDgBi5v/D7ZgDZYtYDHE4XHd+Yh9XmIC48iJrRIdSLD6dufBi1YkOZtfkoADMe7q5x0sCkKArTHuhGt7f+5j/fruX7uzvSpb5c2/CUsCD9lEz9JK0gu9PF7vR8rm2bqHUUv2AyGqgeFcz2o7kcyS7kSHYhq/dlYjIomIwKhXYX17atSa3YUK2jBiyDQWHhk71p+fJsbvy/f/j9/q6k1IrWOpZfiNBRcff7aZnFu9IBeKB3fY2T+I8bO9QmxHz65l+O4lWSzw5uzNvDU7SIJcowGw2sf8m9F/zVHy5lx1HZx8cTIoLNWkcoN78v7s8U9/4mx4VpnET/MvKKmDBnJy9O20KB/fRdCUPMRkb1qs/IHvU0SifOFGQysnXMZQBc9u4i9p3I1ziR/kUG+9nIXVGUgYqi7FAUJVVRlNH/cr9rFUVRFUVp57mIFVfkcHIsp4jbuyRrHUW38oocfLsijeTRf9Hutbm8N28XYRYj9eJPvViGmI3c3jWZh/o20DCpOJdQi4kNL7mP6+s5bgFHsgs0TqRvkSH6Gblf8GVIURQj8CHQHzgIrFIUZZqqqlvPuF8E8BDwjzeCVsS8bccBuKeH9PxeDJvDxd/bj/HYzxuwltk3/I1rWjAkpQZhQSamrj/E6MmbAJXr29fiqcsaaRdY/KuoEDNrnu9H29fm0vnNv1n9fD/iwoO0jqVLflXcgQ5AqqqqewAURfkRGAJsPeN+rwJvAU94NOElePKXDQDUjA7ROInvc7lUVqad5LnfNrE7/dTb90f6NuCWzklUOaMY9G9alacnb+Sa1jV58cqmsn7Ax1UJD2LFM33p9OY82r02lw0vDSBKR4XKV0ToaFqmPElrAgfKfHwQ6Fj2DoqitAZqqar6p6Io5y3uiqKMBEYC1K5d++LTXoQCm5N8m5MH5ULqeamqyrYjubw5YxuLd2WU3n5du1o80Kf+v3a8lLzdNxsMUth1olpUMIue7E2PcfNp9cpstrxyma5a+3yBni6oludf9ly/uaUrWBRFMQATgNsv9ECqqn4KfArQrl07r+5ROn2TewHHLV2SvPk0unTgpJUP/k7lp9WnXrN7NIjjmcFNaFwtotzFWo7L05/aVUKZ/WgPBkxYRLOXZrH91YEEm+Xfsbz01ApZnqQHgbLrmBOBw2U+jgCaAwuKi0I1YJqiKFepqrraU0Ev1uPFUzIJEcFaRfApJ/KK+Gb5Pt6bt6v0tnrxYbx+TQs6JMfq5tBfcekaVo1g6v1dGfLhUloWj+DlPOHy8bdpmVVAA0VR6gCHgOuBG0s+qapqNlC6BE5RlAXAE1oW9pITU54eGNgX+fKLHExdf5hnfzu1FWyoxcj4Ea3o07gqFpP8QgeqVrWi+eGeTtzw2Qq6/fdvlo3uK6eT/YuS0670NI11waSqqjoURXkAmAUYgS9UVd2iKMoYYLWqqtO8HfJi/b7uEADXt/fuvL4vcne6HOfxn9eTX6bT5fWrm3N165q6+uEU3tW5XhU+u7Ut93yzhsvfX8yMh7vL9ZPzsBWfVaunKaxy/aarqjodmH7GbS+e5769Lj3WpXlh6hYAYsIsGiepHOfrdHm4bwNuPUenixAl+jetxvgRrXjs5w3c/Pk/fHtXRynw51DkcBd3Pb3b9bthXJbVffDyK1f5/zmp247kMHbGdhbuTC+9rTydLkKUNbRNIllWO2P+3MojP63nvetbax3J59iKi3uQFHft/LjK3QFyTRv/3CjswEkrH85PLf0+Abo3iOPZi+x0EaKsO7vVIavAxvvzUokNs/DSlc20juRTihzuKU4ZuWuo5BDsSB31o17IibwiJi3fx7tlOl3qxofxhnS6CA96rH8jMvPtfLk0jZhQi2wnUYaM3DWWnlsEwLhrW2qc5NKdq9MlxGxkwnXS6SK859Wrm5ORV8T4OTuJCTVzS+dkrSP5hJILqlLcNTJpeRoAl7esrmmOirI7Xczbdpwnftlw2pFe0ukiKtPEm9pw/acreGHqFqJCzFyVUlPrSJorspcUdz/rltGL9/9OJcRsJNSin2/L5VJZlXaS537fTOrxvNLbH+pTn1u7JMsGT6LSKYrCD/d0YsC7i3joR/eRiX2aVNU6lqZKRu56esesnyp4AYez3FuZvj28lcZJymf70RzenH56p8vwtok81LeBdLoIzRkMCrMe6UGH1+dy59er+fk/nelQJ1brWJo5NXKX4l7p/m/xHgD6NU3QOMn5Hcy0MnH+br5fub/0tm7143hmcGOaVo+UThfhU4wGheXP9KXxCzMY8cly/nywG81rRmkdSxM2p3TLaOaLpWnEhwf53JzYyXwb3y7fx/i5O0tvqxPn7nTpWEc6XYRvs5gMbB0zkMYvzOSK/y1h7mM9qZ8QrnWsSlcycrfoaA8evyjuJceHjR3WQuMkblabu9Ol5Ig/cHe6jB/Rir5NpNNF6Euw2cjmVy6j+Uuz6Dd+IYuf6h1wU4clh9aYpLhXrg/n7wagR8N4zTLYnS7mbz/O479sILfwVKfLa1c34+rWiYRLp4vQsfAgE+tf7E/KmDl0f2s+K5/tS0Jk4Oy4WrIZoZ74RcX5efUB6sSFVfq2pS6Xyup9mTz/+yZ2HpNOF+HfokMtrHquH+1fn0uHN+ax9oX+xAbI/k1lB2x6ofvivutYLgCvXd280p5zx9Fcxs7Yxvwdp3e6PNinAbWrBNbbVRFY4iOCWDq6D13H/k2bV+ew6eUBujqdqKJyi6S4V7oJc9wXKjvVreLV5zmYaeWjBbv57p9TnS5d61fh2cFNpNNFBJSa0SHMf6IXvd9eQIuXZ7NtzEBCLL7VyOBpMi1TyVRVZcbmI1wXvoOffszmxhtvvPAXXYST+Ta+W7GPd+ac6nRJrhLKm0NbSqeLCGh14sKY8XB3Br23mCYvzmTHawN9rlPNk3IKZOReqbYczqGp6Rj1a9egzLGul8RqczBt/WFGl+l0CTYbGD8ihX7S6SJEqSbVI5l8XxeGfbSMtq/OZf2L/XXVTXIxsmXk7n2qqpZOgbzz53oSDdn07dabFStWVPgxz9fp8uqQZlzTRjpdhDiftkkxTLqrA7d8vpLe7yxg4RO9/fIdbU6BFHevOpZTyKD3FtMqMZrr2teCQxuwVW2GwXDxowWXS2XN/kye/20zO4ovygI82Nvd6RIfIZ0uQpRH9wbxTLypNaO+W8ewj5YxZVQXv7sGJd0yXmYxGsgusDN/x3EOpqVSRTWBOZJ1+zNxlXNWZsfRXMbO3Mb87ac6Xa5tm8hD0ukiRIUNblGDsUMdjJ6yibu/Wc3nt7XXOpJHyQVVL4sONWMyKDhdKpHOHGqbsnAdWsA/h4LB0rMAAA1hSURBVFUsipMpU6YwdOjQs77uUFYBE+enntbp0qWeu9OlWQ3pdBHCE67vUJusAjtjZ2znqV838Na1+tjErzzypBXSuxRFoWpkMPtPWlnjSGSNw32UXpIln/5Vsk4r7Jn5Nr79Zx/vzD7V6ZJUJZQ3h7agU50qfjkvKITW7u1Zj8x8G58s2kNsWBCjBzXWOpJHFNpd6K1k6Kq4A9SODWX/SWvpxyFmA1e2rE4NmwOrzcEfGw7z9ORTnS5BJgMTrkuhb5MEv27VEsJXPDO4CSetNj5euJvoUDP39qyndSSP0NthOfpKCzSsGsGS1AzA3aJ4b896NKsRxeO/FPDsi7NK7zfmqmYMbSudLkJoYdy1rTiRZ2PsjO3EhJq5rn1trSNdMr3VEn2lBeolhGE2uKdoIoLNTJh76tDo+3vX53bpdBHCJ3x+WzuumbiMpydvIiLYxOAWNbSOdEkigvVVLvWVFogJNePeWlklPbeIoW1q8kjfhtLpIoSPURSFKfd1oefb8xn13Tom3WWmewPtdm69VJE620NHd8W9Z8N4bu+SxLVta0mnixA+zmBQmP94L1LGzOGWz1cy+b4utE2K0TpWhUSG6Ku4626tcFiQmZevak7zmlFS2IXQAZPRwJoX+gEw7KNlbDuSo3GiiomS4i6EEKcLMhnZNmYgAIPeW8zejHyNE108vV1QleIuhKgUIRYjG18eAEDvtxdwOKtA40QXR28XVKW4CyEqTWSwmbUv9Aegy9i/Sc8t0jhR+entUBIp7kKIShUbZuGfZ/sC0P71uWRb9bFvi4zchRDiAqpGBrP4qd4AtBoz26f3blFV966EUtyFEKIcasWGMvexngA0f2kWhXanxonOze50F/dgs762L5HiLoTQTP2EcP58sBsAzV6cid3p0jjR2Yoc7hcdvZ3Cpq+0Qgi/07xmFD+N7IRThU5vzMNZ3sMZKonN4X7BCZLiLoQQF6dj3Sp8cVs7TuTbGPTeotJ5bl9QJMVdCCEqrk+Tqrx3XQo7j+Vxw2crfKbAnxq5y5y7EEJUyJDWNRlzVTNW7DnJ/d+v1ToOcGrkLnPuQghxCW7tksxj/RsyfdNRXvh9s9ZxdDvnrq/GTSFEQHiobwMyrTa+XJpGbJiFR/s31CyLXrtlpLgLIXzSS1c240Sejffm7SI61MwdXetokkOvc+5S3IUQPuu961PIyCvilT+2EhViZmibxErPIHPuQgjhYYqi8N3dHWlcLYLHft7AnK1HKz1DaXE36qtc6iutECLgKIrCXw91p2pkEPd8s4YVe05U6vOXbItgNurrcCAp7kIIn2c0KCx5ug8Wo4HrP13BxoNZlfbcucWbmunt5Dcp7kIIXTAbDaWHfVz1wVJ2HcutlOfNLdTHlsRnkuIuhNCNYLORLa9cBkD/CYvYf8Lq9efMLfTd7Yj/jRR3IYSuhAWZ2PCSewTfY9x8jmYXevX5ZOQuhBCVJCrEzOrn+wHQ6c15nMjz3nF9uQUychdCiEoTFx7E8mf6AND2tbnkeGmEnS0jdyGEqFzVo0JY8EQvAFq+PBurzfOj7JwCKe5CCFHpkuPCmPVIDwCavjirdC8YT8mRC6pCCKGNRtUi+G1UFwBSXpnz/+3dfWxV9R3H8fentAWxyOMkTBDRQaBjRmfDcG46JptsZjVbyCIJi2Qqw8VtmZvODLcsGuMiMybLWIA9OGPCVEy2MachTvGJiNoFRcRVa8EJZFIREERKKd/9ca+2w0JPH+453NPPK7nJOb2/e+6Xb+79cO555HA/3q5vvzfLmJll59zTR7Lyqs/wfls7Fy5Zy5F+ul3f/lavuZuZZeqznxjD8vmfZseeg9QvXdcvd3N6r7V/N/OkxeFuZrlyyfRx/Gru2WzavpcFdz3X54APYGh1eV3uFxzuZpZDc+smcNOl03ji1bf58aqNfV5ezeDyuzp6+VVsZpbAVZ8/k93vHWLp468z8uQqbrq0ttfLKsdwT7TmLmmOpEZJTZJu7OL56yRtlrRR0qOSJvZ/qWZmPXP9nKnMmzGB3z+1hd+uber1coYNyWG4SxoELAW+AtQC8yQd/V/gBqAuIs4GHgBu7+9Czcx647ZvnM2Xa8dy+5pGVj77Rq+WccpJVf1cVeklWXOfATRFRHNEHALuBS7rPCAi1kbEB5dnWw+kfy8sM7NjWP6t8zhv4kh++pdNPLhxR49fPzyn4X4a8Gan+W3Fvx3LlcDDfSnKzKw/SWLVd85n0piTuXblBp54taVHrx82JJ/h3tXtR7o8tkjSfKAOWHKM5xdKapDU0NLSs+aamfVFRYV45IcXMvykKq7443M0bH0n8WtPKcNt7kkq3gZM6DQ/HvjI7xpJs4HFwEUR0eX1NyNiBbACoK6urn9OHzMzS6hyUAXPL57NlJseZu6yZ/jH9z/HJz8+vNvXDT1ygGXLln04v3v3bmbNmsXMmTNLWW6fJFlzfx6YLGmSpGrgcmB15wGSzgWWA/URsbP/yzQz6x/VlRX8+5Y5AFz666dpbtnf7WtGjBrNokWLWLRoEQsXLqSqqoqpU6eWutQ+6TbcI+IwcC2wBngFuD8iXpZ0s6T64rAlQA2wStILklYfY3FmZpkbUjWIl4r3Y/3iHU+wfc/7xx3f+VDILVu2MGrUKEaMGFHSGvsq0XHuEfFQREyJiLMi4tbi334eEauL07MjYmxEnFN81B9/iWZm2Ro2pIoNP/sSABf88jF27uu4Xd++g2207Gv98OqSnS8/sGnTJqZPn55usb3gyw+Y2YA18uRqnlt8MQAzbn2UPQcOsWt/K/W/Wccldz7JwbbCRcOqKwtR2d7eTmNjI7W1vT/bNS0OdzMb0E4dNoSnfzILgHNufoSv/eZp3nznAAcPt/PS9r0ADK4srLm/9tprjBs3jpqamszqTcrhbmYD3viRQ7n72zMAeOvdVg4fCdraj/DPzYXjQz5Ycy+XTTLgcDczo2nnPn5w7wYqBO3Fm3y0tQdrNv8XgMGVFbS1tdHc3My0adOyLDWx8jsy38ysn8373bPsOfDR2+m99W5hJ2t1ZQVVVVXccMMNaZfWa15zN7MB77avf4rzzxpN9aAKTqrqiMUKFU7Qrx5UflHpNXczG/Bm145ldu1Ydu1v5e8v7uCe9W+wfff7tB4uHAo5uKr87sTkcDczKxpdM5gFF0xiwQWTeL1lP3et28qDG3cwamh11qX1mPrjBrK9UVdXFw0NDZm8t5lZuZL0r4io625c+W1IMjOzbjnczcxyyOFuZpZDDnczsxxyuJuZ5ZDD3cwshxzuZmY55HA3M8shh7uZWQ453M3McsjhbmaWQw53M7MccribmeWQw93MLIcc7mZmOeRwNzPLIYe7mVkOOdzNzHLI4W5mlkMOdzOzHHK4m5nlkMPdzCyHHO5mZjmkiMjmjaV9QGMmb37iGQO8nXURJxD3o4N70cG9KJgYER/rblBlGpUcQ2NE1GX4/icMSQ3uRQf3o4N70cG96BlvljEzyyGHu5lZDmUZ7isyfO8TjXvx/9yPDu5FB/eiBzLboWpmZqXjzTJmZjlU8nCXNEdSo6QmSTd28fxgSfcVn39W0hmlrikrCXpxnaTNkjZKelTSxCzqTEN3veg0bq6kkJTboySS9ELSN4ufjZclrUy7xjQl+J6cLmmtpA3F78pXs6jzhBcRJXsAg4DXgTOBauBFoPaoMd8FlhWnLwfuK2VNWT0S9mIWMLQ4fc1A7kVx3DDgSWA9UJd13Rl+LiYDG4CRxflTs647436sAK4pTtcCW7Ou+0R8lHrNfQbQFBHNEXEIuBe47KgxlwF3F6cfAC6WpBLXlYVuexERayPiQHF2PTA+5RrTkuRzAXALcDtwMM3iUpakF1cDSyNiN0BE7Ey5xjQl6UcApxSnhwM7UqyvbJQ63E8D3uw0v634ty7HRMRhYC8wusR1ZSFJLzq7Eni4pBVlp9teSDoXmBARD6ZZWAaSfC6mAFMkrZO0XtKc1KpLX5J+/AKYL2kb8BDwvXRKKy+lPkO1qzXwow/PSTImDxL/OyXNB+qAi0paUXaO2wtJFcCdwIK0CspQks9FJYVNM1+g8GvuKUnTI2JPiWvLQpJ+zAP+FBF3SDofuKfYjyOlL698lHrNfRswodP8eD76E+rDMZIqKfzMeqfEdWUhSS+QNBtYDNRHRGtKtaWtu14MA6YDj0vaCswEVud0p2rS78jfIqItIrZQuCbT5JTqS1uSflwJ3A8QEc8AQyhcd8Y6KXW4Pw9MljRJUjWFHaarjxqzGriiOD0XeCyKe0pyptteFDdFLKcQ7HnernrcXkTE3ogYExFnRMQZFPY/1EdEQzblllSS78hfKexsR9IYCptpmlOtMj1J+vEf4GIASdMohHtLqlWWgZKGe3Eb+rXAGuAV4P6IeFnSzZLqi8P+AIyW1ARcBxzzsLhylrAXS4AaYJWkFyQd/aHOhYS9GBAS9mINsEvSZmAtcH1E7Mqm4tJK2I8fAVdLehH4M7AgpyuEfeIzVM3McshnqJqZ5ZDD3cwshxzuZmY55HA3M8shh7uZWQ453M3McsjhbmaWQw53M7Mc+h+Oqt+9vWhdAgAAAABJRU5ErkJggg==\n"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Solution:  \n#### Example:\n<pre>\nS = {0, 1, 2, 3}\n\nTSP(0, {1, 2, 3}, 0) = min(dist[0][1] + TSP(1, {2, 3}, 0), \n                           dist[0][2] + TSP(2, {1, 3}, 0),\n                           dist[0][3] + TSP(3, {1, 2}, 0))\n\nTSP(1, {2, 3}, 0)    = min(dist[1][2] + TSP(2, {3}, 0), \n                           dist[1][3] + TSP(3, {2}, 0))\nTSP(2, {1, 3}, 0)    = min(dist[2][1] + TSP(1, {3}, 0), \n                           dist[2][3] + TSP(3, {1}, 0))\nTSP(3, {1, 2}, 0)    = min(dist[3][1] + TSP(1, {2}, 0), \n                           dist[3][2] + TSP(2, {1}, 0))\n\nTSP(2, {3}, 0)       = min(dist[2][3] + TSP(3, {}, 0))\nTSP(3, {2}, 0)       = min(dist[3][2] + TSP(2, {}, 0))\nTSP(1, {3}, 0)       = min(dist[1][3] + TSP(3, {}, 0))\nTSP(3, {1}, 0)       = min(dist[3][1] + TSP(1, {}, 0))\nTSP(1, {2}, 0)       = min(dist[1][2] + TSP(2, {}, 0))\nTSP(2, {1}, 0)       = min(dist[2][1] + TSP(1, {}, 0))\n\nTSP(1, {}, 0))       = dist[1][0]\nTSP(2, {}, 0))       = dist[2][0]\nTSP(3, {}, 0))       = dist[3][0]\n</pre>"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "end_time": "2019-05-19T02:00:15.847443Z",
          "start_time": "2019-05-19T02:00:15.844253Z"
        }
      },
      "cell_type": "markdown",
      "source": "## TSP Bit-DP with memoization"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2019-05-20T03:04:08.120191Z",
          "end_time": "2019-05-20T03:04:10.077484Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "def memoize(f):\n    cache = {}\n    def func(*args):\n        if not args in cache:\n            cache[args] = f(*args)\n        return cache[args]\n    return func\n\n@memoize\ndef TSP_BitDP(pos, visited):\n    if (1 << num) - 1 == visited: # if all visited\n        return dist[pos][0]\n    \n    d_min = np.inf\n    for i in range(num):\n        if (visited & (1 << i)) == 0: # if not visited\n            d = dist[pos][i] + TSP_BitDP(i, visited | (1 << i))\n            if d < d_min:\n                d_min = d\n    return d_min\n\n%time print('Total Length:', TSP_BitDP(0, 1))",
      "execution_count": 219,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Total Length: 3.766406692306571\nCPU times: user 1.9 s, sys: 23.2 ms, total: 1.92 s\nWall time: 1.93 s\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "",
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "_draft": {
      "nbviewer_url": "https://gist.github.com/f9f0169ca72cc48711e96fc8666740ca"
    },
    "gist": {
      "id": "f9f0169ca72cc48711e96fc8666740ca",
      "data": {
        "description": "TSP DP",
        "public": true
      }
    },
    "kernelspec": {
      "name": "py36",
      "display_name": "py36",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.6.7",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}