From cecdcdb230662af594ce68715c61f1263bff9ace Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 26 Jul 2021 07:57:58 +0200 Subject: add munkres files --- buch/papers/munkres/teil3.tex | 124 ++++++++++++++++++++++++++++++++---------- 1 file changed, 94 insertions(+), 30 deletions(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index b67ad74..806cd83 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -3,38 +3,102 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Teil 3 +\section{Der Algorithmus in Form von bipartiten Graphen \label{munkres:section:teil3}} -\rhead{Teil 3} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? +\rhead{Der Algorithmus in Form von bipartiten Graphen} +Mit der ungarischen Methode können also lineare Optimierungsprobleme +gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen +entstehen. -\subsection{De finibus bonorum et malorum +Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen +so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der +Gesamtgewinn maximiert werden kann. + +Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen +zwischen den Elementen zweier Mengen. +Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen» + +\subsection{Beweis, dass der Algorithmus Fortschritte macht +\label{munkres:subsection:malorum}} +Wir müssen zeigen, dass der Algorithmus, solange das Matching nicht +die maximal mögliche Größe hat, immer in der Lage ist, Fortschritte +zu machen --- das heißt, entweder die Anzahl der übereinstimmenden +Kanten zu erhöhen oder mindestens eine Kante zu straffen. +Es genügt zu zeigen, dass bei jedem Schritt mindestens eine der +folgenden Bedingungen erfüllt ist: + +\begin{itemize} +\item +$M$ die maximal mögliche Größe. +\item +$Gy$ enthält einen Erweiterungspfad. +\item +$G$ enthält einen losen Pfad: einen Pfad von einem Knoten in $Rs$ +zu einem Knoten in $T$ / $Z$ die aus einer beliebigen Anzahl von +festen Kanten, gefolgt von einer einzelnen losen Kante, besteht. +Die freie Kante einer freien Bahn ist also $Z$ (beinhaltet $T$), +so garantiert es, dass Delta gut definiert ist. +\end{itemize} +Wenn $M$ die maximal mögliche Größe hat, sind wir natürlich fertig. +Andernfalls muss es nach Berges Lemma im zugrundeliegenden Graphen +$G$ einen Augmentierungspfad $P$ in Bezug auf $M$ geben. +Dieser Pfad darf jedoch nicht in $G_y$ existieren: Obwohl jede +geradzahlige Kante in $P$ durch die Definition von $M$ fest ist, +können ungeradzahlige Kanten lose sein und in $G_y$ fehlen. +Ein Endpunkt von $P$ liegt in $R_{S}$, der andere in $R_T$; w.l.o.g., +nehmen Sie an, es beginnt in $R_{S}$. +Wenn jede Kante von $P$ dicht ist, dann bleibt sie ein augmentierender +Pfad in $G_y$ und wir sind fertig. +Andernfalls sei $uv$ die erste lose Kante auf $P$. +Wenn $v$ kein Element von $Z$ ist, dann haben wir einen losen Pfad +gefunden und sind fertig. +Andernfalls ist $v$ von irgendeinem anderen Pfad $Q$ aus festen +Kanten von einem Knoten in $R_{S}$ erreichbar. +Sei $P_{v}$ der Teilpfad von $P$, der bei $v$ beginnt und bis zum +Ende reicht, und sei $P'$ der Pfad, der gebildet wird, indem man +entlang $Q$ gebildet wird, bis ein Scheitelpunkt auf $P_{v}$ erreicht +wird, und dann weiter bis zum Ende von $P_{v}$. +Beachten Sie, dass $P'$ ein erweiternder Pfad in $G$ mit mindestens +einer losen Kante weniger als $P$ ist. +$P$ kann durch $P'$ ersetzt und dieser Argumentationsprozess iteriert +werden (formal, unter Verwendung von Induktion auf die Anzahl der +losen Kanten), bis entweder ein erweiternder Pfad in $G_y$ oder ein +losender Pfad in $G$ gefunden wird. + +\subsection{Beweis, dass die Anpassung des Potentials $y$ $M$ unverändert lässt \label{munkres:subsection:malorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. +Um zu zeigen, dass jede Kante in $M$ nach der Anpassung von $y$ +erhalten bleibt, genügt es zu zeigen, dass für eine beliebige Kante +in $M$ entweder beide Endpunkte oder keiner von ihnen in $Z$ liegen. +Zu diesem Zweck sei $vu$ eine Kante in $M$ von $T$ nach $S$. +Es ist leicht zu sehen, dass wenn $v$ in $Z$ ist, dann muss auch +$u$ in $Z$ sein, da jede Kante in $M$ dicht ist. +Nehmen wir nun an, dass $u$ kein Element von $Z$ und auch $v$ kein +Element von $Z$ ist. +$u$ selbst kann nicht in $R_{S}$ sein, da es der Endpunkt einer +angepassten Kante ist, also muss es einen gerichteten Pfad von engen +Kanten von einem Knoten in $R_{S}$ zu $u$ geben. +Dieser Pfad muss $v$ vermeiden, da es per Annahme nicht in $Z$ ist, +also ist der Knoten, der $u$ in diesem Pfad unmittelbar vorausgeht, +ein anderer Knoten $v$ (ein Element von $T$) und $v$ ein Element +von $u$ ist eine enge Kante von $T$ nach $S$ und ist somit in $M$. +Aber dann enthält $M$ zwei Kanten, die den Knoten $u$ teilen, was +der Tatsache widerspricht, dass $M$ ein Matching ist. +Jede Kante in $M$ hat also entweder beide Endpunkte oder keinen +Endpunkt in $Z$. +\subsection{Beweis, dass $y$ ein Potential bleibt +\label{munkres:subsection:malorum}} +Um zu zeigen, dass y nach der Anpassung ein Potenzial bleibt, genügt +es zu zeigen, dass keine Kante ihr Gesamtpotenzial über ihre Kosten +hinaus erhöht. +Dies ist für Kanten in $M$ bereits durch den vorangegangenen Absatz +bewiesen. +Man betrachtet also eine beliebige Kante $uv$ von $S$ nach $T$. +Wenn $y(u)$ erhöht wird um $\Delta$, dann wird entweder $v\in +\mathbb{Z}_n$ in diesem Fall wird $y(v)$ verringert um $\Delta$, +wobei das Gesamtpotenzial der Kante unverändert bleibt, oder $v\in +T\setminus Z$, wobei die Definition von $\Delta$ garantiert, dass +$y(u)+y(v)+\Delta \le c(u,v)$ +Also $y$ bleibt ein Potential. -- cgit v1.2.1 From 4f9cf26c7802a163da6b18cec9db62e75a9730cb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Tue, 27 Jul 2021 12:30:10 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 122 +++++++++++------------------------------- 1 file changed, 32 insertions(+), 90 deletions(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 806cd83..cd47c92 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -3,102 +3,44 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Der Algorithmus in Form von bipartiten Graphen +\section{Der Munkres-Algorithmus (Ungarische Methode) \label{munkres:section:teil3}} -\rhead{Der Algorithmus in Form von bipartiten Graphen} -Mit der ungarischen Methode können also lineare Optimierungsprobleme -gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen -entstehen. +\rhead{Der Munkres-Algorithmus (Ungarische Methode)} -Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen -so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der -Gesamtgewinn maximiert werden kann. +Mit der ungarischen Methode können also lineare 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 +Gesamtgewinn maximiert werden kann. -Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen -zwischen den Elementen zweier Mengen. -Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen» - -\subsection{Beweis, dass der Algorithmus Fortschritte macht +\subsection{Geschichte \label{munkres:subsection:malorum}} -Wir müssen zeigen, dass der Algorithmus, solange das Matching nicht -die maximal mögliche Größe hat, immer in der Lage ist, Fortschritte -zu machen --- das heißt, entweder die Anzahl der übereinstimmenden -Kanten zu erhöhen oder mindestens eine Kante zu straffen. -Es genügt zu zeigen, dass bei jedem Schritt mindestens eine der -folgenden Bedingungen erfüllt ist: - -\begin{itemize} -\item -$M$ die maximal mögliche Größe. -\item -$Gy$ enthält einen Erweiterungspfad. -\item -$G$ enthält einen losen Pfad: einen Pfad von einem Knoten in $Rs$ -zu einem Knoten in $T$ / $Z$ die aus einer beliebigen Anzahl von -festen Kanten, gefolgt von einer einzelnen losen Kante, besteht. -Die freie Kante einer freien Bahn ist also $Z$ (beinhaltet $T$), -so garantiert es, dass Delta gut definiert ist. -\end{itemize} -Wenn $M$ die maximal mögliche Größe hat, sind wir natürlich fertig. -Andernfalls muss es nach Berges Lemma im zugrundeliegenden Graphen -$G$ einen Augmentierungspfad $P$ in Bezug auf $M$ geben. -Dieser Pfad darf jedoch nicht in $G_y$ existieren: Obwohl jede -geradzahlige Kante in $P$ durch die Definition von $M$ fest ist, -können ungeradzahlige Kanten lose sein und in $G_y$ fehlen. -Ein Endpunkt von $P$ liegt in $R_{S}$, der andere in $R_T$; w.l.o.g., -nehmen Sie an, es beginnt in $R_{S}$. -Wenn jede Kante von $P$ dicht ist, dann bleibt sie ein augmentierender -Pfad in $G_y$ und wir sind fertig. -Andernfalls sei $uv$ die erste lose Kante auf $P$. -Wenn $v$ kein Element von $Z$ ist, dann haben wir einen losen Pfad -gefunden und sind fertig. -Andernfalls ist $v$ von irgendeinem anderen Pfad $Q$ aus festen -Kanten von einem Knoten in $R_{S}$ erreichbar. -Sei $P_{v}$ der Teilpfad von $P$, der bei $v$ beginnt und bis zum -Ende reicht, und sei $P'$ der Pfad, der gebildet wird, indem man -entlang $Q$ gebildet wird, bis ein Scheitelpunkt auf $P_{v}$ erreicht -wird, und dann weiter bis zum Ende von $P_{v}$. -Beachten Sie, dass $P'$ ein erweiternder Pfad in $G$ mit mindestens -einer losen Kante weniger als $P$ ist. -$P$ kann durch $P'$ ersetzt und dieser Argumentationsprozess iteriert -werden (formal, unter Verwendung von Induktion auf die Anzahl der -losen Kanten), bis entweder ein erweiternder Pfad in $G_y$ oder ein -losender Pfad in $G$ gefunden wird. +Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht. +Der Name ``Ungarische Methode'' ergab sich, weil der Algorithmus +weitestgehend auf den früheren Arbeiten zweier ungarischer Mathematiker +basierte: Dénes Kőnig und Jenő Egerváry. +James Munkres überprüfte den Algorithmus im Jahr 1957 und stellte fest, +dass der Algorithmus (stark) polynomiell ist. +Seitdem ist der Algorithmus auch als Kuhn-Munkres oder +Munkres-Zuordnungsalgorithmus bekannt. +Die Zeitkomplexität des ursprünglichen Algorithmus war $O(n^4)$, +später wurde zudem festgestellt, dass er modifiziert werden kann, +um eine $O(n^3)$-Laufzeit zu erreichen. -\subsection{Beweis, dass die Anpassung des Potentials $y$ $M$ unverändert lässt +\subsection{Besondere Leistung der Ungarischen Methode \label{munkres:subsection:malorum}} -Um zu zeigen, dass jede Kante in $M$ nach der Anpassung von $y$ -erhalten bleibt, genügt es zu zeigen, dass für eine beliebige Kante -in $M$ entweder beide Endpunkte oder keiner von ihnen in $Z$ liegen. -Zu diesem Zweck sei $vu$ eine Kante in $M$ von $T$ nach $S$. -Es ist leicht zu sehen, dass wenn $v$ in $Z$ ist, dann muss auch -$u$ in $Z$ sein, da jede Kante in $M$ dicht ist. -Nehmen wir nun an, dass $u$ kein Element von $Z$ und auch $v$ kein -Element von $Z$ ist. -$u$ selbst kann nicht in $R_{S}$ sein, da es der Endpunkt einer -angepassten Kante ist, also muss es einen gerichteten Pfad von engen -Kanten von einem Knoten in $R_{S}$ zu $u$ geben. -Dieser Pfad muss $v$ vermeiden, da es per Annahme nicht in $Z$ ist, -also ist der Knoten, der $u$ in diesem Pfad unmittelbar vorausgeht, -ein anderer Knoten $v$ (ein Element von $T$) und $v$ ein Element -von $u$ ist eine enge Kante von $T$ nach $S$ und ist somit in $M$. -Aber dann enthält $M$ zwei Kanten, die den Knoten $u$ teilen, was -der Tatsache widerspricht, dass $M$ ein Matching ist. -Jede Kante in $M$ hat also entweder beide Endpunkte oder keinen -Endpunkt in $Z$. +Es 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. + -\subsection{Beweis, dass $y$ ein Potential bleibt +\subsection{Beispiel eines händischen Verfahrens \label{munkres:subsection:malorum}} -Um zu zeigen, dass y nach der Anpassung ein Potenzial bleibt, genügt -es zu zeigen, dass keine Kante ihr Gesamtpotenzial über ihre Kosten -hinaus erhöht. -Dies ist für Kanten in $M$ bereits durch den vorangegangenen Absatz -bewiesen. -Man betrachtet also eine beliebige Kante $uv$ von $S$ nach $T$. -Wenn $y(u)$ erhöht wird um $\Delta$, dann wird entweder $v\in -\mathbb{Z}_n$ in diesem Fall wird $y(v)$ verringert um $\Delta$, -wobei das Gesamtpotenzial der Kante unverändert bleibt, oder $v\in -T\setminus Z$, wobei die Definition von $\Delta$ garantiert, dass -$y(u)+y(v)+\Delta \le c(u,v)$ -Also $y$ bleibt ein Potential. +\begin{figure} +\centering +\includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres} +\caption{Händisches Beispiel des Munkres Algorithmus.} +\label{munkres:Vr2} +\end{figure} -- cgit v1.2.1 From 6c2ea74f867d898626e5ef25c61814cd2aa49bbd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= 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