{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Travelling Salesman Problem\n", "\n", " Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Overview\n", "\n", "One of the most famous NP-hard problems in combinatorial optimization, the travelling salesman problem (TSP) considers the following question: \"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?\" \n", "\n", "This question can also be formulated in the language of graph theory. Given a weighted undirected complete graph $G = (V,E)$, where each vertex $i \\in V$ corresponds to city $i$ and the weight $w_{i,j}$ of each edge $(i,j,w_{i,j}) \\in E$ represents the distance between cities $i$ and $j$, the TSP is to find the shortest Hamiltonian cycle in $G$, where a Hamiltonian cycle is a closed loop on a graph in which every vertex is visited exactly once. Note that because $G$ is an undirected graph, weights are symmetric, i.e., $w_{i,j} = w_{j,i}$. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Use QNN to solve TSP\n", "\n", "To use QNN to solve travelling salesman problem, we need to first encode the classical problem to quantum. \n", "The encoding consists of two parts:\n", "\n", "1. The route how the salesman visits each city is encoded in quantum states -- ${\\rm qubit}_{i,t} = |1\\rangle$ corresponds to salesman visiting city $i$ at time $t$. \n", " 1. As an example, if there are two cities $\\{A,B\\}$, visiting $A$ then $B$ will be in state $|1001\\rangle$, as the salesman visits the city $A$ at time $1$ and the city $B$ at time $2$.\n", " 2. Similarly, $|0110\\rangle$ means visiting $B$ then $A$.\n", " 3. Note: $|0101\\rangle$ means visiting $A$ and $B$ both at time $2$, so it is infeasible. To avoid such states, a penalty function will be used (see the next section for details.)\n", "\n", "2. The total distance is encoded in a loss function: \n", "\n", "$$\n", "L(\\psi(\\vec{\\theta})) = \\langle\\psi(\\vec{\\theta})|H_C|\\psi(\\vec{\\theta})\\rangle,\n", "\\tag{1}\n", "$$\n", "\n", "where $|\\psi(\\vec{\\theta})\\rangle$ is the output state from a parameterized quantum circuit. \n", "\n", "The details about how to encode the classical problem to quantum is given in detail in the next section. \n", "After optimizing the loss function, we will obtain the optimal quantum state. Then a decoding process will be performed to get the final route." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Encoding the TSP\n", "\n", "To transform the TSP into a problem applicable for parameterized quantum circuits, we need to encode the TSP into a Hamiltonian. \n", "\n", "We realize the encoding by first constructing an integer programming problem. Suppose there are $n=|V|$ vertices in graph $G$. Then for each vertex $i \\in V$, we define $n$ binary variables $x_{i,t}$, where $t \\in [0,n-1]$, such that\n", "\n", "$$\n", "x_{i, t}=\n", "\\begin{cases}\n", "1, & \\text {if in the resulting Hamiltonian cycle, vertex } i \\text { is visited at time } t\\\\\n", "0, & \\text{otherwise}\n", "\\end{cases}.\n", "\\tag{2}\n", "$$\n", "\n", "As there are $n$ vertices, we have $n^2$ variables in total, whose value we denote by a bit string $x=x_{1,1}x_{1,2}\\dots x_{n,n}$. Assume for now that the bit string $x$ represents a Hamiltonian cycle. Then for each edge $(i,j,w_{i,j}) \\in E$, we will have $x_{i,t} = x_{j,t+1}=1$, i.e., $x_{i,t}\\cdot x_{j,t+1}=1$, if and only if the Hamiltonian cycle visits vertex $i$ at time $t$ and vertex $j$ at time $t+1$; otherwise, $x_{i,t}\\cdot x_{j,t+1}$ will be $0$. Therefore the length of a Hamiltonian cycle is\n", "\n", "$$\n", "D(x) = \\sum_{i,j} w_{i,j} \\sum_{t} x_{i,t} x_{j,t+1}.\n", "\\tag{3}\n", "$$\n", "\n", "For $x$ to represent a valid Hamiltonian cycle, the following constraint needs to be met:\n", "\n", "$$\n", "\\sum_t x_{i,t} = 1 \\quad \\forall i \\in [0,n-1] \\quad \\text{ and } \\quad \\sum_i x_{i,t} = 1 \\quad \\forall t \\in [0,n-1],\n", "\\tag{4}\n", "$$\n", "\n", "where the first equation guarantees that each vertex is only visited once and the second guarantees that only one vertex is visited at each time $t$. Then the cost function under the constraint can be formulated below, with $A$ being the penalty parameter set to ensure that the constraint is satisfied:\n", "\n", "$$\n", "C(x) = D(x)+ A\\left( \\sum_{i} \\left(1-\\sum_t x_{i,t}\\right)^2 + \\sum_{t} \\left(1-\\sum_i x_{i,t}\\right)^2 \\right).\n", "\\tag{5}\n", "$$\n", "\n", "Note that as we would like to minimize the length $D(x)$ while ensuring $x$ represents a valid Hamiltonian cycle, we had better set $A$ large, at least larger than the largest weight of edges.\n", "\n", "We now need to transform the cost function $C(x)$ into a Hamiltonian to realize the encoding of the TSP. Each variable $x_{i,j}$ has two possible values, $0$ and $1$, corresponding to quantum states $|0\\rangle$ and $|1\\rangle$. **Note that every variable corresponds to a qubit and so $n^2$ qubits are needed for solving the TSP.** Similar as in the Max-Cut problem, we consider the Pauli $Z$ operator as it has two eigenstates, $|0\\rangle$ and $|1\\rangle$. Their corresponding eigenvalues are 1 and -1, respectively.\n", "\n", "Now we would like to consider the mapping\n", "\n", "$$\n", "x_{i,t} \\mapsto \\frac{I-Z_{i,t}}{2}, \\tag{6}\n", "$$\n", "\n", "where $Z_{i,t} = I \\otimes I \\otimes \\ldots \\otimes Z \\otimes \\ldots \\otimes I$ with $Z$ operates on the qubit at position $(i,t)$. Under this mapping, if a qubit $(i,t)$ is in state $|1\\rangle$, then $x_{i,t}|1\\rangle = \\frac{I-Z_{i,t}}{2} |1\\rangle = 1 |1\\rangle$, which means vertex $i$ is visited at time $t$. Also, for a qubit $(i,t)$ in state $|0\\rangle$, $x_{i,t} |0\\rangle= \\frac{I-Z_{i,t}}{2} |0\\rangle = 0|0\\rangle$.\n", "\n", "Thus using the above mapping, we can transform the cost function $C(x)$ into a Hamiltonian $H_C$ for the system of $n^2$ qubits and realize the quantization of the TSP. Then the ground state of $H_C$ is the optimal solution to the TSP. In the following section, we will show how to use a parametrized quantum circuit to find the ground state, i.e., the eigenvector with the smallest eigenvalue.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Paddle Quantum Implementation\n", "\n", "To investigate the TSP using Paddle Quantum, there are some required packages to import, which are shown below. The ``networkx`` package is the tool to handle graphs." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:24:17.197426Z", "start_time": "2021-05-17T08:24:12.896488Z" } }, "outputs": [], "source": [ "# Import related modules from Paddle Quantum and PaddlePaddle\n", "import paddle\n", "import paddle_quantum\n", "from paddle_quantum.ansatz import Circuit\n", "from paddle_quantum import Hamiltonian\n", "\n", "# Functions for Salesman Problem\n", "from paddle_quantum.QAOA.tsp import tsp_hamiltonian # Get the Hamiltonian for salesman problem\n", "from paddle_quantum.QAOA.tsp import solve_tsp_brute_force # Solve the salesman problem by brute force\n", "\n", "# Create Graph\n", "import networkx as nx\n", "\n", "# Import additional packages needed\n", "from numpy import pi as PI\n", "import matplotlib.pyplot as plt\n", "import random\n", "import time" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generate a weighted complete graph" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next, we generate a weighted complete graph $G$ with four vertices. For the convenience of computation, the vertices here are labeled starting from $0$." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:24:24.302458Z", "start_time": "2021-05-17T08:24:24.060967Z" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAyu0lEQVR4nO2deXhV5bX/PyskYQpDRJBB5CgiiiOioshgxWoltlarVasF8Vbbam2rVTGt2trbGmwd6yz+CnJrHW+1V0NV1AqCM1IUsUCBoBhRURlzMnHe3x9rh5xzEiAJ+5y998n6PE8ezcnO3ivh5Lvfvd61vkuccxiGYRjZIS/oAAzDMNoTJrqGYRhZxETXMAwji5joGoZhZBETXcMwjCxiomsYhpFFTHQNwzCyiImuYRhGFjHRNQzDyCImuoZhGFnERNcwDCOLmOgahmFkERNdwzCMLGKiaxiGkUVMdA3DMLKIia5hGEYWMdE1DMPIIia6hmEYWcRE1zAMI4uY6BqGYWSR/KADMHKTWGl5HjAY2A/oDBQCtUAcWAasqCgrSQQXoWEEg9g0YMMPPJEdD5QAY4ADgARQD4j34byPfPQp6wPgFaAceNFE2GgPmOgau0SstLwYmAxcAXQDuqIC21IcsAXYCNwMTK8oK/nK7zgNIyyY6BptIlZa3gW4EfgBuqLt4sNpq9AV8APAlIqykiofzmkYocJE12g1sdLyMcAjQDGar/WbOPAVcFZFWcm8DJzfMALDRNdoMbHS8o7ArcD5ZEZs04kDM4DLKspKarJwPcPIOCa6RouIlZYXAc8Dh5EdwW0gDiwETqooK9mcxesaRkYw0TV2iie484ChQKcAQqgGlgKjTXiNqGPNEcYO8VIKzxOc4OJddyjwnBePYUQWE11jZ9yKphSCEtwGOgHDgVsCjsMwdglLLxjbxatSeI7s5nB3Rhw40aoajKhioms0i1eHuxzoH3QszVAJDLE6XiOKWHrB2B5/QOtww0gxMDXoIAyjLdhK12iC19pbSfB53B1RDfS3lmEjathK12iOyWhrb5hJoE0ahhEpbKVrpOC5ha0B+gUdSwuoBAaaO5kRJWyla6QzHnULiwLdgeODDsIwWoOJrpFOCWrPGAW6ABOCDsIwWoOJrpHOGFrnhxskecDYoIMwjNZgOV1jG14+dws+VS1ccGyMM0cMZL89utEhT7jthWXc9uJyP06dTBzoWlFWYm9kIxLYStdIZjCw1a+THTSgBxvidXyyIe7XKZsjgcZtGJHARNdIZj90ppkvXP7YIs6e9jpLKjf6dcrmqEfjNoxIYKJrJNOZ6ORzGxDC5Q1hGDvERNdIppBoiq7ZPRqRwUTXSKYWnc4bJRxgo3yMyGCiayQTJ5qim9GdOsPwk/ygAzBCxTJ8fE+cdcRAjowVc+CAHgCcOGwP9izuzPNLPuX5JZ/6dZl8NG7DiAQmukYyK/Dx6efIWDFnjBi47fNh/XswrH8P1nwV91N089C4DSMSWHOEkUKstHwBcHjQcbSCBRVlJUcEHYRhtBTL6RrpvEJ08roJYG7QQRhGazDRNdIpR1uBo0AVMCvoIAyjNZjoGum8CGwKOoiW4JzbCLwUdByG0RpMdI0UPEPwm9BVZGhJ1FazYf7DdaunnnKaiHQIOh7DaCkmukZzTCfs7428PDa99fdBwBPAv0XkRyJi7cBG6An3H5YRCN6wxwcIb9NBXODeRM2WS4FVwL7APcBqEblWRHoFG55hbB8TXWN7TAHCOmn3S8kv/IVz7k7UYews4G2gN/Bb4EMRuUNE9g4ySMNoDqvTNbZLrLR8NPA84XLxigNfrygrmZ/8oogIMA64CjjZezkBPA780Tm3IKtRGsZ2sJWusV0qykrmATMIT5ohDkxPF1wAp7zsnJsAHAw8iIruWcDbIvKSiHzDE2fDCAwTXWNnXAYsBKoDjqPai+PynR3onFvsnDsf2ButxNgEfA34B7BIRCaKSGEGYzWM7WLpBWOnxErLi4B5zrmhIuLL/LRWUg0sBUZXlJVsbu03i0gP4IfAz4D+3ssfA7cC07x6X8PICia6RosY+POHixJVG1d06N67T15BVj3D4+gK96S2CG4y3ur2e8CVwDDv5Y3AvcDtzrnKXTm/YbQEE12jRYjIj+iQf89u4y+qLxr+jXqRvGyseONozfDlFWUlvhmVi0geutl2Jbr5BlAH/AW4yTm3xK9rGUY6JrrGThGRY4A5QAFw3qCrn1kNPAoUk5nKhjharnaWt5mXMUTkKFR8T6dxj+MZ4I/AK87+QAyfsY00Y4eIyB5o11cBcIdz7iFPCIegDRTV+NcyXOWd7wFgSKYFF8A596Zz7ky03vduVPBPQW8yr4vIGbvYZpwPnAgcgf29GdhK19gBIpIPvIA+gs8HjnfO1SYfEystLwbOB64AugNdaIW4uEQCycvbjOZWbwJmeB1xgSAivYFLgJ8ADZ1tK4CbgRnOudaUz/0E+D06PFOAzcDv0JRJqL0tjMxhomtsFxG5GS3RWgsc7pz7ZHvHxkrL84DxaK50LLpRlQDqaRQd533kO+c61K79T6eaNUsSXYaOOjW/e+9ZntlOKBCRLsBk9Offx3t5HXAHcLdzbt1OTnEI8DpN0y9b0N/L7d7Hzs5j5BgmukaziMhZwCOoaH7NOdeqR31PhPdBH9s7o2PSa9DH92XAitVTT3kdOAo4xTlX7mP4vuGlFk5H875Hei/HgT8DtzjnVm7nW/+BphW2t+pvWDH/FfgNsMaPeI3wY6JrNEFEDgLeQFMFP3XO3ZGh6/wO+BVarvXzTFzDL5LajK8EJngvJ9B89x+dc28nHb4v8B7QkgqPOqAWOBMVaiPHscS+kYLXSPA3VHAfAu7M4OVme//9egav4QtJbcYlNLYZbwW+C7wlIv8UkZM9cS4Fmt18++qrJunqAqArWi1htANspWtsw6tffRL4FvAucIxzLmMbPl6zwpeo6OzpnPs4U9fKBCIyAO1y+yG6iUj//v0/WL169b75+fkF6cffc889vPXWWyxevJgJEybwq1/9ioKCbYfFUTG3ycY5jq10jWRKUcFdD5yeScEF8CohXvY+PSGT18oEzrmPnXNXAXuh7maVF1988QF1dXVNBPe2227j6aef5tprr2X69OmsXLmS+fNTfHvy0OoGI8fJDzoAIxyIyEnAf6PVBec657K14poNlKCbTg9m6Zq+4pzbAPxx5syZ959zzjlrCwoKUnK5y5cv57nnnmPs2LHEYjFEhJkzZ7J5c4rGvgd8ms24jWCwla6BZ/b9MFrWdb1zLpsTdhvyuid46Y3IMnHixO8XFBRsTX/90UcfZeHChdTW1jJixAjuvfdeAIqKihoO2Qxcn71IjSCxlW47x5sr9je0pbccXe1mkw9Qx68BaE5zUZav7xf5wLVofjqFZ599lhtvvJFJkyYxcuRInnnmGQCcc3j2vl9io+TbDZFeWRi7hrfTfg9wGLAS+L5zLqsNCp63QWSqGHbA6WjFRwrr1q2jW7duTJo0CYA+ffrwySefUFFRgYhQV1dXXVdXdz1afma0A0x02zc/AiahO+enOeeCar9tEN0TA7q+H/wYKEp/cffdd+fAAw/koosuory8nIcffpji4mJisRgAmzZt6tS9e/dfisjFXheckeOY6LZTPOew271PL3TOvRtgOC94/x0TkEm6HwzZ3heuu+46BgwYwB133MFhhx3GNddcA0BdXV3tXXfd9WV1dfVg4C50mvGvRWT3LMVsBIDV6bZDRKQvsACdovAn59zPAg4JEVmIpjm+7px7YSeHh5E/oDW7rRkDVLV06dKB+++///FoyVlym/F0tM3Y6nZzDFvptjNEpAD1wu0PzEPdwcJA1PO696HeEnU7OihpkVMDPDB06NAvnXNPACOB49DNzM7AxcAyEXlMRI5s7lxGNDHRbX/ciLqArQW+65zboUhkkajndVcA+wP/i3oCNzvpImkYsUOtLPUTZY5z7hTgIHQK81bUk+FNEXlZREqiXlZnWHqhXSEiZ6P1uPXAcc65JqPMg8IrXfsKdSPbwzn3WcAh7QoD0CeIi7zP0zfIalCjnPN2dBKvzfin6IZnd+/l91Gx/mu6t3HY8JzmBtPoNFeImvtsc5oLk51ntjDRbSekOYdd6pzLpJFNmxCR59H0wveccw8HHY8PNEwhvho1wOmKCs4XwOFofe5OEZHuqID/HBV00Nrm24H7vY64wEnyVC4BxgAHsANPZfRJ+wPgFTSt8mJ7EGET3XaAiPQE3kR32P8CTAzj7C8RuRLdkJrunLsg6Hh8pBA4Cc3bPofm0lv9+/cMgs5BV9EHeS9vQvPJtzvnAvHk9aaHTPbi6obeXGSH35SKQ83dN6ITOqYHOT0k05jo5jheDvAp4Jtot9eoTBvZtBUROQwdt/4xMDCMN4Yw4DW1fAP19v2a93Idaoh+k3NucTbiiJWWd0H3CH6Armj9qDOuQlfADwBTKspKQvle3RVMdHMcEbkGbe1dDxwR5hIk7waxFugNDHPOfRBwSKFHRI5AxfcMGjfGZ6H+vHMydeOKlZaPQSeLRH4idLYx0c1hROQbNPb0lzjnQj+ZQEQeAr4H/Mw596eg44kKIrIPOs/tAhpF8G1UfP/mnKv34zqx0vKOwK3oMNJMiG06cbSS47KKspJmK0KihpWf5Ciec9hf0dzab6IguB5Rr9cNBOfcSufcT1Bv31+jAy+PQGuyl4rIJbvaZhwrLS8C/kn2BBfvOucDL3nXjzy20s1BvD+u+WiH1zPAqdk2smkrXpnUGnRjZbewl0WFFe89MAn4BVq2BVo1cSdwl3Pu89aczxO8ecBQWjb7zW+qgaXA6IqykkibvZvo5hjeJssMYCJasH+Ec259kDG1FhFZgpYbjXPOzQ06nijjTTP+NtpmfJT3cjWNbcb/2dk5vJTCP4HhBCO4DVQD7wDHRznVYOmF3OPHqODG0ZE764MNp0087/3XUgy7iHNuq3Puf4Gj0WnGz6DC+WM07fC4iBy1o3OgOdzDCFZw8a4/HLgl4Dh2CVvpRoex6Bt/APAYaliTguccNgedMHuuc+6v2QzQL0SkBBWHN5xzRwcdT64hIsPQmtrz0PcKwFx0021WcirKq1J4juzlcFtCHDgxqlUNJrrR4Cp0cyQPbZOtBu71Xq+HJs5htzvnfh5IpD4gIkVot1YHYPcAfX5zGhHpj7YZ/5jGNuMleG3Gg65+pgOwHH1PhY1KYEgU63gtvRB+vo0Kbhf08UrQVcdFaPtk7zTnsFfQus3I4pzbDLyGvj+PDzicnMU5V+mcuxoYiK581wDDgD8DK+Or353tnCsOMsYdUAxMDTqItmCiG26Gom27zZX6dEX795ecdtppD6Lph08Il3PYrmB53SzhnNvonLsZrXKYBCzO69i1f8f+Q0d5RkRhpDNwodeCHClMdMNLN3aeSysEdv/LX/5yzkUXXbQVOMM5tzYr0WUeq9fNMs65WufcTOCQ3U/75TREwl5mmEBreCOF5XTDiQBPo45NLdoxrqurqy0oKHgMuBDN+UYar9Tpc/Qxct8wty/nGp5b2BqgX9CxtIBKYGCU3MlspRtOrkSnCGwT3Pr6eqqqqkgkmn9vFRQUFALfQTfT9spCjBnFObcVeMn71Fa72WU8+qQVBboTsby/iW742Af4DZqz3call17K97//faZMmcL69eu3972dUcPo92ictxVlLK8bDCWkvf9CTBdgQtBBtIb8oAMwmtDkDXT11Vezfv16/vCHPzB58mTmzp3Lt771LRKJBHl5Te6b+ejd/wVgb1polB1SGvK6x4tIB2/1a2SeMbTOD3e7lJ12MEcMKqZ/z87Ubk3wr4/Wc8OsD1j+mW+dvHnoJnJksJVu+KgkabjhW2+9xbPPPst9993H4MGD2Weffbj//vs544wzuPnmm9mwYbtDAxzaShtZnHOr0Fbmnqh5i5FhvHzuML/Od85Re7G5pp7/W1TJ5up6vja0DzMvOIqO+b5Kz7BYabkvN4lsYCvd8PEuSf8uRx55JP/4xz/o3r078+bN47nnnmPx4sUsXLiQ6dOn8/TTT3Peec2O2spD6y+jzmy0lOlEdNyQkVkGowMxfeH0e17lnQ+1t2XPnp2ZN+V4+vXozL59ini/cqNfl0mgce/URyIM2Eo3fPwHLYPZ1mnTr59uIo8ePZoFCxbQq1cvTjjhBE466STeeecd6uubtUrNRxsMoo7ldbPLfnhdjn7QILgABd7qdmvC8dkmX/1q6tG4I4GJbjh5HN1B/gIv1dBQ2te3b99tBz322GMMGjSI/PwmDyxb0M241ZkPNeP8E13JHCMiUdlRjzKd8Smfm0yXwg7cdMahAEx7ZSWf+yu6DV2akcBEN7y8DhwI/Kuurq5WHRshLy+PrVu3ctFFF9GjRw9+9rOfpX9fNfAyal4SeTyXtDfRlfu4YKNpFxTis+gWdyngrz84mhGDivnrmx8y9dl/+3l60Hg7+n3STGGiG24+LS4u/sV9992Xv2XLlm0vbtq0iWOOOYYHH3ww/fgE8Ck6MTaXul4aqhhODDSK9kEtPr53BvTszBM/GsVhA3ty98v/4ZdPvufXqZNxQGT8dU10Q4yI9F2/fv2jl156ad4NN9wwC83zup49ezJ58uTm0gpxdNT3pmzHmmEsr5s94vgouv/7o1EM7l3Emq+q6FTQgetOGcZ1pwzj0D17+HUJ0Hjjfp4wk5johhTPOewxtBVz7g033PBt1Pm/kubv6lXA99GRJrnGG+iNZH8R2RNNNRyD5q1fA1aiNpeFQQWYQyxzzvlW1dS3hzZV7lnchQuO3Xvbx5A+vqbn84Flfp4wk5j3QkgRkVuBn6MiOyLJyKYHutE2Cu0aarjLT0VHreciMnz48NnHHHPM+ClTpiwZNGjQ3uiOdScaTbi3oF4NB5AD3hPZRES6o++nsYiMG3j5E6PyCiKTIgV9/3etKCuJhJiZ6IYQETkHneRbBxznnHs1/RDgDOC7aInZ68Dfsxpk5ikGTgC+CXyjrq6uZ21tbUHXrjvsTt0MXIrOiDO2g4j0AkajnVzj0BE42556+55/Gx377htQdG1iQUVZSWSaZ6w5ImSIyMHAA96nlzUjuKCr28e9j1yjEB2a+B00jdINkIKCAgoKCnb4jUARmmKZkckAo4Y3VWRs0sfBaYfUoymcucDcgt32PAX4ERkoHcsACTTuyGCiGyJEpCfwJGriMRO4O9CAguFSdFpGR9pWBjQKTTnkgpF7mxCRvdAVbIPIpjcO1KBPR3NQwXrdObetPCZWWl6H3ryKshLwrlEFzAo6iNZgohsSRCQP+B+0nfFfwI9c+8v9dAaup/lJGS2lFt1wnO9LRCFHtIB7XxpTBWOBQWmHbUF/H3NRoX3LObejEqsX0Y3LKIjuRhotQCOBiW54+BVwCvAVOjo9MiUwPrKVVo75ds5RWVnJ8uXLOe6440CF+xvkqOh6N+dhpIps37TD1qOz8hpEdqFzrsWtvRVlJYlYaflN6MbsrtwAM00VcFOUDMzBRDcUiMjJ6ArPAd/z3LXaI7XonLc9m/tic1aWIkJdXR1XXnklM2bM4MADDyxA0xPXZjrYbOBN0DiMxlTBGKBX2mGf4eVjvY/3kseot5HpwO938RyZJo8I5u+tTjdgRGQftFJBgF87554NOKSgKUc3R5owdepULrvsMtatW7fttZqaGmKxGGPHjuWpp55qeHk/tLQucohIoYiMEpGrRWQW+uTzNnALejPphY7SeQj4IVoi19c5d6Zz7g7n3CIfBJeKspKv0A3dsD5xxYFpXpyRwla6ASIiXYC/oX6xTxP+lUU2KEfbmLunf2HNmjU88cQTVFZWMnjwYCZOnMj+++8PwODBg1m5cmXDoXF0h35elmJuM9603ZE0pgqOoal5ywoaUwVzgYos5funAKc3E08Y+BK4Ougg2oKJbkB4GyD3AoeitbYT/Vih5AAvs5287nnnnceaNWuYNm0aU6dO5eKLL6a4uJhOnTrx3nvvMW3atIZDOxDS7jTPKW0UjSJ7FI0NHg0soVFkX3HOfZzVID0qykqqYqXlZznnng/ZKPY4cFZFWUnVTo8MIdYcERAicglwJ7oZMNI5tzjgkMLEIuCQ9Bfr6+s54IADWL58OaAr32eeeYaePXsycuRI9t57b9C8+HtoHjTwN7eI7EbTRoQOSYc4tFqlIR/7inPu8yyHuV1EJL/3d659r1PssP1D0qUWB6ZXlJVcEnQgbcVENwBEZBS6iskHznHOPRJwSGHj12g1R5NuiN/+9recc845DBkyJP1LCbQ0qho1/VmY6SCbQ0T2oGkjQnKTQT2ao20Q2fmefWXo8NJfj9Ehv6Tv96YmCvvtVy95eUE+QVQD7wDHV5SVRMZVLB0T3SzjdQe9gxrZ3OacuyzgkMLIcDQf26RcqaamhsLCQkSEeDxe37lz563AWjQn/gxaY+rb5IOdISIDSW1EGJoeMtrtldyI4NtUxkwhIrujv9OjgS8K+ux9Zv8L7rgV/flaVdbnE9WomdPoirKS0P/+doSJbhbxnMNeRMt+5gInOOfabefUTngDOIhU4a0GtiYSiQ6rVq3q1K1bt0Tv3r1rROQTYDIZbgf18vCDSa2RjaUdtgV4ldRGhEgZ8IjIIOA5VGBXAyc555bGSsuLUJvNw8ju5locfXI5KeqCCya6WUVEbgN+hjqHHe6c+zTYiEJNJ+AXwDXe5xvRzbGuzrl4IpHo3qFDcmqUKrSF+M9+BeA1IhxAqsj2SztsA00bESJ7IxWRQ4Bn0Z/zXeBk51xlw9djpeUd0fK1yWRHeONozfDlUU4pJGOimyXSnMPGOedyYWhkptkPHdWTh7ak7syAZTVNV54txmtEOJTUnGx6I8LnNG1E8G16bpCIyHGoW113tIrk2865Dc0dGystHw08irrBZUJ842iN8lkVZSWhL/1rDSa6WcBbPbyOvjkvcc61RyOb1iJoK+9RpO7274hq1IegRSVWXrrnCBoFdjRN64Mr0RVsQ07237noiSEiZ6ANF4XAE8D3d5YWiZWWd0F9nC9ENzL9aBmuQm+y04Cro1oWtiNMdDOM5xz2NpoLnAmcn4t/tBngYPRG1Zo/5E3ARUCz1SBerelRpDYipJ9/JY2r2DnAqlz/9/LKF+9Ab3R3AT9rzeo9VlpeDJwPXIHetLrQum7XBCq2G4GbgBlR7DRrKSa6GcTLCf4dNbL5FzCqnRrZtIUY8D5povjhhx8ye/ZsFi9eTElJCSeccELylx3wIJpvbGhEOIbURoT0kqcPSEoXOOfW+P+jhBNvY/B3wC+9l34FlLX1JhMrLc8DxgMno7/vYaig1qOCLui/kUPLJfNobASZBbwUNfOatmCim0FE5DrUyOYrdOROezWyaQt56Mp1m+iuXr2aSZMmMXDgQEaNGsW9997LnXfeyZgxY7Z9U1VV1bquXbvOQIX2cJo2IiwitRHhs8z/KOFDRPKB+9Eb1FbgQufcdD+v4YnwPmhuvjPqj1yD5muXASuiMmLHT0x0M4TnHFbufXqyc+65IOOJKC8BX2v4ZMOGDaxdu5ahQ7UU9oorrqBPnz5cccUV29zHqqurGThwYIMpzlZgAY352PnOuZx9bG0pItIV3QQrQQXwTOdc+Y6/y/ALcxnLACIymEbnsOtMcNtMOUlDJnv06MHQoUOpq9OKrKKiIlasWJFi91hfX7/1wgsvfAI4EejpnBvpnLvKOfeMCe62pocXUcH9AjjeBDe7mOj6jNc6+b80OofdEGhAEUVE5JFHHllRW1vb5GsFBQVs3LiR+fPnc8EFF6R8raioKO+GG2743Dk3OwqdX9lERGJop99ItLzuWOfc64EG1Q4xlzEf8TYm7kNrPZejZTc5vzHgB97vrqERYSww9rzzzhuwadOmZo9/6KGHGDBgAEcc0WQIrKCrXCOJnTU9GNnDRNdfLgHOQ8tfTt9eYbmxrRHhEFIbEXZPPmbr1q3rVq1alTds2LDdGl5zzlFbW8ucOXOYOnUqHTp0YN26dfTq1QvVbQAGok8a67Pwo4Se1jQ9GFnAOWcfPnwAx6LdZg44K+h4wvaBOoaNBK5CjWnW01g+1PBRCTyMjv8ehm70/tI5V+OSuP76613v3r3d2Wef7YYNG+YuvfRSt3nz5uRD1jvnTgr6Zw7DB3AGWjHggMeBTkHH1N4/2u1K1ytnGUxjOUshOqMruZylRakBzznscfTJ4Vbn3KMZCTpCiEgnUhsRRtG0EWEVqRMRVjpPKZKYg26mFYIuEjp16sQJJ5zAueeey/Dhw+nfv3/65fPZzpy19oSI/AT4E5pyuRP4ucuRluUo025KxpIKt0tQl68D2Hnh9geomUk58GJzIuy1kr6EtpC2W+cwESlCGxEazGFG0rQR4d+kNiJ81IJTd6TR7KalxFF7yKWt+J6wk4+aJR2CVh08ib43m9BM08MvganN3NCMAMh50fVaFCejLYrdgK7s3DglGYfa9W0EbkZd67eVHonI7cBPaWfOYV57c8NEhLHACFL3CBy6YZPciNDW382bwJEtOdA5VyUidwNXtvFaYaQXMBt9KuvqvRYHfox24G3DWwTcR2PTww+cczOyFqmxU3JWdD0zjhuBH+C/GccDwJTVU0/5NmoSUgeMdTlcfiMivUnd9DqU1JvXVtScPbkR4UufLj8RuIfm/w1rgNqampqit99+WzZs2PCbCRMm/J4sGplnmEHo77MvTVf7ceAstDSxoenhMWAC1vQQWnIypxsrLR+Dmp4U46/LfcMf/X+5rfVnddzzwO41a94HNQjJKcEVkQGk+sgekHZILboCbcjJvuaca76+a9d5CNgD+A16g+uA3vzeQgVnbvfu3SfX1tb+GHDOuVwR3IOBf6KVGM05rXVG3+cniMhydINyJJp+KHHOvZGlOI1WkFMrXc9g+VbU8SjjBsuJuhqqKxYuLeyzz6Fr7p4cWYNlLwe4N6kiu0/aYXFSJyK86bJv3tMfzWl+hObbt+XYReRU4Cl0hT06y3FlgnGoiO40HZZIJDYffvjhny9atGhvkiY9ZCFGow3kjOgGNUrEORcXkUiNEvFEdn8aUwXjgAFph21Eu5cacrILnHNN28NCgoj0QFd4ALs55zYGGc8uUoKmCVLSKc45tmzZQlFRUcrBiUSCdevWMXLkyCUVFRVfd9b0EGpyQnQ9wZ2HDc1rFq8R4WBSc7K90w77gtSJCIuiVl4kIvPR0rRTnXP/F3Q8bWRf1Aa0a/KL69at47vf/S5XXHEF48ePp2PH1HHo9fX1TkQqOnTocDjWFBJqIp/T9VIKzxOc4OJddyjwXKy0PPDx0N4O9nAaUwWj0bxgMp+QWiP7gYt+y/JsVHS/DkRVdI8kKW0CKrjf+c53GDduHBMmTGj2m/Lz8wVNv8xGSyIjNQyzPRF50UVzuIcRnOA20AkVulvQduCs4TUiHElqI0LXtMMqSBXZFTlYt/k88Gui7b3QjbRNs3g8zpAhQ/jtb38LwN///ncGDRpE165dGTJkSPKhHYEDgb8B30QrSoyQEWnR9aoUzie746B3RGdgcqy0/OFMDtPzSoPSGxE6ph22lNRGhA8zFU+IeBPNRe8nIntF9GdeQNrG2bp16/jwww9xznHJJZewatUq+vTpw4YNG7j22msZMWJE8uGd0ffFFWjJpBEyIpvT9epwl6OPVGGjEhji11A9rxHhWBrzsUfQ9IaZ3oiw1o9rRw0ReQo4FW0K+H8Bh9NWfgf8nKSnlYkTJ/LRRx9x1FFHceONN/Lpp58yY8YM6urquOaaa5o7x0agR3bCNVpDlP10/4DW4YaRYnRKapsQkd4icrqI3CYi7wBfouVDVwFHo/9ub6MdcqcCvZxzhzrnLnXOPd5eBddjtvffrwcaxa5xLeoKtu2mfcMNN9CpUyfmzdMHqD322IMePXoQj2+3ai9XapVzjkiudL3W3kqCz+PuiGqgf0ummopIf1JrZIelHVJH00aEKJdEZQwRGYIaFn0B9Inw5mA+8FwikRiVl5fXCeCDDz5g0qRJjBs3jpKSEn7xi19w+eWXc+6556Z/r0PrmA/McsxGC4jqSncyaTu8ISSB5ptTEGVvEZkkIn8Wkf8AH5NqaRhHTXR+AxwP9HDOjXZqc/icCe4O+Q/aINAL3diMKvXjxo27ZNmyZVJTo8UwBxxwALNnz6ZTp07MmjWLKVOmNCe4oCvkZr9gBE/kVrqeW9ga1AE/7FRu+fe8geuemrofqY0I6baDm0htRHg7zI0IYUdEpqGeG6XOuTaneYJERA4F/tGrV69+7733Xl3fvn3zvHrrHZFA30snok9GRgiJ4kp3PFpWE3oSdTV9Nr87+wv0Ue8+dPWxJ5qj/TtwOboptptzboJzbqpz7lUT3F0m0nldb9LDXKDfF1988fLbb799uIhsQNMG26MO+Bz1MDbBDTFRLBkroWkNaiiRDgX5nWPDe1avXLCW1BrZJRHONUaBF1GBGi0iXZxzvlSRZAMRORP4C+oo9jjw/W9+85s16Cj6+UBRM99WA3yIPkm1503USBBF0R1D6/xwt0vH/DxKTz6AUw7pR1HHfBZ/vIHfzfqAf3203o/TI3l5FA0/efFXLz1wSA42IoQW59wXIrIAfYoYiw5kDD07mfTwLtrwUE6qJ0OV97WT0DIxI+REKr3g5XPTd/bbzHWnDOP8UTHWba7h+SVrOXyvYv7ngqMo7lLg1yXIK+g4eNDVz/h2PqPFRCbF4G2u/h64AxXcXwI/bcb74mX056lErTUTwP3AcZjgRoaorXQH41NrY6+uhZw5YiBbE45zH3iDL7bUUp9wnD58TyYdE+O2F5f7cRnQP4zB6K66kT1mA6WEXHQ9n4z70UqXlkx6eJVGR7iGEVNGhIjUShcdV+JL0fd+e3SjMD+PyvVxvtii+1bvrdGp1MP6dffjEg3Uo3Eb2eVV9NH7YBEJZaWL1879FCq4VcC3WjlaxwQ3gkRNdDvjUz539yKdfLKltlHDq2p1Ed27W7qNwS4hhMcbot3gnKtBNy4BTggyluYQkd3RDb8JaCPH8c65WcFGZWSDqIluIT6J7rrNurrtWtiYYenaUcsgP9/kqzOj0NSMxsgOoczrikgMrUQYiTZyHGujddoPURPdWnx6pFr+2SZq6xP079l526r3kD17AvDBWl/3JBxa0mNknwbRPcGblhE4XtPDa2jKaREwykbrtC+iJrpxfBLddZtreeKdNXTIEx76r6O54+zhfOuQ/myuqefB11b7cYkGHBq3kX3eR83a+xECHwIR+RqNk31fBsbZaJ32R9REdxk+Vlxc//T7zHytgt2LCjlx2B4s/Gg9E//8Bl9u8a8hzCUSHes3rVvp2wmNFuPVRjesdgM1NveaHp4FuqNND99wzm0IMiYjGCLlveDV6W4mQhtTiboaPrr5O3G0NXO+9/Gac26n7mM+cyLwU+Az4HUvjpSJurmIiJwH/A/wrHPu5IBiSG56uANtesjp37uxfSIlugCx0vIFwOFBx9FSaj+rqP7kzz9pzoJyCY0iPJ/Mjc8R4BHgFBo7mbagaY884B10BTYPeIskD9dcQET6oimGOFDsVTVk69qCGpL/0nupFLjRuhPbN1FrjgB4BbXsC8XGyE5IFPaJ3QPcgM4tO9b7OALtrBsGXOgd+6mIvEqjCL/jk/HNsWhZUnLraLJ3xWjUJKUafYJYAbyAllvNRwUrsjjn1orIe+g05FGx0vI5aLPKfujPW4hu0MbR9NWKirKSXV6FtqHpwWgnRFF0y4H/onnjj7BRBcxyzq1Dp9P+H4CIdARGkCrEewCneR8ANSLyFo0i/Kpz7os2xPBdUgW3OQq9D4D9UUGaiJa6bUCnVtwKLG7D9QMlVlqeV3TYN5YW9Bp4cJeho/6KjrBJoE0rQmNXl0P/HvJipeUfoDf3cuDF1oqw1/TwGHqzqwLOtBpco4Eophci5acLDNzZH633GLovjQJ8LHBAM4f+m9SUxPIWPKouST/XjTfeSH5+Pqeeeir77rtvS36OrehKcCj6M4Ueb7rIZOAKl9jaE6Sz5LVq39ihaZiN6Fik6S2cArI7epMaiTY9lFgNrpFM5EQXIFZafjnw3+x8BRckVcA1FWUlt7blm0WkFzrxt2E1fBRNxxOtQ9tdG0T47bScZWd0pbrNwae2tpZbbrmFhx9+mN69e/PCCy8AUFNTw6JFizjwwAPp2rVZ58w6dMT5KW35ebKFN7D0RtTEPIE/75EqNP/9ADBlewNHvaaH59AnhdXASVaDa6QTVdHNqRlpLUFECtFcdvJqeI+0w2rRgZXzgflvvvnm1iOPPPIhtEwJAOccIsLUqVP5/PPPufnmm1m5ciVPPPEEjz32GBs2bODCCy/kqquuai6Mr4Dd/Ph5MkGstHwMumlYTGYqXOLo7+CsirKSeclf8JoenkVrcBcBE6wG12iOqNXpAuAJ2QOEt+kgDkzzS3ABnHO1zrk3nHO3OOe+g6ZX9gUmoVMpFqMr2lHAlcBTf/vb356ura1NmbLR0Jg1Z84cRo0aBcBdd93F2rVree2113jyySepqKjgww8/bC6Mz/z6efwkVlreMVZafje6yuxP5koKO3vnfz5WWn53rLS8I1jTg9E6oriR1sAU4HTCWbP7JXB1Ji/g5XJXeB8zAUSkJ5qSOBY4dsKECWMLCwub3Fg///xzKisrt4nuk08+yeOPP05BQQEHHXQQy5Yto7Kykr322ivlkqighIpYaXkRmvY4jOy9FzqjVQmH5vfsey+6ANg26SGbZWlG9IjkShfAy6udRfhWu3H08TPr9a7OufXOuX84565xzo0fPXp0dXPHvf/++3Ts2JF+/frx1VdfsX79ekaMGLHt6++++y7DhjXxit8M/DNz0bceT3DnoWmXbN98O7vE1iP7nP6rmVLQqRBtejjbBNfYGZEVXQAvrzaD8AhvHN3lnh90IMBQEWk2Yb9y5UqGD9fp5K+88gr777//tq8tXLiQrl270r17d9Ly/QXopl0o8B7tn0crKgLJ7Uteh4L83QbQ/wd3rx7w4z9faV1mRkuItOh6XAYsRDeugqTai+PygONo4Nj0F55//nkmTJjAddddR36+Zpa2bNmSsqqdNWsWo0ePBkgR3Y0bN3YQkYkicpyIhKFq5FY0pRDoZmpeQUfye/Tpk9+jzy1BxmFEh8iLbkVZSQ06lG8pwQlvtXf9k7x4wsB40qYmjx49mh/+8IecffbZzJ07l2uvvZYxY8ZQW1vL9OnTeeihh1i6dCkXXHAB0LjpBjBnzpwCtKX1n8AGEXlTRG4VkTOyPZnBq1I4n/Dk8zsDk2Ol5aODDsQIP5EsGWuOgDZUQFMKC1HB3ZzF6+6MfwGHtuTAxx9/nJkzZ1JVVcWtt97KwQcfnCK4iUSi+sknn3zkjDPO2IJWRxxK0xv2KpK654D3mxmsuMt4dbjL0SqCsFEJDAkin29Eh5wRXdiW57sF7UTKhvDGgenA5SFa4TYwG/ga0MGHc20CxqE3F0SkG9px1VAvfDTQLe17NqJm3Q1C/IZzbsuuBhIrLb8TuIDwrHKTiQMPVJSV/DToQIzwklOi24D3mPcoARTJh4j90NWuHz9/Dep10exQUBHpgBrKJDdu7JV22FYvnoaV8Hzn3JrWBNEem2KM3CPyOd3m8IRwCFo/WY1/doVV3vkeQB8jwyq4oI5ZFwAfoTeJXUl9LGIHU5idc1udc/9yzt3lnPuec24QMBAt6fsTsMA7dATq6fsI8JGIrBaRv4rIJSJymCfeO2Iy4ff/TaD5ZsNolpxc6SbjrY7OB65A22G70LqbTQIV243ATcCMiK1iBNgbXX2OB45D86FxdKNtZ0IXB34LTN2lIESKUP+IhpXwMSS1J3tsotFg/VXgdefcJshNoyOjfZLzotuA90c7HjgZGIt62e7Q4g916JoLzAJeyqE/op5oHnYsOlHiINS3oYDUR/cGn9n9gbV+BuCtaoeRmpLYO+2wBPAuML/HmPM29hj13Z+K5DXrxhMyNgOnVZSVvBB0IEb4aDeim44nwvvQaGbdEc1dJptZt5dfTgFwCCp8JwFHor6zTwMXkyXPBa/0LFmEh+O1qhePv5BuI75JK+0ZgyIB3F5RVhKWmm0jRLRb0TXCj9eEcRRwbP8L77uqoNeA9HREm7n5zEM5dvDuFHctYEvNVt77eD1/eHYp73+y0a9LLKgoKznCr5MZuYOJrhF6vKeSLfhYtfDIhUfz6cZqNlXXc8zgXgzuXcSar6oY/Qff7CXiQNd29LRktJAou4wZ7YfBaMmZb5w97fVt/39g/+6UXzqGfj06k58n1Cd80ckEGvd//DiZkTuY6BpRYD92ULLWViYeM4ghfboxanAvAKa9stIvwQWNdz9MdI00THSNKNCZDEx/nnBQP47eRwW3cn2cBat9rQQUwtk1ZwRMJLaCjXZPIRkQ3bOnvc7Qa//BhTPfZo/unbj73MPZs6dvOiloRYxhpGCia0SBWrR+2hc65ueR50l4TX2COcs+Z0ttPQUd8hi4m2+ulQ4tQTSMFCy9YESBOD6K7vCBPbn97OG8uepLNsTrODK2G907FbBucw2LP97g12Uc4THXN0KEia4RBZbh43v10001rFq3hdFDdqdrYT5fbqnlmXcr+dNLy9lU49t+XT4at2GkYKJrRIEV+JgKW7VuS0rJWIbIQ+M2jBQsp2uEHs/z4oOg42glS6wxwmgOE10jKryCj3ndDJNAjZIMowkmukZUKEdbgaNAFepMZxhNMNE1osKLqN9uFNgIvBR0EEY4MdE1IoGX170J/6aAZIoq4KYc8l42fMZE14gS0wn/ezYPmBF0EEZ4Cfsb2DC24Y1JeoDwNh3EgWkRG+dkZBkTXSNqTEEnMYeRL4Grgw7CCDcmukakqCgrqUKnDIdttRsHzvLiM4ztYqJrRI6KspJ5aN40LMIbB6ZXlJXMDzoQI/yY6BpR5TJgIVAdcBzVXhw2hNJoETYjzYgssdLyImAeMBQf56e1gmpgKTC6oqxkcwDXNyKIrXSNyOIJ3Wh0pZntVEMceAcTXKOVmOgakcYTvK+hNbzZEt64d73jTXCN1mLpBSNniJWWjwYeBYrJzHyyOFqudpa3mWcYrcZWukbO4AnhELSBohr/WoarvPM9AAwxwTV2BVvpGjlJrLS8GDgfuALoDnShdYuMBCq2G1HPhxnWaWb4gYmukdPESsvzgPHAycBYYBgqqPXoxF5BfXodOkklD1iC+uHOAl4y8xrDT0x0jXaFJ8L7APuhed+O6NTeODrTbIVNfDAyiYmuYRhGFrGNNMMwjCxiomsYhpFFTHQNwzCyiImuYRhGFjHRNQzDyCImuoZhGFnERNcwDCOLmOgahmFkERNdwzCMLGKiaxiGkUVMdA3DMLKIia5hGEYWMdE1DMPIIia6hmEYWcRE1zAMI4uY6BqGYWQRE13DMIwsYqJrGIaRRUx0DcMwsoiJrmEYRhb5/+czw0W2lxPWAAAAAElFTkSuQmCC", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# n is the number of vertices in the graph G\n", "n = 4\n", "E = [(0, 1, 3), (0, 2, 2), (0, 3, 10), (1, 2, 6), (1, 3, 2), (2, 3, 6)] # Parameters for edges: (vertex1, vertex2, weight(distance))\n", "G = nx.Graph()\n", "G.add_weighted_edges_from(E)\n", "\n", "# Print out the generated graph G\n", "pos = nx.spring_layout(G)\n", "options = {\n", " \"with_labels\": True,\n", " \"font_weight\": \"bold\",\n", " \"font_color\": \"white\",\n", " \"node_size\": 2000,\n", " \"width\": 2\n", "}\n", "nx.draw_networkx(G, pos, **options)\n", "nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=nx.get_edge_attributes(G,'weight'))\n", "ax = plt.gca()\n", "ax.margins(0.20)\n", "plt.axis(\"off\")\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Encoding Hamiltonian\n", "\n", "In Paddle Quantum, a Hamiltonian can be input in the form of ``list``. Here we construct the Hamiltonian $H_C$ of Eq. (4) with the replacement in Eq. (5). It can be realized with a build-in function \"tsp_hamiltonian(G, A, n)\".\n", "\n", "**Note:** For the salesman problem, the number of qubits can be reduced to $(n-1)^2$ since we can always select city $0$ to be the first city." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:24:25.956145Z", "start_time": "2021-05-17T08:24:25.950463Z" } }, "outputs": [], "source": [ "# Construct the Hamiltonian H_C in the form of list -- with build-in function tsp_hamiltonian(G, A, n)\n", "A = 20 # Penalty parameter\n", "H_C_list = tsp_hamiltonian(G, A, n)\n", "# Generate the Hamiltonian\n", "H_C = Hamiltonian(H_C_list)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Calculating the loss function \n", "\n", "In the [Max-Cut tutorial](./MAXCUT_EN.ipynb), we use a circuit given by QAOA to find the ground state, but we can also use other circuits to solve combinatorial optimization problems. For the TSP, we adopt a parametrized quantum circuit constructed by $U_3(\\vec{\\theta})$ and $\\text{CNOT}$ gates, which we call the [`complex entangled layer`](https://qml.baidu.com/api/paddle_quantum.circuit.uansatz.html).\n", "\n", " \n", "
Figure 1: Parametrized Quantum Circuit used for TSM Problem
\n", "\n", "After running the quantum circuit, we obtain the output state $|\\psi(\\vec{\\theta})\\rangle$. From the output state of the circuit we can calculate the objective function, and also the loss function of the TSP:\n", "\n", "$$\n", "L(\\psi(\\vec{\\theta})) = \\langle\\psi(\\vec{\\theta})|H_C|\\psi(\\vec{\\theta})\\rangle.\n", "\\tag{7}\n", "$$\n", "\n", "We then use a classical optimization algorithm to minimize this function and find the optimal parameters $\\vec{\\theta}^*$. The following code shows a complete network built with Paddle Quantum and PaddlePaddle." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "# In this tutorial we use build-in PQC: complex_entangled_layer()\n", "def cir_TSP(N: int, DEPTH: int) -> Circuit:\n", " cir = Circuit(N)\n", " cir.complex_entangled_layer(depth=DEPTH)\n", " return cir" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:24:26.790290Z", "start_time": "2021-05-17T08:24:26.768068Z" } }, "outputs": [], "source": [ "# Define the loss function\n", "def loss_func(cir: Circuit, H: Hamiltonian) -> paddle.Tensor:\n", " state = cir()\n", " loss = paddle_quantum.loss.ExpecVal(H)\n", " return loss(state)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Training the quantum neural network\n", "\n", "After defining the quantum neural network, we use gradient descent method to update the parameters to minimize the expectation value in Eq. (7). " ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:24:27.958085Z", "start_time": "2021-05-17T08:24:27.952965Z" } }, "outputs": [], "source": [ "DEPTH = 2 # Number of layers in the quantum circuit\n", "ITR = 120 # Number of training iterations\n", "LR = 0.5 # Learning rate of the optimization method based on gradient descent\n", "SEED = 1000 # Set a global RNG seed " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here, we optimize the network defined above in PaddlePaddle." ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:26:08.098742Z", "start_time": "2021-05-17T08:24:28.741155Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "iter: 10 loss: 46.0240 run time: 2.0117030143737793\n", "iter: 20 loss: 22.6653 run time: 3.6998016834259033\n", "iter: 30 loss: 16.6194 run time: 5.470264673233032\n", "iter: 40 loss: 14.3720 run time: 7.512751579284668\n", "iter: 50 loss: 13.5547 run time: 9.417967319488525\n", "iter: 60 loss: 13.1736 run time: 11.14768385887146\n", "iter: 70 loss: 13.0661 run time: 13.029551029205322\n", "iter: 80 loss: 13.0219 run time: 14.56725525856018\n", "iter: 90 loss: 13.0035 run time: 16.211774110794067\n", "iter: 100 loss: 13.0033 run time: 17.93900489807129\n", "iter: 110 loss: 13.0008 run time: 19.850960731506348\n", "iter: 120 loss: 13.0004 run time: 22.275184869766235\n", "The final minimum distance from QNN: [13.000355]\n" ] } ], "source": [ "# Fix paddle random seed\n", "paddle.seed(SEED)\n", "# Record run time\n", "time_start = time.time()\n", "\n", "# Total qubits number: (city number-1)**2\n", "num_qubits = (len(G) - 1) ** 2\n", "\n", "# Create the circuit\n", "cir = cir_TSP(num_qubits, DEPTH)\n", "\n", "# Use Adam optimizer\n", "opt = paddle.optimizer.Adam(learning_rate=LR, parameters=cir.parameters())\n", "\n", "# Gradient descent iteration\n", "for itr in range(1, ITR + 1):\n", " # Calculate the gradient and optimize\n", " loss = loss_func(cir, H_C)\n", " loss.backward()\n", " opt.minimize(loss)\n", " opt.clear_grad()\n", " if itr % 10 == 0:\n", " print(\"iter:\", itr, \" loss:\", \"%.4f\"% loss.numpy(), \"run time:\", time.time()-time_start)\n", " \n", "# The final minimum distance from QNN\n", "print('The final minimum distance from QNN:', loss.numpy())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that ideally the training network will find the shortest Hamiltonian cycle, and the final loss above would correspond to the total weights of the optimal cycle, i.e. the distance of the optimal path for the salesman. If not, then one should adjust parameters of the parameterized quantum circuits above for better training performance." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Decoding the quantum solution\n", "\n", "After obtaining the minimum value of the loss function and the corresponding set of parameters $\\vec{\\theta}^*$, our task has not been completed. In order to obtain an approximate solution to the TSP, it is necessary to decode the solution to the classical optimization problem from the quantum state $|\\psi(\\vec{\\theta})^*\\rangle$ output by the circuit. Physically, to decode a quantum state, we need to measure it and then calculate the probability distribution of the measurement results, where a measurement result is a bit string that represents an answer for the TSP: \n", "\n", "$$\n", "p(z) = |\\langle z|\\psi(\\vec{\\theta})^*\\rangle|^2.\n", "\\tag{8}\n", "$$\n", "\n", "Usually, the greater the probability of a certain bit string, the greater the probability that it corresponds to an optimal solution of the TSP.\n", "\n", "Paddle Quantum provides a function to read the probability distribution of the measurement results of the state output by the quantum circuit:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:26:08.152206Z", "start_time": "2021-05-17T08:26:08.103516Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The reduced bit string form of the walk found: 010001100\n" ] } ], "source": [ "# Repeat the simulated measurement of the circuit output state 1024 times\n", "state = cir()\n", "prob_measure = state.measure(shots=1024)\n", "reduced_salesman_walk = max(prob_measure, key=prob_measure.get)\n", "print(\"The reduced bit string form of the walk found:\", reduced_salesman_walk)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As we have slightly modified the TSP Hamiltonian to reduce the number of qubits used, the bit string found above has lost the information for our fixed vertex $n-1$ and the status of other vertices at time $n-1$. So we need to extend the found bit string to include these information.\n", "\n", "We need to add a $0$ after every $(n-1)$ bits to represent $x_{i,n-1} = 0$ for $i \\in [0, n-2]$. Then at last, we need to add the bit string representation for vertex $n-1$, i.e. '00...01' with $n-1$ 0s to represent $x_{n-1,t} = 0$ for all $t \\in [0,n-2]$. \n", "\n", "After measurement, we have found the bit string with the highest probability of occurrence, the optimal walk in the form of the bit string. Each qubit contains the information of $x_{i,t}$ defined in Eq. (1). The following code maps the bit string back to the classic solution in the form of `dictionary`, where the `key` represents the vertex labeling and the `value` represents its order, i.e. when it is visited. \n", "\n", "Also, we have compared it with the solution found by the brute-force algorithm, to verify the correctness of the quantum algorithm." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:26:08.169372Z", "start_time": "2021-05-17T08:26:08.156656Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The walk found by parameterized quantum circuit: {0: 1, 1: 2, 2: 0, 3: 3} with distance 13\n", "The walk found by the brute-force algorithm: {0: 0, 1: 1, 2: 3, 3: 2} with distance 13\n" ] } ], "source": [ "# Optimal walk found by parameterized quantum circuit\n", "str_by_vertex = [reduced_salesman_walk[i:i + n - 1] for i in range(0, len(reduced_salesman_walk) + 1, n - 1)]\n", "salesman_walk = '0'.join(str_by_vertex) + '0' * (n - 1) + '1'\n", "solution = {i:t for i in range(n) for t in range(n) if salesman_walk[i * n + t] == '1'}\n", "distance = sum([G[u][v][\"weight\"] if solution[u] == (solution[v] + 1) % n \n", " or solution[v] == (solution[u] + 1) % n else 0\n", " for (u, v) in G.edges])\n", "print(\"The walk found by parameterized quantum circuit:\", solution, \"with distance\", distance)\n", "\n", "# Optimal walk found by brute-force algorithm for comparison\n", "salesman_walk_brute_force, distance_brute_force = solve_tsp_brute_force(G)\n", "solution_brute_force = {i:salesman_walk_brute_force.index(i) for i in range(n)}\n", "print(\"The walk found by the brute-force algorithm:\", solution_brute_force, \"with distance\", distance_brute_force)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here, we draw the corresponding optimal walk in the form of graph representation suggested to the salesman:\n", "* The first number in the vertex represents the city number.\n", "* The second number in the vertex represents the order the salesman visits the corresponding city.\n", "* The red edges represent the found optimal route for the salesman." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "ExecuteTime": { "end_time": "2021-05-17T08:26:08.431841Z", "start_time": "2021-05-17T08:26:08.172882Z" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAA1MAAADnCAYAAAD7CwxiAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAABbnElEQVR4nO3deViU5foH8O/7MsMuuCAqSiC4oLki5N5ipbmkLS7lyRYVqU6nzu9Up+W0nazTcqrTenLcKjUzw2OauS8pqamISwruoCAqIAoCwzDL+/vjCWQc1GGZeWf5fq7LK8BZbhLmnvt57+d+JEVRFBAREREREVGdyGoHQERERERE5I5YTBEREREREdUDiykiIiIiIqJ6YDFFRERERERUDyymiIiIiIiI6oHFFBERERERUT2wmCIiIiIiIqoHFlNERERERET1wGKKiIiIiIioHlhMERERERER1QOLKSIiIiIionpgMUVERERERFQPLKaIiIiIiIjqgcUUERERERFRPbCYIiIiIiIiqgcWU0RERERERPXAYoqIiIiIiKgeWEwRERERERHVA4spIiIiIiKiemAxRUREREREVA8atQMgsofFouBkUTmyCktRYbTAaLZA6yPDXyujfVgwopoHQpYltcMkIiJyOuZIIvWwmCKXZLEo2Hq8EBsP5WNXdhGO5pdCliRoZAkKFCgKIEmABAkmiwKLoqBjeDASo5tjSFw4BsaGMXEQEZFHYo4kch2SoiiK2kEQVSnWG7E4LQezUk+gzGBCeaUZdfkBlQAE+vogyE+DpMExGJ8QidAAraPCJSIichrmSCLXw2KKXIK+0ox3VmXi+7QcSBJQYbQ0+DEDtDIsCjAhIRIvDe+CAF+fRoiUiIjIuZgjiVwXiylS3c6sIjz1XTpK9EZUmBqeIK7kr5EREqDFFxPjkRjdvNEfn4iIyFGYI4lcG4spUo3BZMb0FRlISc9tlFW26/HXyhgb3w6vjuoKPw1X4IiIyHUxRxK5BxZTpIoygwkPzdmBzDMlDllpuxp/jYyuESGYP7kvgvw4f4WIiFwPcySR+2AxRU5XZjBhrG4bThSUweDEJFHFTyMjpmUQUpIHMFkQEZFLYY4kci88tJecymAy46E5O1RLEiIGC04UlGHS3B0wmMyqxEBERHQl5kgi98Niipxq+ooMZJ4pUS1JVDGYLMjIK8H0FZmqxkFERFSFOZLI/bCYIqfZmVUkNtKqnCSqVJgsSEnPwa7sIrVDISIiL8ccSeSeWEyRU+grzXjqu3SnTCSqiwqjBX9emA59JVsZiIhIHcyRRO6LxRQ5xb9WZaJEb1Q7jFqV6I14ZzVbGYiISB3MkUTui8UUOVyx3ojFaTku07pwpQqTBd/vykGxiyYyIiLyXMyRRO6NxRQ53OK0HEiS2lFcmywBP6TlqB0GERF5GeZIIvfGYoocymJRMCv1hMv1gV9Jb7RgZuoJWCw8do2IiJyDOZLI/bGYIofaerwQZQaT2mHYpdRgwrYT59UOg4iIvARzJJH7YzFFDrXxUD7K3WQKkN5oxsZD+WqHQUREXoI5ksj9sZgih9qVXQR3aQpQFGBXNlfdiIjIOZgjidyfRu0AyHNZLAqO5pfaddvJA6Mxrk8kOrVqAh9Zwsfrj+DjDUfr9HzP3tkJt8eFo13zQABA5pkS/HvNYaSdvGD3Yxw5VwpFUSC5+m5gIiJya87OkaN7RmDKoPbo0joEvhoZKbtz8FzK/jo9BnMkkS1emSKHOVlUDtnOF9xubUNRrDfiTLG+3s93b++2kCQJq34/i7yLevRt3wJfPZqI8CZ+dj+GLEk4eb683jEQERHZw9k5Mq51E5gtCk6eL6v3YzBHEtnilSlymKzCUmhk+xLF3xbvAwDMfKgP2jULrNfzPb1oL9JPiatQgb4+2PXyHWjir0XvG5phzcGzdj2GRpaQVViG6LCgesVARERkD2fnyPfXHAYAvDaqKzq2alKvx2COJLLFK1PkMBVGCxQndoNXFVIAIAHQ+IgkdbYOK3kKgAqTe2wGJiIi9+XsHNkYmCOJbLGYIocxmi1QVMgTPrKED8b1hJ/GByv252FfbrHd91UUBZUuego9ERF5DrVyZEMwRxLZYpsfOYzWR3b6qe7+Whn/ndgHQ+LCseHQuerWCHtJkgRfDdcYiIjIsdTIkQ3FHElki8UUOYy/VoYE52WK0AAt5j6SiD5RzbAkPRd/X7If5jqe1i4B8Nf4OCZAIiKiPzg7RzYG5kgiWyymyGHahwXDZGcxMyEhEonRzXBj21AAwNCurdCuWQDWZpzD2oxzGBvfDh+M64mMvGKM+OzXWh9jzsMJ6BPVDBfLK1GiN+IfI7oAADYfKcDmIwV2xWGyKGjPjbVERORgzs6RQ7u2wtCurdCzXVMAQEJ0c3wwtgd2ZV/A92k5dsXBHElki8UUOUxU80BY7GwIT4xuhrF9Iqs/7xoRiq4Roci9oMfajHPVrRDXSjytQ/0BAE0DffHYwPbVXy/RG+0upiyKgqgW9ZuUREREZC9n58iubUKsHiO6RRCiW4jCyN5iijmSyBaLKXIYWZbQMTwYB/JKrnvb51L2X/PwwLjWYozrjM3Hr3qbQe9vqnuQV+jUKpiHERIRkcM5O0d+vOFonQ/6vRJzJJEt7iIkh0qMbt4oHeEDYsOwfN9prDxg33lR9SFJQGJ0C4c9PhERUU3MkUTuj1emyKGGxIVjcVoOyiobdi7F8E9TGymiqwvQ+mBIXLjDn4eIiAhgjiTyBLwyRQ41MDYMQX7uUbOXXijE0hnv4siRI2qHQkREXsCdcmTFpYs4vm0V9Hq92qEQuRQWU+RQsiwhaXAM/LUu/qNmqsTF35bgow8/ROfOnTFkyBAsXrwYlZWVakdGREQeyl1ypMVYgcJfv8ejjzyMtm3b4v/+7/9w6NAhtcMicgmu/dtLHmF8QqTLn/Lu5++PHz96AZMnT0ZAQAA2bdqECRMmIDIyEi+++CJOnDihdohEROSB3CFHBgQE4q3JI9GnTx9cuHABH3/8Mbp06YJbb70V3333HQwGg9ohEqmGxRQ5XGiAFhMSIuHvoqem+2tkTEiMxJBB/TBnzhzk5eXhs88+Q7du3ZCfn4/33nsPsbGxGDp0KP73v//BaDSqHTIREXkId8mRTz8+FWlpaUhLS0NSUhKCgoKwefNmTJw4Ee3atcPzzz+Po0cbNi2QyB1JiuLq6yHkCfSVZtzywSbkX3K91atWIX745dnbEOBrfaq7oijYvn07dDodFi9ejIqKCgBA69atMWXKFCQlJSEqKkqNkImIyIO4Y44sKSnBt99+C51Oh3379lV//fbbb0dycjLGjBkDX19fZ4dL5HQspshpdmUXYdLcHagwWtQOpZq/VsaCyX2REN38mrcrKirCvHnzoNPpqvvEJUnCXXfdhccffxwjRoyARuMem4iJiMj1uGuOVBQFO3fuhE6nw6JFi6oHVISHh2Py5MlISkpCTEyMs0ImcjoWU+RUr/z4O1J256LCpH6y8NfIGNsnEm/d083u+yiKgtTUVOh0OqSkpFQPqGjbti2mTp2KqVOnol27do4KmYiIPJi758iLFy9i/vz50Ol0OHjwIACx8Dh06FAkJydj1KhR0Gq1jgqZSBUspsipDCYzHpz1Gw7mlcCgYrLw08i4MSIE3yX1g5/G5/p3qEVhYSG+/vprzJw5s7pPXJZljBo1CsnJyRg2bBh8fOr32ERE5H2qc2TuRRhUrKcamiMVRcG2bduq2+SrBlS0adOmuk3+hhtuaOywiVTBYoqcrqzCiLGv/oATij8MWj+nP7+fRkZMyyCkJA9olPM9FEXBpk2boNPpsHTp0uoBFTfccAOSkpIwZcoUtGnTpsHPQ0REnq8s8wjG/mcDToS08ogcef78+eo2+cOHDwMQV6tGjBiB5ORkjBgxgguP5NZYTJHzvfkmyt56B5MefBsZ7Tqjwomrb/4aGV0jQjB/cl+HHJR47tw5fPXVV5g5cyaysrIAAD4+PhgzZgySk5Nxxx13QJZdc2ITERGpLD8fGDAAZadOY1LyZ8ho2tapLX+OzJGKomDLli3VbfJVC4/t2rWrbpNv27Ztoz4nkTOwmCLnmjMHmDoVkGUYfliC6XIHpKTnOGXDrb9Wxtj4SLw6qku9W/vsZbFYsH79euh0OixbtgxmsxkAEBMTg6SkJDz22GNo1aqVQ2MgIiI3UloK3HYbkJYG9OkDw7oNmL45xyNzZEFBQXWb/LFjxwCIhceqNvmhQ4fyahW5DRZT5Dw//wyMGQOYzcCXXwKPPw5ATDD688J0lOiNDlmB89fICAnQ4ouJ8Ui8ztQ+R8jLy8PcuXMxa9YsnDp1CgCg1Wpx7733Ijk5GbfddhskSXJ6XERE5CKMRmD0aGD1aiAmBti2Dfhjwc2Tc6TFYsHGjRuh0+nw448/wmQyAQCioqIwbdo0TJ48Ga1bt3ZqTER1xWKKnGPHDrHiptcDr7wCTJ9u9df6SjPeWZ2J73flQJYAfSOswgVoZVgUYEJiJF66q4vNGRnOZjabsWbNGuh0OqxYsQIWi/geO3bsiOTkZDzyyCMICwtTNUYiInIyRQEeewz45hsgLEwUUh07Wt3EG3Lk2bNnq9vks7OzAQAajaa6Tf72229nmzy5JBZT5HhHjgADBwKFhSJhzJkDXOVKTLHeiB/ScjAz9QRKDSbojWbU5SdUslgQIFkQHBKEaYNjMC4hEqEBrjeGNScnB3PmzMHs2bNx+vRpAICvry/Gjh2L5ORkDB48mFeriIi8wSuvAG+/DQQGAps2ATfddNWbNkqO9NMg2F/rsjnSYrFg7dq10Ol0+Omnn6rb5GNjYzFt2jQ8+uijCA8PVzlKostYTJFjnT0LDBgAZGUBw4cDy5YBdpwxYbEo2Hq8EJsOF2Bn1nkczS+FLEnQyBIUiI2skiRBAmCyKLAoCjoFAonr/4ch5bkY8OvPkH1cfwXLZDJh5cqVmDFjBlavXo2qX8cuXbogOTkZDz/8MJo1a6ZylERE5BBffgk8+STg4yPy48iRdt2tXjny0jkk/r4VQ0b1x4BnHoMsu/6C3enTp6vb5HNycgCINvn77rsPycnJuPXWW7nwSKpjMUWOc+kScOutQHo6kJAgVtyCg+v1UBaLglNF5cgqLEOFyYxKkwW+Ghn+Gh+0DwtCVItASBYL0KYNUFAA/P470M3+gwZdQXZ2NmbPno05c+bg7NmzAAB/f3+MHz8eycnJ6N+/P5MGEZGnWLoUuP9+0eY3Zw4weXK9H8quHPn11+I5hg0Te7PciNlsxqpVq6DT6bBy5crqNvnOnTtj2rRpeOSRR9CiRQuVoyRvxWKKHKOyErj7bmDtWqBDB2DrVsAZl+UnTwa++gp46y3gH/9w/PM5gNFoxPLly6HT6bBu3brqr3fv3h3Jycl46KGHEBoaqmKERETUIL/+CtxxB2AwAG++Cbz6quOfs6BADLXQaETbfUiI45/TAU6dOlXdJp+XlwcA8PPzq26THzRoEBceyalYTFHjUxTgkUeA+fOBli2B7duB2FjnPPePPwL33it6znfscM5zOtDx48cxa9YszJ07FwUFBQCAwMBAPPDAA0hOTkZiYiKTBhGRO8nIAAYNAi5cAJKTRaufs17HBw0Si5uLFwPjxjnnOR3EZDJhxYoV0Ol0WLNmTXWbfNeuXZGcnIxJkyaxTZ6cgsUUNb4XXwTeew8ICgJ++UW0+DlLWZmYhlRRAZw+DUREOO+5HaiyshJLly6FTqfDpk2bqr/eq1cvTJ8+HSNHjrxqUbVu3Tr06tULLVu2dFa4RERUm9Ongf79gZwcMQp9yRJxpchZ/v1v4O9/B/70J2DBAuc9r4NlZWVVt8mfO3cOgGiTnzBhAj799FOEXOMqHHMkNRSLKWpcn30GPP20SA4//QTcdZfzYxg9Wjz3jBli1c/DHDlyBDNnzsTXX3+N8+fPY8WKFRg+fLjNyNht27Zh0aJFyMnJQUZGBuLj4/HFF1+geXPnn7VFROT1iouBwYPFnt7+/YH168UEP2c6cgTo3Blo2hTIz7drIJQ7MRqNWLZsGXQ6HdavX4/o6GhkZGQgICDA5rbMkdRYWExR40lJAcaPF21+X38tWv3UMGcOMHUqMGKEOCjYQ1VUVODnn3/GqFGj4OfnZ/V3FosFw4YNw4QJEzB16lQAwA8//IBbbrmFI2WJiJzNYBCLi7/8IoqZrVsBtQYmxMUBhw8DGzeK8x891LFjx3D69Gn069ePOZIcyvVnR5N72LIFeOghUUi9/bZ6hRQAjBol+s83bABKS9WLw8H8/f1x//332yQJAFi5ciUuXLiAsrIy/PrrrwCAcePGcdoREZGzWSwiJ/7yC9C6tZikp+Zr8Zgx4r/LlqkXgxN06NABt9xyC3MkORyLKWq4gwfFi7PBIM7LeOkldeNp1Qro10/Es2aNurGoZM6cOQgICEBYWBheeOEFzJw5EwDg46PuCfdERF7nueeA778HmjQBVq0CoqPVjadmMeWlzUnMkdSYnLjrkTxSTo5oXbh4UUzR+/RT500lupYxY8QUweXLxTkeXiYzMxMpKSno1q0bAgMDsXnzZpSXlyMwMBCVlZXIyclBrLMmLBIReasPPwT+8x+xN2npUqBXL7UjAvr2FZN2s7OBAweA7t3VjsjprpUj8/LyEBoaiqCgILXDJDfBK1NUfxcvAsOHA7m5wMCBwLffilPcXcHo0eK/K1YAJpO6sTjZqVOn0KNHD3T749Dipk2bIjs7u3ps7L59+9ChQwfcfPPN+Pbbb1FRUaFmuEREnum778RVKQD45hvg9tvVjaeKj484BxLw+Fa/2lwrR5aUlGDKlClo27Yt/vKXv+DAgQMqR0vugMUU1U9Fhbj6c/Ag0KWLuAJUy7Qc1cTFAR07AkVFYqOvF7nhhhsQGRmJoUOH4s0338SCBQvQr18/BAUFwWw2Y+/evQgODkZqaioeeughtGvXDs899xyOHDmiduhERJ5hw4bLe4c/+AB48EF147mSl+ybqs21cqSvry9KSkpQXFyMzz//HN27d8fAgQMxb9486PV6tUMnF8VpflR3ZjPwwANiel9EhGinu+EGtaOy9fzzIon97W+i1cLL/Pjjj9i4cSMefvhh3HjjjVajYS9duoSFCxdCp9Nhz5491V+/7bbbkJycjHvvvRe+vr5qhE1E5N727gVuvhm4dAn461+Bjz5yjfb3msrLxZmMer3oLmnbVu2InO5aOXLfvn3Q6XRYsGABLl26BABo1qwZHnnkESQnJyMuLk6tsMkFsZiiulEU4JlnxHlSISHAr7+6br91aqpIaLGxwNGjrpfMXICiKEhLS4NOp8N3332H8vJyAEDLli0xefJkJCUlcW8VEZG9srPFGVJnzwITJgALFwKyizYBjRkjukq+/BJ4/HG1o3FJpaWlWLRoEXQ6HdLS0qq/fvPNNyM5OfmqE3XJu7CYorp5/33ghRcAX18x3tWVz6gwm8UY2sJCscn2xhvVjsilFRcXY8GCBdDpdPj999+rv37nnXciOTkZo0ePhtbDDngkImo058+L/cOHDwO33ipypCu/0Z47F5gyRQyRWrVK7Whc3u7du6HT6bBw4UKUlZUBAMLCwvDoo49i2rRp6Nixo8oRklpYTJH9FiwAJk0SHy9aJFbdXN1jj4kDhN9+G3j5ZbWjcQuKomD79u3Q6XRYvHhx9YCK1q1bY8qUKUhKSkJUVJTKUdafxaLgZFE5sgpLUWG0wGi2QOsjw18ro31YMKKaB0KWeRWTiOpArxcDJrZvF90aqalAaKjaUV3buXNAmzZi0mBhoRjdTtdVUlKChQsXYsaMGdi3b1/114cMGYLk5GTcc889btsmz/xYPyymyD7r1gEjRojJeP/5j+gDdwdLlwL33SdGwf72m9rRuJ2ioiLMnz8fOp0OmZmZAABJknDXXXchOTkZI0eOhEbj2icsWCwKth4vxMZD+diVXYSj+aWQJQkaWYICBYoiOkAlSDBZFFgUBR3Dg5EY3RxD4sIxMDaMyYOIrs5kAsaOFcMcbrgB2LbNffYgDRwo4v3hB/E9kN0URcHOnTuh0+mwaNGi6gEV4eHh1W3yMTExKkd5bcyPjYPFFF1fejpwyy1AaakY8/rvf6sdkf3KysQm24oKIC9PrMJRnSmKgtTUVOh0OqSkpKCyshIA0LZtW0ydOhVTp05Fu3btVI7SWrHeiMVpOZiVegJlBhPKK82oy4udBCDQ1wdBfhokDY7B+IRIhAawzZGIalAU4IknAJ0OaNZMTI/t0kXtqOxX1br/0EPA/PlqR+O2Ll68iAULFmDGjBk4ePBg9deHDh2K5ORk3H333S7VJs/82LhYTNG1ZWWJzbTnzgETJ4oXW1fdTHs1d98tzpvS6YBp09SOxu0VFhbim2++gU6nw9GjRwEAsixj5MiRSE5Oxl133aXqKfL6SjPeWZWJ79NyIElAhdHS4McM0MqwKMCEhEi8NLwLAnxd5Dw1IlLXW28Br74K+PuLDo5Bg9SOqG4OHRLFX7NmIs+70Bt+d6QoCrZt21bdJm8wGAAAbdq0wZQpUzB16lRV2+SZHx2DxRRdXWEhMGCAmIR3++3AypVi8IS7mTVLFFEjR4qiihqFoijYtGkTdDodli5dCqPRCECc4ZGUlIQpU6agjZOvBO7MKsJT36WjRG9EhanhSeJK/hoZIQFafDExHonRzRv98YnIjVQNcJAkYMkS4N571Y6ofjp3Bo4cATZtEoMzqFGcP38e8+bNg06nw+HDhwGINvkRI0YgOTkZI0aMcOrCI/Oj47CYotqVlYkCascOoGdPYMsWMQrdHZ09K87D8vUVBWJwsNoReZz8/Hx89dVXmDlzJk6cOAEA8PHxwZgxY5CcnIw77rgDsgOvaBpMZkxfkYGU9NxGWWm7Hn+tjLHx7fDqqK7w03jfKhyR1/v5ZzFa3GwGvvgCePJJtSOqv7//XbTv//WvYk80NSpFUbBly5bqNvmqhcd27dpVt8m3deAeO+ZHx2MxRbZMJrHCtmIFEBUlphO5+16j/v3FAIolS8RACnIIi8WC9evXQ6fTYdmyZTCbzQCAmJgYJCUl4bHHHkOrVq0a9TnLDCY8NGcHMs+UOGS17Wr8NTK6RoRg/uS+CPJz7SEcRNSIdu4Ux4KUl4spsW+/rXZEDbN1q2hPbN8eOH6cZzI6UEFBAb7++mvMnDkTx44dAyAWHkeNGoXk5GQMHTq0Ua9WMT86B4spsqYooiVu9mygeXPxIusJJ32/845Ieo88Ikalk8OdOXMGc+fOxaxZs3Dy5EkAgFarxb333ovk5GTcdtttkBqYtMsMJozVbcOJgjIYnJgoqvhpZMS0DEJK8gCvSBhEXu/oUdH+Xlgo8slXX7l/8WE2iwXTggLg99+Bbt3UjsjjWSwWqzZ5k8kEAIiKikJSUhImT57c4DZ55kfnYTFF1t54A/jnP8Vm2g0bRNLwBBkZ4tDeFi1E25+Lj/P2JGazGWvWrIFOp8OKFStgsYgX9Y4dO2LatGl49NFHERYWVufHNZjMeGDmb8g4U6JKoqjip5FxY0QIvkvq5zUtDURe6dw50eWQlSUOul2+3HMGNkyeLArDt94C/vEPtaPxKmfPnq1uk8/OzgYAaDSa6jb522+/vc5t8syPzsViii6rGtQgy+J8ptGj1Y6o8SgK0KkTcOwYsHkzcPPNakfklXJzczFnzhzMnj0bubm5AABfX1+MHTsWycnJGDx4sN1Xq1758Xek7M51auvC1fhrZIztE4m37uGKLpFHunRJDGdITwcSEsSwBk/af7tsGXDPPUBiomhjJKezWCxYt24ddDodli9fXt0mHxsbW90mHx4ebtdjMT86F4spEn76SbyQWizAjBlAcrLaETW+554DPvwQePZZ4IMP1I7Gq5lMJqxcuRI6nQ6rVq1C1ctQly5dMG3aNDz88MNo3vzq04B2ZhXh4a92OGUzrb38tTLmT+7rdVOMiDye0SiO2FizBoiNFYfc2vmm1m3UPJPx9GkxtIlUk5eXhzlz5mDWrFnIyckBINrk77vvPiQnJ+PWW2+96sIj86PzsZgiMZhhyBBArxfnZbz5ptoROcaWLeLw4Q4dxBhYd+9z9xAnT57E7NmzMXv2bJw9exYA4O/vj/HjxyM5ORn9+/e3Shr6SjNu+WAT8i8Z1Ar5qsKb+GHzc7d55TkbRB5JUYBHHwXmzQNathSFVIcOakflGKNHi4VVT11QdUNmsxmrV6+GTqfDzz//XN0m36lTp+o2+RYtWlTfnvlRHW52+io1usOHgVGjRCE1ZYrYL+WpBgwQe6aOHQMyM9WOhv4QFRWF6dOn49SpU1iyZAmGDh2KiooKzJs3DwMHDkSPHj3w+eefo7i4GADwr1WZKNEbVY66diV6I95ZzZ8tIo/xj3+IQiowUIxD99RCChCj3gHR8kcuwcfHByNHjsTy5cuRnZ2N1157DREREThy5Aiee+45tG3bFg899BBSU1OhKArzo0p4ZcqbFRUBffoA2dnAiBHiBdTTBzM8+ijwzTdiut+LL6odDV3F8ePHMWvWLMydOxcFBQUAgICAAIyd+DC2t7obLtS9YMNPI2Pny3cgNMBDNqYTeSudDnj8ccDHR1yxGT5c7Ygc69w5MdVPqwXOn/esPWEexGQy4eeff8aMGTOwZs2ay23yPfvAMPx1mF34Oomn5kfX/T9OjhcYKNr7broJWLzY8wsp4PJQDa68ubTY2Fi8++67yM3Nxffff48hQ4ZAr9fjx/3nYKioUDu8a5Il4Ie0HLXDIKKGMJtFfmzdWhwV4umFFAC0agX06wdUVor9YeSSqib9rVq1CidOnMDLL7+MVq1aIdc3EsbKSrXDuyZPzY+8MuXtystFT3hQkNqROEdpqdhkW1kJ5OWJRElu4dDhw7jnq4OokPzUDuW6wpv44bcXb4csc18ekduqrBTDJ7wlPwLAe++Jro1Jk0R7I7kFg6ESiW+vQYnR9a+ReGJ+dP3/69RgmZmZyM/Pr964aCUw0LsSRXAwcMcdooBcsULtaKgOCuTm8PELVDsMu5QaTNh24rzaYRDRdVwzP/r6ihzpTaq6N37+GfjjIFlyfTtPFcMsuUfrnCfmRxZTHm769Ol45plncP/992PBggVqh+Ma2OrnljYeykd5pVntMOyiN5qx8VC+2mEQ0TXYlR+9beprXBzQsaPYU711q9rRkJ2YH9XlBZtkvFfVGT6bN2/GypUrsXjxYgwfPhwtW7ZUOzR13X23GPu6fr04W8Obrsy5sV3ZRbCnJ/mde7sjIaoZIpoGoNJswd6ci/jXykwczS+1+7kkCXhmSEdMSIxE8yBfHM8vxftrD+OXwwV23V9RgF3ZnrXyRuRJmB+vQpLEVL8PPhALjrfconZEZAd78yPQODny78M6Y3TPCLQM9kOFyYLDZy/hP+uPYLsdV5w8MT/yypSHslgsyMzMxKeffgqtVguLxYK0tDRMmjQJr7/+OtLT09UOUT1t2gB9+4rDCdetUzsasoPFotj9Qv/gTTeg1GDC8n15KK0w4bbO4Zg3+Sb4aex/uXv85lj89Y5OMJkVrNh/BrEtgzF7UgI6hts/3erIuVJwSyqR62F+vI6q7o3ly8U7X3JpdcmPQOPkyMhmgdiXW4zFu3NxqqgcN7VvjrmPJCJAa98ZUp6WH3llykPJsoyPP/4YAFBcXIwPP/wQn3/+OeLi4jB37lx8/fXXiI+PVzdINY0eDezYIVbe7rlH7WjoOk4WlUO2s93mvi+3If3UBQBAu6YB+PWFIWgTGoAO4cE4mFdy3fv7yBKSBscAAJ74djcO5JXg9EU9nh7SEck3x+C5lP12xSFLEk6eL0d0GK98ErkS5sfrGDBADGo6fhzIyABuvFHtiOga6pIfgYbnSAD4y6I91R+HBmix77WhCPD1QViwL3Iu6K97f0/Lj7wy5QVCQ0OxatUq3HnnnYiMjMSUKVOQnZ2NwsJCtUNTT9XhhCtWiBG45NKyCkuhsXPyT1WSAADtHyttZoti94nwbUL90TzIF2aLggN/JJbfc8WBwV3bhNgds0aWkFVYZvfticj5mB9r4eMDjBolPubeYpdXl/wINDxHVhndMwL/HH0jFkzpCwBYsT/PrkIK8Lz8yGLKCyiKguAah+/pdDr4+/sjLCxMxahU1rUrEBsLFBYC27erHQ1dR4XRAsXujnAh0NcHH4ztCQCYlXoCBXYmipbBYvS63ni5yC6vFFOtWjaxfyy7AqDCxEKdyJUxP15FzVY/cmn1yY9A/XNklZs7huGR/tHo3jYUF8srkXrU/gUIT8uPLKY8VWWlOEMKgCRJkCQJRqMR06dPx6ZNmzjZT5I41c+NGM2WOrXuNwvUYuHUfugT1QwLd57Cu6sP2X3fglKRUAK0PtWDvIL8REd0XZKNoiioNNUybpmI1GcwACYT8+PVDB0K+PuLdvgzZ9SOhq6hrvkRaFiOrPJcyn50fGUlxum2QZYlvHd/D/SJambXfT0tP7KY8kQVFeIspS++APSXL7maTCbExcVh6dKl8PX1VTFAF1HV6rdsGTfZujitj2z3hOK2TQOQ8vgA9Ipsiv/+cgwvL/29Ts91prgCF8or4SNL6N42FADQo11TAEDm2Ut2P44kSfCtw4ZeInKS9euB7t1FkfBHmzfz4xWCgsT7CAD46Sd1Y6Frqkt+BBqeIzWyBF8fkduMZgW7si8gv0QsNMbYuQfK0/Kj53wnJJjNwEMPAampwCefiMLqDwEBARg3bhxHv1YZOBBo3hw4ehQ4fFjtaOga/LUyJNiXLZY8PgCxLYORe6Ec/lofvDaqK14b1RU924nCaGx8O2S/MxIr/zKo1vubLQpmpZ4AAPx3Yjw+HNcTSYPaw2S2QLfluN0xSwD8NfZNNiIiJ9mzB7j3XvG6P2uW2B8E5sdasdXPLdQlPwINz5GtQ/yx8+Xb8d+J8Zg+phuWPjEAHcKDoa80Y2d2kV0xeFp+5DQ/T6IowF//CixZAoSGAqtWAc3su+TqlTQascl23jxxdSouTu2I6EqFhcCOHWj/216YDDcCPtc/4b11qD8AoF2zQEwe2L766xl5JdiXW1y9gmeyXP1q5IzNx+Gv9cH4PpG4u0cEjheU4t9rD+PIOfvHz5osCtp7yKQiIo+QlQWMGAGUlgIPPAC88YbaEbm2u+8WLfHr14v/Z8H2Hw1BTmA2AxkZaJ+aBlNFc0Cy7y19Q3PkJYMJ+3IvIjG6OUIDtCjWV2LjoXx88csxnDxfblcMnpYfWUx5kvfeAz7/HPD1BX78UbQx0LWNHg0cOwbccIPakVBFhVg13rlT9Onv2AGcEFeIoiDB8mwKYMdCVvRLP1/z7+NaNwEgCqarsSjAR+uO4KN1R+yP3+YxFES1CKz3/YmoERUWAnfdBZw9C9x2G/D114DM5pxrat0auPNOoFUrccA9iyl1nT4t8mJVjkxLA0pLL+dHrX1v6RuaI4v1Rjzy1a66xX4FT8uPLKY8xbx5wEsviVWkBQuAW29VOyL3cN99IlkEBKgdiXexWESbTc3Cad8+wGi0vl1gINCnD+S+fdExRIsD9i16XdOA2DAs33caKw+cbfiDXUOnVsGQ6tLITkSOUV4urrIcOQL06AEsXQr42T+Z06v9/LPYe92kidqReJfSUmD37sv5cccOUUxdKSpK5McABQdMjfPUzsiRnpYfWUx5gjVrgClTxMcffwyMG6dqOG5FkoAQ+88OonoqKLAunHbuBC5etL6NJInDIfv2FX9uugno1k20YwJI/OkgDm7LrscAWGvDP01t4CNcnyQBidEtHP48RHQdJpNo6fvtN9GBsGqVaIMn+2g0LKQc7Y92PavC6eBBsehYU0iIyItV+bFvX3HVEI2XHwHH50hPzI8sptzd7t3A/feLhPH888DTT6sdEXm7qna9mokhK8v2dm3aWCeFhIRrFrZD4sKxOC0HZZWufzZFgNYHQ+LC1Q6DyLspCvDkk2IaXbNmwOrVQESE2lGRt6tq16v6k5Ym2ihr0miAXr0u58e+fYHOna/amsr8qC4WU+7sxAmxmbasDPjTn4B331U7IvI2Ve16NRPDvn2iuK8pMFAUSzUTQ7t2qMs814GxYQjy07hFsmjip8GAGM9aeSNyO9Oni4l9/v7AihVAly5qR0TeprRUFEs1uzJqa9eLjrbOj/Hxddp+wPyoLhZT7qqgABg2DMjPF2dBzJ3LzbSNTFEUHDp0CD/99BP+/ve/qx2OaygosE4K9rTr9e0rPtc07OVGliUkDY7Bh+sOo8Louof9BWhlJA2OgSx7Tj84kduZPRt4/XWRF7/7DhgwQO2IPArzYy3MZtGeV3NIxPXa9aq6M/5o16sv5kd1sZhyR2VlYqT3sWPiMvCSJWKCH9Wb2WyGj8/lUXGKokCSJISHh+N///sf+vXrh5tvvlnFCFWg19tO17tWu17Vn4QEh/XYj0+IxAdrXftMMIsCjEuIVDsMIu+1YgXw+OPi4y++AO65R9Vw3B3z41Xk5tpO17tau17NHNmpk0MWv5kf1cNiyt2YTMCECeKXNzpabKblAIUGe+utt3DkyBG89tpr6Ny5MyRJgsFgQIsWLfDAAw9g0aJFnp0s6tquV3NFrY7teg0RGqDFhIRILE7LQYXJ9Vbf/DUyxidGIjTg+udhEZED7NgBjB8vrhK88srloorqzevzI2DbrrdjB5CXZ3u76Gjrwql3b6dNC2Z+VA+LKXeiKEByshhV2qKF2EzburXaUXkEi8WCdevWQf5jtejuu+/G+PHjUVJSgnPnzqFNmzYqR9jIarbr7dgB7NpVe7tet27WhVMjtOs11EvDu2D173kumSxCA7V46S7uyyBSxZEjwMiR4qr6Y48Bb76pdkQewevyY812vao/GRm27XqhodbT9RqhXa+hXhreBasPnkXFJYOqcdTGk/OjpChKY0xSJGd4/XWRHAICgI0bgX791I7IYxw/fhxJSUnYuHEj5s2bh59//hkZGRmIioqCoij45JNP0KFDB7XDrJ+qdr2aiSE72/Z2ERG20/VccSRuejp2TXsek279Myq0rnNWjL9WxoLJfZEQ3VztUIi8z9mzYl9UVhYwfDiwbBmg9bwVcDV4dH4ELrfrVf3Zvbv2dr2ePa33OjmoXa9BzGbseuV9TDJ2Zn50IhZT7kKnE+0Ksgz8+KM4gJAaVbdu3fDjjz+iQ4cOqKysRGZmJrRaLSIjI9HEFYuK2lgsYnW25pAIe9r1qqbrubpvvhG/BxUVeGXSG0i5IREVZvVfwvw1Msb2icRb93RTOxQi73PpkjioPj0dSEwENm0CgoLUjsqjeER+BMTPSlW7XtVeJxdr16u38+eBiROBtWvxyrAnkdL7LlRA/WLPG/Ijiyl3sHw5cO+94o3yzJlAUpLaEXmkb775Bp07d0Y/d7ril59vnRR27gSKi61vU9t0va5dVW/Xq5PKSuBvfxObyQFg2jQYPvoYD85Lx8G8EhhUbPnz08i4MSIE3yX1g5/G5/p3IKLGU1kpFhfXrgU6dAC2bgXCPesMG1fglvnRZKp9ut6Vb3trtutVdWe428/Q3r3ifWJ2NhAWBsOi7/HgET/mRydhMeXqtm8Hbr9dtGq9/jrwxhtqR+SxzGYzZFmGZDKJwtXPdS6RAxA/A+np1tP1rtWuV/WnTx/XbNez15kzwLhx4k2Sr68oqKZOBQCUGUwYq9uGEwVlqiQMP42MmJZBSEkegCA/NypOiTyBogCPPALMny/e/G7bBsTGqh2VR6rOj5IkhjEEBTlt8JBdFKX26Xrl5da3q2rXq5kjO3Z0vXa9uvj2W7HIrteLjpMlS4AbbmB+dCIWU67s0CFg4ECgqEi8eZw507VevDyRwSBWrlq2BCJVHN95Zbvejh3A/v227XpBQbVP1/MU27YBY8eKgqptW5Ek+va1ukmZwYRJc3cgI6/EqUMp/DUyukaEYP7kvh6fKIhc0osvAu+9J14Hf/lFvBaSY+XmigFGnTuLdnG11GzXq/pz5ozt7dq3t86P7tCuZy+jEXj+eeCTT8TnkyeLxUZ//+qbMD86B4spV3XmDNC/P3DypDhTaulS92rLcleKIgoZHydfjq5q16s5Xe/Kdj1ZvtyuV9WS4G7tevZSFGDGDOCZZ0TCuOUW4PvvrzopyWAyY/qKTKSk5zjlwEJ/rYyx8ZF4dVQXj25dIHJZn30GPP20eP376SfgrrvUjsg7GI3OH+xRs12v5nS9K9++Nm1qO13P3dr17HXunDgCYMsW8e/x6adi2nMtC+7Mj47HYsoVlZQAN98sBgf07Qts2MDNtJ6kql2vZmI4edL2dm3b2k7XCw52frzOVlEBPPEE8PXX4vO//hV4/327Eviu7CL8eWE6SvRGh6zC+WtkhARo8cXEeCR66FQiIpeXkiLeSCqKeJ145BG1I6LGUrNdr+Z0vdra9Xr1st7r5O7tevb67Tfg/vvF4IyICPH70L//de/G/Og4LKZcTWUlMGKEKKA6dhT7RFq2VDsqqi+LBTh82Hq6nj3ten37imLK25w6Bdx3n0ieAQHA7NliOlEd6CvNeGd1Jr7flQNZAvSNsBIXoJVhUYAJiZF46a4uCPD1jtU2IpezZQswdKhoyX77beDll9WOiBri0iXRiVEzR9bWrhcTY1049e5t1c7mNWbOBP7yF/FecdAg4Icf6nTeKPOjY7CYciUWCzBpErBwoWhn2r5d9PuS+zh3znoD7PXa9WpO13N2a6Gr2bgRmDABKCwUP/dLl4qNwvVUrDfih7QczEw9gVKDCXqj2aYr5FokCQjQ+iDYT4Npg2MwLsEzT24nchsHDog3kMXFwJNPAp9/zn3E7sRkEv+GNXPk9dr1qrozvH1R2WAAnnpKLDAC4uMPPxRDmeqB+bFxsZhyJc8/D3zwgWjl2rwZiI9XOyKvcuHCBWzduhVbt27FTTfdhDFjxlSf+F6r8nLb6XrXaterOV3PG9r17KUoIim88IJYUBg2TCwoNG+cNgGLRcHW44XYdLgAO7PO42h+KWRJgkaWoABQFAWSJEECYLIosCgKOrUKRmJ0CwyJC8eAmBaQZb5hI1JVTo44lDc3V4yA/uEHLkA5UZ3zo6KIf7Oa+bG2dj2t1na6XocO3tGuZ6+cHDGIaedOcTVOpwMefrhRHpr5sXGwmHIVH38M/N//iT7glSuBO+9UOyKvYjAYkJSUhIKCAgwePBgbNmzAxIkTMWXKlMs3KisTCbzmdD2z2fqBgoLEoZE1V9S8sV3PXmVlwJQpYrgEAPzjH8A//+nQN0kWi4JTReXIKixDhcmMSpMFvhoZ/hoftA8LQlSLQDH+l4hcw4ULwODBYgjBwIHAunWeM5HNDdiVHxUF2LMHWLPmco48e9b2wWJirAunXr28s13PXps3i6NBCgqAqCjgf/9z6EI782P9eOAYMDf0/feikAKAr75iIaUCSZLw8ssvIy4uDgDQsmVL7NmzB+Xl5QisGv9qMgGPPXb5TrIM9OhhO12Pq6X2OXZMrDAfOCDOwfrmG/G5g8myhOiwIESHcagLkcurqADuuUcUUl26iEPsWUg5lV35sbJSdBR8+OHlOzZrdnmqHtv16kZRxMjz554Ti7Z33AEsWgS0aOHQp2V+rB8WU2rbtOny5dr33gMeekjdeLyUr68v4uLiYLFYIMsyIiIi8M0331xOFOJGYvRo1coa2/Xq7+efgT/9Sex9iIsT+6P+SNRERADEm8hJk8TQiYgIYPXqRmv/JfvZlR/9/MSEuYoK6+l6vIpRd+Xl4hDehQvF5y+8IIatcKHWZbHNT02//y4205aUiOksn3zCFx5Hs1jEYcj5+eLF/iornA8++CBGjBiBSZMmOTlAD2exAG+9Bbzxhlh5u/deMdo4JETtyIjIlSiKOGfus8/E68OvvwLdu6sdlecrKRGDk3r3vmrhyvzoQCdOiLy4f7/YNvD112K/FLk0XplSy6lT4pDBkhLxi/Kf/7CQcoSzZ22n65WUiGlxBw7UepdVq1ahuLgYw4cPd3KwHq64WFyFXb5c/Ky//Tbw4ovcaExEtv79b1FI+foCy5axkHIEk0ks6tbMkZmZopCdMweYPNnmLsyPDrR6tTgK5MIFcVVv6VIx+ZdcHospNRQViUIqL08czjt/Pi/fNoaq6Xo1D/s7dcr2du3aiQ2cGusf/6oWhkWLFuGVV15BWFgYzGYzZFnmhsuGysgQq21Hjog++oULxe8AEdGV5s8XrU1VH996q6rheARFEfnwyul6er317bRaMRRCqwWMxurD0pkfHUhRgHfeAV55RXx8993i5z40VO3IyE4sppxNrwdGjxarPzfeCPz4IyfZ1EdVu17Nwun3322n6wUH207Xi4io9SFlWcYXX3yBNWvWQKvV4oUXXkDHjh3x0UcfoWnTpo7/njxVSgrw6KNicl/PnmIaUUyM2lERkStat+7yFZH//AcYP17deNxVVbtezRx57pzt7WJjrfPjVabrMT86SEmJyI9Ll4qOjX/+UxRV7NhwKyymrsJiUXCyqBxZhaWoMFpgNFug9ZHhr5XRPiwYUc0D6z5b32wWm+63bhVXR1avFqv0dH1V7XpVf3btEien1yTL4s16zcP+unSx+6qfoiiorKxEnz59cPPNN+Pxxx9HfHz8tc/SoKszm8Wo8/feE59PnAjMmgXU3LRMRG7HIfkREJ0F990n2s+eew74618bPXaPVLNdr+rPoUO2h+E2a2Y9ffamm4CwMLuegvnRAQ4dEh0bhw6Jq1DffguMHKl2VFQPHEDxh6qDyzYeyseu7KIrDi5ToChi0UCCVH1wWcfwYCRGN8eQuHAMjA27dvJQFHFi9X//K073Tk0FunVz2vfnVsrLRftBVVLYubP2dr3ISOvCqU8fsWGT1Hf+PPDAA8D69aKY/eADsZmc7SBEbsfh+REQG+8HDBBXTyZOFG1OfKNuq6pdr2Z+vFa73pWH4fI12DX8+KPYQ3zpkngvuHSp+Pcht+T1xVSx3ojFaTmYlXoCZQYTyivNqMv/EAlAoK8Pgvw0SBocg/EJkQgN0Nre8J13gJdfFuND164Ve6VItOtlZlpvgLWnXa9vX6BNG+fGWqN/nK6hanX55EkgPBxYvBi45Ra1oyKiOnJafiwsFIXU0aPA7beLg+t9fRvr23BvxcWX2/WqcuT12vWqDsP183NenCaTWDhjsXZtZjPw2mvAv/4lPh8/Xgz74DErbs1riyl9pRnvrMrE92k5kCSgwmhp8GMGaGVYFGBCQiReGt4FAb5/tJd9843oiZUk8cbSm8dcnjljO12vtna97t2tE0NcnHpDOsxmUSCkpgJ/+5s6MbiLefPEWVwVFeKq4ZIloqWViNyGU/NjWZkooHbsEG3aW7Z471EJRqNYTKw5JKK2dr3mza27Mm66yeGHuV6VooiCLyVF/PslJqoThzsoKhJXXdesEe9z3nsPePZZFqAewCuLqZ1ZRXjqu3SU6I2oMDU8SVzJXyMjJECLLybGI/HQTmDUKPGG/NNPxXlS3uLKdr0dO4CcHNvbRUZaF07x8a7VrpebK2IMCBDta1c5m8qrGY2i0Pz8c/H51KniY2eujBJRgzk1P7YLEXtGVqwAoqKA7dud33GgFkURV+9rFk7p6bbter6+1u16N93keu16//d/wMcfA88/D7z/vtrRuKZ9+8TPelaW2Kf2/ffAkCFqR0WNxKuKKYPJjOkrMpCSntsoK23X4+8DjN2zBq+u+RJ+zz0LvPuuw59TNWaz7XS9Awds2/WaNLncrle1suYOyTMhQRSGy5eLsaV0mV4PDB0qDtX09RVFVFKS2lERUR04PT9qZYwtOYZXP/8b/EJDgG3bgM6dHf68qqnZrlfVnVFbu16HDrbT9Vx9UeqXX4DbbgM6dQIOH1Y7GtezahVw//0iV/bpIyba3nCD2lFRI/KaYqrMYMJDc3Yg80yJQ1bbrsbfaEBXyyXM/9dEBPl70H6bqna9qj9pabbtej4+ol2vZjuCmu16DTF9uuhznjIFmD1b7WhUkZubi/DwcPheuZehrEysSC5fLlo9+vVTJ0AiqhdV82NBFuZP7Y+gwQOc9rwOV9Wud+V0vSs1b247XU+tdr2GMJnE/tgLF8Qe6Lg4tSNSRa050mIRewK7dhULsf/9L7tbPJBXFFNlBhPG6rbhREEZDE5MFFX8NBJiWgYjJXkAgvzccBp9Wdnldr2qlgR3bNdriP37RT94eLgoJL1sytTzzz+PjIwM6HQ6tG3b1vaQxooK0dbZvLk6ARJRvaieHyUFMa1D3Dc/VrXr1Syc0tPFa2JNvr5A797Wi4uxsa7VrtcQkyYBCxaIfUB//7va0TjdNXOkwSAKzVatPOffm6x4fDFlMJnxwMzfkHGmRJVEUcVPI+PGiBB8l9QPfhoXvjJjNttO17teu17Vipo7tOvVl6IA7duLpLltG9C/v9oROc0///lPbNu2DT/88ANCvHVjOJEHYn6sh4sXbafr5efb3q5mu17fvmIxztXb9RoiJQUYN05MZdy6Ve1onIo5ktxwGahupq/IQKbKiQIADCYLMvJKMH1FJt66x4XOl8rLs94Ae7V2vSvPq+jc2T3b9epLkoAxY8QQkWXLvKqY0mg0eO211xASEoLU1FQoioLWrVujU6dOaodGRA3A/HgdRqPoSrhyut6VWrSwvuKUmOie7XoNMWyYuPq2fbvYC9aqldoROQ1zJHl0MbUzq0hsplU5UVSpMFmQkp6DMb0ikBitQjtUzXa9qj+5uba3u+EG6ytOffoAgYHOj9fVVBVTy5d79jCRK2RmZqJp06a4ePEiXn/9dXTt2hV6vR7Dhg3D1KlT1Q6PiOqB+fEKigJkZ9tO17tau17NxcWYGLZvNWkiptOtXg38/DMwebLaETkNcyR5bJufvtKMWz7YhPxLBrVDsRHexA+bn7vt8jkbjlCzXa/mdD3LFYkzJMR2ul7r1o6Ly50ZjWLP1MWLwJEjQMeOakfkFLt378YTTzyByMhIzJ8/H76+vli3bh3mzZuHTz/9FC1btlQ7RCKqA6/Pj4B1u15Vy15t7XodO1rnR09v12uIGTOAJ54ARo8WHRxegjmSPPbK1L9WZaJEb1Q7jFqV6I14Z3Um3hzdiO0MeXm20/VKS61v4+NjuwE2Ls7rhinUm1YLjBgBLFwoEsVzz6kdkVP06tUL48ePx2uvvYaLFy8iIiICUVFR0Gq1aOFtrSxEHsDr8mNVu17NHFnbCO8WLWyn63Gojv3uvlsUU+vWiYFEXtLRwhxJHnllqlhvxE3/Wq96H/i1+Glk7Hz5DoQG1GNcemmpdbvezp3Xb9ermq7nJS9uDrN4MTBhAjB4MLBli9rROJbFUl1oGwwGPP300zh58iQ+/vhjvPLKK2jWrBlmzJgBH2/aO0fk5jw+P1a169XMj2zXc57ERLGYu2yZuELlqRRFjITXip9R5kjv5pHF1KzUE/hw3WGnHDxYXwFaGc/e2RlTB8dc+4ZmM5CRYd3Hfb12vaoVNbbrNb6SEnF6udksNtmGhakdkWOsWgV89x3w5ZdW4+3fffddlJWVwWQy4Z133lExQCKqD4/Kj4Bo16vKj1X/LSiwvV1Vu17N6XpXnplHDffWW8Crr4o9U3PmqB2NY5SXiytwTz8tztKs8XPEHOmdPK6YslgU9Ht3g0v2gl8pvIkffnvxdshyjZWw06dtp+vV1q7Xo4ftdD226znHsGHA2rXAV18Bjz6qdjSNy2IB3n4beP11sfK2dKkYvMHVWiK35/b5sbLSdrretdr1ak7XY7uec/z+u3h/0rKlOJPR067KZGUB990H7N0rjkvJzOQeOvK8PVNbjxeizGBSOwy7lFaYsG3pRgw6XqNl7/Rp2xtGRVlfcWK7nrrGjBHF1PLlnlVMFRcDjzwi2jMkSawwjh7NQorIQ7hVfjSYsG3rAQw6fdB6up7hikLQz8+6Xe+mm9iup6Zu3YDo6MutlgMGqB1R41m7FnjgAXEAb4cOYrGRhRTBA4upjYfyUV5pvv4NXYDeYMTG/y7BoI2zL38xJEQkg5pDIrzovAa3MHo08Oc/A2vWAHo9EBCgdkQNl5EB3HuvmFLYtKkYsjF8uNpREVEjcqv8WGHExjc+tc6PANCpk3XhxHY911J1JuMnn4iFOU8ophRFHIfyj3+Ij0eNAubPF7mSCB5YTO3KLoI9fYt+GhkvDe+CUT3aINhPgwOni/HWykzszblo93ON7hmBKYPao0vrEPhqZKTszsFzKfvtvr8iy9jVORHopGG7njtp105cHUxPBzZsEC+s7mzJEnGFrbRU9H8vXQrExqodFRE1MnvzI9A4OVKSgGeGdMSExEg0D/LF8fxSvL/2MH45XMuepisosoxd7XuKCaps13MvNYup995TO5qGuXRJdGwsXSo+f/114LXX+D6NrHjUT4PFouBofun1bwjgtVFd8eiAaBSWGrA24yzib2iG+ZNvQrNA+6cHxbVuArNFwcnzZfUNGUdaREL573/Fm9kuXfgL6i7GjBH/Xb5c3TgawmwGXnoJGDtWFFIPPihOr2chReRx6pIfgcbJkY/fHIu/3tEJJrOCFfvPILZlMGZPSkDH8GC77n+kTSyUFSvEm9dhw1hIuYtBg8RVm8OHa9/T5i4OHxZXP5cuBUJDgZ9+At54g+/TyIZH/UScLCqHbEefdIsgX4zrEwmzRcGfZu/A04v24sd9p9HEX4tH+kfb/XzvrzmM+77chtRjhfWOWZYknDxfXu/7k0qqiqmffrKdrOgOzp8XK77vvis2CH/0EfDtt1aT+4jIc9ibH4HGyZE+soSkP6bxPfHtbjz7wz7oUk9A4yMj+WY7pvSB+dFtabXAyJHiY3ddcFy2TFwJPXQIuPFGccCzu3ehkMN4VDGVVVgKjXz9ZNGpVRP4amTkXdTjfFklAOD33GIAQNc2IQ6N8UoaWUJWYf2vbJFKevQQg0HOnhWTpdzJnj1AQoLYTNuyJbB+PfB//8cN20QezN78CDROjmwT6o/mQb4wWxQcyCup12MwP7qxqgXHZcvUjaOuzGYx2v2ee0SL37hxwG+/idH6RFfhUcVUhdECxY6O8LBgsVm1rPLyVKOqTbktmzh3MosCoMLkHhuCqQZJunwgoTutvC1YIDYEZ2eLVbfdu4Fbb1U7KiJyMHvzI9A4ObJlsLid3ng5v5X/8Xj2PgbzoxsbNkxcodq2rfZzv1zRhQvi6tNbb4lWvvffB77/Hgi2ry2VvJdHFVNGswX2nJpVWCpW2oJ8L8/fCPITZyEUOPn8DUVRUOnCJ9HTNbjTypvRCDzzDDBpElBRAUyZAmzZAkRGqh0ZETmBvfkRaJwcWVAqbheg9am+6B3kp6nTYzA/urGQEGDIEDH9bsUKtaO5vv37RcfG6tXinLK1a4Hnn2fHBtnFo4oprY9s18/90fxLqDRZENE0oHoFrke7pgCAzLMlDozQliRJ8NV41D+D97j5ZrEpNSMDOHZM7Wiu7uxZ4PbbgU8/FSuFOh0wezbg7692ZETkJPbmR6BxcuSZ4gpcKK+Ejyyhe9vQKx7jkl2Pwfzo5txlwfG774D+/YETJ8Sk3t27Rc4kspNHvUr5a2VIuH62KCytREp6LnxkCd9O6YfPHuiN0T0iUGow4ZvtJwEAY+PbIfudkVj5l0FXfZyhXVvhg7E9MLhDGAAgIbo5PhjbAxMS7F/tlwD4azzshHBvodWKIQ6A67b6/fYb0KcPkJoKRESIq1HTpqkdFRE5mb35EWicHGm2KJiVegIA8N+J8fhwXE8kDWoPk9kC3ZbjdsXB/Ojm7r5b/HftWnEmo6sxmYC//Q2YOBEoLxcj0H/9VeyHJqoDjzpnqn1YMEwW+/oY/vnTQZjMFozs3gbRLVphT85FvL0yA0V/bLatWsG71uN1bROCsX0uF07RLYIQ3UJMQ/s+LceuOC6VleHLf/8TB3t3QUJCAnr27IkATzgE1luMGSNWtZYtEy/KrmTmTOCpp0SL3+DBwOLFQOvWakdFRCqoS34EGidHzth8HP5aH4zvE4m7e0TgeEEp/r32MI6cs29Ee0lpKV5/9gms6d4Rffr0QUJCAqKjoyGx9co9tGsnFvN27xaDjqqKK1eQnw9MmAD88gug0YhzsZ54gm19VC+SotjbRe36LBYFXV5fDUMj9Fi/OrILpgyKwZPf7sbKA2cbIbraWYwG5Hx4f/XnPj4+uPHGG5GQkFD9p0ePHvDzc+5gDLJTcbGYiGc2A+fOAWFhakck9kT95S+ilQ8Ann4a+OADcSWNiLxSY+ZHwDk58sr8CADNmze3yo99+vRBZGQkCyxXNX26OCdsypTLOUltu3YB990H5OaKBcaUFGDgQLWjIjfmUcUUAIz6LLV6DGtDrHp6MI7mX8LTi/Y2PKhriGmqwdgmx5GWloa0tDRkZGTAbLaeXqTVatG9e/fqlbmEhAR069YNvr6+Do2N7DR0KLBuHfDNN8DDD6sbS06OOIR3506xJ2rWLOChh9SNiYhcQmPlR8A5ObJzywD8uUMpdu/ejbS0NOzatQsFtUyGa9mypVWBlZCQgIiICIfFRXWwbx/QqxcQHg6cOaP+gbdz5gBPPglUVorJtj/8IFrgiRrA44qpf/50EF9vy7ZzAKy6JAl4bEB7vDaqa/XXysvLsW/fvuriKi0tDZmZmbjyn8nX1xc9e/a0KrC6du0KLa8+ON8XX4h2uvvuA5YsgcWi4GRRObIKS1FhtMBotkDrI8NfK6N9WDCimgdCtvO8lzr55Rdg/HgxhjY6Gvjf/4DevRv/eYjILbl7flQUBbm5udW5sarIOn/+vM39W7dubXMFqzXbnJ1PUYD27YGTJ8WY9P791cmRBoOYaKvTic+feAL4+GOAi9LUCDyumEo9WoDHF+xGWaXrn00R6OuDmZMSMKjDtVvDSktLsXfvXqsC6/Dhwza38/f3R69evaoTR0JCArp06QIfH27gdSTLqVPYessYbIwbgF13TcDRwjLIkgSNLEGBAkURbwwkSDBZFFgUBR3Dg5EY3RxD4sIxMDasYYlDUURSeP550W44dCiwcKEY70pE9AdPzI+KouDkyZNW+XH37t24ePGizW3btm1rU2C1bNnSQd8BVbE88wy2Lt+CjROewK62XXA0v9S5OfL0adGx8dtvgJ8f8OWXwGOPNd43SF7P44opi0VBv3c3IN/J50XVR6smftj+4u31epEoKSnBnj17rBLIsVrGcwcGBqJ3795WyaNTp04ssBpBsd6IxWk5mJV6AmUXSlAua6HUoYVBgnjDEOSnQdLgGIxPiERoQB2vLJaXA0lJongCgBdfFAcO8t+XiK7gLflRURScOHHCKj+mp6ejpMS2xTEqKsqqw6NPnz5o3rx5Y3wLXq86R67PRNmlcpT7+kORnJwjU1OBcePEnubISNGxkZBQt8cgug6PK6YAYFbqCXy47jAqjK572F+AVsazd3bG1MExjfaYFy5cQHp6enXrQ1paGrKysmxuFxwcjPj4eKsVutjYWMh2FgJ6vR4vvvgimjVrhgcffBCdO3dutO/BHegrzXhnVSa+T8uBJKFRfs4CtDIsCjAhIRIvDe+CAF87iqETJ4B77xWHDQYHA19/Ddx//3XvRkTey1vzo8ViwbFjx2wKrLKyMpvbxsTEWHV4xMfHo2nTpnY/F3OkC+RIRQE+/1xM2TWZxAHCixaJgVFEjcwji6livRE3/Wt9o00tcgQ/jYydL99R91WWOjp//nx1cVX131OnTtncLiQkxGp1LiEhAe3bt691QlJhYSHmzZuHzz77DBMmTMC7774LAMjIyMCGDRvQq1cv9OvXzyP3b+3MKsJT36WjRG9EhQN+vvw1MkICtPhiYjwSo6+xOrp6NfDgg8DFi0CnTsDSpUDXrle/PRERmB9rMpvNOHLkiFWBtWfPHuhrOROpY8eONgVWkyZNan1c5kiVc2R5OfD448D8+eLz554D3nlHjEAncgCPLKYA4LVlB7A4Lcchv8wN5a+RMT4xEm+O7qbK8+fn59sUWKdPn7a5XbNmzXD8+HE0a9bM6usWiwWyLONPf/oTRo4ciYkTJ2L9+vVYsmQJiouLcfjwYTz++ONISkqCoigeMbLWYDJj+ooMpKTnOmVF118rY2x8O7w6qiv8ah5aabGIpPDqq2LlbfRoYN48IDTU4TERkWdgfrw6k8mEzMxMqw6PvXv3wmCwbo2UJAlPPfUU3n33XQQGBlr9HXOkijkyO1t0bOzdCwQGAnPnivOkiBzIY4spfaUZt3ywySV7w1uF+OGXZ2+zr5XLSc6cOWOVPNLS0mA0GpGXl1frGVeXLl3Crbfeiu+++w6dOnXCsGHDMGHCBEyePBl79+7F559/jjfeeAPt2rVT4btpXGUGEx6aswOZZ0qc+ubDXyOja0QI5k/uiyA/DVBSIk5o//FHsVv3zTeBl19Wf9QsEbkV5se6MRqNOHjwoFWO3LdvH9566y08++yzte5BZo50PJscuW4d8MADQFEREBsrcmU3dYpy8i4eW0wBwK7sIkyau8OlesP9tTIWTO6LhGu1cLkARVFw/vx5hIaG1tqKkJGRgQcffBD79u0DALRo0QK5ubnVhVe3bt2wZcsWhLnCIbYNUGYwYaxuG04UlKnSFuOnkRHTMggpt7ZA0Pj7gcOHgaZNgW+/BUaMcHo8ROQZmB8bxmAwwGg0Ijg4uNa/Z450Dj+NjJiwIKSU/4agV14S3RsjRogcWYd9bkQN4dFL2onRzTE2vh38Na7xbfprZIyNj3SLRCFJEsLCwq7a07137160atUKALBr1y6EhIQgICAAsizj7NmzKCoqcvskYTCZ8dCcHaolCRGDBSfOlmDSR2tgOHYc6N5dnN7OQoqIGoD5sWH8/PyuWkgBdc+R7riu7TI5Mu8CJmVIMEgy8PrrwE8/sZAip3KNV1EHenVUV3SNCIGfygnD74/L0a+O6qJqHI0lNzcX/fv3BwCkp6cjPj6++u+2bt2K2NhYAKJ3HAAqKyvx/vvv47777sO//vUvrFmzBoWFhc4PvA6mr8hA5pkS1TdqGxQJGWHRmJ78HrB9O9Chg6rxEJFnYH50nLrmSJPJhEGDBuGJJ57AnDlzsG/fPhiNRucHXgcukyNlDTJaxWL6B0uBN95g6zs5ncePNvHT+GD+5L7qX4ZuGYT5k/tab5R0Q8uWLcMnn3yCPXv2YNy4cQCAoKAgq5PlN27ciKFDh1rdT6/XY/369Vi3bh2WLl1a/fXo6GirCYLx8fE2Ay/UsDOrSGykdZEN2hVaP6QEdsGYAgMSg4LUDoeIPADzY+Orb47Mzc3F1q1bsXXr1uqv+fv7o1evXlaTduPi4qBxgal0Lpkji2SMyS669iRcIgfw6D1TNZUZTJg0dwcy8lTeIOnm9Ho9fv31V+zcuRMbNmzAHXfcgSeeeAJPPvkkwsPDIcsyFEXBE088YXW2hqIoOHr0KHbt2mV1xkd5ebnNc8TGxtoUWCEhIc77Hl14c3Z4Ez9sfs61NmcTkXtjfmw89c2RlZWV2L59u9UQqGPHjtk8fmBgIHr37m01pr1Tp061DsFw2PfIHElkxWuKKaBqdGcmUtJznDi6MxKvjuriEStu15Keno5ly5ahqKgIb7zxBlq0aHHd+5jNZhw6dMhqRPuePXtQUVFhc9tOnTpZFVi9e/e+Zr96Q7y67AB+4NhgIvIizI+OVZ8cefHiRaSnp1sVWFlZWTa3Cw4ORnx8vFWB1aFDB8gOandjjiSy5lXFVJVd2UX480IXOHiVbJhMJmRkZFQnjt27d2Pv3r2orKy0up0kSYiLi7MqsHr16mVz3kdd8UBLIvJmzI+u7fz58zYF1qlTp2xuFxISYtUe2KdPH8TExDT4TCvmSCJbXllMAeIy9TurM/H9rhzIEqBvhJW4AK0MiwJMSIzES3d14WXmRlJZWYmDBw9aFVj79++32ZwryzJuvPFGqwTSs2dP+Pv72/1cs1JP4MN1h11qXPCVArQynr2zM6YOjlE7FCLyQMyP7iU/Px+7d++2Ogfr9OnTNrdr1qyZTYEVFRVVpwKLOZLIltcWU1WK9Ub8kJaDmaknUGowQW80oy7/RyQJCND6INhPg2mDYzAuIZKrIU5gMBjw+++/W63OHThwAGaz2ep2Go0G3bp1s0og3bt3r/UgYotFQb93N7hkH/iVwpv44bcXb4csN2yVkYjoapgf3deZM2esCqxdu3bh3LlzNrdr0aKFVYdHQkIC2rZtW2uBxRxJVDuvL6aqWCwKth4vxKbDBdiZdR5H80shSxI0sgQFYoCCJEmQAJgsCiyKgk6tgpEY3QJD4sIxIKYFf2lVptfrsX//fqsCKyMjo3r0bBWtVosePXpY9Zd369YNv2VfxOMLdqOs0nyVZ3Adgb4+mDkpAYM6uPdZXkTk+pgf3Z+iKMjLy7Pq8Ni1a1etR5SEh4fbFFht2rRB6tEC5kiiWrCYugqLRcGponJkFZahwmRGpckCX40Mf40P2ocFIapFYIN7j8nxysrKsG/fPqsC69ChQzYHJPr5+SHm/udRHtlXLKe6OEkCHhvQHq+N6qp2KETkZZgfPYOiKMjJybHKj7t370ZRUZHNbSMiItBmxFMoDOsOwPX/bZkjyZlYTJHXuXTpEvbu3WuVQI4cOYLWj34Mv9b2HYj74bieGBgbhmZBWpQZzPj99EW8v/owDp4psTuOvw/rjNE9I9Ay2A8VJgsOn72E/6w/gu0nztt1/+5tQ/DTU4Ptfj4iIqJrURQF2dnZNgVWcXGx3TmyMfLjs3d2wu1x4WjXXAyVyjxTgn+vOYy0kxfsfgzmSHIWFlNEAC5cvIib/r0V9u6pXZTUD+dKKnCpwoT+sS0Q2zIYuRfKMej9TXY/52cP9IYsSygqq0SvyKbo3jYU+koz4t9aB73x+m0UfhoZh968iyvARETkMBaLBceOH8eIrw7DpFw/3zRGfvz177fhUoUJ+3OL0TMyFHGtQ3CpwojbP9ps954t5khyFs84JY+ogS6atND4+MBosa8X/IFZv1V/fGNECH7+y2C0CQ2ARpZgsti3PvGXRXuqPw4N0GLfa0MR4OuDsGBf5FzQX/f+siTh5PlyRIcF2fV8REREdSXLMrTNIqDVHIfJjoW+xsiPTy/ai/RT4ipUoK8Pdr18B5r4a9H7hmZYc/CsfXEzR5KTsJgiApBVWApNHTdIP9w/Ch3Dm2BArDh8cVbqCbsTRZXRPSPQJ6oZ4m9oBgBYsT/PrkIKADSyhKzCMiYKIiJyqLrmyIbmx6pCChA7tDQ+4rnPFtuXHwHmSHIeFlNEACqMFiioWyE0olsb9IsRiSLvoh6769DLXeXmjmEY2ycSAHCxvBKpR20nK12NAqDC5PpTlYiIyL3VNUc2Rn4EAB9ZwgfjesJP44MV+/OwL7fY7vsyR5KzyGoHQOQKjGZLnc5PAUQrQ+dXVyFpXhpahfjjv3+KR7umAXV6jOdS9qPjKysxTrcNsizhvft7oE9UM7vuqygKKl34FHoiIvIMdc2RjZEf/bUyZk1KwPBubbDh0Dn8bfG+Ot2fOZKchcUUEQCtj2z3RHQ/jYyqbgeDyYLNRwpQVmmC1kdG5B+Th65HI0vw9RG/fkazgl3ZF5BfIjbVxtjZkiBJEnw1/BUmIiLHsjdHNkZ+BMQ+4m+n9MOQuHAsSc/FtPm7UWmuW2HEHEnOwjY/IogVMMnOszN6RzbFJw/0xs6sIhTrjUiMbo4Qfy0KSw04cFq0IIyNb4cPxvVERl4xRnz2q81jtA7xx4q/DMK24+dxvqwS3SJC0CE8GPpKM3Zm257xURsJgL/Gx+7vkYiIqD7szZGNkR8BYM7DCegT1QwXyytRojfiHyO6AAA2HynA5iMFdsXMHEnOwmKKCED7sGC7N8eeu2RAVmEZBnUMQ5CvBkVllVixPw+fbjyKSwYTgMvn/l7tMS8ZTNiXexGJ0c0RGqBFsb4SGw/l44tfjuHk+XK74jBZFLTnxloiInIwe3NkY+RHAGgd6g8AaBroi8cGtq/+eoneaHcxxRxJzsJiighAVPNAWOxsCM8qLLMa/VqbuNZNAAAzNh+v9e+L9UY88tWuugV5BYuiIKqF/W0TRERE9WFvjmyM/AigTmdSXQ1zJDkLm0mJAMiyhI7hwY32eANiw7B832msPGDfeRj10alVMA8jJCIih2vMHOmM/AgwR5Lz8MoU0R8So5vjYF5JHQek1274p6mN8ChXJ0lAYnQLhz4HERFRlcbKkY7OjwBzJDkXr0wR/WFIXDgCfd1js2qA1gdD4sLVDoOIiLwEcyRR7VhMEf1hYGwYgvzc42JtEz8NBsRw1Y2IiJyDOZKodiymiP4gyxKSBsfAX+vavxYBWhlJg2Mgy+wFJyIi52COJKqda/9GEDnZ+ITIOp3yrgaLAoxLiFQ7DCIi8jLMkUS2WEwR1RAaoMWEhEj4u+ip6f4aGRMSIxEaoFU7FCIi8jLMkUS2XPO3gUhFLw3vghAXfSEODdTipbu6qB0GERF5KeZIImsspoiuEODrgy8mxrtcX7i/VsYXD8YjwE2mKRERkedhjiSy5lq/CUQuIjG6OcbGt3OZVgZ/jYyx8ZFIiG6udihEROTlmCOJLnON3wIiF/TqqK7oGhECP5WThZ9GRteIELw6iq0LRETkGpgjiQQWU0RX4afxwfzJfRHTMki1ZOGnkRHTMgjzJ/eFn4atC0RE5BqYI4kEFlNE1xDkp0FK8gDcGBHi9HYGf42MGyNCkJI8wG0OSiQiIu/BHEkESIri6icGEKnPYDJj+opMpKTnoMJocfjz+WtF//ero7pwtY2IiFwacyR5MxZTRHWwK7sIf16YjhK9ERWmxk8Y/hoZIQFafDExHoncSEtERG6EOZK8EYspojrSV5rxzupMfL8rB7IE6BthFS5AK8OiABMSI/HSXV042pWIiNwScyR5GxZTRPVUrDfih7QczEw9gVKDCXqjGXX5bZIkIEDrg2A/DaYNjsG4BJ7aTkREnoE5krwFiymiBrJYFGw9XohNhwuwM+s8juaXQpYkaGQJCgBFUSBJEiQAJosCi6KgU6tgJEa3wJC4cAyIaQFZltT+NoiIiBodcyR5OhZTRI3MYlFwqqgcWYVlqDCZUWmywFcjw1/jg/ZhQYhqEQhJYmIgIiLvwxxJnobFFBERERERUT3wnCkiIiIiIqJ6YDFFRERERERUDyymiIiIiIiI6oHFFBERERERUT2wmCIiIiIiIqoHFlNERERERET1wGKKiIiIiIioHlhMERERERER1QOLKSIiIiIionpgMUVERERERFQPLKaIiIiIiIjqgcUUERERERFRPbCYIiIiIiIiqgcWU0RERERERPXAYoqIiIiIiKgeWEwRERERERHVA4spIiIiIiKiemAxRUREREREVA8spoiIiIiIiOqBxRQREREREVE9/D/T3EShZJpRhQAAAABJRU5ErkJggg==", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "label_dict = {i: str(i) + \", \" + str(t) for i, t in solution.items()}\n", "edge_color = [\"red\" if solution[u] == (solution[v] + 1) % n\n", " or solution[v] == (solution[u] + 1) % n else \"black\"\n", " for (u, v) in G.edges]\n", "label_dict_bf = {i: str(i) + \", \" + str(t) for i, t in solution_brute_force.items()}\n", "edge_color_bf = [\"red\" if solution_brute_force[u] == (solution_brute_force[v] + 1) % n\n", " or solution_brute_force[v] == (solution_brute_force[u] + 1) % n else \"black\"\n", " for (u, v) in G.edges]\n", "\n", "# Draw the walk corresponding to the dictionary presented above on the graph\n", "fig, ax = plt.subplots(1, 2, figsize=(15, 4))\n", "for i, a in enumerate(ax):\n", " a.axis('off')\n", " a.margins(0.20)\n", "nx.draw(G, pos=pos, labels=label_dict, edge_color=edge_color, ax=ax[0], **options)\n", "nx.drawing.nx_pylab.draw_networkx_edge_labels(G, pos=pos, ax=ax[0], edge_labels=nx.get_edge_attributes(G, 'weight'))\n", "nx.draw(G, pos=pos, labels=label_dict_bf, edge_color=edge_color_bf, ax=ax[1], **options)\n", "nx.drawing.nx_pylab.draw_networkx_edge_labels(G, pos=pos, ax=ax[1], edge_labels=nx.get_edge_attributes(G, 'weight'))\n", "plt.axis(\"off\")\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The left graph given above shows a solution found by the parameterized quantum circuit, while the right graph given above shows a solution found by the brute-force algorithm. It can be seen that even if the order of the vertices are different, the routes are essentially the same, which verifies the correctness of using parameterized quantum circuit to solve the TSP." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Applications\n", "\n", "The TSP naturally applies in many transportation and logistics applications, for example, the problem of arranging school bus routes. The school bus application provides the motivation for Merrill Flood, a pioneer in the field of management science, to study TSP research in the 1940s. More recent applications involve food delivery route management [1] and power delivery for cable firms [2]. \n", "\n", "Other than those transportation applications, TSP also has wide usefulness in other management problems like scheduling of a machine to drill holes in a circuit board [3], reconstructing an unknown fragment of DNA [4] and scheduling optimal route in construction management [5]. Some consulting companies like [Nexus](https://nexustech.com.ph/company/newsletter/article/Finding-the-shortest-path-Optimizing-food-trips) have utilized this to provide management service.\n", "\n", "The TSP, as one of the most famous optimization problems, also provides a platform for the study of general methods in solving combinatorial problem. This is usually the first several problems that researchers give a try for experiments of new algorithms.\n", "\n", "More applications, formulations and solution approaches can be found in [6]." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "_______\n", "\n", "## References\n", "\n", "[1] Bräysy, Olli, et al. \"An optimization approach for communal home meal delivery service: A case study.\" [Journal of Computational and Applied Mathematics 232.1 (2009): 46-53.](https://www.sciencedirect.com/science/article/pii/S0377042708005438)\n", "\n", "[2] Sloane, Thomas H., Frank Mann, and H. Kaveh. \"Powering the last mile: an alternative to powering FITL.\" [Proceedings of Power and Energy Systems in Converging Markets. IEEE, 1997.](https://ieeexplore.ieee.org/document/646046)\n", "\n", "[3] Onwubolu, Godfrey C. \"Optimizing CNC drilling machine operations: traveling salesman problem-differential evolution approach.\" [New optimization techniques in engineering. Springer, Berlin, Heidelberg, 2004. 537-565.](https://link.springer.com/chapter/10.1007/978-3-540-39930-8_22)\n", "\n", "[4] Caserta, Marco, and Stefan Voß. \"A hybrid algorithm for the DNA sequencing problem.\" [Discrete Applied Mathematics 163 (2014): 87-99.](https://www.sciencedirect.com/science/article/pii/S0166218X12003253)\n", "\n", "[5] Klanšek, Uroš. \"Using the TSP solution for optimal route scheduling in construction management.\" [Organization, technology & management in construction: an international journal 3.1 (2011): 243-249.](https://www.semanticscholar.org/paper/Using-the-TSP-Solution-for-Optimal-Route-Scheduling-Klansek/3d809f185c03a8e776ac07473c76e9d77654c389)\n", "\n", "[6] Matai, Rajesh, Surya Prakash Singh, and Murari Lal Mittal. \"Traveling salesman problem: an overview of applications, formulations, and solution approaches.\" [Traveling salesman problem, theory and applications 1 (2010).](https://www.sciencedirect.com/topics/computer-science/traveling-salesman-problem)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3.8.13 ('new_pq')", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.13" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": false }, "vscode": { "interpreter": { "hash": "58b83104798ee1b81625bc6249d4d66f2bacd4a7d411a9b7a27bac0b4765adf2" } } }, "nbformat": 4, "nbformat_minor": 4 }