{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DS 24 – Optimale Lösung und Brute-Force-Ansatz\n",
    "**Informatik 10 – MINT-Zweig | Informatisches Problemlösen**\n",
    "\n",
    "## Lernziel\n",
    "Ich definiere eine optimale Lösung als beste zulässige Lösung bezüglich eines Kriteriums und beschreibe einen Brute-Force-Ansatz zu ihrer Ermittlung."
   ]
  },
  {
   "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 **zulässige Lösung** erfüllt alle Bedingungen des Problems (z. B. \"besucht jede Stadt genau einmal\").\n",
    "- Eine **optimale Lösung** ist unter allen zulässigen Lösungen diejenige, die bezüglich eines festgelegten Kriteriums (z. B. Gesamtlänge) **am besten** ist.\n",
    "- Ein **Brute-Force-Ansatz** (\"rohe Gewalt\") ermittelt die optimale Lösung, indem er **alle** zulässigen Lösungen systematisch erzeugt, bewertet und die beste auswählt.\n",
    "- Vorteil: Brute-Force liefert garantiert die **optimale** Lösung.\n",
    "- Nachteil: Die Anzahl der zu prüfenden Lösungen wächst bei vielen Problemen sehr schnell (z. B. **faktoriell** beim TSP) – Brute-Force wird für größere Instanzen schnell unpraktikabel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 💡 Beispiel: TSP von Hand mit Brute-Force\n",
    "Wir verwenden die Entfernungstabelle aus DS 23 (4 Städte A, B, C, D). Berechnet **von Hand** die Gesamtlänge für die Rundreise `A → B → C → D → A`:\n",
    "\n",
    "`10 (A-B) + 35 (B-C) + 30 (C-D) + 20 (D-A) = 95`\n",
    "\n",
    "Wiederholt das für mindestens zwei weitere Rundreisen und vergleicht die Längen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Berechnungen hier)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🐍 Kontrolle: Brute-Force in Python\n",
    "Die folgende Zelle probiert **alle** Rundreisen aus und findet die optimale Lösung – vergleicht das Ergebnis mit euren Handrechnungen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "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 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",
    "beste_reise = None\n",
    "kuerzeste_laenge = None\n",
    "\n",
    "for permutation in permutations(staedte[1:]):\n",
    "    reise = [staedte[0]] + list(permutation)\n",
    "    laenge = rundreise_laenge(reise)\n",
    "    print(reise, \"->\", laenge)\n",
    "    if kuerzeste_laenge is None or laenge < kuerzeste_laenge:\n",
    "        kuerzeste_laenge = laenge\n",
    "        beste_reise = reise\n",
    "\n",
    "print(\"\\nOptimale Rundreise:\", beste_reise, \"mit Länge\", kuerzeste_laenge)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🚀 Optionale Vertiefung – Neue Probleminstanz mit Python\n",
    "Stellt eine eigene Entfernungstabelle für **5 Städte** auf (frei erfunden, plausible Werte) und passt den Python-Code oben entsprechend an, um die optimale Rundreise zu finden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# OPTIONAL: Eigene 5-Städte-Instanz definieren und Brute-Force anwenden\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 2 – Wachstum beobachten\n",
    "Zählt die Anzahl der geprüften Rundreisen bei 4, 5 und 6 Städten (Tipp: Es sind `(n-1)!` Reisen bei `n` Städten, wenn man die Startstadt festhält). Was fällt euch am Wachstum auf?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Beobachtung hier)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## ✅ Hinweis zu Übung 1\n",
    "Kopiert dazu einfach den `entfernungen`-Dictionary-Block von oben, fügt die fünfte Stadt mit allen nötigen Paar-Entfernungen hinzu und erweitert die `staedte`-Liste."
   ]
  }
 ],
 "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
}
