Najkrajse poti.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d0356b4b-3b66-4348-9a70-f772acb4876c",
   "metadata": {},
   "source": [
    "# Najkrajše poti\n",
    "\n",
    "Klasičen problem na grafih je iskanje najkrajših poti. Zanima nas na primer najkrajša pot med parom vozlišč $A$ in $B$ (*single-pair shortest path*). Naj bo ta najkrajša pot sestavljena iz vozlišč $A, ... X, B$, kjer je $X$ predzadnje vozlišče na poti. V tem primeru mora biti tudi pot od $A$ do $X$ najkrajša, sicer bi lahko pot od $A$ do $B$ izboljšali. Pri iskanju najkrajše poti od $A$ do $B$ posledično izračunamo tudi najkrajše poti do ostalih vozlišč na tej poti.\n",
    "\n",
    "Če bomo že morali izračunati najkrajše poti iz $A$ do več drugih vozlišč, pa jih lahko izračunamo iz začetnega vozlišča kar do vseh (*single-source shortest path*). Opazimo tudi, da bodo te najkrajše poti v grafu formirale **drevo najkrajših poti**. Vsako vozlišče bo imelo namreč enega optimalnega predhodnika/starša na najkrajši poti (npr. $X$ bo predhodnik $B$-ja). Koren drevesa pa bo seveda v vozlišču $A$.\n",
    "\n",
    "Za problem iskanja najkrajših poti med vsemi pari točk, lahko $N$-krat poženemo algoritem za iskanje drevesa najkrajših poti iz posameznega začetnega vozlišča. Obstajajo pa tudi drugi algoritmi, ki si namenjeni prav iskanju poti med vsemi pari točk. Tak primer je *Floyd-Warshall*-ov algoritem, ki ga tu ne bomo obravnavali.\n",
    "\n",
    "Ukvarjali se bomo predvsem z neusmerjenimi grafi. V usmerjenih grafih je situacija namreč podobna in lahko uporabimo enake razmisleke."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "dd0daee2-cd1a-4486-bb56-c6efa6699700",
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <fstream>\n",
    "#include <vector>\n",
    "#include <queue>\n",
    "#include <algorithm>\n",
    "using namespace std;\n",
    "\n",
    "typedef pair<int,int> PII;\n",
    "typedef vector<int> VI;\n",
    "typedef vector<pair<int,int>> VII;\n",
    "typedef vector<vector<int>> VVI;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e0838df4-7f90-48fd-9b27-4484477751f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "template<typename T>\n",
    "void print(const vector<T> &sez) {\n",
    "    for (T x : sez) cout << x << \" \";\n",
    "    cout << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b8e2b72-0048-4ee8-b87b-2846544bfb06",
   "metadata": {},
   "source": [
    "## Neuteženi grafi\n",
    "\n",
    "V neuteženih grafih ni potrebe po kompliciranju, saj že poznamo metodo **iskanja v širino (BFS)**, ki obiskuje vozlišča od bližnjih proti bolj oddaljenim glede na število povezav. Potrebuje je malenkostno dopolnitev, da bo poleg obiskovanja vozlišč beležila še dolžine poti in prednike vozlišč v drevesu najkrajših poti.\n",
    "\n",
    "<img alt=\"neutežen graf\" src=\"graph.svg\" width=\"250px\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "95de136a-b584-460f-9438-ef99593e45a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "ifstream fin(\"graph.txt\");\n",
    "int n,m;\n",
    "fin >> n >> m;\n",
    "vector<vector<int>> sosedi(n);\n",
    "for (int i=0;i<m;i++) {\n",
    "    int a,b;\n",
    "    fin >> a >> b;\n",
    "    sosedi[a].push_back(b);\n",
    "    sosedi[b].push_back(a);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "df8a3eb9-f26f-4c57-a0d3-aff43bdb9578",
   "metadata": {},
   "outputs": [],
   "source": [
    "void BFS_distance(vector<VI> &adj, int start, vector<int> &dist, vector<int> &prev) {\n",
    "    int n=adj.size();\n",
    "    dist=vector<int>(n,-1); prev=vector<int>(n);\n",
    "    vector<int> vis(n);\n",
    "    queue<int> q;\n",
    "    q.push(start); vis[start]=1;\n",
    "    dist[start]=0; prev[start]=-1;\n",
    "    while (!q.empty()) {\n",
    "        int x=q.front(); q.pop();\n",
    "        for (int y : adj[x]) {\n",
    "            if (!vis[y]) {\n",
    "                q.push(y); vis[y]=1;\n",
    "                dist[y]=dist[x]+1; prev[y]=x;  // distance, previous node\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "6a22cb39-f43a-44d6-bc96-f5539d9a40d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 3 2 1 2 3 2 \n",
      "-1 0 3 1 0 1 7 1 \n"
     ]
    }
   ],
   "source": [
    "vector<int> dist, prev;\n",
    "BFS_distance(sosedi,0,dist,prev);\n",
    "print(dist);\n",
    "print(prev);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03f2418b-528b-45b2-84eb-37f1e2ad3aff",
   "metadata": {},
   "source": [
    "## Uteženi grafi\n",
    "\n",
    "V uteženih grafih pa je situacija malo bolj zapletena. Omejili se bomo na grafe s **pozitivnimi (nenegativnimi) utežmi**, s kakršnimi imamo večinoma opravka v praksi, kasneje pa se bomo vrnili še k negativnim utežem. Utež (ceno, dolžino) povezave med vozliščema $X$ in $Y$ bomo označili z $w(X,Y)$.\n",
    "\n",
    "<img alt=\"utežen graf\" src=\"weighted.svg\" width=\"200px\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "627bee86-e963-407b-85ef-37aa6d2bb929",
   "metadata": {},
   "outputs": [],
   "source": [
    "ifstream fin(\"weighted.txt\");\n",
    "int n,m;\n",
    "fin >> n >> m;\n",
    "vector<VII> adjw(n);\n",
    "for (int i=0;i<m;i++) {\n",
    "    int a,b,w;\n",
    "    fin >> a >> b >> w;\n",
    "    adjw[a].push_back({b,w});\n",
    "    adjw[b].push_back({a,w});\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0458ea97-ec26-462a-a53b-08466040a28c",
   "metadata": {},
   "source": [
    "### Dijkstrov algoritem\n",
    "\n",
    "Tako kot smo v neuteženem primeru z iskanjem v širino računali najkrajše poti od bližnjih proti bolj oddaljenim vozliščem, bomo to storili tudi tu. Najbližje vozlišče je kar izhodiščno, $d(A) = 0$. Naslednje najbližje vozlišče pa bo eno od njegovih sosedov. Ker povezave niso negativne, je nemogoče, da bi dosegli manjšo razdaljo po kakšni poti z več povezavami. Tem neizračunanim sosedom do sedaj izračunanih vozlišč bomo rekli okolica. To so vozlišča, ki še niso izračunana in so iz že izračunanih dosegljiva po eni povezavi. Za vsako od njih bomo hranili potencialno najkrajšo pot $p(Y)$: kakšna bi bila razdalja, če bi se do njega premaknili z enega izmed že izračunanih vozlišč. Če iz okolice izberemo vozlišče $X$ s trenutno najmanjšo potencialno dolžino $p(X)$, bo to zagotovo dejanska najmanjša dolžina poti do tega vozlišča ($d(X) = p(X)$). Zaradi odsotnosti negativnih povezav, bi bila katerakoli druga pot od že izračunanih vozlišč do $X$ sestavljena iz več povezav in zato daljša. Množico že izračunanih vozlišč smo torej povečali z novim vozliščem $X$. Poskrbeti moramo še za posodobitev okolice. Vse sosede $Y$ vozlišča $X$ dodamo v okolico, če so že v njej, pa zgolj posodobimo njihovo potencialno oddaljenost z $p(Y) = \\min(p(Y), d(X)+c(X,Y))$. Postopek ponavljamo, dokler nimamo izračunanih najkrajših poti do vseh vozlišč."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1d3a409-833e-484f-af5b-b9b11ec6053a",
   "metadata": {},
   "source": [
    "V postopku imamo opravka s tremi skupinami vozlišč. V prvi skupini so tista, za katera imamo že izračunane najkrajše poti. V drugi skupini so vozlišča iz okolice, ki imajo samo potencialne dolžine. Tretja skupina pa so še povsem neobiskana vozlišča. Pri implementaciji bomo vse te informacije hranili v tabeli potencialnih razdalj. Razdalja -1 bo označevala še neobiskano vozlišče iz tretje skupine, -2 pa že izračunano iz prve."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b89a0c36-30fe-4308-866d-24311f8bfe54",
   "metadata": {},
   "outputs": [],
   "source": [
    "void Dijkstra(vector<VII> &adjw, int start, vector<int> &dist, vector<int> &prev) {\n",
    "    int n=adjw.size();\n",
    "    dist=vector<int>(n,-1); prev=vector<int>(n,-1);\n",
    "    vector<int> p(n,-1);  // provisional distance (-1=unvisited, -2=done)\n",
    "    p[start]=0;\n",
    "    while (1) {\n",
    "        int x=-1;  // smallest provisional\n",
    "        for (int i=0;i<n;i++) if (p[i]>=0) {\n",
    "            if (x==-1 || p[i]<p[x]) x=i;\n",
    "        }\n",
    "        if (x==-1) break;\n",
    "        dist[x]=p[x]; p[x]=-2;\n",
    "        for (auto [y,w] : adjw[x]) {  // update neighbors\n",
    "            int d=dist[x]+w;\n",
    "            if (p[y]==-1 || (p[y]>=0 && d<p[y])) { \n",
    "                p[y]=d; prev[y]=x; \n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "5111944a-5613-4eb9-ab2b-29fafeb5a9d8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 4 11 17 9 22 7 8 11 \n",
      "-1 0 4 2 7 3 0 6 7 \n"
     ]
    }
   ],
   "source": [
    "vector<int> dist, prev;\n",
    "Dijkstra(adjw,0,dist,prev);\n",
    "print(dist); print(prev);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac7da855-8f09-4661-83f3-a31517eaf3c1",
   "metadata": {},
   "source": [
    "Prostorska zahtevnost algoritma je $O(n)$. Časovna zahtevnost pa je odvisna od iskanja najmanje potencialne razdalje ($O(n^2)$) in posodabljanja sosedov ($O(e)$). Ker je $e=O(n^2)$, je časovna zahtevnost take implementacije algoritma $O(n^2)$.\n",
    "\n",
    "Razmislimo o izboljšavi. Težavno je iskanje vozlišča z najmanjšo potencialno razdaljo. Hkrati pa moramo biti sposobni posodabljati potencialne razdalje sosedov. Vozlišča iz okolice s potencialnimi razdaljami bi lahko hranili v uravnoteženem iskalnem drevesu. Tako lahko v času $O(\\log n)$ poiščemo najmanjšega in spremenimo potencialno razdaljo vozlišča. Časovna zahtevnost bi bila $O(n \\log n + e \\log n) = O(e \\log n)$.\n",
    "\n",
    "Iskanje najmanjšega elementa je namen prioritetne vrste, zato je to v praksi pogostejši način implementacije, ki je tudi preprostejši in zato bolj učinkovit. Če za prioritetno vrsto uporabimo dvojiško kopico, mora ta omogočati tudi spremembo prioritete. Pravzaprav gre samo za zmanjšanje prioritete v minimalni dvojiški kopici, kar lahko dosežemo v logaritemskem času. Tudi ta rešitev ima časovno zahtevnost $O(e \\log n)$.\n",
    "\n",
    "V spodnji implementaciji pa bomo malo \"goljufali\" in se izognili spreminjanju prioritet. Pri posodabljanju bomo v prioritetno vrsto samo vstavili novo manjšo vrednost, stare pa ne bomo izbrisali. Nova vrednost bo prišla iz vrsto prej, zato lahko stare neveljavne vrednosti, ki pridejo iz vrste nekoč kasneje, enostavno ignoriramo. V tabeli razdalj `dist` bomo hranili razdalje do vseh vozlišč (nekatere so pravilne, druge zgolj potencialne). Vozlišča, katerih razdalje so zgolj potencialne, bomo hranili v prioritetni vrsti. Ko pride vozlišče iz prioritetne vrste, vemo, da je njegova razdalja pravilna in posodobimo sosede. V prioritetni vrsti je lahko $O(e)$ elementov, zato je taka tudi prostorska zahtevnost. Časovna zahtevnost pa je $O(e \\log e) = O(e \\log n^2) = O(e \\cdot 2\\log n) = O(e \\log n)$. Goljufija torej ni bila prav huda.\n",
    "\n",
    "Vso to kompliciranje pa ima smisel samo, če je graf dovolj redek. Če je graf gost in vsebuje skoraj vse možne povezave ($e \\approx n^2$), je časovna zahtevnost $O(e \\log n)$ pravzaprav $O(n^2 \\log n)$, kar je slabše od $O(n^2)$, s čimer smo začeli."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d2207e84-99fb-4bb7-a7b1-c9718ec56bbf",
   "metadata": {},
   "outputs": [],
   "source": [
    "void Dijkstra_PQ(vector<VII> &adjw, int start, vector<int> &dist, vector<int> &prev) {\n",
    "    int n=adjw.size();\n",
    "    dist=vector<int>(n,-1); prev=vector<int>(n,-1);\n",
    "    priority_queue<PII, vector<PII>, greater<PII>> pq;  // (distance, node)\n",
    "    dist[start]=0; pq.push({0,start});\n",
    "    while (!pq.empty()) {\n",
    "        auto [d,x]=pq.top(); pq.pop();\n",
    "        if (dist[x]!=d) continue;  // ignore old values\n",
    "        for (auto [y,w] : adjw[x]) {  // update neighbors\n",
    "            int d=dist[x]+w;\n",
    "            if (dist[y]==-1 || d<dist[y]) {\n",
    "                dist[y]=d; prev[y]=x;\n",
    "                pq.push({d,y});\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "0027ef26-7587-486e-8ff9-f7a0192c6824",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 4 11 17 9 22 7 8 11 \n",
      "-1 0 4 2 7 3 0 6 7 \n"
     ]
    }
   ],
   "source": [
    "vector<int> dist, prev;\n",
    "Dijkstra_PQ(adjw,0,dist,prev);\n",
    "print(dist); print(prev);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01f23cd1-096d-42af-a376-a57eef6d7a55",
   "metadata": {},
   "source": [
    "Algoritem lahko v nekaterih primerih še izboljšamo. Pogosto so uteži relativno majhna cela števila. Naj bo $c$ največja utež v grafu. Največja oddaljenost vozlišča v grafu bo tako $(n-1)c$. Namesto v prioritetni vrsti lahko vozlišča s potencialnimi razdaljami hranimo \"popredalčkana\" v tabeli, ki na mestu $i$ hrani seznam vozlišč na razdalji $i$. Temu rečemo tudi vrsta z vedri (*bucket queue*). Podobno kot prej ne spreminjamo vrednosti, ampak dodajamo nove in po potrebi ignoriramo stare. Prostorska in časovna zahtevnost take rešitve sta $O(e + nc)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "edf5e19d-1ed3-4cf9-aaa1-78a61e2bcb97",
   "metadata": {},
   "outputs": [],
   "source": [
    "void Dijkstra_BQ(vector<VII> &adjw, int start, vector<int> &dist, vector<int> &prev) {\n",
    "    int n=adjw.size();\n",
    "    dist=vector<int>(n,-1); prev=vector<int>(n,-1);\n",
    "    int c=0;  // maximum weight\n",
    "    for (int x=0;x<n;x++) for (auto [y,w] : adjw[x]) c=max(c, w);\n",
    "    int maxd=(n-1)*c;\n",
    "    vector<VI> bq(maxd+1);  // bucket queue\n",
    "    dist[start]=0; bq[0].push_back(start);\n",
    "    for (int d=0;d<=maxd;d++) {\n",
    "        for (int x : bq[d]) {\n",
    "            if (dist[x]!=d) continue;  // ignore old values\n",
    "            for (auto [y,w] : adjw[x]) {  // update neighbors\n",
    "                int d=dist[x]+w;\n",
    "                if (dist[y]==-1 || d<dist[y]) {\n",
    "                    dist[y]=d; prev[y]=x;\n",
    "                    bq[d].push_back(y);\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ad6ed1be-2930-4e4d-8ba6-41f121756c3b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 4 11 17 9 22 7 8 11 \n",
      "-1 0 4 2 7 3 0 6 7 \n"
     ]
    }
   ],
   "source": [
    "vector<int> dist, prev;\n",
    "Dijkstra_BQ(adjw,0,dist,prev);\n",
    "print(dist); print(prev);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "301ef140-3e57-4b6a-8e9f-8acfa1b924e5",
   "metadata": {},
   "source": [
    "### Negativne uteži\n",
    "\n",
    "Do sedaj smo se omejili na pozitivne oz. nenegativne uteži. Negativne uteži imajo smisel samo na usmerjenih grafih. Sicer bi se lahko sprehajali tja in nazaj po isti negativni povezavi in imeli vedno krajšo pot.\n",
    "\n",
    "Kje pa pride do težave na usmerjenih grafih? Naša predpostavka, da ima vozlišče v okolici z najmanjšo potencialno razdaljo prav tako tudi dejansko razdaljo, ni več resnična. To lahko demonstriramo s spodnjim primerom."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "c23a7435-9b94-4997-89db-4d98c154af7a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2 3 \n",
      "-1 0 0 \n"
     ]
    }
   ],
   "source": [
    "// (0,1,2), (0,2,3), (2,1,-2)\n",
    "vector<VII> adjw = {{{1,2},{2,3}},{},{{1,-2}}};\n",
    "vector<int> dist, prev;\n",
    "Dijkstra(adjw,0,dist,prev);\n",
    "print(dist); print(prev);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00113c71-76da-44e2-9b06-66c8cf7ec5d5",
   "metadata": {},
   "source": [
    "Situacija je lahko še slabša. V usmerjenem grafu se lahko pojavi negativen cikel (cikel z negativno vsoto uteži). V takem primeru koncept najkrajših poti tudi nima smisla, ker lahko krožimo po ciklu in s tem poljubno krajšamo svojo pot. \n",
    "\n",
    "Obstajajo algoritmi, ki uspešno rešujejo probleme najkrajših poti tudi v prisotnosti negativnih povezav in zaznavajo prisotnost negativnih ciklov. Klasičen primer je Bellman-Fordov algoritem, ki ga boste obravnavali kasneje."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5f1afd2-43d3-4b1b-8e69-c3ec5d83e9ae",
   "metadata": {},
   "source": [
    "## Primeri\n",
    "\n",
    "Grafi so zelo pogost način modeliranja relacij, iskanje najkrajših poti pa eden najobičajnejših problemov na njih. V nadaljevanju si bomo ogledali nekaj primerov sorodnih problemov."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cccde94e-6349-479e-a2fa-9606df9ffaa4",
   "metadata": {},
   "source": [
    "### Najširša pot\n",
    "\n",
    "Recimo, da z grafom modeliramo cestno omrežje. Povezave predstavljajo dvosmerne ceste, vozlišča pa križišča. Uteži povezav ustrezajo širini ceste. Kakšna je največja širina vozila, ki se lahko pripelje od vozlišča $A$ do $B$?\n",
    "\n",
    "Gre za problem iskanja najširše poti (*widest path, maximum capacity path*). Pri njem iščemo pot od $A$ do $B$, za katero bo veljalo, da je najmanjša utež na poti čim večja. Za primerjavo nas je v klasičnem problemu najkrajših poti zanimala tista pot, kjer je bila vsota uteži čim manjša. Vsoto smo torej zamenjali z minimumom, minimizacijo pa z maksimizacijo.\n",
    "\n",
    "Uporabimo lahko povsem enak razmislek kot pri Dijkstrovem algoritmu. Poti do vozlišče bomo računali od širših proti ožjim. Najširša pot ($\\infty$ širine) vodi do začetnega vozlišča. Na vsakem koraku bomo med izračunana vozlišča dodali vozlišče iz okolice, do katerega vodi trenutno najširša potencialna pot. To ima zagotovo pravo vrednost, saj bi kakršnakoli druga pot obiskala več povezav, kar širine poti ne more povečati, temveč jo kvečjemu zmanjša."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5653bc0e-31c4-44ee-86c5-15ecb5d96cb4",
   "metadata": {},
   "source": [
    "### Najdaljša pot\n",
    "\n",
    "Kaj pa, če nas namesto najkrajše poti zanima najdaljša? Trivialno, uteži negiramo in je problem rešen. Žal ne, ker s tem dobimo graf z negativnimi cikli. Pravzaprav je koncept najdaljše poti slabo definiran - lahko bi se sprehajali sem in tja po isti povezavi in poljubno podaljšali pot.\n",
    "\n",
    "V primeru najdaljše poti nas zanimajo poti brez ponovljenih vozlišč. Pri najkrajših poteh je bilo to samoumevno, saj od večkratnega obiskovanja vozlišč ni nobene koristi ampak samo škoda. Izkaže se, da gre za težek problem, ki spada v razred NP-polnih (*NP-complete*) problemov. Več o tem pa pri predmetu Izračunljivost in računska zahtevnost.\n",
    "\n",
    "Izjema so usmerjeni aciklični grafi (DAG), ki ne vsebujejo ciklov. Tam smo že rešili prav ta problem, le da smo mu rekli kritična pot."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae8a719a-03d0-4c19-82e4-c8e5a6a6c4cd",
   "metadata": {},
   "source": [
    "### 15 Puzzle\n",
    "\n",
    "Verjetno poznate drsno sestavljanko prikazano na spodnji sliki. Igra se na mreži velikosti 4x4, kjer se na vsakem polju nahaja ploščica z enim izmed števil od 1 do 15. Vsako število se pojavi enkrat, eno polje pa je prazno. Zanima nas, kako naj s premiki ploščic na prazno sosednje polje uredimo števila po velikosti (po vrsticah od zgoraj navzdol in znotraj vrstice od leve proti desni). Še bolje, izračunajmo najmanjše potrebno število potez.\n",
    "\n",
    "<img alt=\"15 puzzle (wikipedija)\" src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/15-puzzle_magical.svg/600px-15-puzzle_magical.svg.png\" width=\"150px\">\n",
    "\n",
    "V tem primeru nimamo opravka z **grafom stanj**. Vsako stanje sestavljanke ustreza nekemu vozlišču. Za izračun najmanjšega števila potez bomo uporabili iskanje v širino (BFS). Seveda ne bomo vnaprej zgradili celotnega grafa, ker bi bil ta prevelik, ampak ga bomo odkrivali sproti. Rečemo, da bo graf predstavljen *implicitno* s stanji sestavljanke. Za vsako stanje oz. vozlišče znamo namreč izračunati njegove sosede. Pri tem upamo, da bomo dosegli rešitev dovolj zgodaj, preden bomo preiskali prevelik del grafa.\n",
    "\n",
    "Obstajajo tudi izboljšave tega osnovnega preiskovanja, ki z uporabo hevristik usmerjajo iskanje proti delom grafa, v katerih je bolj verjetno, da bomo našli rešitev. Primer nadgradnje iskanja najkrajših poti z uporabi hevristik je algoritem *A\\**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "db396b29-eb92-4c9f-a7dc-20136e950425",
   "metadata": {},
   "outputs": [],
   "source": [
    "int puzzle15(VVI start, vector<VVI> &seq) {\n",
    "    map<VVI, int> dist;\n",
    "    map<VVI, VVI> prev;\n",
    "    queue<VVI> q;\n",
    "    q.push(start); dist[start]=0;\n",
    "    VVI goal = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};\n",
    "    while (!q.empty()) {\n",
    "        VVI state=q.front(); q.pop();\n",
    "        if (state == goal) break;\n",
    "        // next states\n",
    "        for (int i=0;i<4;i++) for (int j=0;j<4;j++) if (state[i][j]==0) {  // find empty cell\n",
    "            for (auto [di,dj] : VII{{0,1},{0,-1},{1,0},{-1,0}}) {  // possible moves\n",
    "                int i2=i+di, j2=j+dj;\n",
    "                if (i2<0 || i2>=4 || j2<0 || j2>=4) continue;\n",
    "                VVI state2=state;  // adjacent state\n",
    "                swap(state2[i][j], state2[i2][j2]);\n",
    "                if (dist.count(state2)==0) {  // new?\n",
    "                    dist[state2] = dist[state]+1;\n",
    "                    prev[state2] = state;\n",
    "                    q.push(state2);\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    // reconstruct sequence of states\n",
    "    VVI state=goal;\n",
    "    seq.push_back(state);\n",
    "    while (state!=start) {\n",
    "        state = prev[state];\n",
    "        seq.push_back(state);\n",
    "    }\n",
    "    reverse(seq.begin(),seq.end());\n",
    "    return dist[goal];\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "bbac528b-ffad-4827-b74a-a8d7e17b4e41",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "\n",
      "5 0 2 3 \n",
      "6 1 7 4 \n",
      "9 10 11 8 \n",
      "13 14 15 12 \n",
      "\n",
      "5 1 2 3 \n",
      "6 0 7 4 \n",
      "9 10 11 8 \n",
      "13 14 15 12 \n",
      "\n",
      "5 1 2 3 \n",
      "0 6 7 4 \n",
      "9 10 11 8 \n",
      "13 14 15 12 \n",
      "\n",
      "0 1 2 3 \n",
      "5 6 7 4 \n",
      "9 10 11 8 \n",
      "13 14 15 12 \n",
      "\n",
      "1 0 2 3 \n",
      "5 6 7 4 \n",
      "9 10 11 8 \n",
      "13 14 15 12 \n",
      "\n",
      "1 2 0 3 \n",
      "5 6 7 4 \n",
      "9 10 11 8 \n",
      "13 14 15 12 \n",
      "\n",
      "1 2 3 0 \n",
      "5 6 7 4 \n",
      "9 10 11 8 \n",
      "13 14 15 12 \n",
      "\n",
      "1 2 3 4 \n",
      "5 6 7 0 \n",
      "9 10 11 8 \n",
      "13 14 15 12 \n",
      "\n",
      "1 2 3 4 \n",
      "5 6 7 8 \n",
      "9 10 11 0 \n",
      "13 14 15 12 \n",
      "\n",
      "1 2 3 4 \n",
      "5 6 7 8 \n",
      "9 10 11 12 \n",
      "13 14 15 0 \n"
     ]
    }
   ],
   "source": [
    "VVI state = {{5, 0, 2, 3},\n",
    "             {6, 1, 7, 4},\n",
    "             {9, 10,11,8},\n",
    "             {13,14,15,12}};\n",
    "vector<VVI> seq;\n",
    "cout << puzzle15(state, seq) << endl;\n",
    "for (VVI state : seq) {\n",
    "    cout << endl;\n",
    "    for (VI row : state) print(row);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53f976be-dbd4-4414-ac7d-ef0d4f29f3bf",
   "metadata": {},
   "source": [
    "Za konec zgolj kot zanimivost omenimo še reševanje **Rubikove kocke**. Iskanje najkrajših poti je še vedno predmet algoritmičnega raziskovanja. S precej računske moči so nedavno dokazali, da je mogoče vsako stanje Rubikove kocke rešiti v največ [20 potezah](http://www.cube20.org/) oz. [26 potezah](http://www.cube20.org/qtm/) (če je ena poteza rotacija ploskve samo za 90° in ne 180°)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}