From 6c2ea74f867d898626e5ef25c61814cd2aa49bbd Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Marc=20K=C3=BChne?= <kuehnee@Marcs-MacBook-Pro.local>
Date: Sat, 31 Jul 2021 11:57:23 +0200
Subject: neue version

---
 buch/papers/munkres/teil3.tex | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

(limited to 'buch/papers/munkres/teil3.tex')

diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex
index cd47c92..6307f55 100644
--- a/buch/papers/munkres/teil3.tex
+++ b/buch/papers/munkres/teil3.tex
@@ -7,7 +7,7 @@
 \label{munkres:section:teil3}}
 \rhead{Der Munkres-Algorithmus (Ungarische Methode)}
 
-Mit der ungarischen Methode können also lineare Optimierungsprobleme gelöst
+Mit der ungarischen Methode können also Optimierungsprobleme gelöst
 werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen.
 Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so
 optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der
@@ -29,15 +29,16 @@ um eine  $O(n^3)$-Laufzeit zu erreichen.
 
 \subsection{Besondere Leistung der Ungarischen Methode
 \label{munkres:subsection:malorum}}
-Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem
+Die Ungarische Methode ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem
 in polynomieller Zeit löst.
 Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms
-wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert.
-
+wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei die "Grösse" des Problems.
 
 \subsection{Beispiel eines händischen Verfahrens
 \label{munkres:subsection:malorum}}
 
+Die ungarische Methode kann in einem einfachen händischen Beispiel
erläutert werden. Es gibt eine Ausgangsmatrix. Diese Matrix wird in mehreren Schritten immer
weiter reduziert. Anschließend erfolgen mehrere Zuordnungen. Hierbei ist zu beachten, dass
jede Zeile und jede Spalte immer genau eine eindeutige Zuordnung ergibt.
Die optimale Lösung ist erreicht, wenn genau $n$ Zuordnungen gefunden
sind.
+
 \begin{figure}
 \centering
 \includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres}
-- 
cgit v1.2.1

