diff options
author | JODBaer <JODBaer@github.com> | 2021-07-26 14:15:57 +0200 |
---|---|---|
committer | JODBaer <JODBaer@github.com> | 2021-07-26 14:15:57 +0200 |
commit | 9356db2fc0d95e60043c6ce62fa906964869cae2 (patch) | |
tree | f3cf93ea263d777c2396ee5e21369ec99868d53b /buch/papers/munkres/teil1.tex | |
parent | update (diff) | |
parent | Merge pull request #45 from NaoPross/master (diff) | |
download | SeminarMatrizen-9356db2fc0d95e60043c6ce62fa906964869cae2.tar.gz SeminarMatrizen-9356db2fc0d95e60043c6ce62fa906964869cae2.zip |
Merge commit '56443dfc2486e08b0ed3bf8ecc61c9ad8a83e213' into Baer
Diffstat (limited to '')
-rw-r--r-- | buch/papers/munkres/teil1.tex | 62 |
1 files changed, 14 insertions, 48 deletions
diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index f4f5e39..7cbbbfd 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -3,53 +3,19 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Teil 1 +\section{Was ist die ungarische Methode? \label{munkres:section:teil1}} \rhead{Problemstellung} -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 -\begin{equation} -\int_a^b x^2\, dx -= -\left[ \frac13 x^3 \right]_a^b -= -\frac{b^3-a^3}3. -\label{munkres:equation1} -\end{equation} -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? - -\subsection{De finibus bonorum et malorum -\label{munkres:subsection:finibus}} -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 \eqref{000tempmlate:equation1}. - -Et harum quidem rerum facilis est et expedita distinctio -\ref{munkres:section:loesung}. -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 -\ref{munkres:section:folgerung}. -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. - - +Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem +in polynomieller Zeit löst. +\begin{itemize} +\item +Polynom = vielgliedrig +\end{itemize} +Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms +wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. +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. |