Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » lexikographisch kleinsten Pfad in einer Matrix finden
Autor
Universität/Hochschule J lexikographisch kleinsten Pfad in einer Matrix finden
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 253
  Themenstart: 2022-01-28

Hallo, Hier ist ein wie ich finde kniffliges algorithmisches Problem: Gegeben ist eine \(M \times N\) Matrix, die jede Zahl von \(1\) bis \(M \cdot N\) genau einmal enthält. Man startet in der oberen linken Ecke und muss zur unteren rechten Ecke gelangen, indem man immer entweder ein Feld nach unten oder nach Rechts läuft. Jeder so entstandene Pfad muss dann der größe nach aufsteigend sortiert werden. Es wird nach dem Pfad gesucht, der - nachdem er sortiert wurde - lexikographisch am kleinsten ist. Lexikographisch meint hier die konkatenation der einzelnen Zahlen als Stringfolge betrachtet. Also \(1,2,4\) ist als "Eins Zwei Vier" zu lesen.


   Profil
Kitaktus
Senior Letzter Besuch: im letzten Monat
Dabei seit: 11.09.2008
Mitteilungen: 6954
Wohnort: Niedersachsen
  Beitrag No.1, eingetragen 2022-01-28

Das Problem ist trivial. Wenn alle Zahlen verschieden sind, kann man mit einem ganz einfachen Greedy-Verfahren diesen Weg bestimmen: Wähle immer von den (maximal zwei) möglichen Nachfolgern den kleineren aus. Beweis: Sei P der so bestimmte Weg. Sei Q irgend ein anderer Weg vom Start zum Ziel. Die Anfangsstücke von P und Q stimmen überein bis zu einem Knoten u und weichen danach ab. Auf dem Weg P folgt nach u der Knoten v und auf dem Weg Q der Knoten v'. Nach der Definition von P muss v < v' gelten. Damit ist P auch lexikograhisch kleiner als Q. Wären nicht alle Zahlen verschieden, dann könnte man aber jeden kürzesten Wege Algorithmus entsprechend anpassen. Die "Schwierigkeit" wäre nur, dass man als "Länge" für jeden Teilpfad alle bisher verwendeten Einzellängen abspeichern muss.


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3548
  Beitrag No.2, eingetragen 2022-01-28

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) @Kitaktus: Ich glaube mit "Jeder so entstandene Pfad muss dann der größe nach aufsteigend sortiert werden." ist gemeint, dass zuerst für jeden Pfad die Label sortiert werden. Es ist dann der Pfad gesucht, dessen sortiertes Label lexikographisch minimal ist. Der Greedy-Algorithmus ist dann nicht mehr optimal: Betrachte $\begin{pmatrix}2 & 4 & 1\\ 3 & 5& 6\end{pmatrix}$. Der gierige Pfad 2-3-5-6 ist hier nicht optimal, denn 2-4-1-6 (nach Sortierung entspricht das 1-2-4-6) ist besser. Wenn meine Interpretation richtig ist, dann ist das Problem aber immer noch recht leicht zu lösen: Der optimale Pfad muss auf jeden Fall das Feld mit der Zahl 1 enthalten, sagen wir dieses wäre an Position $(i,j)$. Wenn man rekursiv einen optimalen Pfad von $(1,1)$ zu $(i,j)$ und einen von $(i,j)$ zu $(m,n)$ wählt, dann findet man den optimalen Pfad.\(\endgroup\)


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 253
  Beitrag No.3, vom Themenstarter, eingetragen 2022-01-28

Nuramon hat recht, tut mir Leid wenn ich das uneindeutig beschrieben habe.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 253
  Beitrag No.4, vom Themenstarter, eingetragen 2022-01-28

Wenn beispielsweise 100 in der Matrix enthalten ist, dann könnte man doch einen Pfad konstruieren, bei dem 100 die kleinste Zahl ist und dann wäre dieser Pfad lexikographisch kleiner als der, der mit 1 beginnt.


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3548
  Beitrag No.5, eingetragen 2022-01-28

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Ok, das kommt darauf an, was Du mit lexikographisch meinst. Ich dachte, es ginge um die lexikographische Ordnung auf der Menge der $mn$-Tupel natürlicher Zahlen. Wenn Du die Stringkonkatenation der Dezimaldarstellungen meinst, dann stimmt meine Lösung natürlich nicht.\(\endgroup\)


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 253
  Beitrag No.6, vom Themenstarter, eingetragen 2022-01-28

Ich hab die Frage noch einmal präzisiert :)


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3548
  Beitrag No.7, eingetragen 2022-01-28

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Mit dem Edit finde ich das jetzt nocht verwirrender. \quoteon(2022-01-28 20:40 - dvdlly im Themenstart) Lexikographisch meint hier die konkatenation der einzelnen Zahlen als Stringfolge betrachtet. Also \(1,2,4\) ist als "Eins Zwei Vier" zu lesen. \quoteoff Meinst Du wirklich "Eins Zwei Vier"? Also in Wörtern ausgeschriebene Zahlen mit Leerzeichen getrennt? Ich hätte "124" erwartet.\(\endgroup\)


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 253
  Beitrag No.8, vom Themenstarter, eingetragen 2022-01-28

Das Rätsel ist ursprünglich in Englisch, aber ich bin davon ausgegangen, dass es so zu verstehen ist. Würde man das so interpretieren wie du alternativ sagst, dann würde mein Gegenbeispiel mit 100 auch nicht funktionieren (die Zahl wäre dann ja nicht 100 und demnach vermutlich lexikographisch größer als 1).


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2451
  Beitrag No.9, eingetragen 2022-01-28

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) Ich würde auch sagen, da von Zahlen die Rede ist, und aber nicht von Stellenwertsystemen zu irgendeiner festgelegten Basis (was ja angenommenerweise in einer Übersetzung auftauchen müsste), ist mit der lexikographischen Ordnung jene auf $\IN^*$ gemeint (mit dem gewöhnlichen < auf $\IN$ als Grundlage). Mit ein wenig Umkodierung also: Worte aus $\{1,\dotsc,NM\}$ der Länge $N+M-1$ entsprechen eineindeutig Mengen von natürlichen Zahlen aus $\{1,\dotsc,NM\}$ mit der Kardinalität $N+M-1$, und für den Größenvergleich der Mengen $A$ und $B$ schaut man sich das kleinste Element an, das in $A$ enthalten ist, aber nicht in $B$ (oder umgekehrt). Wenn es das gibt, ist $A\(\endgroup\)


   Profil
Kitaktus
Senior Letzter Besuch: im letzten Monat
Dabei seit: 11.09.2008
Mitteilungen: 6954
Wohnort: Niedersachsen
  Beitrag No.10, eingetragen 2022-01-29

Sorry, da hatte ich Dich missverstanden. Aber auch das Problem ist nicht schwer. Man sucht das Minimum der Einträge. Dieser Wert muss auf dem Pfad liegen. Nun streicht man diese Zahl und außerdem alle Zahlen, die entweder rechts und oberhalb der Zahl liegen, oder links und unterhalb. Unter den übrig gebliebenen Zahlen sucht man wieder das Minimum, das ebenfalls auf dem Pfad liegen muss. Wieder streicht man diese Zahl und alle rechts-oben oder links-unten usw.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 253
  Beitrag No.11, vom Themenstarter, eingetragen 2022-01-30

Hey, Ja richtig das habe ich mir auch überlegt :)


   Profil
dvdlly hat die Antworten auf ihre/seine Frage gesehen.
dvdlly hat selbst das Ok-Häkchen gesetzt.
dvdlly wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]