{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DS 25 – Heuristiken: Der Greedy-Ansatz\n",
    "**Informatik 10 – MINT-Zweig | Informatisches Problemlösen**\n",
    "\n",
    "## Lernziel\n",
    "Ich definiere den Begriff der Heuristik, beschreibe eine Heuristik zur Problemlösung und wende sie auf Probleminstanzen an."
   ]
  },
  {
   "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",
    "- Eine **Heuristik** ist eine Lösungsstrategie, die **schnell** eine (meist gute, aber nicht garantiert optimale) Lösung liefert, ohne alle Möglichkeiten zu prüfen.\n",
    "- Eine **Greedy-Heuristik** (\"gierig\") trifft in jedem Schritt die Entscheidung, die im **Moment** am besten erscheint, ohne spätere Auswirkungen zu berücksichtigen.\n",
    "- Beim TSP: Die Greedy-Heuristik **Nearest Neighbor** wählt von der aktuellen Stadt aus immer die **nächstgelegene, noch nicht besuchte** Stadt.\n",
    "- Heuristiken sind **schneller** als Brute-Force, liefern aber **nicht immer** die optimale Lösung – manchmal führt eine \"im Moment beste\" Entscheidung in eine Sackgasse."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 💡 Beispiel: Nearest Neighbor von Hand\n",
    "Mit der Entfernungstabelle aus DS 23/24, Start in `A`:\n",
    "1. Von `A` aus: nächstgelegene unbesuchte Stadt ist `B` (Entfernung 10).\n",
    "2. Von `B` aus: nächstgelegene unbesuchte Stadt ist `D` (Entfernung 25, da `C` mit 35 weiter ist).\n",
    "3. Von `D` aus: einzige verbleibende Stadt ist `C` (Entfernung 30).\n",
    "4. Zurück nach `A` (Entfernung 15).\n",
    "\n",
    "Route: `A → B → D → C → A`, Länge: `10 + 25 + 30 + 15 = 80`\n",
    "\n",
    "Die Route `A → B → D → C → A` hat die Länge **80** und ist für diese Instanz zugleich optimal. Das Beispiel zeigt also: Eine Heuristik kann das Optimum treffen, garantiert dies aber nicht."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🐍 Kontrolle: Nearest-Neighbor-Heuristik in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entfernungen = {\n",
    "    (\"A\", \"B\"): 10, (\"A\", \"C\"): 15, (\"A\", \"D\"): 20,\n",
    "    (\"B\", \"C\"): 35, (\"B\", \"D\"): 25, (\"C\", \"D\"): 30,\n",
    "}\n",
    "\n",
    "def entfernung(ort1, ort2):\n",
    "    if (ort1, ort2) in entfernungen:\n",
    "        return entfernungen[(ort1, ort2)]\n",
    "    return entfernungen[(ort2, ort1)]\n",
    "\n",
    "def nearest_neighbor(staedte, start):\n",
    "    unbesucht = set(staedte)\n",
    "    unbesucht.remove(start)\n",
    "    route = [start]\n",
    "    aktuell = start\n",
    "\n",
    "    while unbesucht:\n",
    "        naechste = min(unbesucht, key=lambda stadt: entfernung(aktuell, stadt))\n",
    "        route.append(naechste)\n",
    "        unbesucht.remove(naechste)\n",
    "        aktuell = naechste\n",
    "\n",
    "    return route\n",
    "\n",
    "def rundreise_laenge(reise):\n",
    "    laenge = 0\n",
    "    for i in range(len(reise) - 1):\n",
    "        laenge += entfernung(reise[i], reise[i + 1])\n",
    "    laenge += entfernung(reise[-1], reise[0])\n",
    "    return laenge\n",
    "\n",
    "staedte = [\"A\", \"B\", \"C\", \"D\"]\n",
    "route = nearest_neighbor(staedte, \"A\")\n",
    "print(\"Nearest-Neighbor-Route:\", route)\n",
    "print(\"Länge:\", rundreise_laenge(route))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 1 – Anderer Startpunkt\n",
    "Wendet die Nearest-Neighbor-Heuristik **von Hand** an, aber startet diesmal in Stadt `C`. Vergleicht die Route und Länge mit dem Ergebnis von Start `A`. Was fällt euch auf?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# OPTIONAL: Ergebnis der Handrechnung mit Start \"C\" kontrollieren\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🚀 Optionale Vertiefung – Heuristik vs. Optimum\n",
    "Vergleicht für eure **eigene 5-Städte-Instanz aus DS 24 Übung 1**: Wie lang ist die Route der Nearest-Neighbor-Heuristik im Vergleich zur optimalen (Brute-Force-)Route? Berechnet die **prozentuale Abweichung**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# OPTIONAL: Heuristik-Route und optimale Route einer 5-Städte-Instanz vergleichen\n",
    "\n"
   ]
  }
 ],
 "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
}
