Skip to content

Instantly share code, notes, and snippets.

@sr229

sr229/commonalgorithms.ipynb

Created June 29, 2021 07:20
Show Gist options
  • Save sr229/bfd6c7d9d3858ea6a63d82b8867c99c9 to your computer and use it in GitHub Desktop.
Save sr229/bfd6c7d9d3858ea6a63d82b8867c99c9 to your computer and use it in GitHub Desktop.
Download ZIP
CommonAlgorithms.ipynb
Display the source blob
Display the rendered blob
Raw
commonalgorithms.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "CommonAlgorithms.ipynb",
"provenance": [],
"toc_visible": true,
"authorship_tag": "ABX9TyNIDARYdpFR6opy5jICNo/5",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/sr229/bfd6c7d9d3858ea6a63d82b8867c99c9/commonalgorithms.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Rb_hvLo0PLq1"
},
"source": [
"# First things first\n",
"\n",
"The following snippet below are dependencies required for the entire notebook to function properly. Please run this first before executing everything else.\n",
"\n",
"*(PS: if you're in JetBrains DataLore, use the packages section instead).*"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 428
},
"id": "HDI2_w9tqLFT",
"outputId": "cf62b899-6eda-4c98-8a51-4e7be161c6f9"
},
"source": [
"!pip install cplex\n",
"!pip install --upgrade ortools"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"Collecting cplex\n",
"\u001b[?25l Downloading https://files.pythonhosted.org/packages/85/9a/582da8fe452a29dc1a2ad01ac2a92c8407a0255889dce08c2cd1471abcbb/cplex-20.1.0.1-cp37-cp37m-manylinux1_x86_64.whl (30.9MB)\n",
"\u001b[K |████████████████████████████████| 30.9MB 121kB/s \n",
"\u001b[?25hInstalling collected packages: cplex\n",
"Successfully installed cplex-20.1.0.1\n",
"Collecting ortools\n",
"\u001b[?25l Downloading https://files.pythonhosted.org/packages/6a/bd/75277072925d687aa35a6ea9e23e81a7f6b7c980b2a80949c5b9a3f98c79/ortools-9.0.9048-cp37-cp37m-manylinux1_x86_64.whl (14.4MB)\n",
"\u001b[K |████████████████████████████████| 14.4MB 285kB/s \n",
"\u001b[?25hCollecting protobuf>=3.15.8\n",
"\u001b[?25l Downloading https://files.pythonhosted.org/packages/4c/53/ddcef00219f2a3c863b24288e24a20c3070bd086a1e77706f22994a7f6db/protobuf-3.17.3-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.whl (1.0MB)\n",
"\u001b[K |████████████████████████████████| 1.0MB 27.1MB/s \n",
"\u001b[?25hRequirement already satisfied, skipping upgrade: absl-py>=0.11 in /usr/local/lib/python3.7/dist-packages (from ortools) (0.12.0)\n",
"Requirement already satisfied, skipping upgrade: six>=1.9 in /usr/local/lib/python3.7/dist-packages (from protobuf>=3.15.8->ortools) (1.15.0)\n",
"Installing collected packages: protobuf, ortools\n",
" Found existing installation: protobuf 3.12.4\n",
" Uninstalling protobuf-3.12.4:\n",
" Successfully uninstalled protobuf-3.12.4\n",
"Successfully installed ortools-9.0.9048 protobuf-3.17.3\n"
],
"name": "stdout"
},
{
"output_type": "display_data",
"data": {
"application/vnd.colab-display-data+json": {
"pip_warning": {
"packages": [
"google"
]
}
}
},
"metadata": {
"tags": []
}
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "DMT7pM_drAw0"
},
"source": [
"# Algorithms"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "tEG2_TraFKNr"
},
"source": [
"## Farthest first traversal\n",
"\n",
"In computational geometry, the farthest-first traversal of a bounded metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-selected points. The same concept can also be applied to a finite set of geometric points, by restricting the selected points to belong to the set or equivalently by considering the finite metric space generated by these points. For a finite metric space or finite set of geometric points, the resulting sequence forms a permutation of the points, known as the greedy permutation.\n",
"\n",
"\\-[Wikipedia](https://en.wikipedia.org/wiki/Farthest-first_traversal)"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 265
},
"id": "k7vWa8FUF2Ef",
"outputId": "89c024f9-6a8d-4512-dd2d-c5678591d73a"
},
"source": [
"# From: https://gist.github.com/nkt1546789/8e6c46aa4c3b55f13d32\n",
"# Includes numpy fixes from Seyoung Park.\n",
"import numpy as np\n",
"\n",
"def fft(X,D,k):\n",
" \"\"\"\n",
" X: input vectors (n_samples by dimensionality)\n",
" D: distance matrix (n_samples by n_samples)\n",
" k: number of centroids\n",
" out: indices of centroids\n",
" \"\"\"\n",
" n=X.shape[0]\n",
" visited=[]\n",
" i=np.int32(np.random.uniform(n))\n",
" visited.append(i)\n",
" while len(visited)<k:\n",
" dist=np.mean([D[i] for i in visited],0)\n",
" for i in np.argsort(dist)[::-1]:\n",
" if i not in visited:\n",
" visited.append(i)\n",
" break\n",
" return np.array(visited)\n",
"\n",
"if __name__ == '__main__':\n",
" import matplotlib.pyplot as plt\n",
" n=300\n",
" e=0.1\n",
" mu1=np.array([-2.,0.])\n",
" mu2=np.array([2.,0.])\n",
" mu3=np.array([0.,2.])\n",
" mu=np.array([mu1,mu2,mu3])\n",
" x1=np.random.multivariate_normal(mu1,e*np.identity(2),int(n/3))\n",
" x2=np.random.multivariate_normal(mu2,e*np.identity(2),int(n/3))\n",
" x3=np.random.multivariate_normal(mu3,e*np.identity(2),int(n/3))\n",
" X=np.r_[x1,x2,x3]\n",
" y=np.concatenate([np.repeat(0,int(n/3)),np.repeat(1,int(n/3)),np.repeat(2,int(n/3))])\n",
"\n",
" X2=np.c_[np.sum(X**2,1)]\n",
" D=X2+X2.T-2*X.dot(X.T)\n",
" centroid_idx=fft(X,D,3)\n",
" centroids=X[centroid_idx]\n",
"\n",
" colors=plt.cm.Paired(np.linspace(0, 1, len(np.unique(y))))\n",
" plt.scatter(X[:,0],X[:,1],color=colors[y])\n",
" plt.scatter(centroids[:,0],centroids[:,1],color=\"black\",s=50)\n",
" plt.show()\n",
" "
],
"execution_count": null,
"outputs": [
{
"output_type": "display_data",
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD4CAYAAADvsV2wAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nOydd5xcVfn/3+feqbuzvSfZzaZ3SIWEXqSKgIqA7YsoYAVE/X5/KCp2sQuiWFCqFEVFFJAOUkJ6L5uyaVuyvc5Ovff8/riTzc7Ondme3WzO+/UKJPeee86ZZPa55zzneT6PkFKiUCgUivGPNtoTUCgUCsWxQRl8hUKhOEFQBl+hUChOEJTBVygUihMEZfAVCoXiBMEx2hNIRn5+viwvLx/taSgUCsVxxbp16xqllAV298aswS8vL2ft2rWjPQ2FQqE4rhBCHEh2T7l0FAqF4gRBGXyFQqE4QVAGX6FQKE4QlMFXKBSKEwRl8BVjimBrA0071hBoOjzaU7El3NFCa+U2wp2toz0VhWLAjNkoHcWJhWlE2XT/nVS/8280pxszEqJo0bks/vyP0Z2u0Z4ephFlywPf5dCbT6M5XJjRMKVnvZ+Trv8GQtNHe3oKRb9QK3zFmGD3M3+geuVzmJEw0a4OzEiYug2vs/2xn4z21ADY9Y/7qHrrGWt+gU7MSJiqN//Jrqd/N9pTUyj6jTL4ijFB5XMPYYaDcdfMSIgDrz3FSEl4Syk5+PrfefUr7+U/N61gzS9uobNmn23bff95FKPX/IxwkMrnHx6RuSkUI4Fy6ShGHSklEX+b7T0zHEQaUYTDOezj7vzrPVQ+/xBGKABA7dpXaNi6krN/+A/SCyfFzy/QYdtHpMv+ukIxFlErfMWo03agIuk9zelGGwFjH+nqZO+zD3QbewCkiREKsOeZP8S1FUKQOXm2bT9ZU+YO+9wUipFCGXzFqFO/6Y2k91yZeSMypv/wftsXiTQNmnetT7i+4Lqvo7s8IGI/MkJDd3lYcN0dIzI/hWIkUC4dxajTWbM/6b3cmQtHZExPbhFmNGxzR5BeNDnhat6sxZz5nSfZ/c/f0VK5FXdmLmXnfYicaSeNyPwUipFArfAVo0560SSEbuO20TQmnX7ZiIzpyS6gaOHZaE533HXd5Wb65TfYPpMxaTqa00WwuY72Q7vY9tAPeOXLl4zZnAGFojfK4CtGnbKzP4jm6LXZFAJPThFFC88asXEXfe5HTFx+CZrTheZ04ckpZPEXfkruDPtdxYHXnqJm1QuYkRBGsIto0E+goZq1d39xxOaoUAwnyqWjGHW8ecUsvOl7rL/vq8iYm8WZlsGpX/71iCY1OdxeFn32h5z0qTuJBDpxZ+YhhEjafv+Lf44/5MXy+bcd2EGwpR5PTuGIzVWhGA6GvMIXQpQKIV4TQmwXQmwTQtxq0+YcIUSbEGJj7Nc3hzquYvwQDfjZ8tD3kUb06LVgF+t/8/+Qpjnk/sOdbVT8/df89xtXs/pnn6dxx+q4+7rLgycrP6WxB4j2MvZHEEJPek+hGEsMxwo/CnxZSrleCJEBrBNCvCSl3N6r3ZtSypFxyCqOS1ort7HjL7+gqWIDZjgAPRKspBGlq7Gaxu2rKJi/YtBjhDtbef329xPuaMaMWLuHhi3vMPdj/48p77l2QH1NOPUiKp9/OOGw15meQXpR2aDnqFAcK4a8wpdS1kop18d+3wHsACYOtV/F+KZlz2be/s7HaNj8NmaoK87YH0EaBp01lUMap/I/j8QZe7AyZLf/+ccDXpVPf98NePKK0d1eAITuRHd7WfS5H/W5O1AoxgLD6sMXQpQDi4BVNrdXCCE2ATXAV6SU22yevwm4CaCsTK2YxjPbH/9pglRBb4SukzFpxpDGqdvwRpyx7+5b02k/WJH0gNYOly+Lc+56mqq3/kXjtpWkFUyi/D3Xklag1jeK44NhM/hCCB/wN+CLUsr2XrfXA5OllJ1CiEuBp4GEn2Qp5e+B3wMsXbp0ZARUFGOCtv07Ut4Xmk568WTy5iwb0jjuzFzb69KI4vJlp3y2YetKKp9/mFB7M8VLzmPKhR/BmZZB+flXU37+1UOal0IxGgxLWKYQwoll7P8spfx77/tSynYpZWfs988BTiFE/nCMrTg+8eQWpbzvSPNx+tcfGrKrZOql16G7vHHXhKbjmzQdX0l50uf2Pvcgq3/6Oeo2vE7r3s3s+sd9vPG1DxLp6hzSfBSK0WQ4onQE8Edgh5Ty50naFMfaIYQ4JTZu01DHVhy/zHr/ZxOSnnqSXjQZZ1rGkMcpXHA6s6+5Fd3lweH1obs8ZE6ezalf+U3SZyJdnez4y91xLiczEiLYWs/+l58Y8pwUitFiOFw6pwMfB7YIITbGrn0NKAOQUv4WuAr4rBAiCgSAa+VIad4qjgsmnvZegu3NbHvkhwkHtrrbS/n51wzbWNMuuY7J515F2/4duDJy8eYW0VG9B2kYePOKE9q37duGpjvoHRBqhkPUrX+NGUkycRWKsc6QDb6U8i0g5b5bSnkvcO9Qx1KML6Zd/HHyZi9h5fevxzQMSwZZCIoWnUPpWVcOuL+2/dtp3rUBd3YBRYvOiauU5fCkkzNjERV/u5c9zz6A7nBiRiPkzz2Fpbf8Aoc3vbutKyMHaRo2Iwjc2coTqTh+UZm2ilElu3wuF/7mTeo2vE6otYHc2UvJKps1oD5MI8rae26jYdNbSCnRdAeay83p33iEjIlTkaZJxT9+w55n7seMhACIxv7fuG0VG377VZbddk93fxmlM0grnERndWWc4ReaBhLaD+4is2zmMHx6heLYIsaqZ2Xp0qVy7dq1oz0NxRgkGgrQfmAnroxsfCVT2PfS42x/7McYoZ5hngLfhCmc99Nn2f74z9n34qMJsghH0BwuLrrvTZzpmd3XAk2HefeuG+k8vD8uAxhNQ3e4WPCJb1B2zgeoeudZdj75SwJNtaQVTGT2tV9i4qkXjdAnVyj6RgixTkq51O6eWuErjiv2v/Ik2x79EULTkUYU34SpmNFwL2MPIOms3cczH18AhgEkX9gITSfsb48z+EYoQLC1PrG8omlihINsefC7mIbBtkd+0H246687yMb7bgcYlNEPtTdz6M1/0lVfRd6sxZSccgGaY/QLuCvGD2qFrzhuaNq5lnfvujE+YeuIuJqtz71/uDJyuOi+N+OE2t7+3nU07VhjmwEM4PD60BwOwh2tCffSi8o4/xcvDGgOrZVbeed7n8A0opiRkBVKqmmY0Qi600XpWVcy55rbcHjSBvbhFCccqVb4Sh5ZcdxQ+fxDidm5pjEkY6+5PCy4/htxxl6aJk071iY19kfa2Bl7AH991YDmIKVk3b1fIRr0d58xGOEARtCPjIaJBjo58OpfePfHNw2oX4WiN8rgK0aFtgM72f/yExxe9xpmNNKvZ4ItDcM+D3dmLiVL3xN/UQg0PbW3U3d7SBac5srMGdAcgs11fRZRMSNh2vZtp7Vy64D6Vih6ogy+4phiGlFW/+Jm3rrzw2x99C7W//p/eemW8+k8fKDPZ4sWnZMyWWswhDtbObz+tbhrQggmnnYpIkXx9NwZC9Gc9v51b17JgOYgHI6Uu4keLWk/tHtAfSsUPVEGX3FM2f/yEzRsegsjHMQMh4gG/YTamvpVNWrKhR/BnZUXZ2h1l5dJZ1xhFRhPgdAdRwuQ98AIdtG2L0HHj/n/cwdZk2dbz9lQt/HNpLsAb25iMlcqPFn5ZE6eZTu/3qSSg1Ao+kIZfMUx5cCrf0n0w0uTzpp9BJpqUz6re9KY/r4b8eQW4/D6yJoyj2Vf+hWLP3cXy277FdlT5+Pw+sgsn8Osq27GE8uidaRlMGH5xd2yxj3RXB4iXR288/1P8PpXP8DOv/+GaMCPM83Hmd95kqzyObZz0Zwu2+Qs3Z02qKSxJTf/HE92Pron3XbnIBxOfBOmkDMAdU+FojcqLFNxTLGTKgbLjWIkuQfWIemqn3yW5op13fH0nTWV1K1/jcKTTifY1kBH1R6E7qCr7hB7n3uQ7CnzCLU2Eg348R8+aCVOJcwnxP7X/gaxoibtB3aw55+/Y8UdD5I3cxG+knLLb57gcpHMvuY2dj75CyRgRsPoDhcly95D8ZLzaN61geqVzyGExsTTLyNn2oKUfy/phZN4z90vU7/pLQLNtbgy8tj/0p9p2rkOoelMWH4xJ133daW7rxgSKixTcUzZ+dSv2POv+xMMvzevhPfc80pSg1a/6U3W/PKLGKGuuOua082y237Fml/egtmHvv5A0Jwuzv/FiwSbD/P2d6/rjp4BQGikF07ivJ//h3B7MzXv/odIoIOCBaeTM20BWx+5K24nozvdTL30E8y5OqH6ZxyRrk4CTTV480q6heOkaYDQlKFX9BuVeKUYM0y/7JPUrnmZrvoqjFAXmtON0HWW3PyzlEatbsMbCcYeACHY+9yDyH5G+vQXMxJhzS9vxeH2xmfaCkFawUSW334/QgjcWXlMueijgBVe2bZ/B/tfeTLu5WOEg+x99gFKz7wcX8mUhLGkabLtsZ+w/6XHLdE2I0LZuR9iwf98dUSLuCtOPJTBVxxTHJ50zv7+X6ld8zKNO9aQlj+B0rOuxJNdkPI5V0YOwuFMMOyapoM0k4idDQVJ655NCVeF0EgrmEh6UWn3tcbtq9ny0PfpOLTLdo5Wd5K69W/ge2+iwd/z7B858MqTmJFQ907i0Ot/w52Rw6wPfn74PpLihEcd2iqOOZrDxcQVl3LyJ+9kxuU39mnsAUrPutJ+tSsE5Rd8GN19bDJQpWnQXLGeUHszYBViX/XjT9NxaJd1P9lOQwjqNv2Xt771ETb+4Rt0VB+t1bv32QcTdH6McJC9zz80Mh9CccKiDL7iuCCtYCKLP/9jHJ50HF4fDk86rowcVnz1fkqWvoe82Utso3CSIgSay82EUy9GG8hzWLV2I10dAFT8/dcY4VAfT1iHw4071tC8awMH3/gH/73jgzTuWA1ApLPN9ploVwfS7K3Kr1AMHuXSURw3TFh2AUUnn0Xz7g1oupPcmQu7V/2n/u991K5+iaqVz4KmU7fu1T79+md+6wmyymdjRMJsffgHVK98jmhXJ6mE1sByS6UXWi6djkO7+2xvZeRKOHIWYBoYYYNN99/J+T97nszJc2jbl5hBm1E60zaySKEYLOrbpDiu0F1uCuYtJ2/2kjgXz5HQxVNu+xWn3PpLZl75mT4SmQQbf38Hz9+0gnfvuoHSM6/g0vtXM/MDn+szm9eMhNn26F1E/O1WwlSK+j+aw4mWJCmsq76KSFcHC677mpU41n1oLdBdHhZcd0fKeSgUA0UZfMW4w4xGOPDaX1O0sAxr2/7tRDpbadqxhpU/+CRNFeuZ/r4bkkfGxF4gka529r38BG/e+WFmXHETuiv5C8LhTcfly7S9J4SG5nSTO3MRZ3zrMUqWvoe0olKKl5zL6d98lPy5p/Tr8yoU/UW5dBTjjvpNbxLxd4BM9H8L3WlF9PS6Z4SDbH/sJ8y59jZkMhdNj2dkNEKg+TCBxlqW334/m//4LTqq98Q1110e5v/PHQRbG6j46z1xGcaa08WE5Zd0l2HMKp8TV3VLoRgJhmzwhRClwMNAEZYz8/dSyrt7tRHA3cClQBfwCSnl+qGOrVDY0VVfhTTs/fd5806hadsqpJH4Mmjbv52Oqj3Qz4NSI9hFw7Z3OfmTd3LuT/5FoKmW3c/cT9OO1XgLJjLjfTeSN3sJ0jTorKmk6q1n0JxuzEiYvNlLOen6bw7pcyoUA2U4VvhR4MtSyvVCiAxgnRDiJSnl9h5tLgFmxH6dCtwX+79CMeykF0/G7JksFUP3pFF2xhW07t5INJB434xEkIaB0HXoZx7XwdeeomjhWRQvPhdvXgknXf+NhDZC01l443eZfdXNdFTvjcXxlw34cykUQ2XIPnwpZe2R1bqUsgPYAUzs1ewK4GFp8S6QLYQYmIasQtFPdv3zd2AmumVc6VlMWH4RZedeleRJSf2Wd/DmFvdSyUx+KCuNKOt//X8YkTBt+3ew5pe38PrtV7Ll4R8QDfrj2npyCimYv0IZe8WoMaw+fCFEObAIWNXr1kTgUI8/V8WuxckjCiFuAm4CKCtTPxQKCLbUs+fZB2jc9i7evBKmX/Yp8mYvSdq+o3ovbft3kBAqKQR5c5ZZSV/LL2Xfi4/Zhm121R/i9G8+ypYHvkPt2peR0iSzdCadtfswk8bbS3Y+dQ97//1At5+//WAF+/7zCBmlsyh/zzVMPveDqj6tYtQZNoMvhPABfwO+KKVsH0wfUsrfA78HSzxtuOamOD4JNB3mja+9n0jAj4xGaD+wk8atKznphm9TesblGOEgO/5yNwdf/xtmOET+/OWUnHKhpUfTuzMpCTTWAJAxcRpCaLZHs501+9j66A85+YZvs+TmnwGS2rWvsPF3X8PE3uBHA372/utP2MXjdxyqYPuff0LNu//htDseUHH1ilFlWAy+EMKJZez/LKX8u02TaqC0x58nxa4pFEnZ9fR9RLo648TLjHCQrQ9+n4nLL2H1z75A08613foz9ZvepHHHmqMJTj3QnG7y5p5CsK2JbY/eheZ0xRQ7exlpaVLzznPUrnoRhyedrPI5TDztMoxIX0795OsTIxygtXIr9ZvfImf6SVYB9D5KKCoUI8FwROkI4I/ADinlz5M0ewb4ghDiCazD2jYpZepqF4oTnobN78QrVcYwjSh1m96kqWJdvGyxlJihAOiOWDRM7J6m4/CkkTd7GS9+9kz6yoyVpoE0DcKREA1b3qZhy9tWwRPdYfsy6Q9GqIs1v7wVaRpouoMpF32MOVffqtQwFceU4VhmnA58HNgihNgYu/Y1oAxASvlb4DmskMw9WGGZ1w/DuIpxjjs7j66GqoTr0ozSUbU7+VGqEUX3+kgrmEDE30HhwjOZfdUtvPqVS+lbBsEeMxJGc7ooPuUS6ja+iRHoHHgfsTh8Ixph338eQRoG8z76v4Oaj0IxGIZs8KWUb5EqjMFqIwGl86oYENPe+0k23Hd7vJJkLNt151/usU2sOoIRCrDk5gfImjwbgPZDuxIUKQeKGY1iRsLxu4pBYoSD7H/pMWZ/6JaUmboKxXCiTpAUY5YJp1zIlAs/Gn9RmpbvPYWxB0te4YiBl1Ky86/DkMUqTfx1B9Eczn4/YhVPt18PSSmJ+O2VMhWKkUAZfMWYJtBcl9RgpkSa3Rr5h9datWKHiubyUDB/hU192+S4s/LJm2ufY6g5Xbgyc4c8L4WivyiDrxjT1G/674AMbE9W/uB6jHCQyhceHbIbRnO68GTlMeuDN1uyxf1c5acXlTL32i9Zapg90F1e5lx9q4rWURxTlMFXjGkcQ6hkFQ0H2fiHb9J+sCJlO5HK6AoNb8Ekpr/vBs76/t9wpvlYcfsfmHDqRdBHhI3u9jL9sk+RM20Bp339QfLmLMPh9eGbOI2FN3030V2lUIwwQg5y9TTSLF26VK5du3a0p6EYBUwjSuveLYBVL3bXP34Ti5kfOEJ32IZ2Hm0gEJojqdia5nRz7k+fJb0gXi2ko3ovq378GYItdZjdGbtWoROr8pZgzrW3MfWijw1q3grFYBFCrJNSLrW7p/aTijFF47ZVrLn7VmTUMtKa00XuzMU0bl9tf1ArBKVnf4Calc/ZRuGkNPYAUiY19gBmNMz6X/8vZ37rsaPXjCjvfP96Qq2N9Azz1BxOTr39D7jSM/GVTFHRN4oxh3LpKMYMofYWVv30s0Q624gG/USDfsIdLbTs3czpdz5GwYLT4tworowcFn3mLhbe8G18E6f1WamqNyldOUeQktbKrTRVrOvWs2/cvgoj2EXvmH5pGtStfZmsybOVsVeMSdQKXzFmqHn3OWxdjFLSWVXBiq/+EWkamNEousuNlJLG7avY+dS9TFxxKaE5jdSufhGJJNBYmzJ0U/ek4fT6CLY00GfmbTTCu3fdCMDMD3yOtLwS2yekadDVWMvWR39E3frXcKZnMu2S65iw4lLEYCKNFIphRhl8xZgh3NlqG01jRiOEO614daHp6C4dMxph1U8/R3PFOoxQAM3lQQjBqf/3W/LnnMK6e79CzeoXbRQxBe7sfOZc/UW2Pvoj+pt5e8RdtOvvv2HuR75i6wbSHC4Or3slLqpo4x++Qdv+Hcz9yFf695fQD6SUGKEudJdHSTMoBoRy6SjGDPlzlyeEL4LlG8+ftzzu2sH/Pt1t7MGSLTBCAdbefRvSNFjwiW/gyS6wGUUSDfppP1SR0nefDCMU4MArf2HqRR+PHc4emaMLMxpOCCE1QgEqX3iEUFvTgMeyo3rVC7x087k8f8OpPH/Dqez46z1WyUaFoh8og68YM+TOWkzB/NPiDKnu9lK06Gxypi2g7cBOqt95lrb9Ozj033/YHtKa4RBt+3fg8mUx8fT32Y5jRsK0Hdg5aKmFUGsjcz78ZZZ84WcUnHQGOTMX4c4pTNpec7ho3bdtUGP1pH7L22y873aCzXVI0yAa9FP57IPseOIXQ+5bcWKgXDqKMYMQgmW33U3VO89y6I1/gBCUnfNBihadw9vfu47WPZsRmo40TasMoQ0S2Z2Z6ysqRXd7Ewy75nSTXT6P1sqtscPXAU2S3FmLEUJQvORcipecC8DzN61I+og0onhSvBD6S8VT98YVQgdLennfi39m1lU3q4NiRZ8og68YUwhNp/SMyyk94/Lua5sf+C4tuzfGxeIL3WFF7PRyZzg86WRNnoOUkvz5K9CcLstI9nC1CE1j+pWfpn7LW3TW7O+/a0cIHO40Zl/9xYRbvuLJtOxptX0svbi8W8RtKPjrDia9F+5oxpunqoYqUqNcOooxz6E3n05IvLLi660kJ6E70N1pOLzpnPKlX1Gz6gVe/PzZvPqlizFCQbReK99ooJNXvvge5n3sq0y56KNozv6VHvQWTOKs7z9FxsSpCfdmX32r7fmDN38Cy7/6h/5/2BQke2kI3YE7K39YxlCMb5TBV4x5kmbZSlhxx4PMueY2Fnzi61x47xtEg11s/N3XCLU2YEYjmJEQZijY6zlJtKuTtXffypxrbuOi37xJzoyF6C4vpChBGKivijtf6EnB/BUsueXnpBdPBsCZlsnMD3yW99z9Mp5hMsazP5T4UtHdXmZ+4HMDUvBUnLgoaQXFmGflDz9Fw9aV8REwQpA/91ROu+OBuLZvfftjNFes61/HQsPlyyKzdCYzP/A5nL4s3r3rRkKtDUkfyZ29hDO++WjKbqWUIxZ337xrA9se+wntB3bizi5g5vs/S9lZV47IWIrjk1TSCsrgK8Y8nbX7efOb12CEQ5iREJrTjeZ0cea3n0hwr7z4+XMIttQNeAzd5WHR535Ec8V6Kp9/mGTx+ZrDyQX3vo5byRorxihKS0dxXOMrKee8nz3PgVf/Stu+bWSVz2HyeVfjzspLaJs1dR7BdfUMtJShEQ6y9aHvc9YP/k71O/9OHjevaQmRMgrF8cKw+PCFEH8SQtQLIbYmuX+OEKJNCLEx9uubwzGu4sTBnZnLzCs/zbLb7mHm+z9ra+wBq2SgO/HwtD+EOlrQdJ1zf/JvsqefZD+PrHwVDaM4bhmuQ9sHgYv7aPOmlHJh7Nd3hmlchSKOrLJZLL/9D+TNW44jLQPfhKmc9KlvMfua28gonUlawaSkB6+apuPwpOPyZbP8/35HWsHE7raaw4Xu9rL4s3cpXRzFccuwuHSklP8VQpQPR18KxWCp3/w2mx/4NoGGGjSHk8nnXc3cj3wZzWGFXc684ibAkmXY8sB34hKyNJeHsvM+1B3t4vJlc86PnqHq7X/RuH016UWTKT//Q2p1rziuOZY+/BVCiE1ADfAVKWVCrrkQ4ibgJoCysrJjODXF8U5r5VbW/PwL3f51I2yw/9W/EOlqZ9FnfhjXtvTMKwi11LPr6d+BAGkYlJ5xOfM+8r9x7RyeNMrPv4by8685Zp9DoRhJhi1KJ7bC/7eUcr7NvUzAlFJ2CiEuBe6WUs5I1Z+K0lEMhNU/+wKH171K78Nazeniwntfx5WRk/CMEQ4RaKrFnZWPM813jGaqUIwsox6lI6Vs7/H754QQvxFC5EspG4/F+IrxT0dNJXaROZrDRaCp1tbg6y43vpLyAY3jrzvI7qd/R/PujaQXT2bG5TeSO3PRIGetUBxbjonBF0IUA3VSSimEOAXrsHh49GIVCiBn2ny66g4gzfiiJ2Y0Qlrh8LgHO6orefMbVxMNB8E06KyppGHrSpbe/DOKl5w3LGMoFCPJcIVlPg6sBGYJIaqEEJ8SQnxGCPGZWJOrgK0xH/49wLVyrGZ8KY5LZlzxGTRnouzA1Is/Pmzumh1P/JxoqCtOsM0MB9n8p+/YV+pSKMYYwxWl8+E+7t8L3DscYykUdmRMnMoZdz7Ctj//hJY9m3D5spl22SeZcuFHh22Mpoq1CQVOAMIdLYTbm5PmBigUYwWVaasYN2SVz03Q1hlOXBm5RGKlFuMQAoc3fcTGVSiGC6WWqVD0kxnvuyEhaUtzupl42mW20sgKxVhDGXyFop+Unv1+pl36CTSnG4fXh+Z0UbzkXE66/uujPTWFol8otUyFYoBEA378dQfw5BQpv71izDHqcfgKxXjC4U0nq3zuaE9DoRgwyqWjUCgUJwjK4CsUCsUJgjL4CoVCcYKgDL5CoVCcICiDr1AoFCcIyuArFArFCYIy+AqFQnGCoAy+QqFQnCAog69QKBQnCMrgKxQKxQmCMvgKhUJxgqAMvkKhUJwgKIOvUCgUJwjK4CsUCsUJwnAVMf+TEKJeCLE1yX0hhLhHCLFHCLFZCLF4OMZVKBQKRf8ZrhX+g8DFKe5fAsyI/boJuG+YxlUoFCcwMtCIrFuLbNmFlOZoT2fMMywFUKSU/xVClKdocgXwsLTKa70rhMgWQpRIKWuHY3yFQnFiIaWJ3PUXqFsLQrcuOtJg4RcQXlWFLBnHyoc/ETjU489VsWtxCCFuEkKsFUKsbWhoOEZTUygUxx11a6FuPZhRMELWr1ArctufRntmY5oxdWgrpfy9lHKplHJpQUHBaE9HoVCMUWT1m2CGe1+FrnpkoGlU5nQ8cKwMfjVQ2uPPk2LXFJekO1cAACAASURBVAqFYuAYvY19DCFsXgSKIxwrg/8M8D+xaJ3lQJvy3ysUikFTsAg0myNIzQVpRcd+PscJw3JoK4R4HDgHyBdCVAF3Ak4AKeVvgeeAS4E9QBdw/XCMqxg6gYhBRX0HdR0h0t0OZhf6yE93j/a0FIqUiNJzkA3rIdhqreiFDkJDzPkoQowpT/WYQliBM2OPpUuXyrVr1472NPqkIxRlU00bdR1BnLrGrAIfMwt8CCFGe2p90hU2+M/OOiKmiRn7GuhCsHxyDmU5aaM7OYWiD6QRgfr1yJad4M5FTFiB8OaP9rRGHSHEOinlUrt7w7LCP1Hpihi8UFFH1JBIIGwYbKptpz0YZVlZzmhPr0+2Hm4nbJj0fOUbUrLmUCuTsr1ox8FLS3HiInQnlJyKKDl1tKdy3KD2PkOgor4Dw5TxBtOUVDb7CUSMUZtXf6ltD2K3vzOkxB8e+/NXKBQDQxn8QRKKGhxo7up2hfREF4K2YOTYT2qAuB32//xSSly6Wt0rFOMN5dIZBKGoyfM76wlE7VO5TSnxucb+X+2cogxWHWzB6PHW0gQUZXhwO/RRnJlCYY+M+JF7n4GGTdaFwkWIqe9DONWZU39QK/xBsKuhk1DU3uUhgHyfG5977Bv8smwvcwp86AKcmkAXkJ/u4rTJuaM9NYUiAWkayPW/tLJsjaD16/Bq5Ia7lY5OPxn7VmkMUtsetHXlABT6XJw55fjQ8hBCsGBCFrMKM2gLRvA69ePiRaU4QWnaCuF2kD0WW9KAUCs0bYf8+aM3t+MEtcIfBF6n/V+bLgRLS3Nw6sfXX6vLoVFwnOxKFCcw/lpLM6c3Rti6p+iT48syjRFmF2ag9wpZFECmx0Gmxzk6k1IoxjvefNBtkgJ1F3iV9lZ/GLcGP2KY7Gro4I29jaw91EL7MEbNFPjcLJmUhUMTODSBLgS5aS7OnpY66UNKSVNXmMomP43+EGM16U2hGJPknxwz+D0XWwJ0j3Ln9JNxuYcPR01eqKgjEDEwpPX1qGzq4vQpuUzM8g64P1NKoobEqYvuDNpp+T7Kc9NpDUZw61qf7pCoYfL63kaaA5Hur2uG28F50wtwJQmPVCgURxG6Exbfhqx4Alp2WxdzZiJmXYuw0dWR0SDywItQvx4QUHwqouw8hO46thMfQ4xLg7+jvoOuiNF9sCqxkolWHWjhygWefmeQGqZkQ3UrlU1+TMDr0Fk8KYvSbCsETNcEeWn9+/JsrGmjqSscd9jbFoywrqqFFeXHxyGvQjHaCE8O4uTPIs2o9Wc7ATViET0b7oauBpBWWw69gmypgEW3dC/cZKQLue9ZqN8AiFiY53sRjoEvDI8HxuXS8lBrwDaKxpCSjmC03/2sPdRCZZMfQ4KUlpTCyv0tNHTGHxxFDZPa9iANncndNPttkrRMCQdbA8q1o1AMEKE5khp7AJq2QbD5qLEHMCPQWQ1te4EeL4XadyHaBVE/1K5Ebrhn3IZ5jssVvjNJlqiUEkc/M0jDUZP9LYlG2pCSrYfbOXe6dUi0r8nPmqpWNKydhFMTnD0tn5xeK38jiVE3pfWcymtVnMhIKaFtL7JuHQCiaAlkTRu0CKHsOGgf0SMNaD8I2dOhebsV0tk7zDPYDM07IG/eoMYey4xLgz+zwMeaQ61xGaQCyPI6Se9nBmwgYqAJgWljqDtD1qqhLRCxxpGSI1+ZqCl5bU8jVy4oiXMdlWR6qGlL1K4p9LlGTKTMH46ytbadus4QXofOnOIMJg3iDEOhGGnknn9YK+1Y8RJZtw5KliNmfGBQ/QlPLlJzJRZD0RzgiSUWdlYnD/PsrBmXBn9cunTKc9KYmpuGJuiOpPG5HQNKiEp369gtygWQG1u972nstH0hGFJyuD0Yd23JpGxcDq07nFMX1k5kWenIqGp2haP8Z2cd+5q78IcNGrvCvLOvmR11HSMynkIxWGRnDdSujDfOZthyr3TWDK7TwsWg9ZYHEVaBlCMRPZ5UYZ7j81xtXK7wRSwBam5RBk1dYTwOnfx014C2hw5NY26Rj+31nfFaM5pgfnEmAKFe0sI9CRvxd9JdDi6bW8y+Jj/NXRGyvQ6m5qWPmGbNtroOIoZMkD7ecridGQXpOLRx+a5XjADSCCMr/w2HV1lFw7OnI2Z8EJFWODwDNG0H00aqxDQsX7xvwoC7FA4PLLwFueMR6KoHJPgmIub+z1Hff8FJsPefsXKJR35ShPUSyD9psJ9mTDMuDf4R0lwO0oYgYjavOBOvU2d7XQfBqEl+uouFE7LI8jrxh6NoQqAJbA5jJYUZiSsHl64xqzAj4brlPmJYjX99R8j2ZaQB7cFo9y5FoegLufWP0Lr36AFoyy7k+l/AKV9DuBK/zwNGd4LQoPdBqdCs1fYgEb4SxLL/Q4Y7AIFw+eLv6y5Y/EXkzsehvdK6mDUVMfsjqQ+Ej2PG56caJoQQTMv3MS0//ouys76DTTVtCBKNva4JZhf4SHP2bbybu8Ks3N9MZ9j6QcpNc3FaeW6/zxlSkebSaQ8lRiQZUuLtx9wUCgDpr4W2yvhoFyQYEWTNO4jyiwbXr5TQuhvZtMMqPG6HEFCwcFD9x3WT6qUU6YT0QvBkQ/7JiPz5x0W1usEyXDVtLwbuBnTgfinlXb3ufwL4CVAdu3SvlPL+4Rh7oEQME00IdG1w/6jtwQiba9pswz5LMtzMKsygJNOTso99zX62HW6nIxS/jW3yh3l5VwPvm1c85IPcuUUZNHSG46KDjkgfK4Ov6Df+Omul3RsZhY5Dg+pSShO57QForjhajxYAzVrtg7Xan/0RhDtrcPPuB+b+F+HgS5abCgkNm5H582HOx8et0R+ywRdC6MCvgQuAKmCNEOIZKeX2Xk2flFJ+YajjDZZGf4jVB1toD0YRAkqzvSwbhNDZwRb7GH9NQDBqsq6qhUy3k3nFmeSlJ25Hd9R1sOVwe9y5wBGsMolWTP9gMoJ7UpThYUlpNhuqW5HScjOVZHpYoaSPFQMhrTDR1QJWtItv0uD6bNh81NjD0bBIzQUzrrLcKbmzRyz5SZoGcu/TUP1m/A0zDI1boXUP5Mw42t4IQ9s+6zNnTTmui6QPxwr/FGCPlLISQAjxBHAF0NvgjxqdoSiv7mnsNrJSWslZgYjB+TMGdvAkkxzTmhJaApZeT0fI4HBHiDOn5sWt9g3TiuG3M/ZH+5F0DVN5wWl56UzJTaMzFMXt0FRRE8WAEb4JyIzJ0L4/3q0jHIgJpw2qT1m3NjFcEkBoCGc6Im/u4Cbb3/F3/cXS1LfDDCMbNyNiBt+s3wA7H4/tciRoTlhwEyKzbETnOFIMx6tqItBzb1cVu9abDwohNgshnhJClNp1JIS4SQixVgixtqGhYRimZlHR0IHZy8iaEpr8kQGXIuxvcW9DStZVtcZdC0SMpFE9RxAxIbbhQhOCTI9TGXvFoBEn3QjFp1jGDmElRC2+FeHOHFyHyQ5EjSBy99+QzTvjLkspkf5aZPuBbkmFwSAjfsz2A3B4bXyyVfzkukM1ZVcD7HzMejkZQStmP9KJ3Hwf0hj7JUztOFaHtv8CHpdShoQQnwYeAs7r3UhK+Xvg9wBLly4dNr2BtkDUPmJFWKv/rAFIGud4Xcwu9LGzvhNDSgQkNeIdoSibatqobPITNSWFPjcyxepeF1CQ7rJ1BSkUo4XQ3YhZV8Osq5FSDtm/LUpORTZtt1/lB5usqKB5n0TkzUF2NSC3/MHKiI25UuTsD6MVnNzv8WTEj9z+iOWqEQApdtCajihaZj13eLW9O0uaVpbuAOYwVhgOg18N9FyxT+Lo4SwAUsqmHn+8H/jxMIzbb/LTXTT4Q7YyCdnegevXnzQhi9IcL1WtAQSwq7GTUDTRkAtgZ10HR74yNb2SsXricWjMLPAx2yZsU6EYKwzLYWbObChZHku2slkpmxFk5TPI9GJY99PEbNgdjyLTihHpRf0aTm75PXRUWav6lMtIAdPef7TfiN9+JyAlRLr6NfZYYzhcOmuAGUKIKUIIF3At8EzPBkKIkh5/vBzYMQzj9psZBT4cvaJydCEozfYOOgQyx+tiQUkW80uymFuUmVAQRRPWd6svCSaPQ+O0yTm8f8EE5hVnDjp6SKE4XhBCoM34ACz+UvJGXfWw+i576QPTQNa806+xpP+wJZOQ1IVzZFI6LLoFbeLRcwmRN9c6SE6cAOTM7Nf4Y40hr/CllFEhxBeAF7DCMv8kpdwmhPgOsFZK+QxwixDiciAKNAOfGOq4A8Hr1LloVhEbqls53GF9gTwOjXSnTiBiDDhM0TAlzV1hnLpGlsfBrAIfgYjB7oZOREx/pzDdTaM/hM3CvxtdCC6bU4RT+dcVYxhpGlC3Bnl4DQgdMWEFFCwcumsnvRjpSLOUKnujOWIZsHaYEG7r3yChtljYp53PPTb/jElW5nBmefztvLmQORnaDxx1P2kumHAa4jiVXhBjVZp36dKlcu3aJCfpg6Q1EOHlXfUYUmJKaxWuC8EFswr77cff3+xn9cGWbpVLly44d3oBuWkuIoZJZzhKutNBIGLwQkV9UpVMsHR+zp9RcMyyXqOmpCoWnZSf7hqw3ITixENKE7npvkSjV7AQbc5Hhty/eeh12PdcvD9fc1lG2gjYP6Q5ETOuQpSc2nf/bfth469sVvgCipcjZl2d8mdAmgbUr7fE3HQnomQF5M4Z0z83Qoh1UsqldvdOqEzbtYdaiPRw5Jux+PR1h1o5b0bfNTFbusKsOtAS56YJG5IXKuq5Yl4xaS4HOV4XhinJ8DjITXMmFD3piSklnmOUBNUWjPDyrgZMKTFM2V285exp+cqNpEhOc0W8sQfr9w0bkKXnInwlyZ/tB2LS2Vao84GXrEgYRxpMuRSq3wJ/EoPvybPE0VIgwx3WYW/HIewd9xLq1iKFBjOvSmrAhaZD8TJE8bKBfbAxyglj8KWUNPjtt4j1nTZ+Qht2NXQm9cmvOdTKoolZrD7YQmNsnJJMDxMzvVS1BRK+cpqAIp+7XxIMw8Hb+5oIG0dnHzUljf4wuxo6mVOkDooV9siWCvtoGqQV9TJUgy8EovRc5KSzwYiAbu06peZA7noqcey0YsSS26xyh6nmvfVP0HEw9eAyAnVroGgxZE8b0uc4Xjh+U8b6QcQwqWzys6W2ndr2YMLB6hH6u8LtiiQ/+KnvCPLSrnoa/GEk1pqitj1IWzDCh06ewCml2bh0S6pZE9bL4PQByDUPBX842q3h3xNDSiqb/MdkDorjFKcPhM26UOjgTBu2YYTQEA730ZV20TKYeJbly9c9Vg5A9gzE4i8i7CSNeyADTdDZT9kHM4ysXz/E2R8/jNsVflsgwsu76zGltZp1aAI9JsjX08WiCSsjtT9MyPB0H/r2RgiB0Wv5L7FeEg3+MNPyfUzJS8cfiuJy6Lh7FC6XPc4UBuIblFJS0x6kqjWAU9eYmpduG2aa6phmbJ7gKMYKongp8sALNl8UAfkLRm5cIRDTLkOWnQf+WnBn9/+gNOKPHdT2J0lL2GsFjVPGrcF/Z39znCZ91JRoWBE7waiJEJbBLPS5OXlCaoGmrnCUqCnRU5RHdGiCQDTR4SOltFbXGVbWa0avw+H9zX421rQRiJi4dI25RRnMLvR1G/7OUJT11a3UdYTQNcH0vHTmFWciBPy3spGGzjBR00oA29PYyeJJ2Uzvpe6Z7tJJczno6LXK1wVMyR2+VZpi/CHc2TD/k8jtD8dWDhJ0N2L+DZa88EijuyHchjz0GtIIQc5MxITTEal2F+nFqVc5PdEc3YlWJwLj0uAHIgbtocQwLBOQAi6aXUh7MEqWx0FmiuicrnCUt/Y10RKIoAmRUgPHztgDIETS5K6q1gCrD7Z2R/KEDZMth9uRWGqXwVikTyRWaCVqSnbWd9AajDAlN63b2IO1ADMkrK9qpSw7DVePHYQQgtPKc3l1dwOmtFw5Dk1YIaWFvsSJKRQ9ELlz4LTvWT5xoVthjMdgVSzNKHLjvdbB65Eom9bdyH3PI+d9Aq3AvkiJ0F3IqVfAnr8m6dlhRWQKoPT8EdfFkRG/VU/A4bFkKRIqcR07xqXBT+UUEUCWx9lnGKaUklf2NOIPWbIMdqUM+4PPpZOXJOxyc21bQtimYUq217Uzp9DHnkY/UdPsVbUKqtuCNHSGuo19T4QQ1HWGKM2OVxrMTXNx+bwSDrR20RW2wjJLMj0jVk9XMb4Qmg5ZU47JWLKzGrnveWjbC9Egif4kE7Y/jDzt2winvTtW+IqRmjMxk1fokDcXkT3d+r8339LnCTSBy5e0v8FiHnoN9j0bOweJia+d/DnEIKp4DQfj0uB7nDpZHme3euURtH64MEJRk7ZghGDEINgPsbO+mJnvS+qX9ydRxYwaklDUpKkrUQ7iCL1LKPYk2SG0y6ExI1+t6BVjF9l+0FrV20YG9aJxKySLxQ80Yrv0k4YVCTTpLADMqv9aBhmsDN78BYjZH05wV0kzCg0bke0HIa0QUbSkT/lm2bYvlmMQpfs8wQhZeQ2nfXtUZJbHpcEHOK08l5d3NWBI2X1om+VxMqfIXuFPSsnGmjZ2NXSiC0FUyv67AUkuoZCbQggtw+1IeCmBtZ55dXc9xZleNJHc6NshYuGeCsVQkP7DyJq3IdRmSQwULukzFLJf/YY7IdQC3gKr7mzv+5XP9M/YI3tV4epxx38Y2bTVXqdHc0HGZKtd4xao/Hf8eE1bkRVPIuZ+PG7Ocv0vINxhtdVcyH3PwaJbU+r5yJp3Ysa+F2bYcvH00Nw/Voxbg5/pcXL5/GIOtQboChvkpbnITXMSMUx0oSWsuiub/Oxu8HcnY/UXXUCxz0N1R6Iwmke3pI4bOkNsrGmjNRDB69SZX5xBeW46Cydk8d/KRuwW651hA12zDnr7ms8RnSABnD1VJVIphoZZvwl2PhorLG5acsWHXofFtyEcfYRESgmdVVbpwIyybheJNCLInY9B42Yr1FKayElnI6a8N/5ncSBVtHLnJY7fXIHcen9s7gnZL+BwI4qXWQqavY09WC+Jhk3I6FXdK3i571nrJXVEOdMMWwJvOx9DLLkt+fyiXTZzABD2GkHHgHFr8AEcmsaU3HQihsm7B1qoabcy9zwOnWVlOUzoUZzkiNzxQDEl1Pvt//GiEnbWtbOppr17B9ARirL6YCuhqMmswgxOnpDF+upEXRBDwuGOEOfPKGD1wRbbnYD1WQQLJ2Tj0DVKMj0JInEKxUCQZhQqHo9fHZthS7a45i1E2fnJnw22IDf/FoItsaLkUWTZhWjlF1qKla27rYZGzJVZ9QbSk4OYcPrRTpy+vo2hcMCUSxGe7PjxpURWPGG/sgcoOAmmXYE88BJUv2G/+gZr7hE/HHHZNGyykUmW0HkIGQ0lfQmKgpORLbsTXyrSgKypqT/jCDGuDf4R3qxspMF/VOKgK2LwVmUTF8wqIMfrImyYKZOqUiEhTq6hJ1FTsqGmPeG6ISVbDrczo8BHQbobXWC7yndqGrlpLi6eXcSW2ja2H+6Icx3pmmBecRZT+plHoFD0SWc1tqtSMwL1GyCVwd/yB0vlsufzB1/GRB419r37PPgaxAy+7IjtDBKwIoNwZViuoOJl9oee4TaIdCT/bE3brCSuunVJ3UEAaDq4c47+OamvXSQvwA6W/EPNO5Zapxm22msOmHp56rDSEWTcG/yOUJRGfyTBD25Kyc66Tk6emMULO+tsI15GEsOQvLSrnuYu+9WIrglmFBw9YJ1fnIlhSnY1+K3vGTCnKIMZ+crYK4YR3Z08hj3FIaXsqoNAAwkvCzNsuYOSETPwUprIzb+zX93nzUHMu77vcEbdnTqT0IzA4XdT96E5LYPcc6ziZVb927gdgQbZ01PmIgjNAQtvRtautLT/NSeUXYCWn+iKOlaMe4PvD0fRbFbQEutlsLmmjVCyGPoRxISkxl4TMCM/nUlZR11OQggWTsxmfkkWwZiks/LVK4adtCLwZENXL+OtuRATz0j+XCSQfCWcykVzZKXeti/5Ya3m7FfsunB4kRll0F7ZZ1tbMsoQUy6x8g569lt+CbKt0sr4NU1rB+BMR8zuWy1UNm6Bvf+EI7Xxtj+AOeUytNJzBjfHITLuDX62x2nrm9cEFPrc7G3yDyj0MlVJw+FAAOdNL6AgSaSNQxP43OP+n00xSgghYMFNyI2/PqpTLw2YeDrk2yc6AeCbiO1PhuYAbyH4a+yfm3al9X8j5vLoRUdXmCeffJG9wa3MmDmLa665hoyMDCvrtv2A5aLJKD168DvY7F9nhqXTY/PSEroLFn0R2iotl5cnD3Jn9/kSkuFO2PnnxDOFfc8ic2cj0osHN9chMO4th8epMz3fx94mf1ymrEMTzCr0sb+lK2WJyyPoQuDQBSUZbva3JJFtBZwaRIawYdD7cAsmwx+OUtcRwqEJJmR5cGgnjj6IYngR3nxY/g0rdDDSCVlTLImFVGg6FCyCw6vpNvyaE1yZMOvDsOneXit9DcrORTuS5Zo1JUGz/q0t1Vx2+z8xTfAHI6R73XzpS1/i3w//hDNy98Z2FBKc6bDg01aIZNv+gX9gzRnTxU/+MyOEsBQ1B6Kq2bQV21wA00DWrUNMfe/A5zpExr3BB1g8MYssj4Od9Z2EDZOSDDcnTcjC69SZnpfO9rp220PTIwhgyaRspuWnI6XkYGt10tj4M6bk89rexqT92LmXemJIa1cyELbUtrG9rsMSnIqNc/a0/KS7BIWiL4TQBhQnLnc+AQ0bObrKF5a2/eIvobnSkYu/ZIU3tu0Ddyai7AJE4cKj4zk8yBlXwe6nwIzS0RXistv/SUcPt6c/EAJCXPbRW6h66lP4vLHVvBFCbvoNcsENYCavG21L3jxE+cWIjNKEWzLYbB24evMQ6YOQgZZ2oaEAZt8lF0eIE8LgCyGYnu9LEBUDmFucQXMgTHVb8i+KEBA2DJ7fWUdHKJoyIavOJh7/CDI2l74yuqrbAkzOtV4uuxo6qWjoJBw1Kcxws3BCVpz+T31niB11ndYLqEe/b+xt5MypeWR7nbhVCUXFCCL9ddCwoZfrQkI0gGipgKLFiPQixPxPpuxHKzkVmVGKrF3Jk/ffj5lkVWWaJk++uotPvXf+0YtGEPY83f9JCwfkzEBbcGPi5zENZMXj1gtMOEAaSN8kxEk39ZldG0fuPOAfidc1J6Lg5P73M4wMy75fCHGxEKJCCLFHCHG7zX23EOLJ2P1VQojy4Rh3MERNk6auMP5wFCNW8i/L40ypv+N1aGypbac1EMEwZUof/o56u7Cyozj7OGiVwLsHWwhEDNZXtbKpph1/2CBiSqrbgrxYUY8/fDRaYG+j3/aMImJK3tjbyNNba1lzsIWxWspSMQ5o34e96yKMrHodGepn/VlA+Cagzfgge6pa8AftQyf9wSh7a3r3KVKHZMahQdESxLzrbe/KQ69Zsfdm1HqRmBHoOIiseLLfnwOw8gSmXGa5to6YWs0FJSsQmZMH1NdwMeQVvhBCB34NXABUAWuEEM9IKbf3aPYpoEVKOV0IcS3wI+CaoY49UHbWd7C5th0B3ZLCfblY0l06gtRtetJXs5w0Fz7D7KP0IVQ2+tnT5E9oEzUlO+o6WFpqxQkbCQkhRzky533NfnxuPamshEIxJJwZyQ+eOg4hV30P5l1vSTT0k+nTppLuWWdr9NM9Tqb1ljQ3I5AzO5YHkISMcig7H5E3N/WBa81biQet0oDGLUgjMiCJCa30HGTubGTdepBRRMHCEVfnTDmfYejjFGCPlLJSShkGngCu6NXmCuCh2O+fAs4Xx7gKcE1bgM017RimTJAUToVVmHz4/G1twQhlOWlcMruQ4hQ+9rrOkG2FLgk09SjVODknrc/sWkNCRUPqnYdCMWhyZ1srV1ukJUOw/SHMaBDZtANZv9GSDE7BtZ++Ay1J4IGmCa45b2b8RWd6bCWdhLwFiJM/g1awoO8Qz6RhpMn1e1Ih0ovRpl6KNu3yUTX2MDwGfyLQUwCjKnbNto2UMgq0Acemvl+MHfUdg5JOSKVKmYpkJtgfNthY3coLFQ0pC6qku3Xb+Qogw3N0YzYxy0uhz92n0Q9HlUtHMTIITUcs+oIVfpnsmy8lvHMncvuDyIrHkSvvxKx6I2mfmRPn8ezfHyMjzU167MwqPc1LRkYG//7xh44e2B4hGogdGiehZSfynW9gNmzq+wPlzLL/HN6CgfnwxyBj6tBWCHETcBNAWdng3oSGaVWY8ji1uMPKwFBiJQdISaabkkwPG6vabFU0jdgBa22Sg2IBlGZ5qe8IJewuJFCe42XtoRYaOkOkux3MLfIxIz+dqrYgh1q6CNv4ivJTqHYqFENFpBUhp38Atj9o+b17Y5dUVflvZNZU2wgZgDMv+iA1dRfx5JNPsmfPHqZPn87VF59KeuUjiatwMwKhRBmTuPsAOx5FZk5BuJO7N8XU9yFbdlm5ATIKaFZlrFnH3As97IihHuYJIVYA35JSXhT781cBpJQ/7NHmhViblUIIB3AYKJApBl+6dKlcu3btgOayq6GTTbHDHFNKJmR6WDE5F4euse5QC7sbB5ZkNRjSXVYGbHvQyvB1aoLQIHYJbl0j1LtILtaWTGhWwt+RXnUhWD45h7KcNOo7Qry+txFTWofLAkum4YKZhUkrbykUQ8Ws3wA7H0suXGaLsIqVpxdD/XpLp37CGVC4KGkNCdlZjVx/dz8llJPg9MHUyxDFpyYfJ9yJrHnLCiNNK0JMOsvKT0jWtvotq2BLWiFi0tmItMLBz2+ICCHWSSmX2t0bjhX+GmCGEGIKUA1cC/TOOX4GuA5YCVwFvJrK2A+G6rYAG2va4pKratqDvHughTOm5jG3OJMDLQFbI9pfvA5BMGofpSOA6flpVDYHuudgSgZl7IGk8zS7/3MUQ0rWVrUyKdtLYYabC2cVsqOug7ZghNw0F3OLMtA08BSpYAAAHQdJREFUwbpDLdR2hPA6deYU+piQdXxvTxVjAymlFRJpa+yFlZSFsLkvLbnkHiGdsqMK2vYiZn7IfrD0CZaIWrBp8BOOdMLuvyMDTUmTn4TLhyi/OOG6lCaEWq26vs50SyF03U8hGrJ2A617kYfXwEk3WVW1xhhDNvhSyqgQ4gvAC4AO/ElKuU0I8R1grZTyGeCPwCNCiD1AM9ZLYVjZXteRUHPWlFDdHiAUNfE6dS6ZU8T6qlYOtibPlE1FyJDkeHSag4mHuJqw/OTJYodHmqghCUQM0l0Osr1OVpTndt8LRAye31FHOFYbtyMUpckf5uSJmcwqyBiV+SrGEUYweUik0GHp7bDmh/b3jTBxKxgzDIdXIUvPQ3gTj/ks6YcbrVW+Mbif4+5xql5Hlp1vJX1Jack/hDstqQYbNUvZtMOSX452WXr+OTOtw+pIT9170wpH3fkEnHpH0h3EaDEsPnwp5XPAc72ufbPH74NAklf28BBIIm+sCUEoauB2aHidOqdPyWNZ1GRPUydba1Nn2PbGlNgae7D88gcG8CJxCOtrPlzvB4nEqdufwW+v6+guhH4EQ0o21bQzLc+nNPQVQ0NzxRKUbNwsnhy0tHzMkhVWuGMCNjtZoVm6Nd48K4a/fgMyGoCMMiuZy+GBudfBlt+RtMBIf5y3QodAI9KVYen4B5p66PhfgFZ+UXdT6a9FbvtT/C6lZVcs2dFmrFCLpanvGlslRcfUoe1QKPS52dfclXBdAOmu+I/pcmi0B6MDMvbDSZbHwQUzC6ltD/LugWYgeXjoER+8wPrRmJLjZV9LIG43owmYmOlFSsmW2jbqOkKkuxzMLvSRk+bicEfQ9vBYAO0xt49CMViEpiMnnhGTEO5hEDUXTL7gSKOB9AguH7JxG3L7g5ZR7Q6H1JC6M0lFK+s+2dOsZDDTJHnxUazEKneWVZzFXxff9uArVnZtTMpYVr0RG7MHfckjDENJyOFm3Bj8+cWZVLUGiPbIhNWFYOHELFsZ4eq2IWwHh8ipZbk4dY2ynDSKMzz8//bOPDiO87zTz9s9F+bAfRG8IZLgLUqiDoqSrJK9XoXU4Vw+NocTy9KmVtmKq1KbeMt/JLvZrVLtOru1R6oSV5yNau1o6drYsWNRtiVbirS+qIuWeIrgJRIHcRDHAIMBZqbf/aMHIIDpAQYYAENivqcKRcxMT/fX4MzbX7/f+/5+HcNjdA4l6RgamxH4bREe2VqPqttw1RAJYFtCyGdzuieOJUJGlaZokL0tlRzNpm0chb7RCa4MjnFgUw1hv82wRwOLo0rIZ0TWDMUjmw+7blldP2XKGGTTo0jT3e4GdoC53Z+n9gR2EK3cBD/9U4+8vzOvI5bc/q8gNYL2HIcL/5hngdeG+t3uvka7c8flTKAXv+tq8YuVNUX3uhvx4dbnZ2Y+V7cTsW8+LatVE/CjQR+Pbm/iZPcwPSPjhAM2O5sqWVOZa5QMbqon321fIR/LuZjrhrLCb1E3rUQy4HNtGDfXRrh0PcHJ7mESqQy1YT/7WqpnbDvJnpYqtjfFGEqmCPttwgEfb14ZYDx9I23jNpUpb14Z5MDGGnpHJ3LuChqiQcKBVfMRMJQQsWxk66+grY+5Zt/BKtcAZPL1pv3oldc8rAKnYfkhWIPs+TwMXULnFDzJh6KJXuj7hXuxaNrvKnjK7EVjB0Y6XQtCsQGPBefRbvTEV2H3U1C9xVXi9Gq8qt8Lfe9nvXozEF2HbP/MIsa+/Kyqb3s06OPejbXzbwi01kU42xOfMaMWoDEWpHdk3DNi11b4GEpm5m3gaowG6Bud8EzTNETyX/U31YbZVFuY9Znftqiftq+u4aTnRSbtKNGgnzvWVnG840bJakM0yAObVrT3zVAGiB2AWYutqg4MX3IDYiZfp6q4aR+xXaORRevaR+Gt57LfX3WP2XiXO5u/9D1IdN9QsRzrgXYPcbMbI4eBc9B/Eln7oFt6mUowNR20AtB8L9a2X0WTA+64QzULVtZUJwM977jVPWIhLQegfu+yLPiuqoC/EHY3V9I/OkFfVqZABCr8Ngc21nJ1cIx3O4ZyAvtQMo3ftghaFmOpjKfopS3C7S3VXBpI5Gjw2wJblsmSMGBbjHoI+6sqfkvYWh+ltTbCcDJF0G8T9hsFTcPKoKeeh/7T89TOq5teSXShp78OmxeqFZ8NjrOrhZyUW/ZZs9UN8LPz7k46O3s/752TdybQ3l9g1e+B/f8GvfQ96D/l2j2uexhZc6979FANhGpy3z8PqureRQy2T/19dOgCNJxEdszvqLVQyjbg25bwyNYGricmGBhLEQnYNEWDiLhesrXhAK+c65lRRZNR0IzDzvoY2xpi2OJq1Ezq7FeFfNy1zk3D1Ib9VPgtzvaMkJxmofhqex8VfovdTZVsqotgW8Kl66O81zXMWCpDNOjjjpaqBdfIb2+McezDgZyLVMC2pp6zLaHGLNAaVhCNX3UD5EIaspwJdza+87fh5P+atWg7C7GhosH9fbaB+vT99byTJ3XjuO/ZfBguftcj5SRTdxsSrFr6btvBczOC/dR4e99F1z/sbdZeBGUb8AESE2ksETbXhrM5/ZlYIjizAqij0DGUZM8aV61vV3Mlu5orUdUZt2Aiws6mSqIBHz/7cICMo1MpnkTK4c2rg5zpG2FrfYTjHcNTQXk4meaNi/3cu6GGTbWF3w1srKlgcGwiR545mXb43pkeDu9oImRm9YaVZuj8vP4PnmgGCTfBgT+F3l+gV/8fJDxsEkVg1+/C218m/8qbuKkex+OiIT6o3OymbC7/IFcWwvIhzfcVNmRVtPsYXH3N1fap3Y5senROtzC9ftb7zkfVLftc4oBfliUayVSGVz7o4R9PdfPyBz188/1OLl2fqd4XsCXv53QomeKH53rpnmZ2MhnsHVWGkymS2b6Akx4NYZA1UU+mOd45nDMrdxR+enmA1y/0kSqwM1hE2NYQ81zmSjsOH/QZtUxDCfDHsp22C0UhEEX8EaTlfmTHZ7zVMJ2MW7PvFcwnEcuVb2jYM2sf7uxd1j2I2H5kzzOuR64ddH8sH2w+VLDCpV74Dpz7ezeXPz4IXcfQt76MTsyh0++PZCt9PMbs0fxVLGU5w/+nC30MJFIoTM3gj304SCzon6qKiYX8xEI+hsZSOTeJjrpOU/3nJ7hnQ/XUTPxi/yhvdwyi6u63KRZibCL/B1HB82IwyWSd/oOt3hoesxkcm8BnCSmPjuPekblL2QyGZaF+t2tbuCBcjZ3pZY0SW4+u/QhceWXWtgrt33QD+mhX/l1e/r5bl990BwycdaUQatuQ1seRgNttLtWtcP+fwfXsekNN29Rr86ETI9k+hOnfdwfSSbTjDWTzIe8zbboLvfRSbiZKZG7T+EVSdjP8oWSKobF0zt83o8qZnplX4oda64gGffiyjU+zyajyztUhHFV6RsZ588ogqYyrt+9o1u5wnpX2uV511NUDGk8XpscfCfo8O3cFqAzefE0ghtWP2AFk3+9DqJa5P+3TUWTrr+Y+nU8/RyyIzeEgpRl3QVhT0PMusv+PsB58DmvX7+YIoontRxr2Ik37Cw72AIx0eM/UNe1W+uRBglWu9aMdunF34Y8ie3/P7SheYspuhp9MZfK6XCVmyTNEAj4O72jieiLFq+29OTNncMsekymH09dy9fYddQ1U7DzHs0VYWxWiYziZd6bvSkM4BfnSVoX81Ib9OW5aliW0Nc7f4q2qXB9LEU+mqQz5TAdumaNOGnqPo73vu+mVlvuR6GyriwJIj2VnvgXm8i2/t0lJvs7VzDhcK1RZV6D3PWg5UOD2BRKqztN5K5BHZXNqi9odcPA/wPBl9+JVudFt9loGyi7g11QEPOvoLYHmWO4VVUSoiwSIBGwGPbpVFSVgC4k8qRtbhHs31nDp+hgdQ2No9lgCbKip4J711ZzrH+V4x1De2flsaYi5eOi2eo5dHqBj2O0kDvtt7tlQM8P43ItUxuHV9j4Gkym3cUyhLuLnI7fV48vjPGRYvaiTRt/9H26axJkABO0+hm79NaxsKWJB+xkfQt/7q4XJGUe9c+bSfB/aM9ssffJABTpR6fyduotBwk1odB3EP5wZ+C0fsv7h+d9v+VxJiGWm7AJ+wGexsynG6Z6RqVm1JRD0WWxryD8L3tVcyc8uzyx7tAU21obx2RaNsRDDyZGcOgFH3QvJ+uowjirX4uOMpTLURwJTQbitIcbaygpeOtNNZpbOfT5piLznZ1s80FpHOuOQdpSgzyqogeOdq4MMjM28M+gbneB4x9CUf66hfNDuY9OCPUxaFXLu/6KN+wqWDdCun7PgvvVEJ+pkcmb5Ut2Khpth5EqeNxaACNTuWPz759r1nqfR0//bra4RC3whZNunFndXtEyUXcAH2LOmiuqKAGd74iTTDmurQuxojBGcQ1dmQ02Y0YkMJ7pdVx1HlfXVYfavc4PhzqYYl64nZqhS2pawuzk2pWJpieSVeogGfRza0cyJrsKkIebDZ1sUkAUC3FTOpYFEzh2Go3DxesIE/HKk97j3rFxsV2Kgtq2w/YwPzl1B44U6kLjmXZJYjPqkFYCW+5FI0+L3MQfiDyN7/yWaSrhprFDNsqVmFktZBnyA9dUVrK9eWHPTjqYY2xqijEykqfDZBKZdICr8Nr+0vZET3XG640lCPpsdTbEFHSMSKFwaYqnJVyw0uw/BUCbY+SYauiDZA6nZgl57G5wFpFE043ayelHTlm1UWkAjV0UDVG1Gmu5GarbOf/jRbohfdTtnq1oXLHEg/vCylFQuBWUb8BeLbQlVefLh4YCPezZ4z4Y1W8nTHR8nYFtsrA3fNPIGIkJjNEDPSO6MrsljXcOw+pGWg+j1M7mzfDsElXNUxMymfi9UvOKaixSE5YqP5ZEpkDX3oR2vw/jQjVy5FXDTNH15DMqTA8jtzyKh/A1Q4Gra6Knn3bJMEUAgWA23PzunB+6txM11v7HCjE6kGRlPs8Ruizk4qrxxoZ/XL/Rz6lqc97qG+O7JbjpLKNE8m7vX1+C3BTs7mbHFXQ+4a93cXxLD6kRq22DDI26p4WQj0mS54ALSFGL5kDv+YI47hkksN3BHmpFdn8u/P18IuesPYd3D7sw9tgFp+ySy63egKs+ip2W7zVlkg3rfCfTq6+jQhRnffb36WrYGP+U6cWXGIdGLnvlawed7s7PqZviDQ8P85d9+jXPnzrGjbStPf/Y3qaqceXUeSqb48cV+RsbTgBDyWxzcVOcpRbwUfDgwxrWRcdLTvG5B+cml6/zynpYFLcouF5UhP4/taOZ8/yiDYylqwn5uq4vOua5hWN1Ymx5FWw66KRRfGKq3eJdLzoP4gmjzva7j1ezSRfFB6xNQUefOwCMt86ZQxB9Bbnscbnt8xvMaXeeajnstEk/6z77737Jlopls/f56dOdn4eKL0P1zj6M5rk9tKuFpe7iUaCrB8HtHOPKNI7RfGWDL9t18+tk/o7Ju6eQVZLlnt4tl//79+tZbhdbWuvzgR6/xiScex3EcxscSBCvCWJbF0Rdf5OGPPAS4na3fPtGVYxLus4Qndq1ZcIBLZRxGJtJE/L4ZOf3pvNbeS1c8N4fpt4QHW+tM2sSw6tHUKPrWl13bP2fCXfwVG9nzeaRm29IcY7QbffvPc/P7gSrkwJ+gx/8iO9OfronuA1/IvQjkc7ASH3LgTxbWiLXQsavDG3/9LI994as4jjKaTBMJ+bEs4cWXvs+DDz1c8L5E5G1V3e/1WlEzfBGpBY4Am4BLwCdVdcBjuwzwfvbhh6r6RDHH9SIej/OJJx5nbPSGZsz4mGt5ePjwYa51dxGNRrOuUh7aNgqXBxJzlmbO3F55t2OI9r4RJCuy1lob4a711TlCbPlmLDrHawbDakL8Ebj7i2655+A5d0bfcjCn07WoY0Sa0e2/AWdfcJ9QhUAlsvdpNz0zfJGc5i9NQ2oenalQjSu+tozEL7/DY1/4G+KJGxer0aT7++HDh+nsukY0WvwYir1f/yLwQ1XdCvww+9iLMVXdl/1Z8mAP8HcvvIDjeNf7ZhyHI0eOAG43rVflSUaV0Tl0b2ZzuidOe/8omaz94GQJ4/tdwznbttZFPI3CLRHqZ6WRNDuOZB5TdoPhVkV8Qax1D2Lt/hzWbU8uabCfxGrchxz8j+5aw51fQO79ktsUdeF7c7tteY/YFVfb/hvLPjE7cuQFnDylck4mMxW/iqXYHP6TwMPZ358HXgP+uMh9Lor29vapGf1sxscStLe3A1AfCbj/ebOCvs8SGqKFe1Cenda4NUlGlQ96R9i7pnLGB2RdVYgN1RVcHhhD0ak7gIda62bcDfSMjPOzy9dJphwUpS4c4P5NdYQDN0c1j8FwKyCWD6o2Tz3WoUvQ/ZM8W1tuRU5OOkegbhey9dfmre5ZCto7BqZm9LMZHRufil/FUmzAb1LVSYm6biBfR0NIRN4C0sBzqvoPXhuJyDPAMwAbNhQmSTpJ27ZthCrCJD2CfkU4zJYtWwCoCwdojLgliFPGIAKVQR8tC2hymsgjWzxpoj59PiAi3LuxlrbGFN3xJAHbYn11xVRDFrgVQ6+d75txEekbneCH53p4bGezSf0YDHOgqmjnj+Hyy67rVbgZ2fIJpGZbtg8gz927Lwy+ACQHubHY6+rny87fdi0bV4Atu+8jEvqaZ9CPRCJT8atY5l20FZFXgGaPl74EPK+q1dO2HVDVnAJaEVmrqh0i0gr8CPioqp6f67gLXbSNx+O0rF3LSDxXezoai9HV2TmVA3OyM/EL/aM4Cptrw7Q1RhekGfODs9foT+T+51SGfBze4fXnmpv3Ooc43RPPaYDyWcJDZmHXYJgT5/LLbrCf3jcgWT/b+MWsG9YsxAfbfh2p24me/QZcP+mm+Gu2uaWeoZVrgozH46xd20I8nrueEIvF6JwWv+ajqEVbVf3YHDu+JiJrVLVLRNYAHn9VUNWO7L8XROQ14A5gzoC/UGKxGC8dPcqhQ4dIpTMks1U6IsIf//fnmbBuXKktEbY3xtjeuPhV9zvXVfOj9r5ZnrXC/kXWrcfH03m7XWereBoMhhuok4YPX8ltEtM0XPMqtcwigtTvdss89zzlmq1DSeQQYrEYR4++xKFDh3Ach9HRUSKRiFtlePTokizYQvEpne8AnwWey/777dkbiEgNkFDVcRGpBw4C/6nI43rywAMP8Oap8/zXv36erssXadqwmQMff5xQOMLr5/t4cveaJUuN1EeCfHxbIye6hxkcm6Ay5Gd3c+WiJYUbo0FPmWRVN5dvMBjykBpZ2IKs2G4N/rZPutVDk0+XWPfmgQceoLOzkyNHjtDe3s6WLVv41Kc+tWTBHooP+M8B3xCRp4DLwCcBRGQ/8Huq+nlgB/BXIuLgVgU9p6qnijxuXrrGhY88+emc51OOcj2RWtLmqmjQ5u711QTswhQp52JzbZjTPXHGUpmpmb4tsLaqYl5pY4OhrPFHCw/4/iiy/hFovCOvfEMpiUajPPXUU8u2/6ICvqr2Ax/1eP4t4PPZ338C7CnmOAthLstAr/r7xZDKOBz7cICrWWmECr/NPetraM6z6NsdT3Kia5iRiTS1FQH2rKmkZtas3Wdb/PO2Jk52D3NlcAyfJWypj7C1wL4Ag6FsiV8t3Cg9WINseGR5x3MTs+qkFTbVhulPTHgG/qVKjbxxsZ/ekfGpmfjoRIbXL/Tz8bZGqitmzsY/HEjM0NHvSCXpHhnnY1sbctI/QZ/FneuqudPo1xgMBaOdP6YgzX0rgKw9uOzjuZlZdUIpm2rC1Ib9U41OFu5i6oGNtUuiWRMfT9M3LdhP4nh44qoq71wdzLmzyDjK8Y6hosdiMBiAtHf/DQCW3xVls/xQvwea71m5cd2ErLoZvm0Jj2xpoHMoSedwkpDPorUuQjS4NKc6OpHGEskJ4grEZ1kgpjKao9kzyfXEAizfDAZDXqThdnTgXG6VjtjQ9i8QZxwqNyGRhZdLrzZWXcAHt+xyXXUF6xZocFIIVSF/Xk/chujsvLx4dvUChG4SLXyD4Zan8U7o+PEM/10sH2w+jNV0R6lHd1OxKgP+clLht7mtLsKF/sRU4BfcO4u2WXX9lghb6yOc6x2d5YUr7GpaPuU9g6GcEMsHd/xr6HkH7TkO/gjScj8yTV7B4GIC/iK4a101sZCPD3pGmMgozbEgt7dUUeExa7+9pYqMo1zoH50q3dzdXMnmukjOtgaDYXGI5YPme5Ayz9HPhwn4i0BEaGuI0dYw/yzdEmH/+hr2tVSRTDtU+O2bwvDEYDCUHybgrxA+2yJqr7qiKIPBcAthIpDBYDCUCSbgGwwGQ5lgAr7BYDCUCSbgGwwGQ5lgAr7BYDCUCaZKx2AwrHo00Yt2H4N0AqnbCbU7Sq5/XwpMwDcYDKsap+ddOPN3rma+ZtDuN6GqFfY8jVjlJXFSfpc4g8FQNmhmAs68AE4KNGsV6kzA0AXoPV7awZUAE/ANBsPqZei8a2c4G2cCvfbWyo+nxJiAbzAYVi8yR9baKj+v6KICvoj8uoicFBEn62Obb7tHReSsiLSLyBeLOabBYDAUTFUreOXprQDSct/Kj6fEFDvDPwH8CvB6vg1ExAb+AvglYCfwGRHZWeRxDQaDYV7EspE9T4MdAjuYdcDyQctBqNle6uGtOMWamJ8GpmR/83AP0K6qF7Lb/h/gSeBUMcc2GAyGQpDKTXD/v4f+U5Aeg5qtSEV9qYdVElaiLHMtcGXa46vAvStwXIPBYABA7AA07iv1MErOvAFfRF4BvMwgv6Sq317KwYjIM8AzABs2bFjKXRsMBkPZM2/AV9WPFXmMDmD9tMfrss95HesrwFcA9u/fn2sEazAYDIZFsxJlmW8CW0Vks4gEgE8D31mB4xoMBoNhGsWWZf6yiFwFDgAvisj3s8+3iMhRAFVNA78PfB84DXxDVU8WN2yDwWAwLJRiq3S+BXzL4/lO4NC0x0eBo8Ucy2AwGAzFIao3Z6pcRHqBy6UeRxHUA32lHsQysprPz5zbrclqPjco/Pw2qmqD1ws3bcC/1RGRt1Q1b/fxrc5qPj9zbrcmq/ncYGnOz2jpGAwGQ5lgAr7BYDCUCSbgLx9fKfUAlpnVfH7m3G5NVvO5wRKcn8nhGwwGQ5lgZvgGg8FQJpiAbzAYDGWCCfjLiIj8ZxE5IyLvici3RKS61GNaKgo1v7mVWM1GPSLyNyLSIyInSj2WpUZE1ovIqyJyKvuZ/INSj2mpEJGQiBwTkV9kz+3fFbM/E/CXl5eB3aq6F/gA+LclHs9SMq/5za1EGRj1/C3waKkHsUykgT9U1Z3AfcCzq+j/bhx4RFVvB/YBj4rIoq26TMBfRlT1B1ktIYCf4SqFrgpU9bSqni31OJaQKaMeVZ0AJo16VgWq+jpwvdTjWA5UtUtV38n+HsfV7Fpb2lEtDeoykn3oz/4sutLGBPyV43PAS6UehCEvXkY9qyJolBMisgm4A/h5aUeydIiILSLHgR7gZVVd9LmthOPVqqYQgxgR+RLubefXV3JsxbKS5jcGQ7GISBT4e+ALqjpc6vEsFaqaAfZl1wC/JSK7VXVRazEm4BfJfAYxIvI7wGPAR/UWa3pYAvObW4mCjXoMNx8i4scN9l9X1W+WejzLgaoOisiruGsxiwr4JqWzjIjIo8AfAU+oaqLU4zHMiTHquUUREQG+CpxW1f9S6vEsJSLSMFndJyIVwD8Dzix2fybgLy//E4gBL4vIcRH5y1IPaKnIZ35zq7LajXpE5AXgp0CbiFwVkadKPaYl5CDwW8Aj2e/ZcRE5NN+bbhHWAK+KyHu4k5KXVfW7i92ZkVYwGAyGMsHM8A0Gg6FMMAHfYDAYygQT8A0Gg6FMMAHfYDAYygQT8A0Gg6FMMAHfYDAYygQT8A0Gg6FM+P9hk98a4FYRRAAAAABJRU5ErkJggg==\n",
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
]
},
"metadata": {
"tags": [],
"needs_background": "light"
}
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "YQYEpXf-zO1h"
},
"source": [
"## Christofide's algorithm\n",
"\n",
"The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space(they are symmetric and obey the triangle inequality). It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides, who published it in 1976.\n",
"\n",
"\n",
"*Code by [Andrew Zhuravchak](https://github.com/Retsediv/ChristofidesAlgorithm)*"
]
},
{
"cell_type": "code",
"metadata": {
"id": "WzkCxymGzSd8"
},
"source": [
"def tsp(data):\n",
" # build a graph\n",
" G = build_graph(data)\n",
" print(\"Graph: \", G)\n",
"\n",
" # build a minimum spanning tree\n",
" MSTree = minimum_spanning_tree(G)\n",
" print(\"MSTree: \", MSTree)\n",
"\n",
" # find odd vertexes\n",
" odd_vertexes = find_odd_vertexes(MSTree)\n",
" print(\"Odd vertexes in MSTree: \", odd_vertexes)\n",
"\n",
" # add minimum weight matching edges to MST\n",
" minimum_weight_matching(MSTree, G, odd_vertexes)\n",
" print(\"Minimum weight matching: \", MSTree)\n",
"\n",
" # find an eulerian tour\n",
" eulerian_tour = find_eulerian_tour(MSTree, G)\n",
"\n",
" print(\"Eulerian tour: \", eulerian_tour)\n",
"\n",
" current = eulerian_tour[0]\n",
" path = [current]\n",
" visited = [False] * len(eulerian_tour)\n",
" visited[0] = True\n",
"\n",
" length = 0\n",
"\n",
" for v in eulerian_tour[1:]:\n",
" if not visited[v]:\n",
" path.append(v)\n",
" visited[v] = True\n",
"\n",
" length += G[current][v]\n",
" current = v\n",
"\n",
" path.append(path[0])\n",
"\n",
" print(\"Result path: \", path)\n",
" print(\"Result length of the path: \", length)\n",
"\n",
" return length, path\n",
"\n",
"\n",
"def get_length(x1, y1, x2, y2):\n",
" return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (1.0 / 2.0)\n",
"\n",
"\n",
"def build_graph(data):\n",
" graph = {}\n",
" for this in range(len(data)):\n",
" for another_point in range(len(data)):\n",
" if this != another_point:\n",
" if this not in graph:\n",
" graph[this] = {}\n",
"\n",
" graph[this][another_point] = get_length(data[this][0], data[this][1], data[another_point][0],\n",
" data[another_point][1])\n",
"\n",
" return graph\n",
"\n",
"\n",
"class UnionFind:\n",
" def __init__(self):\n",
" self.weights = {}\n",
" self.parents = {}\n",
"\n",
" def __getitem__(self, object):\n",
" if object not in self.parents:\n",
" self.parents[object] = object\n",
" self.weights[object] = 1\n",
" return object\n",
"\n",
" # find path of objects leading to the root\n",
" path = [object]\n",
" root = self.parents[object]\n",
" while root != path[-1]:\n",
" path.append(root)\n",
" root = self.parents[root]\n",
"\n",
" # compress the path and return\n",
" for ancestor in path:\n",
" self.parents[ancestor] = root\n",
" return root\n",
"\n",
" def __iter__(self):\n",
" return iter(self.parents)\n",
"\n",
" def union(self, *objects):\n",
" roots = [self[x] for x in objects]\n",
" heaviest = max([(self.weights[r], r) for r in roots])[1]\n",
" for r in roots:\n",
" if r != heaviest:\n",
" self.weights[heaviest] += self.weights[r]\n",
" self.parents[r] = heaviest\n",
"\n",
"\n",
"def minimum_spanning_tree(G):\n",
" tree = []\n",
" subtrees = UnionFind()\n",
" for W, u, v in sorted((G[u][v], u, v) for u in G for v in G[u]):\n",
" if subtrees[u] != subtrees[v]:\n",
" tree.append((u, v, W))\n",
" subtrees.union(u, v)\n",
"\n",
" return tree\n",
"\n",
"\n",
"def find_odd_vertexes(MST):\n",
" tmp_g = {}\n",
" vertexes = []\n",
" for edge in MST:\n",
" if edge[0] not in tmp_g:\n",
" tmp_g[edge[0]] = 0\n",
"\n",
" if edge[1] not in tmp_g:\n",
" tmp_g[edge[1]] = 0\n",
"\n",
" tmp_g[edge[0]] += 1\n",
" tmp_g[edge[1]] += 1\n",
"\n",
" for vertex in tmp_g:\n",
" if tmp_g[vertex] % 2 == 1:\n",
" vertexes.append(vertex)\n",
"\n",
" return vertexes\n",
"\n",
"\n",
"def minimum_weight_matching(MST, G, odd_vert):\n",
" import random\n",
" random.shuffle(odd_vert)\n",
"\n",
" while odd_vert:\n",
" v = odd_vert.pop()\n",
" length = float(\"inf\")\n",
" u = 1\n",
" closest = 0\n",
" for u in odd_vert:\n",
" if v != u and G[v][u] < length:\n",
" length = G[v][u]\n",
" closest = u\n",
"\n",
" MST.append((v, closest, length))\n",
" odd_vert.remove(closest)\n",
"\n",
"\n",
"def find_eulerian_tour(MatchedMSTree, G):\n",
" # find neigbours\n",
" neighbours = {}\n",
" for edge in MatchedMSTree:\n",
" if edge[0] not in neighbours:\n",
" neighbours[edge[0]] = []\n",
"\n",
" if edge[1] not in neighbours:\n",
" neighbours[edge[1]] = []\n",
"\n",
" neighbours[edge[0]].append(edge[1])\n",
" neighbours[edge[1]].append(edge[0])\n",
"\n",
" # print(\"Neighbours: \", neighbours)\n",
"\n",
" # finds the hamiltonian circuit\n",
" start_vertex = MatchedMSTree[0][0]\n",
" EP = [neighbours[start_vertex][0]]\n",
"\n",
" while len(MatchedMSTree) > 0:\n",
" for i, v in enumerate(EP):\n",
" if len(neighbours[v]) > 0:\n",
" break\n",
"\n",
" while len(neighbours[v]) > 0:\n",
" w = neighbours[v][0]\n",
"\n",
" remove_edge_from_matchedMST(MatchedMSTree, v, w)\n",
"\n",
" del neighbours[v][(neighbours[v].index(w))]\n",
" del neighbours[w][(neighbours[w].index(v))]\n",
"\n",
" i += 1\n",
" EP.insert(i, w)\n",
"\n",
" v = w\n",
"\n",
" return EP\n",
"\n",
"\n",
"def remove_edge_from_matchedMST(MatchedMST, v1, v2):\n",
"\n",
" for i, item in enumerate(MatchedMST):\n",
" if (item[0] == v2 and item[1] == v1) or (item[0] == v1 and item[1] == v2):\n",
" del MatchedMST[i]\n",
"\n",
" return MatchedMST"
],
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"id": "jeaC6QQjqSsB"
},
"source": [
"## Kruskal's MST\n",
"\n",
"Kruskal's MST is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which:\n",
"\n",
" - form a tree that includes every vertex\n",
" - has the minimum sum of weights among all the trees that can be formed from the graph\n",
"\n",
"*Code from [Programiz](https://www.programiz.com/dsa/kruskal-algorithm)*"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "HX1_2puEqh1p",
"outputId": "4e634e9e-5bca-46e4-98d2-8f6cd0fdd49d"
},
"source": [
"class Graph:\n",
" def __init__(self, vertices):\n",
" self.V = vertices\n",
" self.graph = []\n",
"\n",
" def add_edge(self, u, v, w):\n",
" self.graph.append([u, v, w])\n",
"\n",
" # Search function\n",
"\n",
" def find(self, parent, i):\n",
" if parent[i] == i:\n",
" return i\n",
" return self.find(parent, parent[i])\n",
"\n",
" def apply_union(self, parent, rank, x, y):\n",
" xroot = self.find(parent, x)\n",
" yroot = self.find(parent, y)\n",
" if rank[xroot] < rank[yroot]:\n",
" parent[xroot] = yroot\n",
" elif rank[xroot] > rank[yroot]:\n",
" parent[yroot] = xroot\n",
" else:\n",
" parent[yroot] = xroot\n",
" rank[xroot] += 1\n",
"\n",
" # Applying Kruskal algorithm\n",
" def kruskal_algo(self):\n",
" result = []\n",
" i, e = 0, 0\n",
" self.graph = sorted(self.graph, key=lambda item: item[2])\n",
" parent = []\n",
" rank = []\n",
" for node in range(self.V):\n",
" parent.append(node)\n",
" rank.append(0)\n",
" while e < self.V - 1:\n",
" u, v, w = self.graph[i]\n",
" i = i + 1\n",
" x = self.find(parent, u)\n",
" y = self.find(parent, v)\n",
" if x != y:\n",
" e = e + 1\n",
" result.append([u, v, w])\n",
" self.apply_union(parent, rank, x, y)\n",
" for u, v, weight in result:\n",
" print(\"%d - %d: %d\" % (u, v, weight))\n",
"\n",
"\n",
"g = Graph(6)\n",
"g.add_edge(0, 1, 4)\n",
"g.add_edge(0, 2, 4)\n",
"g.add_edge(1, 2, 2)\n",
"g.add_edge(1, 0, 4)\n",
"g.add_edge(2, 0, 4)\n",
"g.add_edge(2, 1, 2)\n",
"g.add_edge(2, 3, 3)\n",
"g.add_edge(2, 5, 2)\n",
"g.add_edge(2, 4, 4)\n",
"g.add_edge(3, 2, 3)\n",
"g.add_edge(3, 4, 3)\n",
"g.add_edge(4, 2, 4)\n",
"g.add_edge(4, 3, 3)\n",
"g.add_edge(5, 2, 2)\n",
"g.add_edge(5, 4, 3)\n",
"g.kruskal_algo()"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"1 - 2: 2\n",
"2 - 5: 2\n",
"2 - 3: 3\n",
"3 - 4: 3\n",
"0 - 1: 4\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "H1eqHQnwr-Vi"
},
"source": [
"## Prim's MST\n",
"\n",
"Prim's MST is a algorithm that finds a minimum spanning tree for a weighted undirected graphs. The algorithm finds the subset of edges that forms a tree that includes every vertex where the total weight of all the edges in the tree is minizmed.\n",
"\n",
"*Code from [Programiz](https://www.programiz.com/dsa/prim-algorithm)*"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "AMAQDsPrsPM8",
"outputId": "94cd5afc-b19c-4db6-bcaf-b483fd3e0e44"
},
"source": [
"INF = 9999999\n",
"# number of vertices in graph\n",
"V = 5\n",
"# create a 2d array of size 5x5\n",
"# for adjacency matrix to represent graph\n",
"G = [[0, 9, 75, 0, 0],\n",
" [9, 0, 95, 19, 42],\n",
" [75, 95, 0, 51, 66],\n",
" [0, 19, 51, 0, 31],\n",
" [0, 42, 66, 31, 0]]\n",
"# create a array to track selected vertex\n",
"# selected will become true otherwise false\n",
"selected = [0, 0, 0, 0, 0]\n",
"# set number of edge to 0\n",
"no_edge = 0\n",
"# the number of egde in minimum spanning tree will be\n",
"# always less than(V - 1), where V is number of vertices in\n",
"# graph\n",
"# choose 0th vertex and make it true\n",
"selected[0] = True\n",
"# print for edge and weight\n",
"print(\"Edge : Weight\\n\")\n",
"while (no_edge < V - 1):\n",
" # For every vertex in the set S, find the all adjacent vertices\n",
" #, calculate the distance from the vertex selected at step 1.\n",
" # if the vertex is already in the set S, discard it otherwise\n",
" # choose another vertex nearest to selected vertex at step 1.\n",
" minimum = INF\n",
" x = 0\n",
" y = 0\n",
" for i in range(V):\n",
" if selected[i]:\n",
" for j in range(V):\n",
" if ((not selected[j]) and G[i][j]): \n",
" # not in selected and there is an edge\n",
" if minimum > G[i][j]:\n",
" minimum = G[i][j]\n",
" x = i\n",
" y = j\n",
" print(str(x) + \"-\" + str(y) + \":\" + str(G[x][y]))\n",
" selected[y] = True\n",
" no_edge += 1"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"Edge : Weight\n",
"\n",
"0-1:9\n",
"1-3:19\n",
"3-4:31\n",
"3-2:51\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Pgltw8VPrFjp"
},
"source": [
"# Problems"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "4rrpuhMyMx3Z"
},
"source": [
"## Knapsack Problem\n",
"\n",
"The knapsack problem is a problem that given the weights and values of each item, determine how much you can put inside a Knapsack. This can be solved naively or using dynamic programming with approximation algorithms.\n",
"\n",
"*Code sample from [GeeksforGeeks](https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/).*"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "wWWnWNGEM9NY",
"outputId": "fc7750f6-ebe7-46c1-f025-1eb578a5aaab"
},
"source": [
"def knapSack(W, wt, val, n):\n",
" dp = [0 for i in range(W+1)] # Making the dp array\n",
" \n",
" for i in range(1, n+1): # taking first i elements\n",
" for w in range(W, 0, -1): # starting from back,so that we also have data of\n",
" # previous computation when taking i-1 items\n",
" if wt[i-1] <= w:\n",
" # finding the maximum value\n",
" dp[w] = max(dp[w], dp[w-wt[i-1]]+val[i-1])\n",
" \n",
" return dp[W] # returning the maximum value of knapsack\n",
" \n",
"# Driver program to test above function\n",
"val = [60, 100, 120]\n",
"wt = [10, 20, 30]\n",
"W = 50\n",
"n = len(val)\n",
"print(knapSack(W, wt, val, n))"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"220\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "dwOw5tKTq3_V"
},
"source": [
"## Shortest Route Problem\n",
"\n",
"This is a shortest route problem implemented in Python. Shortest route or also known as the \"Traveling Salesman Problem\" is a problem in algorithms to discover the shortest path to the solution. This algorithm is a **P** problem.\n",
"\n",
"![](https://www.geeksforgeeks.org/wp-content/uploads/Euler12-300x225.png)\n",
"\n",
"*Snippet is from the [Google OR-tools page](https://developers.google.com/optimization/routing/tsp).*"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "3Ck6FzYvq3Fz",
"outputId": "b1fd0c05-5d06-4aa0-d2c9-5eeeb1daec94"
},
"source": [
"\"\"\"Simple travelling salesman problem between cities.\"\"\"\n",
"\n",
"from ortools.constraint_solver import routing_enums_pb2\n",
"from ortools.constraint_solver import pywrapcp\n",
"\n",
"\n",
"def create_data_model():\n",
" \"\"\"Stores the data for the problem.\"\"\"\n",
" data = {}\n",
" data['distance_matrix'] = [\n",
" [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],\n",
" [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],\n",
" [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],\n",
" [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],\n",
" [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],\n",
" [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],\n",
" [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],\n",
" [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],\n",
" [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],\n",
" [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],\n",
" [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],\n",
" [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],\n",
" [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0],\n",
" ] # yapf: disable\n",
" data['num_vehicles'] = 1\n",
" data['depot'] = 0\n",
" return data\n",
"\n",
"\n",
"def print_solution(manager, routing, solution):\n",
" \"\"\"Prints solution on console.\"\"\"\n",
" print('Objective: {} miles'.format(solution.ObjectiveValue()))\n",
" index = routing.Start(0)\n",
" plan_output = 'Route for vehicle 0:\\n'\n",
" route_distance = 0\n",
" while not routing.IsEnd(index):\n",
" plan_output += ' {} ->'.format(manager.IndexToNode(index))\n",
" previous_index = index\n",
" index = solution.Value(routing.NextVar(index))\n",
" route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)\n",
" plan_output += ' {}\\n'.format(manager.IndexToNode(index))\n",
" print(plan_output)\n",
" plan_output += 'Route distance: {}miles\\n'.format(route_distance)\n",
"\n",
"\n",
"def main():\n",
" \"\"\"Entry point of the program.\"\"\"\n",
" # Instantiate the data problem.\n",
" data = create_data_model()\n",
"\n",
" # Create the routing index manager.\n",
" manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),\n",
" data['num_vehicles'], data['depot'])\n",
"\n",
" # Create Routing Model.\n",
" routing = pywrapcp.RoutingModel(manager)\n",
"\n",
"\n",
" def distance_callback(from_index, to_index):\n",
" \"\"\"Returns the distance between the two nodes.\"\"\"\n",
" # Convert from routing variable Index to distance matrix NodeIndex.\n",
" from_node = manager.IndexToNode(from_index)\n",
" to_node = manager.IndexToNode(to_index)\n",
" return data['distance_matrix'][from_node][to_node]\n",
"\n",
" transit_callback_index = routing.RegisterTransitCallback(distance_callback)\n",
"\n",
" # Define cost of each arc.\n",
" routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)\n",
"\n",
" # Setting first solution heuristic.\n",
" search_parameters = pywrapcp.DefaultRoutingSearchParameters()\n",
" search_parameters.first_solution_strategy = (\n",
" routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)\n",
"\n",
" # Solve the problem.\n",
" solution = routing.SolveWithParameters(search_parameters)\n",
"\n",
" # Print solution on console.\n",
" if solution:\n",
" print_solution(manager, routing, solution)\n",
"\n",
"\n",
"if __name__ == '__main__':\n",
" main()"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"Objective: 7293 miles\n",
"Route for vehicle 0:\n",
" 0 -> 7 -> 2 -> 3 -> 4 -> 12 -> 6 -> 8 -> 1 -> 11 -> 10 -> 5 -> 9 -> 0\n",
"\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Ep_E9UUA0T9m"
},
"source": [
"Similarly, it can be solved using Christofide's algorithm, which is implemented on the Algorithms section, which is a approximation algorithm."
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Z6l3_mkUzvV_",
"outputId": "fe004fa2-14df-48a9-98e2-ca8034d8830e"
},
"source": [
"# Another example using Chirstofide's algorithm. \n",
"# Code for the algorithm is in the Algorithm section\n",
"points = [\n",
" [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],\n",
" [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],\n",
" [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],\n",
" [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],\n",
" [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],\n",
" [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],\n",
" [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],\n",
" [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],\n",
" [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],\n",
" [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],\n",
" [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],\n",
" [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],\n",
" [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]\n",
"]\n",
"\n",
"length, path = tsp(points)\n"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"Graph: {0: {1: 3466.237441376456, 2: 1003.3967311088869, 3: 1376.8271496451543, 4: 2298.817304615571, 5: 1831.5012967508376, 6: 2832.759785085915, 7: 257.6703320136022, 8: 3286.996349252612, 9: 1228.2788771284802, 10: 1782.225855496435, 11: 2997.642573756918, 12: 2719.038065198794}, 1: {0: 3466.237441376456, 2: 2462.857892774165, 3: 2091.9046345376264, 4: 1167.4592069961159, 5: 1642.4155990491565, 6: 959.9635409743435, 7: 3427.5151349045855, 8: 420.4866228549964, 9: 2238.011840898077, 10: 1717.800046571195, 11: 470.1967673219373, 12: 751.4532586927812}, 2: {0: 1003.3967311088869, 1: 2462.857892774165, 3: 376.65103212390113, 4: 1295.422710932613, 5: 831.8329159152095, 6: 1868.373891917782, 7: 987.0162106064926, 8: 2291.9703313961113, 9: 224.89997776789573, 10: 798.4297088660967, 11: 1994.2838313540026, 12: 1715.9944638605336}, 3: {0: 1376.8271496451543, 1: 2091.9046345376264, 2: 376.65103212390113, 4: 925.212408044769, 5: 455.4031181272258, 6: 1500.4416016626571, 7: 1340.6002386990688, 8: 1915.3198166363757, 9: 157.07959765672945, 10: 429.073420290747, 11: 1622.3495307731932, 12: 1342.810857864949}, 4: {0: 2298.817304615571, 1: 1167.4592069961159, 2: 1295.422710932613, 3: 925.212408044769, 5: 483.0424411995285, 6: 787.472539203749, 7: 2264.0558738688405, 8: 1032.8523611823714, 9: 1070.5606008068858, 10: 582.5547184599915, 11: 699.193821482999, 12: 424.0106130747201}, 5: {0: 1831.5012967508376, 1: 1642.4155990491565, 2: 831.8329159152095, 3: 455.4031181272258, 4: 483.0424411995285, 6: 1071.5022165166063, 7: 1785.1210043019494, 8: 1460.6087771884709, 9: 608.9351361187823, 10: 141.6756859873987, 11: 1172.232912010237, 12: 891.3613184337763}, 6: {0: 2832.759785085915, 1: 959.9635409743435, 2: 1868.373891917782, 3: 1500.4416016626571, 4: 787.472539203749, 5: 1071.5022165166063, 7: 2738.209999251336, 8: 579.4005522952149, 9: 1657.404295879554, 10: 1071.6198019820276, 11: 656.942158793299, 12: 578.3562915712079}, 7: {0: 257.6703320136022, 1: 3427.5151349045855, 2: 987.0162106064926, 3: 1340.6002386990688, 4: 2264.0558738688405, 5: 1785.1210043019494, 6: 2738.209999251336, 8: 3220.1572942947987, 9: 1205.1111981887811, 10: 1717.5951210922788, 11: 2957.320577820403, 12: 2676.2604507035558}, 8: {0: 3286.996349252612, 1: 420.4866228549964, 2: 2291.9703313961113, 3: 1915.3198166363757, 4: 1032.8523611823714, 5: 1460.6087771884709, 6: 579.4005522952149, 7: 3220.1572942947987, 9: 2069.543911106986, 10: 1505.8691842255091, 11: 428.47637041031794, 12: 624.3212314185703}, 9: {0: 1228.2788771284802, 1: 2238.011840898077, 2: 224.89997776789573, 3: 157.07959765672945, 4: 1070.5606008068858, 5: 608.9351361187823, 6: 1657.404295879554, 7: 1205.1111981887811, 8: 2069.543911106986, 10: 585.8754133772811, 11: 1769.3852039620995, 12: 1491.143520926138}, 10: {0: 1782.225855496435, 1: 1717.800046571195, 2: 798.4297088660967, 3: 429.073420290747, 4: 582.5547184599915, 5: 141.6756859873987, 6: 1071.6198019820276, 7: 1717.5951210922788, 8: 1505.8691842255091, 9: 585.8754133772811, 11: 1248.9651716521162, 12: 967.8476119720501}, 11: {0: 2997.642573756918, 1: 470.1967673219373, 2: 1994.2838313540026, 3: 1622.3495307731932, 4: 699.193821482999, 5: 1172.232912010237, 6: 656.942158793299, 7: 2957.320577820403, 8: 428.47637041031794, 9: 1769.3852039620995, 10: 1248.9651716521162, 12: 281.4480413859723}, 12: {0: 2719.038065198794, 1: 751.4532586927812, 2: 1715.9944638605336, 3: 1342.810857864949, 4: 424.0106130747201, 5: 891.3613184337763, 6: 578.3562915712079, 7: 2676.2604507035558, 8: 624.3212314185703, 9: 1491.143520926138, 10: 967.8476119720501, 11: 281.4480413859723}}\n",
"MSTree: [(5, 10, 141.6756859873987), (3, 9, 157.07959765672945), (2, 9, 224.89997776789573), (0, 7, 257.6703320136022), (11, 12, 281.4480413859723), (1, 8, 420.4866228549964), (4, 12, 424.0106130747201), (8, 11, 428.47637041031794), (3, 10, 429.073420290747), (4, 5, 483.0424411995285), (6, 12, 578.3562915712079), (2, 7, 987.0162106064926)]\n",
"Odd vertexes in MSTree: [0, 12, 1, 6]\n",
"Minimum weight matching: [(5, 10, 141.6756859873987), (3, 9, 157.07959765672945), (2, 9, 224.89997776789573), (0, 7, 257.6703320136022), (11, 12, 281.4480413859723), (1, 8, 420.4866228549964), (4, 12, 424.0106130747201), (8, 11, 428.47637041031794), (3, 10, 429.073420290747), (4, 5, 483.0424411995285), (6, 12, 578.3562915712079), (2, 7, 987.0162106064926), (6, 12, 578.3562915712079), (0, 1, 3466.237441376456)]\n",
"Eulerian tour: [10, 5, 4, 12, 6, 12, 11, 8, 1, 0, 7, 2, 9, 3, 10]\n",
"Result path: [10, 5, 4, 12, 6, 11, 8, 1, 7, 2, 9, 3, 10, 10]\n",
"Result length of the path: 8358.574525117918\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "UuHwud-upUif"
},
"source": [
"## Vertex covering Problem\n",
"This is a vertex covering problem implemented using Python. The basic idea of the problem is to select the smallest set of vertices such that each edge in the graph is incident on at least one selected vertex. This problem is a **NP-complete** problem, and can be solved using an approximation algorithm.\n",
"\n",
"![](https://media.geeksforgeeks.org/wp-content/uploads/minimumvertexcover.png)\n",
"\n",
"This example uses the following graph: \n",
"\n",
"```\n",
" g\n",
" / \\\n",
" / \\\n",
"a --- b --- e\n",
"| \\ | / |\n",
"| \\ | / |\n",
"c --- d --- f\n",
"```\n",
"\n",
"*Code snippet by [Zayd Hammoudeh ](https://gist.github.com/ZaydH/d7a7afd98957a3bd10801181863ce135)*"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Eue9S7KEpTlo",
"outputId": "cc6d6c31-9dbd-46a9-f024-d5e261bc68d2"
},
"source": [
"import cplex\n",
"\n",
"\n",
"def _main():\n",
" r\"\"\"\n",
" Example Undirected Graph:\n",
" g\n",
" / \\\n",
" / \\\n",
" a --- b --- e\n",
" | \\ | / |\n",
" | \\ | / |\n",
" c --- d --- f\n",
" \"\"\"\n",
" prob = cplex.Cplex()\n",
" prob.set_problem_name(\"Minimum Vertex Cover\")\n",
"\n",
" # PROBLEM TYPE OPTIONS\n",
" # =============================\n",
" # Cplex.problem_type.LP\n",
" # Cplex.problem_type.MILP\n",
" # Cplex.problem_type.fixed_MILP\n",
" # Cplex.problem_type.QP\n",
" # Cplex.problem_type.MIQP\n",
" # Cplex.problem_type.fixed_MIQP\n",
" # Cplex.problem_type.QCP\n",
" # Cplex.problem_type.MIQCP\n",
" # =============================\n",
" prob.set_problem_type(cplex.Cplex.problem_type.LP)\n",
"\n",
" # We want to find a maximum of our objective function\n",
" prob.objective.set_sense(prob.objective.sense.minimize)\n",
"\n",
" # Variable Names\n",
" names = [\"a\", \"b\", \"c\", \"d\", \"e\", \"f\", \"g\"]\n",
"\n",
" # Objective (linear) weights\n",
" w_obj = [1, 1, 1, 1, 1, 1, 1]\n",
" # Lower bounds. Since these are all zero, we could simply not pass them in as\n",
" # all zeroes is the default.\n",
" low_bnd = [0, 0, 0, 0, 0, 0, 0]\n",
" # Upper bounds. The default here would be cplex.infinity, or 1e+20.\n",
" upr_bnd = [1, 1, 1, 1, 1, 1, 1]\n",
" prob.variables.add(names=names, obj=w_obj, lb=low_bnd, ub=upr_bnd)\n",
"\n",
" # How to set the variable types\n",
" # Must be AFTER adding the variablers\n",
" #\n",
" # Option #1: Single variable name (or number) with type\n",
" # prob.variables.set_types(\"0\", prob.variables.type.continuous)\n",
" # Option #2: List of tuples in the form (var_name, type)\n",
" # prob.variables.set_types([(\"1\", prob.variables.type.integer), \\\n",
" # (\"2\", prob.variables.type.binary), \\\n",
" # (\"3\", prob.variables.type.semi_continuous), \\\n",
" # (\"4\", prob.variables.type.semi_integer)])\n",
" #\n",
" # Vertex cover requires only integers\n",
" all_int = [(var, prob.variables.type.integer) for var in names]\n",
" prob.variables.set_types(all_int)\n",
"\n",
" constraints = []\n",
" # Edge ab\n",
" constraints.append([[\"a\", \"b\"], [1, 1]])\n",
" # Edge ac\n",
" constraints.append([[\"a\", \"c\"], [1, 1]])\n",
" # Edge ad\n",
" constraints.append([[\"a\", \"d\"], [1, 1]])\n",
" constraints.append([[\"a\", \"g\"], [1, 1]])\n",
" constraints.append([[\"b\", \"d\"], [1, 1]])\n",
" constraints.append([[\"b\", \"e\"], [1, 1]])\n",
" constraints.append([[\"c\", \"d\"], [1, 1]])\n",
" constraints.append([[\"d\", \"e\"], [1, 1]])\n",
" constraints.append([[\"d\", \"f\"], [1, 1]])\n",
" constraints.append([[\"e\", \"g\"], [1, 1]])\n",
" constraints.append([[\"f\", \"e\"], [1, 1]])\n",
"\n",
" # Constraint names\n",
" constraint_names = [\"\".join(x[0]) for x in constraints]\n",
"\n",
" # Each edge must have at least one vertex\n",
" rhs = [1] * len(constraints)\n",
"\n",
" # We need to enter the senses of the constraints. That is, we need to tell Cplex\n",
" # whether each constrains should be treated as an upper-limit (≤, denoted \"L\"\n",
" # for less-than), a lower limit (≥, denoted \"G\" for greater than) or an equality\n",
" # (=, denoted \"E\" for equality)\n",
" constraint_senses = [\"G\"] * len(constraints)\n",
"\n",
" # And add the constraints\n",
" prob.linear_constraints.add(names=constraint_names,\n",
" lin_expr=constraints,\n",
" senses=constraint_senses,\n",
" rhs=rhs)\n",
" # Solve the problem\n",
" print(\"Problem Type: %s\" % prob.problem_type[prob.get_problem_type()])\n",
" prob.solve()\n",
" print(\"Solution result is: %s\" % prob.solution.get_status_string())\n",
" print(prob.solution.get_values())\n",
"\n",
"\n",
"if __name__ == \"__main__\":\n",
" _main()"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"Problem Type: MILP\n",
"Version identifier: 20.1.0.0 | 2020-11-11 | 9bedb6d68\n",
"CPXPARAM_Read_DataCheck 1\n",
"Found incumbent of value 7.000000 after 0.00 sec. (0.00 ticks)\n",
"Tried aggregator 1 time.\n",
"MIP Presolve eliminated 5 rows and 0 columns.\n",
"MIP Presolve modified 4 coefficients.\n",
"Reduced MIP has 6 rows, 7 columns, and 16 nonzeros.\n",
"Reduced MIP has 7 binaries, 0 generals, 0 SOSs, and 0 indicators.\n",
"Presolve time = 0.01 sec. (0.01 ticks)\n",
"Probing time = 0.00 sec. (0.00 ticks)\n",
"Tried aggregator 1 time.\n",
"Detecting symmetries...\n",
"Reduced MIP has 6 rows, 7 columns, and 16 nonzeros.\n",
"Reduced MIP has 7 binaries, 0 generals, 0 SOSs, and 0 indicators.\n",
"Presolve time = 0.01 sec. (0.01 ticks)\n",
"Probing time = 0.00 sec. (0.00 ticks)\n",
"Clique table members: 8.\n",
"MIP emphasis: balance optimality and feasibility.\n",
"MIP search method: dynamic search.\n",
"Parallel mode: deterministic, using up to 2 threads.\n",
"Root relaxation solution time = 0.00 sec. (0.01 ticks)\n",
"\n",
" Nodes Cuts/\n",
" Node Left Objective IInf Best Integer Best Bound ItCnt Gap\n",
"\n",
"* 0+ 0 7.0000 0.0000 100.00%\n",
"* 0+ 0 5.0000 0.0000 100.00%\n",
"* 0+ 0 3.0000 0.0000 100.00%\n",
" 0 0 cutoff 3.0000 3.0000 4 0.00%\n",
" 0 0 cutoff 3.0000 3.0000 4 0.00%\n",
"Elapsed time = 0.05 sec. (0.05 ticks, tree = 0.01 MB, solutions = 3)\n",
"\n",
"Root node processing (before b&c):\n",
" Real time = 0.05 sec. (0.06 ticks)\n",
"Parallel b&c, 2 threads:\n",
" Real time = 0.00 sec. (0.00 ticks)\n",
" Sync time (average) = 0.00 sec.\n",
" Wait time (average) = 0.00 sec.\n",
" ------------\n",
"Total (root+branch&cut) = 0.05 sec. (0.06 ticks)\n",
"Solution result is: integer optimal solution\n",
"[1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0]\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "8JSeaTVPCQyt"
},
"source": [
"Another way to do this using approximation algorithm, which never finds a vertex cover whose size is more than twice the size of the minimum possible vertex cover.\n",
"\n",
"*Code from [GeeksforGeeks](https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/)*"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "V-wIsC0bCjod",
"outputId": "e9da8335-2b0a-4c19-cbd5-1920b4c4095e"
},
"source": [
"from collections import defaultdict\n",
" \n",
"# This class represents a directed graph\n",
"# using adjacency list representation\n",
"class Graph:\n",
" \n",
" def __init__(self, vertices):\n",
" \n",
" # No. of vertices\n",
" self.V = vertices\n",
" \n",
" # Default dictionary to store graph\n",
" self.graph = defaultdict(list)\n",
" \n",
" # Function to add an edge to graph\n",
" def addEdge(self, u, v):\n",
" self.graph[u].append(v)\n",
" \n",
" # The function to print vertex cover\n",
" def printVertexCover(self):\n",
" \n",
" # Initialize all vertices as not visited.\n",
" visited = [False] * (self.V)\n",
" \n",
" # Consider all edges one by one\n",
" for u in range(self.V):\n",
" \n",
" # An edge is only picked when\n",
" # both visited[u] and visited[v]\n",
" # are false\n",
" if not visited[u]:\n",
" \n",
" # Go through all adjacents of u and\n",
" # pick the first not yet visited\n",
" # vertex (We are basically picking\n",
" # an edge (u, v) from remaining edges.\n",
" for v in self.graph[u]:\n",
" if not visited[v]:\n",
" \n",
" # Add the vertices (u, v) to the\n",
" # result set. We make the vertex\n",
" # u and v visited so that all\n",
" # edges from/to them would\n",
" # be ignored\n",
" visited[v] = True\n",
" visited[u] = True\n",
" break\n",
" \n",
" # Print the vertex cover\n",
" for j in range(self.V):\n",
" if visited[j]:\n",
" print(j, end = ' ')\n",
" \n",
" print()\n",
" \n",
"# Driver code\n",
" \n",
"# Create a graph given in\n",
"# the above diagram\n",
"g = Graph(7)\n",
"g.addEdge(0, 1)\n",
"g.addEdge(0, 2)\n",
"g.addEdge(1, 3)\n",
"g.addEdge(3, 4)\n",
"g.addEdge(4, 5)\n",
"g.addEdge(5, 6)\n",
" \n",
"g.printVertexCover()"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"0 1 3 4 5 6 \n"
],
"name": "stdout"
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "60jMQViI2y_C"
},
"source": [
"## Hamiltonian Circuit Problem\n",
"\n",
"A NP-complete problem. Hamiltonian circuit problems are a path that visits each vertex exactly once, and the Hamiltonian cycle or circuit is a Hamiltonian path, that there is an edge from the last vertex to the first vertex.\n",
"\n",
"![](https://static.javatpoint.com/tutorial/daa/images/hamiltonian-circuit-problems8.png)\n",
"\n",
"*This code is from the almighty [Stack Overflow Gods](https://stackoverflow.com/questions/47982604/hamiltonian-path-using-python).*"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "zZ1bRpal3KrC",
"outputId": "f675702c-c546-47c3-afe6-f019d3c34547"
},
"source": [
"def hamilton(G, size, pt, path=[]):\n",
" print('hamilton called with pt={}, path={}'.format(pt, path))\n",
" if pt not in set(path):\n",
" path.append(pt)\n",
" if len(path)==size:\n",
" return path\n",
" for pt_next in G.get(pt, []):\n",
" res_path = [i for i in path]\n",
" candidate = hamilton(G, size, pt_next, res_path)\n",
" if candidate is not None: # skip loop or dead end\n",
" return candidate\n",
" print('path {} is a dead end'.format(path))\n",
" else:\n",
" print('pt {} already in path {}'.format(pt, path))\n",
"\n",
"G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]}\n",
"\n",
"# Get in there Lewis\n",
"print(hamilton(G, 4, 1))"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"hamilton called with pt=1, path=[]\n",
"hamilton called with pt=2, path=[1]\n",
"hamilton called with pt=1, path=[1, 2]\n",
"pt 1 already in path [1, 2]\n",
"hamilton called with pt=3, path=[1, 2]\n",
"hamilton called with pt=1, path=[1, 2, 3]\n",
"pt 1 already in path [1, 2, 3]\n",
"hamilton called with pt=2, path=[1, 2, 3]\n",
"pt 2 already in path [1, 2, 3]\n",
"hamilton called with pt=4, path=[1, 2, 3]\n",
"[1, 2, 3, 4]\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "2YlcOYIFvHQo"
},
"source": [
"## Turing halting problem\n",
"\n",
"While not exactly an algorithm, the Turing halting algorithm defines if a problem is undecidable. Usually these problems are under the **NP-hard** classification. The most practical example of this are infinte loops and user input.\n",
"\n",
"![](https://www.tutorialspoint.com/automata_theory/images/halting_machine.jpg)"
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 214
},
"id": "Tj6hEvx9vT3f",
"outputId": "0e5b5d56-6fe0-4b1a-dafb-60443a427c39"
},
"source": [
"# Pretty simple right? Now what does this one entail you?\n",
"# Yes! it's a infinite loop! Therefore the result is undecidable\n",
"# as per the Turing halting problem.\n",
"x = input()\n",
"while x:\n",
" pass"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"text": [
"uwu\n"
],
"name": "stdout"
},
{
"output_type": "error",
"ename": "KeyboardInterrupt",
"evalue": "ignored",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-7-352fded23907>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mpass\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;31mKeyboardInterrupt\u001b[0m: "
]
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment