{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Traveling Salesman Problem\n",
    "\n",
    "This notebook demonstrates solving the Traveling Salesman Problem (TSP) using simulated annealing. The TSP is a classic optimization problem where the goal is to find the shortest possible route that visits each city exactly once and returns to the origin city.\n",
    "\n"
   ],
   "id": "25b1e8add1d41851"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.241283Z",
     "start_time": "2025-12-20T19:36:35.233830Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from collections.abc import Sequence\n",
    "from random import uniform\n",
    "from itertools import permutations\n",
    "from time import time\n",
    "\n",
    "from altbacken.external.neighbourhood.permutation import PermutationNeighbourhood\n",
    "from altbacken.external.annealing import SimpleSimulatedAnnealing\n"
   ],
   "id": "7edbba62cc8eb94e",
   "outputs": [],
   "execution_count": 1
  },
  {
   "cell_type": "code",
   "id": "e3ae68fdfe5d68d7",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.280521Z",
     "start_time": "2025-12-20T19:36:35.278103Z"
    }
   },
   "source": [
    "type Graph = dict[int, dict[int, float]]"
   ],
   "outputs": [],
   "execution_count": 2
  },
  {
   "cell_type": "code",
   "id": "c0a340159d184163",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.327367Z",
     "start_time": "2025-12-20T19:36:35.324573Z"
    }
   },
   "source": [
    "def random_graph(n: int, min_dist: float = 1.0, max_dist: float = 100.0) -> Graph:\n",
    "    return {\n",
    "        i: {\n",
    "            j: uniform(min_dist, max_dist) for j in range(i + 1, n)\n",
    "        }\n",
    "        for i in range(n-1)\n",
    "    }"
   ],
   "outputs": [],
   "execution_count": 3
  },
  {
   "cell_type": "code",
   "id": "a8edc40cd4d9ec",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.374051Z",
     "start_time": "2025-12-20T19:36:35.371710Z"
    }
   },
   "source": [
    "def distance_between(graph: Graph, start: int, end: int) -> float:\n",
    "    start, end = min(start, end), max(start, end)\n",
    "    return graph[start][end]"
   ],
   "outputs": [],
   "execution_count": 4
  },
  {
   "cell_type": "code",
   "id": "9dc5a48ca7ccfc85",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.420612Z",
     "start_time": "2025-12-20T19:36:35.418319Z"
    }
   },
   "source": [
    "GRAPH_SIZE: int = 8\n",
    "graph: Graph = random_graph(GRAPH_SIZE)\n",
    "initial_solution = list(range(GRAPH_SIZE))"
   ],
   "outputs": [],
   "execution_count": 5
  },
  {
   "cell_type": "code",
   "id": "6751f739bf33e995",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.466737Z",
     "start_time": "2025-12-20T19:36:35.464114Z"
    }
   },
   "source": [
    "def travel_cost(solution: Sequence[int]) -> float:\n",
    "    current: int = solution[0]\n",
    "    start: int = solution[0]\n",
    "    cost: float = 0.0\n",
    "    for node in solution[1:]:\n",
    "        cost += distance_between(graph, current, node)\n",
    "        current = node\n",
    "    cost += distance_between(graph, current, start)\n",
    "    return cost"
   ],
   "outputs": [],
   "execution_count": 6
  },
  {
   "cell_type": "code",
   "id": "a439585ff96b7fe2",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.512744Z",
     "start_time": "2025-12-20T19:36:35.510564Z"
    }
   },
   "source": [
    "annealing: SimpleSimulatedAnnealing = SimpleSimulatedAnnealing(\n",
    "    travel_cost,\n",
    "    PermutationNeighbourhood(),\n",
    "    10000.0\n",
    ")"
   ],
   "outputs": [],
   "execution_count": 7
  },
  {
   "cell_type": "code",
   "id": "e1b8c68a82860b57",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.563185Z",
     "start_time": "2025-12-20T19:36:35.556572Z"
    }
   },
   "source": [
    "sa_start: float = time()\n",
    "best_match, best_value = annealing.simulate(initial_solution)\n",
    "print(\"SA took:\", time() - sa_start, \"seconds.\")\n",
    "\n",
    "print(\"Best match (SA):\", best_match)\n",
    "print(\"Best value (SA):\", best_value)"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SA took: 0.003637552261352539 seconds.\n",
      "Best match (SA): (1, 6, 5, 7, 4, 0, 3, 2)\n",
      "Best value (SA): 125.91510850173273\n"
     ]
    }
   ],
   "execution_count": 8
  },
  {
   "cell_type": "code",
   "id": "760afbc5c2b092ed",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.655905Z",
     "start_time": "2025-12-20T19:36:35.608834Z"
    }
   },
   "source": [
    "naive_start: float = time()\n",
    "optimal_path = min(permutations(list(range(GRAPH_SIZE)), GRAPH_SIZE), key=travel_cost)\n",
    "print(\"Naive took:\", time() - naive_start, \"seconds.\")\n",
    "print(\"Optimal path:\", optimal_path)\n",
    "print(\"Optimal cost:\", travel_cost(optimal_path))"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Naive took: 0.04398012161254883 seconds.\n",
      "Optimal path: (1, 6, 5, 7, 4, 0, 3, 2)\n",
      "Optimal cost: 125.91510850173273\n"
     ]
    }
   ],
   "execution_count": 9
  },
  {
   "cell_type": "code",
   "id": "6690d4e05a793d30",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-12-20T19:36:35.684443Z",
     "start_time": "2025-12-20T19:36:35.682068Z"
    }
   },
   "source": [
    "print(\"Relative derivation of SA solution:\", (best_value / travel_cost(optimal_path))-1)"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Relative derivation of SA solution: 0.0\n"
     ]
    }
   ],
   "execution_count": 10
  }
 ],
 "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": "python",
   "version": "3.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}