coding-hometask-3-2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Задача 3-2. Задача TSP: нижняя оценка Гельда—Карпа.\n",
    "\n",
    "В этой задаче Вам предлагается релизовать алгоритм Гельда—Карпа для нижней оценки стоимости решения в задаче Euclidean TSP.\n",
    "\n",
    "Сделайте следующее:\n",
    "* Скачайте файл [`tsp-instances.zip`](https://github.com/dainiak/discrete-optimization-course/raw/master/tsp-instances.zip) и разархивируйте из него файлы со входами задачи TSP. Это в точности те же входные данные, что и в задании 3-1.\n",
    "* Реализуйте функцию `lower_bound_tsp`. При этом можно пользоваться каким-нибудь стандартным алгоритмом построения минимального остовного дерева из библиотеки [`networkx`](https://networkx.github.io/), входящей в состав дистрибутива Anaconda.\n",
    "* Запустите функцию `run_all()`, чтобы протестировать свой код, и напишите полученные, как следствия, верхние оценки погрешностей решений, которые были получены Вашими алгоритмами NN и NI при решении задания 3-1. Запишите свои выводы в 1-2 предложениях в последней ячейке ipynb-файла."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "from typing import List, Tuple\n",
    "from math import sqrt\n",
    "from itertools import combinations, islice\n",
    "import networkx as nx\n",
    "\n",
    "def read_tsp_instance(filename: str) -> List[Tuple[int,int]]:\n",
    "    with open(filename, 'r') as file:\n",
    "        coordinates = []\n",
    "        for line in file:\n",
    "            line = line.strip().lower()\n",
    "            if line.startswith('dimension'):\n",
    "                coordinates = [(0, 0)] * int(line.split()[-1])\n",
    "            tokens = line.split()\n",
    "            if len(tokens) == 3 and tokens[0].isdecimal():\n",
    "                tokens = line.split()\n",
    "                coordinates[int(tokens[0])-1] = tuple(map(float, tokens[1:]))\n",
    "        return coordinates\n",
    "\n",
    "\n",
    "def euclidean_distance(point1: Tuple[int,int], point2: Tuple[int,int]) -> float:\n",
    "    return sqrt((point1[0]-point2[0]) ** 2 + (point1[1]-point2[1]) ** 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def trivial_lower_bound(vertex_coordinates):\n",
    "    return sum(islice(sorted(euclidean_distance(a, b)\n",
    "                             for a, b in combinations(vertex_coordinates, 2)), \n",
    "                      len(vertex_coordinates))))\n",
    "\n",
    "def create_graph(vertex_coordinates, y):\n",
    "    res = nx.Graph()\n",
    "    size = len(vertex_coordinates)\n",
    "    res.add_nodes_from(range(size))\n",
    "    for u, v in combinations(range(size), 2):\n",
    "        res.add_edge(u, v, weight=euclidean_distance(vertex_coordinates[u],\n",
    "                                                     vertex_coordinates[v]) - y[u] - y[v])\n",
    "    return res\n",
    "\n",
    "def update_y(mst, y):\n",
    "    size = mst.number_of_nodes()\n",
    "    new_y = [0] * size\n",
    "    for i in range(size):\n",
    "        new_y[i] = y[i] + 2 - mst.degree(i)\n",
    "    return new_y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def lower_bound_tsp(vertex_coordinates: List[Tuple[int,int]]) -> float:    \n",
    "    lower_bound = 0\n",
    "    size = len(vertex_coordinates)\n",
    "    y = [0] * size\n",
    "    \n",
    "    it = 0\n",
    "    t_start = time.monotonic()\n",
    "    while time.monotonic() - t_start < 60:\n",
    "        graph = create_graph(vertex_coordinates, y)\n",
    "        mst = nx.minimum_spanning_tree(graph)\n",
    "        st_weight = mst.size(weight='weight') + 2 * sum(y)\n",
    "        lower_bound = max(lower_bound, st_weight)\n",
    "        y = update_y(mst, y)\n",
    "        it += 1\n",
    "    return lower_bound"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "import pandas as pd\n",
    "from os.path import exists\n",
    "\n",
    "def run_all():\n",
    "    num_instances = 7\n",
    "    instance_filenames = ['d198.tsp', 'd493.tsp', 'd657.tsp', 'd2103.tsp',\n",
    "                          'pr107.tsp', 'pr152.tsp', 'pr439.tsp']\n",
    "    NN = [19376, 44302, 63376, 88554, 49128, 88767, 136200]\n",
    "    NI = [17684, 42286, 59132, 94106, 46397, 81002, 134165]\n",
    "    bounds = []\n",
    "    \n",
    "    for f in instance_filenames:\n",
    "        filename = 'coding-hometask-3-1-files/' + f\n",
    "        if not exists(filename):\n",
    "            print('File not found: “{}”. Skipping this instance.'.format(filename))\n",
    "            continue\n",
    "        instance = read_tsp_instance(filename)\n",
    "        print('Instance {}…'.format(filename), end='')\n",
    "        time_start = time.monotonic()\n",
    "        bound = lower_bound_tsp(instance)\n",
    "        bounds.append(int(bound))\n",
    "        time_nn = time.monotonic()-time_start\n",
    "        print(' done in {:.2} seconds with lower bound {}'.format(time_nn, int(bound)))\n",
    "        \n",
    "    table = pd.DataFrame(index=instance_filenames,\n",
    "                         data=list(zip(bounds,\n",
    "                                       NN, map(lambda n: round(NN[n] / bounds[n], 2),\n",
    "                                               range(num_instances)),\n",
    "                                       NI, map(lambda n: round(NI[n] / bounds[n], 2),\n",
    "                                               range(num_instances)))),\n",
    "                         columns=['НО Гельда-Карпа', 'NN', 'NN-погрешность', 'NI', 'NI-погрешность'])\n",
    "    print(table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Instance coding-hometask-3-1-files/d198.tsp… done in 6e+01 seconds with lower bound 13337\n",
      "Instance coding-hometask-3-1-files/d493.tsp… done in 6e+01 seconds with lower bound 32051\n",
      "Instance coding-hometask-3-1-files/d657.tsp… done in 6.1e+01 seconds with lower bound 45947\n",
      "Instance coding-hometask-3-1-files/d2103.tsp… done in 7.5e+01 seconds with lower bound 76512\n",
      "Instance coding-hometask-3-1-files/pr107.tsp… done in 6e+01 seconds with lower bound 37635\n",
      "Instance coding-hometask-3-1-files/pr152.tsp… done in 6e+01 seconds with lower bound 63450\n",
      "Instance coding-hometask-3-1-files/pr439.tsp… done in 6.1e+01 seconds with lower bound 96986\n",
      "           НО Гельда-Карпа      NN  NN-погрешность      NI  NI-погрешность\n",
      "d198.tsp             13337   19376            1.45   17684            1.33\n",
      "d493.tsp             32051   44302            1.38   42286            1.32\n",
      "d657.tsp             45947   63376            1.38   59132            1.29\n",
      "d2103.tsp            76512   88554            1.16   94106            1.23\n",
      "pr107.tsp            37635   49128            1.31   46397            1.23\n",
      "pr152.tsp            63450   88767            1.40   81002            1.28\n",
      "pr439.tsp            96986  136200            1.40  134165            1.38\n"
     ]
    }
   ],
   "source": [
    "run_all()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Выводы\n",
    "Запишите здесь полученные результаты относительно погрешностей алгоритмов NN и NI."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Результаты записаны выше. Алгоритм Гельда-Карпа для получения НО дает неплохую погрешность относительно NI и NN."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}