-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.tex
1455 lines (1087 loc) · 74.3 KB
/
main.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[runningheads,deutsch]{llncs}
%
\usepackage[T1]{fontenc}
%
\usepackage{graphicx}
%
% Daniel Motz's packages
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{ bbold }
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\setcounter{tocdepth}{3}
\usepackage{tikz}
\usepackage{tikz-3dplot}
\usepackage{pgfplots}
\pgfplotsset{compat = newest}
\usepackage{hyperref}
\usepackage{setspace}
\doublespacing
\usepackage{array} % for \newcolumntype macro
\newcolumntype{C}{>{$}c<{$}} % math-mode version of "l" column type
\newcolumntype{L}{>{$}l<{$}} % math-mode version of "l" column type
\renewcommand{\abstractname}{}
\newcommand{\inline}{\mintinline[fontsize=\normalsize]{c++}{text}}
\newcommand{\estimates}{\overset{\scriptscriptstyle\wedge}{=}}
\DeclareUnicodeCharacter{03BB}{$\lambda$}
\newenvironment{indentleft}[1]{
\setlength{\leftskip}{#1}
}{
\setlength{\leftskip}{0pt}
}
\usepackage{cancel}
% END Daniel Motz's packages
\begin{document}
%
\title{
Einführung in die Künstliche Intelligenz
}
%
\titlerunning{Einführung in die KI}%
\author{Maximilian Stock, Daniel Motz}
%
\authorrunning{M. Stock, D. Motz}
%
\institute{Fakultät für Mathematik und Informatik, Friedrich-Schiller-University,\\ Jena, Germany\\
\vspace{.2cm}
\email{[email protected], [email protected]}
}
%
\maketitle % typeset the header of the contribution
%
% Set paragraph indent to 0mm
\parindent0mm
\section{Der Gegenstandsbereich}
%\subsection{Lernfragen}
%\begin{description}
% \item[Was meint "KI"?] KI ist das Unterfangen, künstliche intelligente Systeme zu bauen.
% \item[Der Turing-Test]
% \item["Starke" und "schwache" KI]
% \item[Symbolische KI vs. Konnektionismus]
%\end{description}
%\subsection{TODOs}
%\begin{itemize}
% \item (Seite 10 FS 1) teleologischer Aspekt WB-Systeme verstehen
% \item (Seite 10 FS 1) "nach generellen Prinzipien strukturiert" verstehen
% \item (Seite 10 FS 1) Wissenstransfer, Erklärung. Was bedeutet das?
% \item (Seite 11 FS 1) Wissenstypen: Begriffe abgrenzen
% \item Hybride (letzte Seite) ergänzen
%\end{itemize}
%\subsection*{Done TODOs}
%\begin{itemize}
% \item Den "nicht-einfachen" Turing-Test (die Verhörsituation) verstehen
% \item Was ist eine einbettende Umgebung in einem PSS?
% \item PSS genauer definieren
% \item Starke und Schwache KI nach Searle verstehen
%\end{itemize}
\subsection{Was ist KI?}
\subsubsection{1. Definitionsversuch}
KI ist das Unterfangen, künstliche intelligente Systeme zu \textit{bauen}.
Mit Intelligenz sind Aufgaben, die Menschen gut bewältigen gemeint. Sie
demonstrieren Intelligenz:
\begin{itemize}
\item Bilderkennung
\item Stimmerkennung
\item Aufstellen vernünftigter Erwartungen (z.B. wenn etwas "John" heißt, erwarten wir, dass es sich nicht um ein Kino oder ein Eis, sondern wahrscheinlich um eine Person; vielleicht noch ein Haustier oder Ähnliches).
\end{itemize}
Nicht alles, was der Mensch gut tut, ist interessant für die KI.
Viele Aufgaben, die gemeinhin als schwierig (Intelligenz voraussetzen) gelten, sind zu \textit{speziell}: Das einzig intelligente, was ein Schachprogramm kann,m ist Schachspielen!
\subsubsection{Einfacher Turingtest}
\begin{itemize}
\item Zwei Räume verbunden durch Fernschreiber
\begin{itemize}
\item in einem Raum der \textit{Tester}
\item im anderen: \textit{Mensch} oder \textit{Maschine}
\end{itemize}
\item Tester hat 30 Minuten Zeit über den Fernschreiber herauszufinden, ob es sich um einen Menschen oder eine Maschine handelt.
\end{itemize}
\subsubsection{2. Definitionsversuch}
KI ist das Unterfangen, ein künstliches System zu bauen, das den Turingtest zuverlässig besteht.
\subsubsection{Der Turing-Test}
In einer "Verhörsituation" gibt es drei Personen, die sich gegenseitig nicht sehen und nur schriftlich kommunizieren können. Person A ist männlich, Person B ist weiblich und Person C hat ein beliebiges Geschlecht. Person C leitet das Verhör und soll bestimmen, welche der Personen welches Geschlecht hat. C kann beide mit X und Y ansprechen und muss am Ende A X und B Y oder B X und A Y zuordnen. A hat das Ziel, dass C die Geschlechter falsch bestimmt. Auch hier: Zeitlimit von 30 Minuten.
Nun fragen wir uns: "Was passiert, wenn eine Maschine die Rolle von A übernimmt?"
\subsubsection{Einwände gegen den Turing-Test:}
Kann die Maschine als Mensch durchgehen, nur weil der Tester schlecht ist? (... z.B. einschläft ...) Man wiederholt den Test mehrfach. Der Test ist sinnfrei, wenn $B$ lügen kann, z.B. vorgibt ein Mann zu sein, weil die "Intelligenz" der Maschine dann irrelevant für den Test ist. Er ist auch sinnfrei, wenn $A$ nicht lügen darf. Man geht explizit davon aus, dass $B$ keine Agenda hat.
\subsubsection{Searle's Einwand}
Der Tester tippt nicht mehr als 10 Zeichen pro Sekunde. Die Maschine muss maximal 18.000 Zeichen beantworten. Da die Anzahl an möglichen Anfragen begrenzt ist, kann man in einer riesigen Tabelle alle möglichen Konfrontationen für diesen Dialog speichern und die Maschine kann mit ihrer Hilfe alle intelligenten Reaktionen nachschlagen. Hier scheiden sich die Geister. Wann ist eine KI eine KI und was muss sie können?
\begin{definition}{Die "starke" KI-Hypothese}
\dots eine \textit{funktionale Definition von Intelligenz} $\Rightarrow$ Turing-Test bestehen.
\end{definition}
\begin{definition}{Die "starke" und die "schwache" KI-Hypothese}
Eine schwache KI ist ein Werkzeug, das genau eine Klasse von Problemen lösen kann; zum Beispiel ein Schachcomputer. Für andere Probleme, etwa das steuern eines Fahrzeugs, ist er ungeeignet. Während eine schwache KI ihren Job nur anhand ihres Trainings erledigt, versteht eine starke KI ihre Aufgabe, und ist in der Lage eigenständig eine Lösungsstrategie zu entwickeln. Diese Fähigkeit zu argumentieren und zu abstrahieren, verleiht ihr außerdem die Fähigkeit, sich weiterzuentwickeln, sich zu verbessern und sich neue Fähigkeiten anzueignen. Sie ist autonom.
\end{definition}
\subsubsection{Was heißt hier "künstlich"?}
Minimalforderung: künstlich $\Rightarrow$ anorganisch. Bringt uns aber nicht weiter...
Besser: Ein künstliches System ist ein \textit{physical-symbol-system} (PSS) im Sinne von Newell und Simon. Ein PSS ist eine \textit{symbol-manipulierende Einrichtung} (enthält Symbole, die zusammen Symbolstrukturen bilden, welche erschaffen, bearbeitet, kopiert und gelöscht werden können. Beispiele: \textbf{Turingmaschine}, Universalrechner). Es muss in eine externe Umgebung eingebettet sein, damit man sein Verhalten evaluieren kann.
Beispiel Schach: Unser Schachbrett ist die \textit{planning domain}. In dieser domain kann man sich nur über Züge von Figuren, die Positionen auf dem Brett und ob das Spiel gewonnen oder verloren ist unterhalten. Unsere KI repräsentiert ihre Erkenntnisse als Objekte in dieser domain.
%https://en.wikipedia.org/wiki/Blocks_world
\subsubsection{3. Definitionsversuch}
KI ist das Unterfangen, ein PSS zu bauen, das den Turing-Test zuverlässig besteht.
Zusatzanforderung mancher KI-ler: Die von dem PSS manipulierten Symbole sollen Objekten in der eingebetteten Umgebung entsprechen.
\begin{definition}{Annahme des Deklarativismus.}
Nach der Annahme des Deklarativismus kann ein System, das alle "intelligenten Antworten" in einer Tabelle nachschlägt, nicht intelligent sein.
\end{definition}
\begin{remark}
Ein neuronales Netz ist keine deklarativistische Teildisziplin. Außer wenn man so viele Neuronen anlegt, dass alle Beispiele "gemerkt" werden können $\Rightarrow$ \textit{overfitting}.
\end{remark}
\begin{remark}{Kann eine KI stark sein, wenn man auf einem Von-Neumann-Rechner ist?}
Wahrscheinlich nein, weil er deterministisch ist.
\end{remark}
\subsubsection{Modellierungsansatz}
\begin{enumerate}
\item Algorithmische Theorie (Problemstellung definieren, Beweis der algorithmischen Lösbarkeit)
\item Repräsentation und Algorithmus (Algorithmus abstrakt entwerfen. Mithilfe eines Modells, z.B. Von-Neumann-Rechner, geeignete Datenstrukturen wählen)
\item Implementation (Umsetzung in einer Programmiersprache bzw. Maschinenanweisungen, Optimierung)
\end{enumerate}
Kompetenz: 1. und 2.
Performanz: 2. und 3.
\subsubsection{Wissensbasierte Systeme}
Ein wissensbasiertes System kann als eine besondere Art von Programmiersystemen angesehen werden. Die Inferenzmaschine ist dabei ein Berechnungsmechanismus für mit der Wissensbasis gegebene Programme. Durch die Eingabe von Wissen wird die Inferenzmaschine programmiert. Das Wissen wird deklarativ repräsentiert. Es besteht sowohl aus Faktenwissen (ähnlich den Daten in einer herkömmlichen Datenbank) als auch Regelwissen, zum Beispiel in Form von Produktionsregeln (wenn ..., dann ...), die symbolisch vorliegen.
Quelle: \href{https://de.wikipedia.org/wiki/Wissensbasiertes_System}{Wikipedia: Wissensbasiertes System}
\pagebreak
\begin{itemize}
\item methodischer Aspekt -- automatische Lösung mit Fachwissen
\begin{itemize}
\item können mithilfe der Ableitungsregeln und dem Wissen in der WB schlussfolgern
\end{itemize}
\item qualitativer Aspekt -- schwieriges Problem
\begin{itemize}
\item WB-Systeme werden in Feldern angewendet, auf denen imperative, algorithmische Lösung schwer realisierbar sind
\end{itemize}
\item teleologischer Aspekt -- praktische Bedeutung
\begin{itemize}
\item
\end{itemize}
\end{itemize}
Ein WB-System benötigt explizit und deklarativ dargestelltes fachgebietsspezifisches Wissen, das nach generellen Prinzipien strukturiert ist und einen generellen Schlussfolgerungsmechanismus.
\subsubsection{Entwurf}
\begin{itemize}
\item Wissensdarstellung ("Knowledge Representation")
\item Wissensausnutzung ("Problem Solving")
\item Wissenserwerb ("Knowledge Acquisition") $\rightarrow$ Erweiterung / Veränderung der WB
\item Wissenstransfer, Erklärung ("Explanation")
\end{itemize}
\subsubsection{Wissensrepräsentation}
\paragraph{Wissenstypen}
\begin{itemize}
\item elementare Tatsachen, Schlussweisen
\item spezielle Fälle, Situationen
\item bestimmte Vorgehensweisen, Algorithmen
\item allgemeine Gesetzmäßigkeiten, Alltagswissen
\end{itemize}
\subsubsection{Logik-basierte Repräsentationsformalismen}
\begin{itemize}
\item Terminologische Logiken, Beispiel: Diagnosesystem für Fahrzeugdefekte. Symptome als Input, Diagnose als Output)
\item Vererbung (von Eigenschaften)
\item Nicht-Monotonie (Monotonie bedeutet, dass bei Erweiterung der Wissensbasis alle bisherigen Schlüsse weiterhin gültig sind. Verwendung von Defaults ist bspw. nicht-monoton.)
\end{itemize}
%\subsubsection{Problemlösungstechniken in WB-Systemen}
%\begin{description}
% \item[Klassifikation] ...
% \item[Zugriff] ...
% \item[Synthese] Schließen von neuem Wissen aus der bestehenden WB (und anschließendes Aufnehmen in die WB)
% \item[Deduktion] Ableitung mithilfe von Ableitungsregel
% \item[Simulation] ...
% \item[Zielorientierte Suche] ...
% \item[Planen als zielorientierte Suche auf Metaebene]
% \item[Strukturanalyse] ...
% \item[Transformation] ...
%\end{description}
\subsubsection{Einsatzbereiche für WB-Systeme}
\begin{itemize}
\item Interpretation physikalischer Daten (Messungen interpretieren)
\item Diagnose von Systemzuständen (Fehler im Auto, kranker Patient)
\item Planung von Handlungen, um Ziele zu erreichen (Marjapussi)
\item Entwurf und Konstruktion nach Spezifikation
\item Unterricht und Training von Kenntnissen und Fähigkeiten (Deep Learning?)
\end{itemize}
\subsection{Wichtige Teilgebiete der KI}
\subsubsection{Klassische (symbolische) KI}
Die klassische KI nutzt zur Problemlösung Repräsentation für Probleme in (menschenlesbaren) Hochsprachen. Sie nutzt logische Programmierung, Produktionsregeln, semantische Netze und \textit{frames}. Aus ihr entstanden Anwendungen wie Expertensysteme (wissensbasierte Systeme) und automatische Beweisprogramme.
\begin{itemize}
\item Wissensrepräsentation
\item Heuristische Suchverfahren
\item Planung
\item Wahrnehmung
\item Deduktion
\item Lernen
\item Sprach- und Bildverarbeitung
\item Verarbeitungsmodelle, KI-Programmiersprachen
\end{itemize}
\subsubsection{Konnektionismus (Soft Computing)}
ist ein Teilgebiet der Kybernetik, welches sich mit dem Verhalten vernetzter Systeme basierend auf Zusammenschlüssen von künstlichen Informationsverarbeitungseinheiten beschäftigt. \textbf{Soft Computing} befasst sich mit der approximativen Lösung. \textit{Es ist von numerischen Verfahren zu unterscheiden.}
\begin{description}
\item[ Neuronale Netze]
\item[ Genetische Algorithmen ] (In Anlehnung an die Natur: Suche nach Lösungen mit stochastischen Optimierungsverfahren)
\item[ Fuzzy Logic ] (Verallgemeinerung der zweiwertigen Booleschen Logik - erlaubt bspw. die Beschreibung der Ausprägung einer Eigenschaft)
\end{description}
%\subsubsection{Hybride}
%\begin{itemize}
% \item
%\end{itemize}
\section{Logik}
%\textbf{TODOs}
%\begin{itemize}
% \item Interpretationsbereich klären (Seite 5 lprelim.div)
%\end{itemize}
\subsection{Lernfragen}
\begin{description}
\item[Logische Programmierung] Besteht aus einer Menge von Axiomen, die als Fakten oder Annahmen zu verstehen sind, aus denen die Anfrage eines Benutzers beantwortet werden soll.
\item[Aussagenlogik] Atome (denen ein Wahrheitswert zugeordnet wird) und Junktoren
\item[Prädikatenlogik] Erweitert um Prädikate (Aussagen mit Leerstellen, wie eine Funktion) und Quantoren ($\exists, \forall$). Bspw. $\forall x \in \text{Menschen}: \text{mutter}(\text{Eva}, x)$
\item[Klausellogik] Formel in KNF, bei der die Konjunktionen jeweils in Mengenschreibweise zusammengefasst werden. Bspw.: \\
$((a \lor b) \land (b \lor c) \land (a \lor \lnot d \lor \lnot e) \land d) \estimates \{\{a,b\}, \{b, c\}, \{a, d, e\}, \{d\}\}$
\item[Aussagenlogische Resolution] Statt eine allgemeine Gültigkeit zu beweisen, leitet es einen Widerspruch für die Negation her
\item[Unifikation] Zwei Ausdrücke werden unifiziert, indem ihre Variablen so durch geeignete Terme ersetzt werden, dass die resultierenden Ausdrücke gleich sind.
\item[Prädikatenlogische Resolution] Zwei Klauseln $K$ und $K'$ werden resolviert, indem man man ein $\phi$ findet, das in $K$ enthalten ist und dessen Negation $\lnot\phi \in K'$. Man bildet dann die Vereinigung $(K \backslash \phi) \cup (K' \backslash \lnot\phi)$ und nennt sie Resolvente.
\item[Aussagenlogische Resolution] Exakt analog zu prädikatenlogischer Resolution. Man nimmt den Term und seine Negation aus den zu resolvierenden Klauseln und bilden ihre Vereinigung.
\item[Inferenz] aufbereitetes Wissen, das aufgrund von logischen Schlussfolgerungen gewonnen wurde
\end{description}
\subsection{Logische Programmierung}
\begin{itemize}
\item Mit Logik lässt sich Wissen formalisieren
\item Die \textbf{Prädikatenlogik} 1. Stufe (PL1) die bekannteste Logik
\item Inferenzmechanismen gestatten es, aus "altem" (explizitem) Wissen, "neues" (implizites) Wissen abzuleiten.
\end{itemize}
Die Klausellogik als syntaktische Teilklasse von PL1 ist für das Theorembeweisen von besonderer Wichtigkeiten
Der auf Klausellogik basierende Resolutionskalkül kann aber auch als \textbf{Programmiersprache} verwendet werden.
Logische Programmierung (z.B. in \textbf{Prolog}) basiert auf \textbf{Klausellogik} und dem Standard-Inferenzmechanismus der \textbf{Resolution}. Prolog ist daher ein \textit{Satisfiability Solver}. Statt Prolog ließe sich eine prädikatenlogische Axiomensammlung auch mit einem anderen SAT-Solver lösen -- der Vorteil besteht darin allerdings in der Einfachheit des Backtracking-Algorithmus. Er besitzt ein vom Programmierer reproduzierbares und planbares Verhalten.
\[
\text{Annahmen} \xrightarrow[\text{als Inferenzregel}]{\text{Resolution}} \text{Konklusionen}
\]
\subsection{Syntax der Prädikatenlogik}
Induktiver Aufbau prädikatenlogische Ausdrücke mit:
\begin{enumerate}
\item \textbf{Konstantensymbolen} $a, b, c, \dots$
\item \textbf{Funktionssymbolen} $f, g, h, \dots$
\item \textbf{Variablensymbolen} $x, y, z, \dots$
\item \textbf{Prädikatensymbolen} likes, father, $\dots$
\end{enumerate}
Man unterscheidet zwischen \textit{Termen, Atomformeln}.
Ein \textbf{Term} ist entweder
\begin{itemize}
\item ein Konstantensymbol,
\item ein Variablensymbolen
\item ein Funktionssymbol angewendet auf ein Tupel (geordnete Anordnung) von Termen.
\end{itemize}
Eine \textbf{Atomformel} ist ein Prädikatsymbol, angewendet auf ein Tupel von Termen.
Ein \textbf{Grundterm/Grundformel} ist ein Term/eine Formel, der/die keine Variablen enthält.
\begin{example}
$a, x$ und $f(b, f(b, y, z), y)$ sind Terme.\\
$\text{likes}(x, \text{dad}(x))$ und \\
$\text{borrows}(\text{doug}, \text{book}, \text{chris})$ sind Atomformeln.
\end{example}
Eine \textbf{wohlgeformte Formel} ist entweder eine Atomformel oder hat eine der folgenden Formen $(W_1, W_2, W \text{ seien wohlgeformt}):$
\begin{align}
(W) \\
W_1 \land W_2 \\
W_1 \rightarrow W_2 \\
\lnot W \\
W_1 \lor W_2 \\
(\exists X) W \\
(\forall X) W
\end{align}
Der \textbf{Gültigkeitsbereich} einer Quantifikation $\forall x$ (bzw. $\exists x$) in einer Formel $\forall x \text{F}$ (bzw. $\exists x \text{F}$) ist genau die Teilformel F. Die Variable $x$ heißt dann \textbf{gebunden} in $\forall x \text{F}$ (bzw. $\exists x \text{F}$).
Eine Variable, die in keiner Teilformel einer Formel F gebunden auftritt, heißt \textbf{frei} in F.
Eine \textbf{geschlossene Formel} ist eine wohlgeformte Formel, in der jedes Vorkommen eines jeden Variablensymbols gebunden ist.
\begin{example}
$(\forall x)((\exists y) \text{child}(x) \rightarrow \text{father}(y, x)).$
\end{example}
Bindungsregeln der logischen Konnektoren und Quantoren:
\setlength{\tabcolsep}{12pt}
\begin{center}
\begin{tabular}{l l l}
$\lnot$ & bindet stärker als & $\land$ und $\lor$ \\
$\land$ und $\lor$ & bindet stärker als & $\rightarrow$
\end{tabular}
\end{center}
\subsection{Prädikatenlogik -- die Semantik}
Die Bedeutung einer logischen Sprache wird mithilfe einer \textbf{Interpretation $I$} festgelegt:
\begin{enumerate}
\item Der \textbf{Interpretationsbereich} $D = dom(I)$ ($dom \estimates$ \href{https://en.wikipedia.org/wiki/Domain_of_discourse}{domain of discourse}) ist eine (nichtleere) Menge von Objekten, auf die sich $I$ bezieht.
\item Jedem Konstantensymbol wird genau ein Element aus $D$ zugeordnet.
\item Jedem $n$-stelligen Funktionssymbol wird genau eine Funktion von $D^n \mapsto D$ zugeordnet.
\item Jedem $n$-stelligen Prädikatsymbol wird genau eine $n$-stellige Relation aus $dom(I)^n$ zugeordnet.
\end{enumerate}
Eine Interpretation weist jeder Formel $G$ einen Wahrheitswert zu:
% TODO weist eine Interpretation einer Formel wirklich einen Wahrheitswert zu?
\begin{itemize}
\item $I \vDash G$, wenn $I$ der Formel $G$ den Wert \textbf{wahr} zuordnet und
\item $I \nvDash G$, falls $I$ der Formel $G$ den Wert \textbf{falsch} zuordnet.
\end{itemize}
\subsection{Wahrheitswert zusammengesetzter Formeln}
Prinzip der \textbf{Kompositionalität}:
Der Wahrheitswert einer Formel setzt sich aus den Wahrheitswerten ihrer Teilformeln zusammen.
\begin{center}
\begin{tabular}{l l l l}
$\lnot W$ & wahr & $\Leftrightarrow$ & $W$ falsch \\
$W_1 \land W_2$ & wahr & $\Leftrightarrow$ & $W_1$ wahr und $W_2$ wahr \\
$W_1 \lor W_2$ & wahr & $\Leftrightarrow$ & $W_1$ wahr oder $W_2$ wahr \\
$W_1 \rightarrow W_2$ & falsch & $\Leftrightarrow$ & $W_1$ wahr und $W_2$ falsch
\end{tabular}
\end{center}
$(\forall x) W$ ist wahr gdw. für \textbf{jedes} Element $e$ aus $\mathcal{D}$, durch Ersetzen der Variablen $x$ durch $e$ eine wahre Formel entsteht, sonst falsch.
$(\exists x) W$ ist wahr gdw. für \textbf{ein} Element aus $e$ aus $\mathcal{D}$, durch Ersetzen der Variablen $x$ durch $e$ eine wahre Formel entsteht, sonst falsch.
\subsection{Begriffe aus der Modelltheorie}
\subsubsection{Modelltheorie}
Inhalt der Modelltheorie sind die Beziehungen zwischen den rein formalen Ausdrücken einer Sprache (syntaktische Ebene) und deren Bedeutung (semantische Ebene). Diese Beziehung wird über sogenannte Interpretationen und eine als Erfüllungsrelation bezeichnete mathematische Relation hergestellt.
Gibt es für eine Formel $F$ eine Interpretation $\mathcal{I}$, die $F$ wahr macht, so heißt $F$ \textbf{erfüllbar} und $\mathcal I$ ein Modell für $F$. \\
Eine Formel $F$ heißt \textbf{gültig}, falls sie in jeder Interpretation wahr ist. Schreibweise $\vDash F$. \\
% TODO ist das wirklich in JEEEEDDDEEEER Interpretation so???
Ist eine Formel $F$ in keiner Interpretation wahr, so nennen wir sie \textbf{unerfüllbar}. \\
Sei $\Gamma$ eine Menge geschlossener Formeln und $F$ eine beliebige geschlossene Formel. $F$ heißt \textbf{logische Konsequenz} von $\Gamma$,
\[
\Gamma \vDash F,
\]
falls für jede Interpretation $\mathcal I$ gilt:
\[
\text{falls } \mathcal I \vDash \Gamma, \text{ dann } \mathcal I \vDash F.
\]
Es gilt damit:
\[
\Gamma \cup \{\lnot F\} \text{ ist unerfüllbar gdw. } \Gamma \vDash F.
\]
Dies impliziert, dass eine Menge an Formeln $\Gamma$ erfüllbar ist gdw. alle Formeln in $\Gamma$ erfüllbar sind.
Daher kann man sich beim Beweis der \textbf{logischen Konsequenz} mit dem Nachweis der entsprechenden \textbf{Unerfüllbarkeit} behelfen.
\begin{example}
Seien in einer Sprache $c_i$ Konstantensymbole, $f_i$ Funktionssymbole, $R_i$ Prädikatensymbole, $x_i$ Variablensymbole.
%
Gegeben seien weiter die Interpretationen $I_1$ und $I_2$:
\begin{tabular}{L L L L l}
I_1: & dom(I_1) & \mapsto & \mathcal N & Domäne der natürlichen Zahlen \\
& c_1 & \mapsto & 0 & Konstantensymbol \\
& f_1^1 & \mapsto & succ & einstelliger Nachfolgerfunktion \\
& R_1^2 & \mapsto & = & zweistelliges Gleichheitsprädikat \\
\\
I_2: & dom(I_1) & \mapsto & \mathcal Q & Domäne der positive rationalen Zahlen \\
& c_1 & \mapsto & 1 & Konstantensymbol \\
& f_1^1 & \mapsto & id & einstellige Identitätsfunktion \\
& R_1^2 & \mapsto & \leq & zweistelliges kleiner-oder-gleich-Prädikat
\end{tabular}
\\
Die Formel
\[
P = (\forall X_1) R_1^2(f_1^1(f_1^1(x_1)), x_1)
\]
bedeutet im Falle der Interpretation
\begin{center}
\begin{tabular}{L l L}
I_1: & für jedes $x \in \mathcal N$ gilt: & succ(succ(x)) = x \\
I_2: & für jedes $x \in \mathcal Q$ gilt: & id(id(x)) \leq x
\end{tabular}
\end{center}
%
Die Aussage $P$ ist
\begin{enumerate}
\item für $I_1$ falsch ($I_1 \nvDash P)$,
\item für $I_2$ dagegen wahr ($I_2 \vDash P)$.
\end{enumerate}
\end{example}
\subsection{Begriffe aus der Beweistheorie}
\subsubsection{Beweistheorie}
ist ein Teilgebiet der mathematischen Logik, das Beweise als formale mathematische Objekte behandelt, was deren Analyse mit mathematischen Techniken ermöglicht. Beweise werden üblicherweise als induktiv definierte Datenstrukturen dargestellt, wie Listen oder Bäume. Diese werden gemäß den Axiomen und Schlussregeln des betrachteten logischen Systems konstruiert. Die Beweistheorie ist von syntaktischer Natur im Gegensatz zur Modelltheorie, die von semantischer Natur ist.
\textbf{Beweisen} ist syntaktisches Folgern
\begin{itemize}
\item in einer Sprache $L$
\item mit vorgegebenen \textbf{Schlussregeln} $R$:
\end{itemize}
\[ \vdash_{L,R}\; := \{(S, s) \, |\, S \subset L, s \in L, S \vdash_{L,R} s\} \]
%
Im logisches Kontext bezeichnet man
\begin{itemize}
\item die Ausgangssätze als \textbf{Axiome},
\item die abgeleiteten Sätze als \textbf{Theoreme},
\item die Ableitungsregeln $R$ als \textbf{Inferenzregeln}.
\end{itemize}
%
\textbf{Ableitungen} sind endliche Folgen
\[ \langle s_1, \dots, s_n\rangle \]
mit
\[ \{s_i \, |\, i < j\} \vdash s_j \]
(für $j \leq n$).
Für jedes Axiom $A$ gilt dann $\emptyset \vdash A$. $S$ stellt unsere bisherige Wissensbasis dar.
In der Logikprogrammierung sind die Axiome üblicherweise \textbf{nicht-logische Hypothesen:}
\begin{itemize}
\item Die Hypothesen drücken Annahmen über den Problembereich aus.
\item Aus den Hypothesen ableitbare Sätze sind \textbf{nicht-logische Theoreme}.
\end{itemize}
%
Probleme, die mit Logikprogrammiersystemen gelöst werden, sind von der Gestalt:
\begin{itemize}
\item Gegeben sei eine Menge $S$ von Annahmen.
\item Gesucht sind Sätze $s$, die syntaktische Konsequenzen dieser Annahmen beschreiben: $S \vdash s$.
\end{itemize}
%
Dabei soll gelten: Falls $S$ die Annahmen \textbf{korrekt} beschreibt, dann drückt $s$ eine Konsequenz ebenfalls korrekt aus.
Was hier \textbf{Korrektheit} bedeutet, legt die intendierte \textbf{Interpretation $\mathcal I$} des Logikprogrammierers fest.
Für $I$ soll gelten:
\[ \text{Falls } I \vDash S \text{ und } S \vdash s, \text{ dann } I \vDash s \]
\subsubsection{Korrektheit der Inferenzregeln}
\[ \Gamma \vdash F \Rightarrow \Gamma \vDash F \]
\parindent 0mm
Korrekte Inferenzregeln sind etwa
\begin{description}
\item[modus ponens:] $B, B \rightarrow A \vdash A$
\item[modus tollens:] $\lnot A, B \rightarrow A \vdash \lnot B$
\end{description}
\subsubsection{Vollständigkeit der Inferenzregeln}
\[ \Gamma \vDash F \Rightarrow \Gamma \vdash F \]
Für korrekte und vollständige Inferenzsysteme fallen syntaktischer und semantischer Ableitungsbegriff zusammen:
\[ \Gamma \vdash F \Leftrightarrow \Gamma \vDash F \]
Der in \textsc{Prolog} verwendete \textbf{Resolutionskalkül}
\begin{itemize}
\item basiert auf nur einer (korrekten) Inferenzregel und
\item ist nur auf Formeln einer speziellen syntaktischen Form, der \textbf{Klauselform}, anwendbar.
\end{itemize}
\subsection{Klausellogik}
Ein \textbf{Literal} ist entweder eine atomare Formel (positives Literal) oder eine negierte atomare Formel (negatives Literal). (Atomare Formel bzw. Atomformeln sind Prädikatensymbolen, angewendet auf ein Tupel von Termen.)
\begin{example}
\[ \text{likes}(chris, mummy), \quad \lnot\text{likes}(chris, suffering) \]
\end{example}
Eine \textbf{Klausel} ist eine Formel der Form $\langle\text{Präfix}\rangle\langle\text{Matrix}\rangle$
\begin{tabular}{l l}
\textbf{Präfix}: & Sequenz von All-Quantifizierungen. \\
\textbf{Matrix}: & Quantorenfreie Konjunktionen von Formeln, \\
& die wiederum nur aus Disjunktionen von Literalen \\
& zusammengesetzt sein dürfen.
\end{tabular}
\begin{example}
\begin{align*}
(\forall x\forall y)( &(\text{likes}(chris, x) \lor \lnot \text{likes(x, logic)})\; \land \\
& \text{likes}(chris, logic)\; \land \\
& \text{likes}(bob, logic)\; \land \\
& (\text{likes}(x,y) \lor \lnot \text{loves}(x, y)))
\end{align*} ist eine
Dies ist eine Menge sogenannter definitver Klauseln.
Lässt man hier die Quantoren weg (implizite All-Quantifizierung), ersetzt $\lor\lnot$ durch \texttt{:-} und schreibt alle Variablen groß, so erhält man ein \textsc{Prolog}-Programm.
\end{example}
Eine \textbf{definite Klausel} enthält genau ein positives Literal und beliebig viele negative Literale.
\section{Suche}
\subsection{Prüfungsfragen}
\begin{description}
\item[Zustandsraum] Baum mit Knoten, die Zustände der Suche beschreiben.
\item[Suche in Zustandsräumen]
\item[Zustandsraumrepräsentationen]
\item[Blinde Suche]
\item[Heuristische Suche]
\item[Vorwärts- und Rückwärtssuche]
\end{description}
\subsection{Zustandsraum}
\begin{itemize}
\item Baum mit Knoten, die Zustände
\item Wurzel ist Startzustand.
\item Es gibt mindestens einen Zielzustand.
\end{itemize}
\subsection{Suche in Zustandsräumen}
\textbf{Die Suchprozedur}
\textbf{Eingabe:}
\begin{enumerate}
\item Startknoten (Plural)
\item Zielknoten (Plural)
\item Funktion, die Nachfolger zu einem Knoten generieren kann (das Erweitern um einen Knoten nennt man expandieren)
\item eventuell Qualitätskriterien
\end{enumerate}
\textbf{Ausgabe:} Den Pfad vom Startzustand zu einem Zielzustand. \\
Der Suchraum besteht zu Beginn des Suchverfahrens nicht. Der Suchraum wächst mit jeder Ebene im Baum exponentiell. Deshalb generiert man den Suchbaum soweit nötig während der Suche. Einerseits ist dies durch den Speicherbedarf und andererseits durch die Berechnung einer Modifikation limitiert. Innere Knoten entsprechen partiellen Lösungen. Blätter im voll expandierten Suchraum sind nicht-expandierbare Knoten.
\textbf{Generische Prozedur zum Lösen von Suchprobleme:}
\begin{enumerate}
\item Sei $L$ die Liste der Startknoten (unser Suchproblem kann daher ein Wald sein) für das Problem (ab jetzt wird $L$ immer die Liste der noch nicht überprüften Knoten darstellen).
\item Ist $L$ leer, so melde einen Fehlschlag. \\
Andernfalls wähle einen Knoten $n$ aus $L$.
\item Stellt $n$ einen Zielknoten dar, so melde Erfolg und liefere den Pfad vom Startknoten zu $n$.
\item Andernfalls ersetze in $L$ den Knoten $n$ durch seine Nachfolgeknoten\\
Markiere dabei die neuen Knoten mit dem jeweils zugehörigen Pfad vom Startknoten. (Markieren kann mit einer sogenannten Closed-List /-Set umgesetzt werden. Knoten werden markiert, indem man sie dort einfügt.)
\item Weiter mit Schritt $2! = 2$.
\end{enumerate}
Das bedeutet: Knoten werden erst beim Expandieren auf Zieleigenschaft überprüft.
Die Art der Wahl in Schritt $2!$ bestimmt die Suchstrategie:
\begin{itemize}
\item \textit{blind:} Wahl allein aufgrund von \textit{Position im Baum} $\rightarrow$ bspw. Tiefen- und Breitensuche.
\item \textit{heuristisch:} Wahl unter \textit{Berücksichtigung der Domäne} $\rightarrow$ bswp. Suchverfahren mit einer Auswahlfunktion die Inhalte der Knoten einfließen lässt.
\end{itemize}
\subsection{Tiefensuche}
\begin{enumerate}
\item Sei $L$ die Liste der Startknoten für das Problem.
\item Ist $L$ leer, so melde einen Fehlschlag. \\
Andernfalls wähle den \textit{ersten} Knoten $n$ aus $L$.
\item Stellt $n$ einen Zielknoten dar, so melde Erfolg und liefere den Pfad vom Startknoten zu $n$.
\item Andernfalls entferne $n$ aus $L$ und füge seine Nachfolgeknoten \textit{am Anfang} von $L$ an. \\
Markiere dabei wieder die neuen Knoten mit dem jeweils zugehörigen Pfad vom Startknoten.
\item Weiter mit Schritt $2!$.
\end{enumerate}
\subsection{Breitensuche}
$\dots$ genau der gleiche Algorithmus wie oben, nur dass man im Schritt 4 die Nachfolgeknoten \textit{am Ende} von $L$ anfügt.
\subsection{Tiefen- vs. Breitensuche, informell}
Suche, die \textit{schnell bei Endzuständen} ankommt ist \textit{speicherökonomisch}:
\begin{indentleft}{1cm}
Allein die Endzustände sorgen für Verkleinerung der Liste $L$ (der momentan gespeicherten Knotenmenge). Denn Eltern, die ausschließlich Endzustände als Kinder besitzen, können verworfen werden.
\end{indentleft}
Daher ist typischerweise Tiefensuche weniger speicherintensiv. Jedoch bestimmt die Form des Suchraums, welche Strategie besser ist.
Breitensuche ist besser, falls:
\begin{enumerate}
\item niedriger Verzweigungsgrad
\item Lösung auf geringer Tiefe
\end{enumerate}
Tiefensuche terminiert nicht, falls es unendlich lange Wurzelpfade gibt (wir beliebig tief expandieren können bzw. der Suchraum unendlich groß ist).
\subsection{Heuristische Suche}
Da wir bei Suchproblemen in der Praxis niemals den vollständigen Suchraum aufstellen, geschweige denn speichern können, benötigen wir eine Funktion, die die Entfernung zum Zielknoten schätzt.
\\
\\
Die heuristische Funktion bestimmt einen möglichst guten als nächsten zu expandierenden Knoten. (Sie nimmt als Eingabe einen Knoten und liefert als Ausgabe einen geschätzten Abstand zum Ziel.)
\\
\\
Beste Heuristik = teuerste Heuristik! (man könnte den gesamten Suchraum zur Bestimmung des optimalen nächsten Knotens bestimmen)
\\
\\
Wir nennen das Berechnen der Heuristikfunktion für alle Knoten im Saum \textit{Meta-level Aktivität} und das Ausführen einer Modifikation \textit{Base-level Aktivität}.
\\
\\
Aufwand auf dem Meta-level muss sich auf dem Base-level bezahlt machen! (Bei blinder Suche ist unser ML-Aufwand $ = 0$.)
\subsection{Vorwärts- und Rückwärtssuche}
Man kann die Suche auch umkehren, sofern die Modifikation umkehrbar und eine Lösung explizit (nicht nur implizit bspw. Kreuzworträtsel) bekannt ist. Wenn der Eingangsgrad größer ist als der Ausgangsgrad, so ist Rückwärtssuche einfacher ($\rightarrow$ man kehrt das Suchproblem um). Dadurch ist die Anzahl der Nachfolger geringer, damit auch die Anzahl an notwendigen Expansionen und auch der Rechenaufwand.
% TODO Prüfen, was damit gemeint ist
Unser Framework ermöglich bis jetzt nur Vorwärtssuche (wir können \textit{nur Nachfolger} generieren).
Abhilfe:
\\
\begin{indentleft}{1cm}
Statt eines \textit{Suchbaums} verwenden wir einen \textit{Suchgraphen} zur Beschreibung des Suchraums.
\end{indentleft}
Mischformen sind ebenfalls möglich: man teilt das Suchproblem in Teilprobleme auf und kann in diesen wahlweise vorwärts oder rückwärts suchen.
\begin{example}
\begin{itemize}
\item Kannibalen und Missionare (zwei Uferseiten und ein Boot. Auf keiner der Seiten dürfen mehr Kannibale sein als Missionare $\rightarrow$ Constraints)
\item Türme von Hanoi (Constraints: man darf immer nur eine Scheibe bewegen. Eine größere darf nicht auf einer kleineren Liegen.)
\item n-Damen-Problem (Damen dürfen sich auf einem $n\times n$-Schachfeld nicht gegenseitig schlagen können)
\item 8-Puzzle
\end{itemize}
\end{example}
$\hookrightarrow$ Constraints verkleinern den Suchraum erheblich!
\subsection{Crux der blinden Suche}
Blinde Suchverfahren sind praktisch nicht einsetzbar. Sie benötigen:
\[ Time(X) = \mathcal O(b^d) \]
Sie müssen im Worst-Case den gesamten Suchraum durchlaufen. Dieser wächst exponentiell.
Daher benötigen wir Verfahren, mit denen wir spezifisch für das gegebene Problem die nächsten zu expandierenden Knoten bewerten können. Die optimale Wahl \textit{sicherzustellen} ist genau so teuer wie \textit{blinde Suche}. Wir suchen daher eine Daumenregel (eine sogenannte Heuristik) zur \textit{Abschätzung} $h$ des echten Abstands $h^*$ zum Ziel.
\begin{example}
8-Puzzle (mit Zahlen). Als Heuristik wählt man die Anzahl an fehlplatzierten Steinen oder die Manhattan-Distanz.
\end{example}
\subsection{Hill Climbing mit Rücksetzen (BTHC)}
\begin{enumerate}
\item Sei $L$ die Liste der Startknoten für das Problem, \textit{sortiert} nach der jeweils geschätzten Distanz $h$ zum ziel.
\item Ist $L$ leer, so melde einen Fehlschlag. \\ Andernfalls wähle den \textit{ersten} Knoten $n$ aus $L$.
\item Stellt $n$ einen Zielknoten dar, so melde Erfolg und liefere den Pfad vom Startknoten zu $n$.
\item Andernfalls entferne $n$ aus $L$ und füge seine Nachfolgeknoten, sortiert nach der jeweils geschätzten Distanz $h$ zum Ziel, \textit{am Anfang} von $L$ an. \\ Markiere dabei die neuen Knoten mit dem jeweils zugehörigen Pfad vom Startknoten.
\item Weiter mit Schritt $2$!
\end{enumerate}
Das ist effektiv Tiefensuche mit einer Heuristik (auch der Speicher- und Zeitbedarf ist vergleichbar). Wir wählen immer das am Besten bewertete Kind und expandieren es. (Eigentlich sortieren wir die Kinder des zuletzt expandierten Knoten nach der Schätzfunktion und fügen sie am Anfang der Openlist $L$ ein.)
\subsection{Striktes Hill Climbing}
\begin{enumerate}
\item Sei $L$ die Liste der Startknoten für das Problem, \textit{sortiert} nach der jeweils geschätzten Distanz $h$ zum Ziel.
\item Ist $L$ leer, so melde einen Fehlschlag. \\ Andernfalls wähle den \textit{ersten} Knoten $n$ aus $L$.
\item Stellt $n$ einen Zielknoten dar, so melde Erfolg und liefere den Pfad vom Startknoten zu $n$.
\item Andernfalls entferne $n$ aus $L$ und füge (nur) den besten Nachfolgeknoten von $n$ (den mit minimaler geschätzter Distanz $h$ zum Ziel) \textit{am Anfang} von $L$ an. \\ Markiere dabei den neuen Knoten mit dem zugehörigen Pfad vom Startknoten.
\item Weiter mit Schritt $2$!
\end{enumerate}
SHC hat \textit{konstanten Speicherbedarf} falls der Ausgangsverzweigungsgrad des Suchbaums beschränkt ist:
\[ \text{Space}(SHC) = \mathcal O(d) \textcolor{gray}{\text{ im Skript steht } \mathcal O(b)} \]
\subsection{Best-First-Suche (BS)}
\begin{enumerate}
\item Sei $L$ die Liste der Startknoten für das Problem.
\item Ist $L$ leer, so melde einen Fehlschlag. \\ Andernfalls wähle denjenigen Knoten $n$ aus $L$, der dem Ziel \textit{schätzungsgemäß am nächsten} ist.
\item Stellt $n$ einen Zielknoten dar, so melde Erfolg und liefere den Pfad vom Startknoten zu $n$.
\item Andernfalls entferne $n$ aus $L$ und füge alle seine Nachfolgeknoten in die Liste $L$ ein. \\ Markiere dabei wieder die neuen Knoten mit dem jeweils zugehörigen Pfad vom Startknoten.
\item Weiter mit Schritt $2$!
\end{enumerate}
Dieses Verfahren betrachtet den gesamten Saum. Wir nehmen aus allen Knoten in der Openlist den vielversprechendsten. BS ist \textit{wesentlich speicherintensiver} als HC, denn die Openlist kann sehr groß werden.
\subsection{Suche als Funktionsmaximierung}
Man kann Suche auch als Funktionsmaximierung sehen.
\begin{center}
\begin{tabular}{l l}
Gegeben: & eine Funktion $f$, die für einen Zustand $p$ dessen \textit{Interessantheit} $f(p)$ misst, \\
gesucht: & das Maximum $\text{max}_p\, f(p)$
\end{tabular}
\end{center}
\subsection{Probleme mit striktem (optimistischem) Hill Climbing}
Bei einem lokalen Maximum, das nicht unserem globalen Maximum (Zielzustand) entspricht gerät das strikte HC in eine Sackgasse ($\rightarrow$ der Algorithmus terminiert mit einem Fehlschlag, da kein BT möglich ist). Das Verlassen des lokalen Maximums setzt voraus, dass wir entgegen der Empfehlung der Heuristik das lokale Maximum verlassen.
Es wäre daher notwendig, den "Horizont zu erweitern". Dies kann einerseits durch einen randomisierten Anteil in der Heuristik oder das vorübergehende einsetzen von Breitensuche realisiert werden. (Hilft auch bei Plateaus. Denn HC würde ohne Heuristik in \text{genau eine} Richtung gehen und alles andere verwerfen. Er läuft damit Gefahr niemals zum Ziel zu kommen.)
Rubik's Cubes sind ein gutes Beispiel für den Einsatz von Makrooperatoren. Es ist sinnvoll mehrere Züge (Drehungen) zu einem Operator zusammenzufassen und diesen als Modifikation zu betrachten (bspw. das Vertauschen zweier Steine).
\subsection{Simulated Annealing}
Ebenfalls HC, wobei man mit einer bestimmten Wahrscheinlichkeit $p$ (proportional zu einer globalen Größe $T$) ein Schritt in eine Richtung unternommen wird, der \textit{keine Minimierung der geschätzten Distanz} $h$ bewirkt. Diese Wahrscheinlichkeit wird mit jeder Iteration langsam reduziert.
$\Rightarrow$ lokale Maxima können wieder verlassen werden (ein hohes initiales $T$ vorausgesetzt)
\section{A-Algorithmus}
$\dots$ die Antwort drauf, dass sowohl HC als auch BS nicht immer \text{eine beste Lösung} finden
\begin{center}
\begin{tabular}{c c c}
\huge Güte einer Lösung & \huge $\thicksim $ & \huge Tiefe im Suchraum \\
& & (je kleiner, desto besser)
\end{tabular}
\end{center}
HC und BS sind gierige Suchverfahren und finden bei einer (einmalig oder partiell) ungenauen Heuristik keine optimale Lösung. Bei einer perfekten Heuristik finden sie die optimale (aber BL- und ML-Aufwand müssen im Verhältnis stehen).
Expandiere den Knoten $n$ zuerst, der \textit{schätzungsgemäß am nächsten} $(h)$ an einem hochliegenden $(d)$ Ziel liegt, d.h. den mit \textit{minimalem} $f(n) := d(n) + h(n)$.
Im Allgemeinen setzt man statt $d$ die Schätzung $g(n)$ der tatsächlichen Kosten $g^*(n)$, die man benötigt, um $n$ zu erreichen.
\pagebreak
\subsection{Der Algorithmus}
\begin{enumerate}
\item Sei $L$ die Liste der Startknoten für das Problem.
\item Ist $L$ leer, so melde einen Fehlschlag. \\ Andernfalls wähle denjenigen Knoten $n$ aus $L$, für den \\
\[ f(n) = g(n) + h(n) \]
\textit{minimal} ist.
\item Stellt $n$ einen Zielknoten dar, so melde Erfolg und liefere den Pfad vom Startknoten zu $n$.
\item Andernfalls entferne $n$ aus $L$ und füge alle seine Nachfolgeknoten in die Liste $L$ ein. Markiere dabei die neuen Knoten mit dem jeweils zugehörigen Pfad vom Startknoten.
\item Weiter mit Schritt $2$!
\end{enumerate}
Im Prinzip Best-First Suche mit $f$ statt $h$.
\subsection{Der $A^*$-Algorithmus}
$h$ ist \textit{optimistisch} (zulässig), falls: \qquad $\forall n: h(n) \leq h^*(n)$\\
(falls also nicht überschätzt wird)
\large Der $A$-Algorithmus wird für zulässiges $h$ zum $A^*$-Algorithmus!
\normalsize
\subsubsection{Eigenschaften des $A^*$-Algorithmus}
\begin{figure}
\begin{center}
\includegraphics[width=8cm]{a_stern_argument_grafik.jpg}
\end{center}
\caption{$A^*$-Algorithmus findet immer das Optimum}
\end{figure}
Je tiefer der Pfad, desto größer wird $f(n) = g(n) + h(n)$, da $g(n)$ überschätzt und $h(n)$ unterschätzt. Also sind die geschätzten Kosten am Anfang immer geringer als die tatsächlichen Kosten am Ende des Pfades. Somit kann ein gefundener Zielpfad nur der Beste sein, denn gäbe es einen noch besseren Pfad, so wäre dessen Schätzung $h$ noch besser gewesen und wir hätten an irgendeinem Punkt in diese Richtung exploriert und somit den suboptimalen Zielpfad nie gefunden.
Falls gilt:
\begin{enumerate}
\item $h_1$ und $h_2$ sind zulässig und
\item $\forall n: h_1(n) \leq h_2(n)$,
\end{enumerate}
dann \textit{exploriert} $A^*$ mit $h_2$ \textit{weniger Knoten} als mit $h_1$; $h_2$ hat dann \textit{mehr Information} als $h_1$.
\subsubsection{Zulässige Schätzfunktionen}
% einfach abtippeln
\begin{itemize}
\item $\forall n: h(n) = 0 \Rightarrow$ \\ $A*$ entartet zu Breitensuche falls $\forall n: g(n) > 0$.
\item Es kann \textit{keine zulässige} Schätzfunktion geben, die \textit{Tiefensuche} realisiert \\ (denn DF findet nicht immer das Optimum).
\item $\forall n: h(n) = h^*(n) \Rightarrow$ \\ \textit{perfekte Heuristik}, aber schwer zu bekommen$\dots$
\item Bei \textit{endlichen Suchräumen} wird jede Schätzfunktion zulässig durch Division mit einer hinreichend großen Zahl $n$ (z.B. mit $n :=$ \# Knoten im Suchbaum)
\begin{itemize}
\item es sollte möglichst gelten $n \approx 1$ \\ (um eine möglichst gute Schätzung $h$ von $h^*$ zu bekommen)
\item wie geeignetes $n$ finden und \\ was wird die so gewonnene Schätzfunktion taugen? $\rightarrow$ auch wenn sie schlecht ist, ist sie immer noch besser als eine Unzulässige.
\end{itemize}
\end{itemize}
\subsection{Branch \& Bound}
\textbf{Wurzelpfad:}
\[ \langle n_0, \dots, n_k \rangle \]
vom Startknoten $n_0$ zum Knoten $n_k$ und
\[ c(n_i \rightarrow n_{i+1}) := \text{ Kosten für die Kante } n_i \rightarrow n_{i+1} \]
setzen:
\[ g(n_k) := \sum^{k-1}_{i=0} c(n_i \rightarrow n_{i+1}) \]
Setzt man außerdem
\[ \forall n: h(n) = 0 \]
so wird aus dem $A^*$-Algorithmus die Suchprozedur \textit{Branch \& Bound}. Das heißt es nicht Breitensuche, denn wir explorieren immer den Weg, der in Summe die wenigsten Kosten $g(n)$ hat.
\subsection{Der $A^*$-Algorithmus auf Graphen}
Was ist neu im Vergleich zum normalen $A^*$-Algorithmus?
\begin{enumerate}
\item Initialisiere $L$ (die \textit{open list}) mit dem Startknoten $s$ für das Problem: $L := \{s\}$.
\item \color{red} Initialisiere die \textit{closed list} $C$ mit $\emptyset$ und erzeuge einen Explorationsgraphen $G$, der nur $s$ enthält. \color{black}
\item Ist $L$ leer, so melde einen Fehlschlag.
\item Andernfalls wähle denjenigen Knoten $n$ aus $L$, für den
\[ f(n) = g(n) + h(n) \]
\textit{minimal} ist \color{red} (dabei bezeichne $g(n)$ die Kosten des günstigsten Pfads vom Startknoten $s$ zu $n$, der bis jetzt gefunden wurde), \\
entferne $n$ aus $L$ und trage $n$ in $C$ ein. \color{black}
\item Stellt $n$ einen Zielknoten dar, so melde Erfolg und liefere den Pfad vom Startknoten zu $n$. \textcolor{gray}{Man verfolgt die in $G$ vorhandenen Elternzeiger von $n$ nach $s$ und liefert den Pfad zurück.}
\item \color{red} Andernfalls expandiere $n$ durch Generieren derjenigen seiner Nachfolger die nicht schon Vorgänger von $n$ in $G$ sind und \\ installiere die Knoten aus der so generierten Menge $M$ als Kinder von $n$ in $G$ (Nachfolgeknoten).
\item Etabliere in $G$ für alle neuen Knoten aus $M$ (also solche, die nicht schon in $L$ oder $C$ enthalten sind), einen Elternzeiger auf $n$ und füge die neuen Knoten aus $M$ in die Liste $L$ ein.
\item Entscheide für jeden alten Knoten $m$ aus $M$, ob sein Elternzeiger auf $n$ geändert werden muss, weil der aktuell betrachtete Wurzelpfad von $m$ (mit dem Vater $n$) billiger als der zum alten Elternzeiger von $m$ gehörende Vater ist (Kostenkorrektur). \\ Verfahre entsprechend für die Nachkommen derjenigen alten Knoten aus $m$, die schon in $C$ lagen und gerade eine Kostenkorrektur erfahren haben (rekursive Propagierung der Kostenkorrektur).
\item Weiter mit Schritt $3$!
\end{enumerate}
Anmerkungen zum Algorithmus:
\begin{itemize}
\item Der Algorithmus entwickelt in $G$ eine Graphen-Repräsentation ($\rightarrow$ Explorationsgraph)
\item $G$ enthält einen ausgezeichneten Untergraphen $T$, den sogenannten \textit{Explorationsbaum}
\item $T$ enthält die gleichen Knoten wie $G$ und ist durch die Elternzeiger aus Schritt $8$ definiert.
\item $G$ enthält also alle soweit entdeckten Pfade von $s$ zu einem beliebigen Knoten $n \in L \cup C$, wobei jeweils einer dieser Pfade (nämlich genau der mit den geringsten akkumulierten $g$-Kosten) durch die Elternzeiger in $G$ ausgezeichnet wird.
\item Wendet man diesen Algorithmus auf einen Baum an, so kann man sich natürlich die closed list $C$ und die Verwaltung der Elternzeiger sparen.
\end{itemize}
\begin{lemma}
Der $A^*$-Algorithmus auf Graphen terminiert für endliche Graphen.
\end{lemma}
\begin{lemma}
Wenn es überhaupt eine erreichbare Lösung gibt,
so existiert auf der Open-List $L$ zu jedem Zeitpunkt, bevor der $A^*$-Algorithmus terminiert, ein Knoten $n'$, der sich
\begin{enumerate}
\item auf einem optimalen Pfad vom Startknoten $s$ zu einem besten Zielknoten befindet und für den gilt:
\item $f(n') \leq f^*(s)$
\end{enumerate}
\end{lemma}
\begin{corollary}
Falls es einen Pfad vom Startknoten $s$ zu einem Zielknoten gibt, so terminiert der $A^*$-Algorithmus (auch für unendliche Graphen).
\end{corollary}
\begin{corollary}
Existiert überhaupt eine (erreichbare) Lösung so wird jeder Knoten $n$ auf $L$, für den
\[ f(n) < f^*(s) \]
gilt schließlich zur Expansion durch den $A^*$-Algorithmus ausgewählt.
\end{corollary}
\begin{corollary}
Wenn überhaupt eine (von $s$ erreichbare) Lösung existiert so gilt für jeden von $A^*$ zur Expansion ausgewählten Knoten $n$:
\[ f(n) \leq f^*(s) \]
\end{corollary}
\begin{definition}
Eine heuristische Funktion $h$ erfüllt die sogenannte \textit{Monotoniebeschränkung}, wenn für jede Kante $n_i \rightarrow n_j$ mit Kosten $c(n_i \rightarrow n_j)$ des Suchraums
\[ h(n_i) - h(n_j) \leq c(n_i \rightarrow n_j)\]
(und außerdem $h(t) = 0$ für alle Zielknoten $t$ gilt.)
$\Rightarrow$ Je näher wir ans Ziel kommen, desto geringer wird die geschätzte Entfernung zum Ziel. Aber die Differenz der beiden Abschätzungen ist geringer als die Kosten der Modifikation.
\end{definition}
\begin{lemma}
Erfüllt $h$ die Monotoniebeschränkung, so ist $h$ schon zulässig.
\end{lemma}
\begin{lemma}
Erfüllt $h$ die Monotoniebeschränkung, so ist $f$ auf Wurzelpfaden monoton steigend, d.h. für jede Kante $n_i \rightarrow n_j$ des Suchraums gilt:
\[ f(n_i) \leq f(n_j) \]
\end{lemma}
\begin{theorem}
Erfüllt die Schätzfunktion $h$ die Monotoniebeschränkung, dann hat der $A^*$-Algorithmus immer schon einen optimalen Pfad für jeden Knoten $n$ gefunden, den er zur Expansion auswählt (es gilt dann also $g(n) = g^*(n)$).
Also muss der $A^*$-Algorithmus weder Kosten noch irgendwelche Elternzeiger in $G$ aktualisieren.
\end{theorem}
\begin{theorem}
Erfüllt $h$ die Monotoniebeschränkung, so ist die Folge der $f$-Schätzwerte zu den Knoten, die vom $A^*$-Algorithmus während der Suche der Reihe nach expandiert werden, monoton steigend.
\end{theorem}
\subsection{Iterative Deepening $A^*$}
Wir legen eine maximale Suchtiefe $c$ fest, die wir immer dann erhöhen, wenn die Open-List leer ist. Wir nehmen immer nur Knoten mit $f(n) \leq c$ in die Open-List auf, wodurch diese klein gehalten wird.
\begin{description}
\item[Speicherbedarf] $\mathcal O(d)$.
\item[Expandiert] genau die gleichen Knoten wie $A^*$.
\item[Optimale Lösung] wird wie bei $A^*$ immer gefunden (wenn diese erreichbar und $h$ zulässig ist).
\end{description}