coding-hometask-3-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Задание по курсу «Дискретная оптимизация», МФТИ, весна 2017"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Задача 3-1. Задача TSP: инкрементальные алгоритмы.\n",
    "\n",
    "В этой задаче Вам предлагается сравнить алгоритмы Nearest Neighbour и Nearest Insertion в задаче Euclidean TSP.\n",
    "\n",
    "**Даны:**\n",
    "* Координаты точек плоскости, являющихся вершинами графа.\n",
    "\n",
    "**Найти:**\n",
    "* Перестановку вершин, задающих минимальный по длине гамильтонов цикл в графе.\n",
    "\n",
    "Сделайте следующее:\n",
    "* Скачайте файл [`tsp-instances.zip`](https://github.com/dainiak/discrete-optimization-course/raw/master/tsp-instances.zip) и разархивируйте из него файлы со входами задачи TSP.\n",
    "* Реализуйте функции `solve_tsp_nearest_neighbour` и `solve_tsp_nearest_insertion`.\n",
    "* Запустите функцию `run_all()`, чтобы протестировать свой код и сравнить качество решений, получаемых Nearest Neighbour и Nearest Insertion. Сильно ли они отличаются? Запишите свои качественные выводы в 1-2 предложениях в последней ячейке ipynb-файла."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def read_tsp_instance(filename):\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",
    "from math import sqrt\n",
    "\n",
    "def euclidean_distance(point1, point2):\n",
    "    return sqrt((point1[0]-point2[0]) ** 2 + (point1[1]-point2[1]) ** 2)\n",
    "    \n",
    "def calculate_tour_length(instance, permutation):\n",
    "    n = len(permutation)\n",
    "    return sum(euclidean_distance(instance[permutation[i]], instance[permutation[(i+1) % n]]) for i in range(len(permutation)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def solve_tsp_nearest_neighbour(instance):\n",
    "    permutation = []\n",
    "    not_used = set(range(len(instance)))\n",
    "    \n",
    "    new_vertex = random.choice(tuple(not_used))\n",
    "    permutation.append(new_vertex)\n",
    "    not_used.remove(new_vertex)\n",
    "    \n",
    "    for i in range(len(instance) - 1):\n",
    "        new_vertex = -1\n",
    "        min_distance = -1\n",
    "        for v in not_used:\n",
    "            new_distance = euclidean_distance(instance[permutation[i]],\n",
    "                                              instance[v])\n",
    "            if new_distance < min_distance or min_distance == -1:\n",
    "                new_vertex = v\n",
    "                min_distance = new_distance\n",
    "        permutation.append(new_vertex)\n",
    "        not_used.remove(new_vertex)\n",
    "    \n",
    "    return permutation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def replacement_loss(new, u, v):\n",
    "    return euclidean_distance(u, new) + \\\n",
    "           euclidean_distance(v, new) - \\\n",
    "           euclidean_distance(u, v)\n",
    "\n",
    "def solve_tsp_nearest_insertion(instance):\n",
    "    permutation = []\n",
    "    not_used = set(range(len(instance)))\n",
    "    \n",
    "    begin, end = -1, -1\n",
    "    min_distance = -1\n",
    "    for v in range(len(instance)):\n",
    "        for u in range(v):\n",
    "            new_distance = euclidean_distance(instance[u],\n",
    "                                              instance[v])\n",
    "            if new_distance < min_distance or min_distance == -1:\n",
    "                begin = u\n",
    "                end = v\n",
    "                min_distance = new_distance       \n",
    "    permutation.extend([begin, end])\n",
    "    not_used.remove(begin)\n",
    "    not_used.remove(end)\n",
    "    \n",
    "    for i in range(len(instance) - 2):\n",
    "        new_vertex = -1\n",
    "        min_distance = -1\n",
    "        \n",
    "        for u in not_used:\n",
    "            vertex_distance = -1\n",
    "            for v in permutation:\n",
    "                new_distance = euclidean_distance(instance[u], instance[v])\n",
    "                if new_distance < vertex_distance or vertex_distance == -1:\n",
    "                    vertex_distance = new_distance\n",
    "            if vertex_distance < min_distance or min_distance == -1:\n",
    "                new_vertex = u\n",
    "        not_used.remove(new_vertex)\n",
    "        \n",
    "        split_place = -1\n",
    "        min_distance = -1\n",
    "        for j in range(i + 2):\n",
    "            new_distance = replacement_loss(instance[new_vertex], instance[permutation[j]],\n",
    "                                            instance[permutation[(j + 1) % (i + 2)]])\n",
    "            if new_distance < min_distance or min_distance == -1:\n",
    "                split_place = j\n",
    "                min_distance = new_distance\n",
    "        \n",
    "        permutation = permutation[0:split_place + 1] + \\\n",
    "                      [new_vertex] + permutation[split_place + 1:i + 2]\n",
    "    return permutation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "from os.path import exists\n",
    "\n",
    "def run_all():\n",
    "    instance_filenames = ['d198.tsp', 'd493.tsp', 'd657.tsp', 'd2103.tsp', 'pr107.tsp', 'pr152.tsp', 'pr439.tsp']\n",
    "    for filename in instance_filenames:\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('Solving instance {}…'.format(filename), end='')\n",
    "        time_start = time.monotonic()\n",
    "        quality_nn = calculate_tour_length(instance, solve_tsp_nearest_neighbour(instance))\n",
    "        time_nn = time.monotonic()-time_start\n",
    "        time_start = time.monotonic()\n",
    "        quality_ni = calculate_tour_length(instance, solve_tsp_nearest_insertion(instance))\n",
    "        time_ni = time.monotonic()-time_start\n",
    "        print(' done in {:.2} seconds with tour length {} using NN and in {:.2} seconds with tour length {} using NI'.format(time_nn, int(quality_nn), time_ni, int(quality_ni)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving instance d198.tsp… done in 0.03 seconds with tour length 19376 using NN and in 1.1 seconds with tour length 17684 using NI\n",
      "Solving instance d493.tsp… done in 0.098 seconds with tour length 44302 using NN and in 1.6e+01 seconds with tour length 42286 using NI\n",
      "Solving instance d657.tsp… done in 0.18 seconds with tour length 63376 using NN and in 3.9e+01 seconds with tour length 59132 using NI\n",
      "Solving instance d2103.tsp… done in 1.8 seconds with tour length 88554 using NN and in 1.3e+03 seconds with tour length 94106 using NI\n",
      "Solving instance pr107.tsp… done in 0.0045 seconds with tour length 49128 using NN and in 0.17 seconds with tour length 46397 using NI\n",
      "Solving instance pr152.tsp… done in 0.0092 seconds with tour length 88767 using NN and in 0.49 seconds with tour length 81002 using NI\n",
      "Solving instance pr439.tsp… done in 0.081 seconds with tour length 136200 using NN and in 9.7 seconds with tour length 134165 using NI\n"
     ]
    }
   ],
   "source": [
    "run_all()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Выводы\n",
    "Алгоритм NI часто дает результат лучше, чем NN, но во всех данных случаях различие было не более чем на 10%. Более того, 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": 2
}