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 From 5c98f91bd4bc2b88c5ee0c746951c91f38963459 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Sun, 1 Aug 2021 14:19:47 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 57 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 55 insertions(+), 2 deletions(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 6307f55..557d179 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -34,14 +34,67 @@ 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. $n$ ist hierbei die "Grösse" des Problems. +\subsection{Unterschiedliche Anzahl von Quellen und Zielen +\label{munkres:subsection:malorum}} +Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt. Das ist z.B dann der Fall, wenn eine 3 Mitarbeiter 4 Eignungstests abdsolvieren müssen. In diesem Fall wird in der Ungarischen Methode die Matrix künstlich mittels einer Dummy Position quadratisch ergänzt. Dummy-Positionen werden dann mit der größten vorhandenen Zahl aus der Matrix besetzt. Beispielsweise eine $4\times 3$ wird zu einer $4\times 4$ Matrix. + \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. +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{enumerate} +\item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei +allen anderen Ziffern in der jeweiligen Zeile subtrahiert. + +\item Danach zieht man wiederum die kleinste Zahl in jeder Spalte von allen +Zahlen in der Spalte ab. + +\item Es sollen möglichst viele Nullen markiert werden, welche freistehend sind. +(Freistehend bedeutet, sowohl in der jeweiligen Zeile und Spalte nur +eine markierte Null zu haben) + +\item Jeweilige Zeilen eruieren, bei welchen keine markierte Null vorhanden sind und kennzeichnen. + +\item In der vorherigen Zeile die 0 eruieren und die Spalte ebenfalls +kennzeichnen (*2) + +\item Im der selben Spalte die Markierte Null eruieren und die dazugehörige +Zeile kennzeichnen (*3) + +\item Alle Zeilen durchstreichen, welche KEINE Kennzeichnungen (*) haben + +\item Alle Spalten durchstreichen, welche EINE Kennzeichnung besitzt! (hier, *2) + +\item Kleinste Ziffer auswählen, welche nicht schon durchgestrichen sind. +(Im Beispiel ist es die Zahl 1. (Egal welche 1) + +\item Die eruierte kleinste Ziffer, wird von den nicht durchgestrichenen Ziffern +subtrahiert. Danach muss die Matrix wieder komplettiert werden. (inkl. Unterstreichen) + +\item Jeweilige Zahlen eruieren, welche vorgängig doppelt durchgestrichen wurden. + +\item Kleinste eruierte Ziffer von vorhin auf die zwei markierten Ziffern addieren. + +\item Es sollen wiederum von neuem möglichst viele Nullen markiert werden, +welche freistehend sind. In diesem Schritt werden nur die markierten Nullen betrachtet. + +\item Aus allen markierten Nullen in eine eins umwandeln. + +\item Die restlichen Ziffern, durch eine Null ersetzen. + +\item Zu guter letzt soll überall wo eine 1 steht, in der Ausgangsmatrix die +dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen ergeben sich nach Summieren der Zahlen der minimalste Transportweg. +\end{enumerate} \begin{figure} \centering -\includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres} +\includegraphics[width=14cm]{papers/munkres/figures/Ungarische Methode Beispiel} \caption{Händisches Beispiel des Munkres Algorithmus.} \label{munkres:Vr2} \end{figure} -- cgit v1.2.1 From 65966d22f384fa01a8db10b7fd47857efde92a81 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:06:30 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 557d179..7faf958 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -94,7 +94,7 @@ dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen \begin{figure} \centering -\includegraphics[width=14cm]{papers/munkres/figures/Ungarische Methode Beispiel} +\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel} \caption{Händisches Beispiel des Munkres Algorithmus.} \label{munkres:Vr2} \end{figure} -- cgit v1.2.1 From a8df39c46bc2ac0e92fc36d14d9d320d748bdf70 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:37:31 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 22 ++++++++++++++++++++-- 1 file changed, 20 insertions(+), 2 deletions(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 7faf958..6dadf32 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -94,7 +94,25 @@ dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen \begin{figure} \centering -\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel} -\caption{Händisches Beispiel des Munkres Algorithmus.} +\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel.png} +\caption{Händisches Beispiel des Munkres Algorithmus, minimalster Transportweg.} \label{munkres:Vr2} \end{figure} + +\subsection{Zuordnung der Kräne +\label{munkres:subsection:malorum}} + +\begin{itemize} +\item Der Kran von Baustelle A1 soll zur Baustelle B2. +\item Der Kran von Baustelle A2 soll zur Baustelle B3. +\item Der Kran von Baustelle A3 soll zur Baustelle B4. +\item Der Kran von Baustelle A4 soll zur Baustelle B1. +\end{itemize} + +\begin{figure} +\centering +\includegraphics[width=3cm]{papers/munkres/figures/Ungarische Methode Beispiel Zuweisung.png} +\caption{Händisches Beispiel des Munkres Algorithmus, Zuweisung der Kräne } +\label{munkres:Vr2} +\end{figure} + -- cgit v1.2.1 From cbd9a9d63f0dfcd3141a9a420dac959e554f9b57 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:49:47 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 6dadf32..874baae 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -111,7 +111,7 @@ dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen \begin{figure} \centering -\includegraphics[width=3cm]{papers/munkres/figures/Ungarische Methode Beispiel Zuweisung.png} +\includegraphics[width=3cm]{papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png} \caption{Händisches Beispiel des Munkres Algorithmus, Zuweisung der Kräne } \label{munkres:Vr2} \end{figure} -- cgit v1.2.1