Very important to use algorithms from hint

Subject:Computer SciencePrice:28.99 Bought3

Share With

Very important to use algorithms from hint. Running time is important too(30 second max). All description is given in the file. The file also contains testing code. Local search: the traveling salesmen problem Hint: search for 2-opt and 3-opt algorithms.
 

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Your solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f063005f2b60c8c028cce011ed8b756c",
     "grade": false,
     "grade_id": "cell-73cf23cba2dc9e54",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import time\n",
    "\n",
    "def tsp(points):\n",
    "    \"\"\"Return one of the shortest tours that touches all points.\n",
    "    \n",
    "    Input:  A list of the form [n, (x_1, y_1), ..., (x_n, y_n)],\n",
    "            where n is the number of points on a plane and (x_i, y_i) are their coordinates.\n",
    "            We assume the Euclidean distance between the points (see the distance function below).\n",
    "    Output: A list of point indices that corresponds to one of the shortes tours\n",
    "            that start and end at point (x_1, y_1) and goe through each other point exactly once.\n",
    "            \n",
    "    \"\"\"\n",
    "    path = []\n",
    "    return path\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "81c58d2387344fc16393a58a82ae08b9",
     "grade": false,
     "grade_id": "cell-13401c13c017b3b5",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Testing code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6ec1704f4c99845ccbf45aa90db4e2e9",
     "grade": true,
     "grade_id": "cell-441d79d04da2b037",
     "locked": true,
     "points": 0,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def distance(p, q):\n",
    "    \"\"\"Return the Euclidean distance between points p = (a, b) and q = (c, d).\"\"\"\n",
    "    return ((p[0]-q[0])**2 + (p[1]-q[1])**2) ** 0.5\n",
    "\n",
    "\n",
    "def get_length(path, points):\n",
    "    \"\"\"Return the length of the path.\n",
    "    \n",
    "    Input:  path is a list of point indices;\n",
    "            points is a list of the form [n, (x_1, y_1), ..., (x_n, y_n)],\n",
    "            where n is the number of points on a plane and (x_i, y_i) are their coordinates. \n",
    "    Output: The length of the input path\n",
    "            assuming the coordinates specified in the input\n",
    "            and the Euclidean distance between the points.\n",
    "    \"\"\"\n",
    "    return sum(distance(points[path[i]], points[path[i+1]]) for i in range(len(path) - 1))\n",
    "    \n",
    "\n",
    "def test(points, baseline_path, short_path):\n",
    "    \"\"\"Test the tsp function on points.\n",
    "    \n",
    "    baseline_path is the length of a simple solution.\n",
    "    short_path is the length of a good solution.\n",
    "    \n",
    "    Your solution should run for at most 30 seconds\n",
    "    and should return a path of length less than than baseline_path\n",
    "    (the only exception is when baseline_path is almost equal to short_path;\n",
    "    in this case, it is OK to return a path of similar length).\n",
    "    The score you get depends on how short your path is. The score is the returned value of the function.\n",
    "    \n",
    "    \"\"\"\n",
    "    if '_inside_grader' in globals() :\n",
    "        return 10  # skip examples while loading\n",
    "    print(\"Baseline path: \", baseline_path)\n",
    "    print(\"Short path: \", short_path)\n",
    "    n = points[0]\n",
    "\n",
    "    path = tsp(points)\n",
    "    \n",
    "    assert len(path) == n + 1, \"The route must contain n + 1 points.\"\n",
    "    assert path[0] == 1 == path[-1], \"The route should start and end at point 1.\"\n",
    "    assert set(path) == set(range(1, n + 1)), \"The route must contain all n points.\"\n",
    "\n",
    "    length = get_length(path, points)\n",
    "    print(\"Your path: \", length)\n",
    "    if length <= short_path + 0.00001: # If your path is just slightly longer than short_path or shorter, you get 10. \n",
    "        return 10    \n",
    "    if length >= baseline_path: # If it is the same as the baseline or longer, you get 1.\n",
    "        return 1\n",
    "    # Otherwise, the number of points you get depends on how close your path is to short_path.\n",
    "    return math.ceil((baseline_path-length) / (baseline_path-short_path) * 10)\n",
    "    \n",
    "\n",
    "# Square 1 x 1. Your algorithm is expected to find a shortest tour, e.g., [1, 3, 2, 4, 1].\n",
    "points = [4, (0, 0), (1, 1), (0, 1), (1, 0)]\n",
    "length = get_length([1, 3, 2, 4, 1], points)\n",
    "assert test(points, length, length) == 10\n",
    "\n",
    "\n",
    "# Line y = x + 1. Your algorithm is expected to find a shortest tour, e.g., [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1].\n",
    "points = [10, (1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20)]\n",
    "length = get_length([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1], points)\n",
    "assert test(points, length, length) == 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "97f8f61bf12827ca9f4df24ac7b9ff4a",
     "grade": false,
     "grade_id": "cell-6e653de6a6fd6fed",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Test with 25 points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "cd4b7038317537fddb62247d5e0d2de1",
     "grade": true,
     "grade_id": "cell-bf1c3b79c2c7f67d",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "points = [25,\n",
    "          (6139, -9327),\n",
    "          (7524, 9018),\n",
    "          (-8201, -4582),\n",
    "          (5277, -13042),\n",
    "          (2541, 156),\n",
    "          (-6748, 14001),\n",
    "          (12371, 6187),\n",
    "          (-3191, 3754),\n",
    "          (-14173, 11185),\n",
    "          (1725, 14670),\n",
    "          (-14467, 12589),\n",
    "          (-703, -13791),\n",
    "          (6151, -7013),\n",
    "          (1367, 14568),\n",
    "          (-13867, 14509),\n",
    "          (405, -6256),\n",
    "          (6185, -13240),\n",
    "          (7325, 5230),\n",
    "          (845, 339),\n",
    "          (7181, -2898),\n",
    "          (-2921, -4544),\n",
    "          (10395, 808),\n",
    "          (11313, 2696),\n",
    "          (-5320, 11409),\n",
    "          (3790, 10442)\n",
    "         ]\n",
    "\n",
    "baseline = get_length(\n",
    "    [1, 13, 20, 22, 23, 7, 18, 2, 25, 10, 14, 24, 6, 15, 11, 9, 8, 19, 5, 16, 21, 3, 12, 4, 17, 1],\n",
    "    points)\n",
    "short = get_length(\n",
    "    [1, 17, 4, 12, 3, 21, 16, 5, 19, 8, 9, 11, 15, 6, 24, 14, 10, 25, 2, 18, 7, 23, 22, 20, 13, 1],\n",
    "    points)\n",
    "\n",
    "test(points, baseline, short)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "fca384e91822759a4255e402f6d5da77",
     "grade": false,
     "grade_id": "cell-6afc06fc1cca0442",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Test with 45 points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "53ff827f9b5f78f77defafd1da9eb9f7",
     "grade": true,
     "grade_id": "cell-614fe0dd38853f28",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "points = [45,\n",
    "          (175, 17),\n",
    "          (134, 299),\n",
    "          (244, 76),\n",
    "          (17, 61),\n",
    "          (111, 273),\n",
    "          (195, 170),\n",
    "          (155, 209),\n",
    "          (57, 251),\n",
    "          (57, 47),\n",
    "          (100, 176),\n",
    "          (182, 251),\n",
    "          (272, 126),\n",
    "          (213, 232),\n",
    "          (131, 52),\n",
    "          (174, 201),\n",
    "          (239, 281),\n",
    "          (8, 40),\n",
    "          (142, 14),\n",
    "          (298, 244),\n",
    "          (28, 121),\n",
    "          (151, 101),\n",
    "          (40, 203),\n",
    "          (70, 105),\n",
    "          (290, 99),\n",
    "          (294, 27),\n",
    "          (221, 153),\n",
    "          (182, 78),\n",
    "          (186, 60),\n",
    "          (70, 52),\n",
    "          (151, 70),\n",
    "          (218, 122),\n",
    "          (58, 8),\n",
    "          (240, 134),\n",
    "          (178, 40),\n",
    "          (71, 20),\n",
    "          (153, 299),\n",
    "          (25, 125),\n",
    "          (6, 148),\n",
    "          (245, 14),\n",
    "          (177, 41),\n",
    "          (237, 116),\n",
    "          (94, 16),\n",
    "          (158, 107),\n",
    "          (3, 21),\n",
    "          (194, 47)\n",
    "         ]\n",
    "\n",
    "baseline = get_length(\n",
    "    [1, 34, 40, 45, 28, 27, 30, 14, 18, 42, 35, 32, 9, 29, 23,\n",
    "     20, 37, 38, 22, 8, 5, 2, 36, 11, 13, 15, 7, 6, 26, 33, 41,\n",
    "     31, 3, 24, 12, 25, 39, 43, 21, 10, 4, 17, 44, 16, 19, 1],\n",
    "    points)\n",
    "short = get_length(\n",
    "    [1, 39, 25, 3, 24, 12, 33, 41, 31, 26, 6, 15, 7, 11, 13,\n",
    "     19, 16, 36, 2, 5, 8, 22, 10, 38, 37, 20, 23, 29, 9, 4, 17,\n",
    "     44, 32, 35, 42, 18, 14, 30, 21, 43, 27, 28, 45, 40, 34, 1],\n",
    "    points)\n",
    "\n",
    "test(points, baseline, short)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "1cbbfb6f1d7ae0933a4fb8be7140f48c",
     "grade": false,
     "grade_id": "cell-71ff3f40be096a85",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# The other eight test cases are hidden"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test with 90+ points\n",
    "# Test with 100+ points\n",
    "# Test with 200+ points\n",
    "# Test with 700+ points\n",
    "# Test with 600+ points\n",
    "# Test with 900+ points\n",
    "# Test with 900+ points\n",
    "# Test with 3000+ points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}