TSP Repetitive nearest neighbors.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Core algorithms: NNA and RNNA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tsp_nna(points, start_node=0):\n",
    "    \"\"\"Nearest-neighbor search TSP approximate solver.\"\"\"\n",
    "    \n",
    "    seq, dist = [start_node], 0.0\n",
    "    cur_node = start_node\n",
    "    points_remaining = set(range(len(points))) - set([start_node])\n",
    "    \n",
    "    while points_remaining:\n",
    "        cand_nodes = list(points_remaining)\n",
    "        \n",
    "        cur_point = points[cur_node]\n",
    "        cand_points = points[cand_nodes]\n",
    "        \n",
    "        # Calculate Euclidean distance between current point and all candidate points\n",
    "        dists = np.sum((cand_points - cur_point) ** 2, axis=1)\n",
    "        next_node = cand_nodes[np.argmin(dists)]\n",
    "        \n",
    "        seq.append(next_node)\n",
    "        dist += np.sqrt(np.min(dists))\n",
    "        points_remaining.remove(next_node)\n",
    "        cur_node = next_node\n",
    "        \n",
    "    return seq, dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tsp_rnna(points):\n",
    "    \"\"\"Repetitive nearest-neighbor search TSP approximate solver.\"\"\"\n",
    "    \n",
    "    return min((tsp_nna(points, start_node=node) for node in range(len(points))),\n",
    "               key=lambda (seq, dist): dist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data helpers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import re\n",
    "\n",
    "BASE_DIR = \"~/scr/tmp/tsp\"\n",
    "def read_tsp_instance(name, base_path=BASE_DIR):\n",
    "    base_path = os.path.expanduser(base_path)\n",
    "    stmt_file = os.path.join(base_path, name + \".tsp\")\n",
    "    soln_file = os.path.join(base_path, name + \".opt.tour\")\n",
    "    \n",
    "    if not os.path.exists(stmt_file) or not os.path.exists(soln_file):\n",
    "        raise ValueError(\"statement file %r or soln file %r missing\"\n",
    "                         % (stmt_file, soln_file))\n",
    "        \n",
    "    with open(stmt_file, \"r\") as stmt_f:\n",
    "        stmt_str = stmt_f.read()\n",
    "    with open(soln_file, \"r\") as soln_f:\n",
    "        soln_str = soln_f.read()\n",
    "        \n",
    "    if \"EDGE_WEIGHT_TYPE : EUC_2D\" not in stmt_str:\n",
    "        print \"%s has non-Euclidean distances; skipping\" % name\n",
    "        return None\n",
    "    \n",
    "    cities = np.array(re.findall(r\"^\\s*\\d+\\s+([^\\s]+)\\s+([^\\s]+)$\",\n",
    "                                 stmt_str, re.M),\n",
    "                      dtype=np.float32)\n",
    "    \n",
    "    soln_str = re.search(r\"TOUR_SECTION\\n(.+)-1\", soln_str, re.S).group(1)\n",
    "    soln = [int(x) - 1 for x in soln_str.strip().split()]\n",
    "    \n",
    "    return cities, soln"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "att48 has non-Euclidean distances; skipping\n",
      "gr120 has non-Euclidean distances; skipping\n",
      "ulysses22 has non-Euclidean distances; skipping\n",
      "fri26 has non-Euclidean distances; skipping\n",
      "gr24 has non-Euclidean distances; skipping\n",
      "gr48 has non-Euclidean distances; skipping\n",
      "gr666 has non-Euclidean distances; skipping\n",
      "lin105 has non-Euclidean distances; skipping\n",
      "gr96 has non-Euclidean distances; skipping\n",
      "bayg29 has non-Euclidean distances; skipping\n",
      "pa561 has non-Euclidean distances; skipping\n",
      "bays29 has non-Euclidean distances; skipping\n",
      "ch150 has non-Euclidean distances; skipping\n",
      "gr202 has non-Euclidean distances; skipping\n",
      "brg180 has non-Euclidean distances; skipping\n",
      "ch130 has non-Euclidean distances; skipping\n",
      "berlin52 has non-Euclidean distances; skipping\n",
      "ulysses16 has non-Euclidean distances; skipping\n",
      "14\n"
     ]
    }
   ],
   "source": [
    "# Read all TSP data into memory.\n",
    "tsp_files = os.listdir(os.path.expanduser(BASE_DIR))\n",
    "names, inputs, solns = [], [], []\n",
    "\n",
    "for filename in tsp_files:\n",
    "    if filename.endswith(\".opt.tour\"):\n",
    "        filename = filename[:filename.index(\".opt.tour\")]\n",
    "        ret = read_tsp_instance(filename)\n",
    "        if ret is None:\n",
    "            continue\n",
    "        \n",
    "        points, soln = ret\n",
    "        names.append(filename)\n",
    "        inputs.append(points)\n",
    "        solns.append(soln)\n",
    "        \n",
    "print len(inputs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparing RNNA solutions + optimal solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def compute_distance(points, trajectory):\n",
    "    dist = 0.0\n",
    "    for node, next_node in zip(trajectory, trajectory[1:]):\n",
    "        point, next_point = points[node], points[next_node]\n",
    "        dist += np.sqrt(np.sum((point - next_point) ** 2))\n",
    "    return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "eil76\n",
      "\t540.002389\t571.146490\n",
      "pcb442\n",
      "\t50336.333870\t57585.752045\n",
      "eil101\n",
      "\t635.984980\t713.492530\n",
      "a280\n",
      "\t2568.881100\t2986.623464\n",
      "tsp225\n",
      "\t3830.500000\t4519.910987\n",
      "rd100\n",
      "\t7888.736187\t9095.832102\n",
      "kroA100\n",
      "\t20997.356293\t23137.514534\n",
      "eil51\n",
      "\t423.900550\t468.037741\n",
      "pr76\n",
      "\t106228.117493\t123389.070679\n",
      "st70\n",
      "\t670.053447\t715.075203\n",
      "pr1002\n",
      "\t256647.984879\t304288.384590\n",
      "kroC100\n",
      "\t20718.451546\t22637.144608\n",
      "kroD100\n",
      "\t20929.027868\t23599.601492\n",
      "pr2392\n",
      "\t377962.820173\t455008.255384\n"
     ]
    }
   ],
   "source": [
    "min_costs, heuristic_costs = [], []\n",
    "\n",
    "for name, points, solution in zip(names, inputs, solns):\n",
    "    print name\n",
    "    heuristic_soln, heuristic_cost = tsp_rnna(points)\n",
    "    min_cost = compute_distance(points, solution)\n",
    "    \n",
    "    min_costs.append(min_cost)\n",
    "    heuristic_costs.append(heuristic_cost)\n",
    "    print \"\\t%10f\\t%10f\" % (min_cost, heuristic_cost)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "min_costs = np.array(min_costs)\n",
    "heuristic_costs = np.array(heuristic_costs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[  5.76740062  14.40195902  12.18700947  16.26164652  17.99793726\n",
      "  15.30151201  10.19251286  10.41215724  16.15481248   6.71912911\n",
      "  18.56254579   9.26079373  12.76014175  20.38439526] 13.3117109379 18.4273440481\n"
     ]
    }
   ],
   "source": [
    "rel_error = (heuristic_costs - min_costs) / min_costs * 100\n",
    "print rel_error, rel_error.mean(), rel_error.var()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100.0 [76, 442, 101, 280, 225, 100, 100, 51, 76, 70, 1002, 100, 100, 2392]\n"
     ]
    }
   ],
   "source": [
    "print np.median([len(points) for points in inputs]), [len(points) for points in inputs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}