Problem Lösen durch Suche

🧠 "Problemlösen durch Suchen" – Was steckt wirklich dahinter?¶

1. 🔍 Was ist ein Suchproblem überhaupt?¶

Du hast ein Problem und suchst eine Lösung → Beispiel: Bauer will Ziege, Kohl und Wolf über den Fluss bringen, ohne dass sich jemand gegenseitig frisst.

Um das als Suchproblem zu lösen, braucht man:

Begriff	Bedeutung
Zustand	Wie die Welt gerade aussieht (z. B. „Ziege ist links“).
Startzustand	Ausgangspunkt (z. B. alles ist auf der linken Seite).
Zielzustand	Wunschzustand (z. B. alles ist sicher rechts angekommen).
Aktionen	Was kann man tun? (z. B. „Bauer fährt mit Wolf nach rechts“).
Übergänge	Durch eine Aktion ändert sich der Zustand.
Kosten	Manche Wege kosten mehr (z. B. Sprit, Zeit…).

➡️ Daraus entsteht ein Zustandsraum, also eine Art riesiges Entscheidungsdiagramm.

2. 🌳 Wie wird das Problem gelöst?¶

Durch Suche im Zustandsraum – du startest beim Ausgangspunkt und probierst Aktionen aus, um ans Ziel zu kommen.

Man unterscheidet zwei Arten von Suchen:

🔵 Uninformierte Suche (blinde Suche)¶

Du hast keinen Plan, was dich dem Ziel näher bringt.
Beispiele:

Verfahren	Beschreibung
Breitensuche	Geht systematisch Ebene für Ebene durch (wie Schlange stehen).
Tiefensuche	Geht so tief wie möglich – oft schnell, aber verirrt sich gern.
Tiefenbeschränkte Suche	Wie Tiefensuche, aber mit Sicherheitsgrenze.
Iterativ vertiefende Suche	Kombi aus beiden: startet flach und geht schrittweise tiefer.
Uniforme Kostensuche	Wählt immer den günstigsten Weg (z. B. wenig Benzinverbrauch).

🧮 Bewertungskriterien für Suchalgorithmen:

Vollständig – Findet der Algo eine Lösung, wenn es eine gibt?
Optimal – Ist es die beste Lösung (z. B. der kürzeste Weg)?
Zeitkomplexität – Wie lange dauert das Ganze?
Speicherbedarf – Wie viel RAM/Platz wird gebraucht?

🟢 Informierte Suche (mit Köpfchen!)¶

Hier hat der Algorithmus eine Heuristik – eine Art „Riecher“ für gute Entscheidungen.

✅ Was ist eine Heuristik (einfach erklärt)?¶

Eine Heuristik ist eine Hilfsmethode,
die dir hilft, schnell eine gute Entscheidung zu treffen,
ohne alles durchzuprobieren.

Beispiele:

Verfahren	Beschreibung
Gierige Suche	Immer zum Knoten, der dem Ziel am nächsten scheint (z. B. Luftlinie).
*A-Suche**	Kombiniert den Weg, den man schon gemacht hat g(n) + den geschätzten Restweg h(n) → f(n) = g(n) + h(n).

📌 Wichtig:
Gute Heuristiken = kluge Tipps, welche Wege sich lohnen → spart mega viel Rechenzeit!

3. 🧹 Beispiele aus dem Alltag¶

Staubsaugerwelt: Der Bot soll alles sauber machen → Suchproblem!
15-Puzzle: Schiebe ein Feld leer und sortiere die Zahlen → Zustände!
Sudoku / Kartenfärbung: Kann als sogenanntes „Constraint Satisfaction Problem“ formuliert werden.
Straßenkarte: Finde den kürzesten Weg von A nach B.

🧩 Fazit:¶

„Problemlösen durch Suchen“ ist im Grunde ein cleveres Durchprobieren von Möglichkeiten – mit oder ohne Plan.

Eine uninformierte Suche ist ein „dummer“ Algorithmus –
er hat keine Ahnung, wo das Ziel ist,
sondern folgt nur stur seiner Suchstruktur (z. B. Breitensuche, Tiefensuche).

Ein Algorithmus, der Heuristiken nutzen kann,
ist informiert – er kann mit Hilfsmethoden und Zusatzinfos gefüttert werden,
um klüger, gezielter und oft schneller zum Ziel zu kommen.

Ohne Plan 🕵️‍♂️	Mit Plan 🧠
Uninformierte Suche	Informierte Suche
Probieren alles durch	Probieren „schlaue“ Wege zuerst
Langsamer	Effizienter, wenn Heuristik gut ist
### 🔍 Vergleich von Suchalgorithmen in Bezug auf Heuristik

Algorithmus	Heuristik?	Speicherbedarf	Optimal?	Komplett?	Geschwindigkeit	Bemerkung
BFS	❌ Nein	Hoch	✅ Ja	✅ Ja	Langsam	Optimal bei gleicher Kosten pro Schritt
DFS	❌ Nein	Niedrig	❌ Nein	❌ Nein	Schnell (aber oft falsch)	Kann sich in Sackgassen verlaufen
IDS	❌ Nein	Niedrig	✅ Ja	✅ Ja	Langsam	Kombination aus DFS & BFS – platzsparend
Uniform Cost Search	❌ Nein	Hoch	✅ Ja	✅ Ja	Mittel	Wie A* ohne Heuristik
A*	✅ Ja	Hoch	✅ Ja	✅ Ja	Schnell (mit guter Heuristik)	Goldstandard für viele KI-Probleme
Greedy Best-First	✅ Ja	Mittel	❌ Nein	❌ Nein	Sehr schnell	Oft nicht optimal – gierig eben 😅
IDA*	✅ Ja	Niedrig	✅ Ja	✅ Ja	Etwas langsamer als A*	A* für wenig Speicher (z. B. eingebettete Systeme)
Weighted A*	✅ Ja	Hoch	❌ Nicht garantiert	✅ Ja	Sehr schnell	Opfer zugunsten der Geschwindigkeit

🧠 Merkhilfe:¶

Suche-Typ	Nutzt `h(n)`?	Beispiel
Informiert	✅ Ja	A, Greedy, IDA
Uninformiert	❌ Nein	BFS, DFS, IDS