coding-hometask-2-2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Задание по курсу «Дискретная оптимизация», МФТИ, весна 2017"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Задача 2-2. Эвристика Кернигана—Лина\n",
    "\n",
    "В этой задаче Вам предлагается добавить к локальному поиска в задаче о сбалансированном разбиении графа эвристику Кернигана—Лина, когда мы, «застряв» в локальном минимуме, тем не менее пытаемся сделать несколько шагов из него, даже если они приводят к временному ухудшению. Надежда здесь на то, что после ухудшения может наступить заметное улучшение результата: нам удастся выпрыгнуть из локального оптимума. Мы рассматриваем безвесовый вариант задачи о разбиении с параметром балансировки $\\alpha=\\frac{1}{2}$:\n",
    "\n",
    "**Даны:**\n",
    "* $G=(V,E)$ — граф без весов на рёбрах\n",
    "\n",
    "**Найти:**\n",
    "* Разбиение $V=V'\\sqcup V''$, такое, что $V'=\\lfloor |V|/2 \\rfloor$ и число рёбер между $V'$ и $V''$ минимально возможное.\n",
    "\n",
    "Сделайте следующее:\n",
    "* Скачайте файл [`partition-instances.zip`](https://github.com/dainiak/discrete-optimization-course/raw/master/partition-instances.zip) и разархивируйте из него файлы со входами задачи.\n",
    "* Для каждого из графов найдите локальным поиском с эвристикой Кернигана—Лина локально минимальное (по количеству рёбер между частями) разбиение вершин графа на две части, мощности которых отличаются не более чем на единицу. \n",
    "* Реализуйте функцию `variable_depth_local_search`; она должна принимать на вход граф в формате, предоставляемом функцией `read_instance`, и возвращать найденное разбиение как множество вершин, лежащих в одной любой из двух компонент разбиения. Ваш локальный поиск должен начинаться с того разбиение, которое уже находится в переменной `starting_point`.\n",
    "* Подберите для каждого из четырёх входных графов глубину поиска так, чтобы он работал не более 60 секунд на Вашем компьютере, и сохраните информацию о подобранных параметрах и любые свои интересные наблюдения в отдельную ячейку настоящего ipynb-файла."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def read_instance(filename):\n",
    "    with open(filename, 'r') as file:\n",
    "        n_vertices = int(file.readline().strip().split()[0])\n",
    "        vertices, edges = set(range(1, n_vertices + 1)), set()\n",
    "        for u in range(1, n_vertices + 1):\n",
    "            for v in map(int, file.readline().strip().split()):\n",
    "                edges.add((u,v))\n",
    "        return (vertices, edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def differences(graph, partition):\n",
    "    # Разница, которую мы получаем при перенесении вершины в другую часть.\n",
    "    diff_exch = [0] * len(graph[0])\n",
    "    for u, v in graph[1]:\n",
    "        if (u in partition) != (v in partition):\n",
    "            diff_exch[u - 1] -= 1\n",
    "            diff_exch[v - 1] -= 1\n",
    "        else:\n",
    "            diff_exch[u - 1] += 1\n",
    "            diff_exch[v - 1] += 1    \n",
    "    return diff_exch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Выбор оптимального обмена вершина при фиксированных данных\n",
    "def best_candidates(graph, part_first, part_second, fixed_first, fixed_second):\n",
    "    diff_exch = differences(graph, part_first)\n",
    "    best_u, best_v, best_diff = -1, -1, 0\n",
    "    for u in part_first - set(fixed_first):\n",
    "        for v in part_second - set(fixed_second):\n",
    "            flag = 0\n",
    "            # Если было ребро между вершинами из разных частей,\n",
    "            # то мы ошибочно посчитали его, и даже дважды.\n",
    "            if (u, v) in graph[1] or (v, u) in graph[1]:\n",
    "                flag = 1\n",
    "            new_diff = diff_exch[u - 1] + diff_exch[v - 1] + 2 * flag\n",
    "            if best_u == -1 or new_diff < best_diff:\n",
    "                best_u = u\n",
    "                best_v = v\n",
    "                best_diff = new_diff\n",
    "    return best_u, best_v, best_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def variable_depth_local_search(graph, max_depth):\n",
    "    starting_point = set(range(1, len(graph[0]) // 2 + 1))\n",
    "    quality = get_quality(graph, starting_point)\n",
    "    part_first = starting_point.copy()\n",
    "    part_second = graph[0] - part_first\n",
    "    fixed_first = set([])\n",
    "    fixed_second = set([])\n",
    "    diff_now = 0\n",
    "    best_diff = 0\n",
    "    depth = 0\n",
    "    while (depth < max_depth):\n",
    "        best_u, best_v, new_diff = best_candidates(graph, part_first, part_second,\n",
    "                                       fixed_first, fixed_second)\n",
    "        diff_now += new_diff\n",
    "        part_first.remove(best_u)\n",
    "        part_first.add(best_v)\n",
    "        part_second.remove(best_v)\n",
    "        part_second.add(best_u)\n",
    "        if diff_now < best_diff:\n",
    "            quality -= diff_now\n",
    "            best_diff = 0\n",
    "            diff_now = 0\n",
    "            depth = 0\n",
    "            fixed_first = set([])\n",
    "            fixed_second = set([])\n",
    "        else:\n",
    "            depth += 1\n",
    "            print('Quality {} not updated, depth {}.'.format(quality, depth))\n",
    "            fixed_first.add(best_v)\n",
    "            fixed_second.add(best_u)\n",
    "    return (part_first - fixed_first) | fixed_second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def get_quality(graph, partition_part):\n",
    "    if not (partition_part <= graph[0]) or abs(len(partition_part) - len(graph[0]) / 2) > 0.6:\n",
    "        return -1\n",
    "    other_part = set(graph[0]) - partition_part\n",
    "    return sum(1 for edge in graph[1] if set(edge) <= partition_part or set(edge) <= other_part )\n",
    "\n",
    "def run_all():\n",
    "    filenames = ['add20.graph', 'cti.graph', 'm14b.graph', 't60k.graph']\n",
    "    depths = [3, 3, 3, 3]\n",
    "    for filename, depth in zip(filenames, depths):\n",
    "        instance = read_instance(filename)\n",
    "        print('Solving instance {}…'.format(filename))\n",
    "        time_start = time.monotonic()\n",
    "        partition = variable_depth_local_search(instance, depth)\n",
    "        quality = get_quality(instance, partition)\n",
    "        time_elapsed = time.monotonic() - time_start\n",
    "        print('Done in {:.2} seconds with quality {}'.format(time_elapsed, quality))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving instance add20.graph…\n",
      "Quality 12462 not updated, depth 1.\n",
      "Quality 12528 not updated, depth 1.\n",
      "Quality 12554 not updated, depth 1.\n",
      "Quality 12580 not updated, depth 1.\n",
      "Quality 12584 not updated, depth 1.\n",
      "Quality 12588 not updated, depth 1.\n",
      "Quality 12622 not updated, depth 1.\n",
      "Quality 12626 not updated, depth 1.\n",
      "Quality 12630 not updated, depth 1.\n",
      "Quality 12672 not updated, depth 1.\n",
      "Quality 12710 not updated, depth 1.\n",
      "Quality 12714 not updated, depth 1.\n",
      "Quality 12718 not updated, depth 1.\n",
      "Quality 12722 not updated, depth 1.\n",
      "Quality 12726 not updated, depth 1.\n",
      "Quality 12730 not updated, depth 1.\n",
      "Quality 12734 not updated, depth 1.\n",
      "Quality 12762 not updated, depth 1.\n",
      "Quality 12788 not updated, depth 1.\n",
      "Quality 12790 not updated, depth 1.\n",
      "Quality 12790 not updated, depth 2.\n",
      "Quality 12790 not updated, depth 3.\n",
      "Done in 2.6e+02 seconds with quality 12790\n",
      "Solving instance cti.graph…\n",
      "Quality 94080 not updated, depth 1.\n",
      "Quality 94080 not updated, depth 2.\n",
      "Quality 94080 not updated, depth 3.\n",
      "Done in 4e+02 seconds with quality 94080\n",
      "Solving instance m14b.graph…\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-132-a5db3ff65058>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mrun_all\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-131-aa6500c4e7d3>\u001b[0m in \u001b[0;36mrun_all\u001b[0;34m()\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Solving instance {}…'\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfilename\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m         \u001b[0mtime_start\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmonotonic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 16\u001b[0;31m         \u001b[0mpartition\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvariable_depth_local_search\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minstance\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdepth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     17\u001b[0m         \u001b[0mquality\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mget_quality\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minstance\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpartition\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     18\u001b[0m         \u001b[0mtime_elapsed\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmonotonic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mtime_start\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-130-7f874ec188b7>\u001b[0m in \u001b[0;36mvariable_depth_local_search\u001b[0;34m(graph, max_depth)\u001b[0m\n\u001b[1;32m     11\u001b[0m     \u001b[0;32mwhile\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mdepth\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     12\u001b[0m         best_u, best_v, new_diff = best_candidates(graph, part_first, part_second,\n\u001b[0;32m---> 13\u001b[0;31m                                        fixed_first, fixed_second)\n\u001b[0m\u001b[1;32m     14\u001b[0m         \u001b[0mdiff_now\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0mnew_diff\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m         \u001b[0mpart_first\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mremove\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbest_u\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-94-1104619cd564>\u001b[0m in \u001b[0;36mbest_candidates\u001b[0;34m(graph, part_first, part_second, fixed_first, fixed_second)\u001b[0m\n\u001b[1;32m     10\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mv\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mgraph\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mu\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mgraph\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m                 \u001b[0mflag\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m             \u001b[0mnew_diff\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdiff_exch\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mdiff_exch\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m2\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mflag\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mbest_u\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0mnew_diff\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mbest_diff\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m                 \u001b[0mbest_u\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mu\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "run_all()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def run_t60k():\n",
    "    filenames = ['t60k.graph']\n",
    "    depths = [3]\n",
    "    for filename, depth in zip(filenames, depths):\n",
    "        instance = read_instance(filename)\n",
    "        print('Solving instance {}…'.format(filename))\n",
    "        time_start = time.monotonic()\n",
    "        partition = variable_depth_local_search(instance, depth)\n",
    "        quality = get_quality(instance, partition)\n",
    "        time_elapsed = time.monotonic() - time_start\n",
    "        print('Done in {:.2} seconds with quality {}'.format(time_elapsed, quality))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving instance t60k.graph…\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-136-777895eeaa3c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mrun_t60k\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-135-5255a1e44717>\u001b[0m in \u001b[0;36mrun_t60k\u001b[0;34m()\u001b[0m\n\u001b[1;32m      6\u001b[0m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Solving instance {}…'\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfilename\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m         \u001b[0mtime_start\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmonotonic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m         \u001b[0mpartition\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvariable_depth_local_search\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minstance\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdepth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      9\u001b[0m         \u001b[0mquality\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mget_quality\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minstance\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpartition\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0mtime_elapsed\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmonotonic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mtime_start\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-130-7f874ec188b7>\u001b[0m in \u001b[0;36mvariable_depth_local_search\u001b[0;34m(graph, max_depth)\u001b[0m\n\u001b[1;32m     11\u001b[0m     \u001b[0;32mwhile\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mdepth\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mmax_depth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     12\u001b[0m         best_u, best_v, new_diff = best_candidates(graph, part_first, part_second,\n\u001b[0;32m---> 13\u001b[0;31m                                        fixed_first, fixed_second)\n\u001b[0m\u001b[1;32m     14\u001b[0m         \u001b[0mdiff_now\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0mnew_diff\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m         \u001b[0mpart_first\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mremove\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbest_u\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-94-1104619cd564>\u001b[0m in \u001b[0;36mbest_candidates\u001b[0;34m(graph, part_first, part_second, fixed_first, fixed_second)\u001b[0m\n\u001b[1;32m     10\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mv\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mgraph\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mu\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mgraph\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m                 \u001b[0mflag\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m             \u001b[0mnew_diff\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdiff_exch\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mdiff_exch\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m2\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mflag\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mbest_u\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0mnew_diff\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mbest_diff\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m                 \u001b[0mbest_u\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mu\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "run_t60k()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Выводы\n",
    "Для графа add20 результат не улучшается на глубинах 2-3 относительно глубины 1 (если считать, что мы начинаем с глубины 0). Для графа cti достаточно вообще только глубины 0. Для остальных двух даже переход по значениям меньше работает очень долго."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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
}