{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DS 29 – Bewertung von Heuristiken & Abschluss\n",
    "**Informatik 10 – MINT-Zweig | Informatisches Problemlösen**\n",
    "\n",
    "## Lernziel\n",
    "Ich beurteile, wie gut eine Heuristik bei verschiedenen Probleminstanzen funktioniert, und festige die Inhalte des Themenfelds."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "sprachhilfe"
    ]
   },
   "source": [
    "## 🗣️ Sprachhilfe\n",
    "- „Es handelt sich um ein Problem/eine Probleminstanz, weil …“\n",
    "- „Der Ansatz prüft/wählt … und benötigt dabei …“\n",
    "- „Die Heuristik ist hier geeignet/nicht geeignet, weil …“"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📌 Merksätze\n",
    "\n",
    "- Um eine Heuristik zu **bewerten**, vergleicht man ihre Lösung mit der **optimalen** Lösung (sofern diese bekannt bzw. berechenbar ist) – üblich ist die **prozentuale Abweichung**.\n",
    "- Eine Heuristik kann bei **manchen** Probleminstanzen die optimale Lösung treffen und bei **anderen** deutlich schlechter abschneiden – deshalb reicht ein einzelner Test nicht aus.\n",
    "- Zur verlässlichen Bewertung testet man eine Heuristik über **mehrere, möglichst unterschiedliche** Probleminstanzen und betrachtet z. B. die **durchschnittliche** Abweichung."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🐍 Experiment: Nearest-Neighbor über mehrere zufällige Instanzen\n",
    "Die folgende Zelle erzeugt mehrere zufällige TSP-Instanzen, löst sie sowohl mit Brute-Force (optimal) als auch mit Nearest-Neighbor (Heuristik) und berechnet die durchschnittliche Abweichung."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from itertools import permutations\n",
    "\n",
    "def zufaellige_instanz(anzahl_staedte, seed):\n",
    "    random.seed(seed)\n",
    "    staedte = list(range(anzahl_staedte))\n",
    "    entfernungen = {}\n",
    "    for i in range(anzahl_staedte):\n",
    "        for j in range(i + 1, anzahl_staedte):\n",
    "            entfernungen[(i, j)] = random.randint(5, 50)\n",
    "    return staedte, entfernungen\n",
    "\n",
    "def entfernung(entfernungen, a, b):\n",
    "    return entfernungen[(a, b)] if (a, b) in entfernungen else entfernungen[(b, a)]\n",
    "\n",
    "def rundreise_laenge(entfernungen, reise):\n",
    "    laenge = 0\n",
    "    for i in range(len(reise) - 1):\n",
    "        laenge += entfernung(entfernungen, reise[i], reise[i + 1])\n",
    "    laenge += entfernung(entfernungen, reise[-1], reise[0])\n",
    "    return laenge\n",
    "\n",
    "def optimale_route(staedte, entfernungen):\n",
    "    beste, beste_laenge = None, None\n",
    "    for perm in permutations(staedte[1:]):\n",
    "        reise = [staedte[0]] + list(perm)\n",
    "        laenge = rundreise_laenge(entfernungen, reise)\n",
    "        if beste_laenge is None or laenge < beste_laenge:\n",
    "            beste, beste_laenge = reise, laenge\n",
    "    return beste, beste_laenge\n",
    "\n",
    "def nearest_neighbor(staedte, entfernungen, start):\n",
    "    unbesucht = set(staedte)\n",
    "    unbesucht.remove(start)\n",
    "    route = [start]\n",
    "    aktuell = start\n",
    "    while unbesucht:\n",
    "        naechste = min(unbesucht, key=lambda s: entfernung(entfernungen, aktuell, s))\n",
    "        route.append(naechste)\n",
    "        unbesucht.remove(naechste)\n",
    "        aktuell = naechste\n",
    "    return route\n",
    "\n",
    "abweichungen = []\n",
    "for seed in range(10):\n",
    "    staedte, entfernungen = zufaellige_instanz(6, seed)\n",
    "    _, opt_laenge = optimale_route(staedte, entfernungen)\n",
    "    nn_route = nearest_neighbor(staedte, entfernungen, staedte[0])\n",
    "    nn_laenge = rundreise_laenge(entfernungen, nn_route)\n",
    "    abweichung = (nn_laenge - opt_laenge) / opt_laenge * 100\n",
    "    abweichungen.append(abweichung)\n",
    "    print(f\"Instanz {seed}: Optimal={opt_laenge}, Nearest-Neighbor={nn_laenge}, Abweichung={abweichung:.1f}%\")\n",
    "\n",
    "print(f\"\\nDurchschnittliche Abweichung: {sum(abweichungen)/len(abweichungen):.1f}%\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 1 – Auswertung\n",
    "Beantwortet anhand der Ausgabe oben:\n",
    "1. Gab es eine Instanz, bei der die Heuristik die optimale Lösung getroffen hat (Abweichung 0 %)?\n",
    "2. Wie groß war die größte beobachtete Abweichung?\n",
    "3. Ist die Nearest-Neighbor-Heuristik eurer Einschätzung nach für den praktischen Einsatz geeignet? Begründet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Antworten hier)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 2 (Abschlussaufgabe) – Zusammenfassung\n",
    "Beantwortet in eigenen Worten (als Wiederholung des gesamten Themenfelds):\n",
    "1. Was ist der Unterschied zwischen einem Problem und einer Probleminstanz?\n",
    "2. Wann liefert ein Brute-Force-Ansatz garantiert die optimale Lösung, und wo liegt sein Nachteil?\n",
    "3. Was zeichnet eine Greedy-Heuristik aus, und welches Risiko birgt sie?\n",
    "4. Nennt je ein Beispiel für ein Problem mit faktoriellem und eines mit exponentiellem Brute-Force-Aufwand."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Antworten hier – als Vorbereitung für einen möglichen Kurztest)*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  },
  "v3_revision": {
   "basis": "MINT-Lehrplan Informatik 10 (2026)",
   "didaktik": "fragend-entwickelnder Kern, kurzer Transfer, flexible Reserve",
   "lerngruppe": "11 SuS"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
