traveling_salesman.ipynb

{
 "metadata": {
  "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.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "['T', 'M', 'P', 'N', 'Y', 'F', 'C', 'L', 'I', 'B', 'H', 'A', 'Z', 'G', 'E', 'X', 'Q', 'Ñ', 'V', 'O', 'J', 'K', 'W', 'R', 'U', 'S']\n"
     ]
    }
   ],
   "source": [
    "import threading\n",
    "import time\n",
    "import numpy as np\n",
    "\n",
    "cond = threading.Condition()\n",
    "\n",
    "class AInt():\n",
    "    def __init__(self, val):\n",
    "        self.v = val\n",
    "\n",
    "done = AInt(0) #shared int\n",
    "\n",
    "#Representation of a city\n",
    "class City():\n",
    "    def __init__(self, label, coordinates, salesman):\n",
    "        self.label = label\n",
    "        self.coordinates = coordinates\n",
    "        self.distance = -1\n",
    "        self._s = salesman\n",
    "        self._t = threading.Thread\n",
    "        self._ok = True\n",
    "\n",
    "    #It just observes the distance between him and the salesman\n",
    "    def observe(self, cond, done):\n",
    "        while self._ok:\n",
    "            self.distance = np.linalg.norm(self.coordinates - self._s)\n",
    "            with cond:\n",
    "                done.v += 1 #atomic\n",
    "                cond.wait()\n",
    "\n",
    "cities = {\n",
    "    \"A\": np.array([1, 2]),\n",
    "    \"B\": np.array([2, 5]),\n",
    "    \"C\": np.array([8, 7]),\n",
    "    \"E\": np.array([4, 3]),\n",
    "    \"F\": np.array([7, 8]),\n",
    "    \"G\": np.array([3, 2]),\n",
    "    \"H\": np.array([1, 4]),\n",
    "    \"I\": np.array([3, 5]),\n",
    "    \"J\": np.array([23, 20]),\n",
    "    \"K\": np.array([41, 3]),\n",
    "    \"L\": np.array([6, 7]),\n",
    "    \"M\": np.array([7, 50]),\n",
    "    \"N\": np.array([8, 23]),\n",
    "    \"Ñ\": np.array([12, 2]),\n",
    "    \"O\": np.array([1, 15]),\n",
    "    \"P\": np.array([5, 34]),\n",
    "    \"Q\": np.array([8, 4]),\n",
    "    \"R\": np.array([90, 2]),\n",
    "    \"S\": np.array([23, 76]),\n",
    "    \"T\": np.array([22, 45]),\n",
    "    \"U\": np.array([45, 89]),\n",
    "    \"V\": np.array([12, 2]),\n",
    "    \"W\": np.array([67, 9]),\n",
    "    \"X\": np.array([3, 0]),\n",
    "    \"Y\": np.array([8, 13]),\n",
    "    \"Z\": np.array([1, 1]),\n",
    "}\n",
    "\n",
    "salesman = np.array([20, 42]) #Salesman start point\n",
    "trace = []\n",
    "cs = []\n",
    "\n",
    "#Initialice city thread observers\n",
    "for k, v in cities.items():\n",
    "    c = City(k, v, salesman)\n",
    "    threading.Thread(target=c.observe, args=(cond, done,)).start()\n",
    "    cs.append(c)\n",
    "\n",
    "\n",
    "while len(cs) > 0:\n",
    "    while done.v != len(cs): #wait till all observers has done\n",
    "        pass\n",
    "\n",
    "    nearer = cs[0]\n",
    "    for i, v in enumerate(cs[1:]):\n",
    "        if v.distance < nearer.distance:\n",
    "            nearer = v\n",
    "\n",
    "    cs.remove(nearer)\n",
    "    nearer._ok = False\n",
    "    salesman[0] = nearer.coordinates[0]\n",
    "    salesman[1] = nearer.coordinates[1]\n",
    "    trace.append(nearer.label)\n",
    "\n",
    "    #Reset the done counter and allow the observers, to observe again\n",
    "    done.v = 0\n",
    "    with cond:\n",
    "        cond.notifyAll()\n",
    "        \n",
    "print(trace)"
   ]
  }
 ]
}