AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

Ein Thema von mariusbenz · begonnen am 16. Sep 2019 · letzter Beitrag vom 23. Sep 2019
Antwort Antwort
Seite 1 von 3  1 23   
mariusbenz

Registriert seit: 6. Mär 2015
27 Beiträge
 
#1

Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 11:48
Hallo,

vorweg: Ich suche nur nach einem zuverlässigen Algorithmus.
Hier mal die Aufgabenstellung (vereinfacht):

Input:
Ein 2-dimesionales Array mit Zahlenwerten, z.B.
1360 2610 2610 2610
1360 2610 2610 1360 1360

Verarbeitung/Ziel:
die Zahlen so sortieren, dass insgesamt möglichst wenige Wechsel entstehen. „Insgesamt“ heißt, dass die vorhergehende und die nachfolgende Zeilen mitberücksichtigt werden sollen, also beim Zeilenwechsel möglichst kein Wechsel des Wertes auftritt. Die Werte können dabei nur innerhalb einer Zeile verschoben werden.
Die Abarbeitung erfolgt von links nach rechts und von oben nach unten (also so wie man es hier in Textform liest).

Output:
Das sortierte 2-dimesionale Array mit Zahlenwerten, z.B.
1360 2610 2610 2610
2610 2610 1360 1360 1360

-> Die Anzahl der "Wertewechsel" wurde von 4 auf 2 reduziert


Ich habe hier mal ein Beispiel mit echten Daten (zur Vereinfachung als Buchstaben) eines möglichen Inputs (pro Zeile können theoretisch ca. 10 verschiedene Werte stehen)
aabb
bbaa
cddd
eeec
eeef
eeef
eeef
eeef
eeef
eeef
gghe
iiig

Dann bin ich mal hingegangen und habe das Vorkommen eines jeden Buchstaben in ein Array gepackt, das sähe dann so aus
Grafik Array_Vorkommen.png

Mit folgendem Algorithmus könnte man dann dieses neue Array abarbeiten:
1. Es werden nur die Felder mit "1" betrachtet
2. In einer Spalte kann man "springen", jedes Feld darf aber nur ein Mal "besucht" werden.
3. Wenn alle Felder einer Spalte besucht wurden, muss man nach rechts in die nächste Spalte. -> Dabei nach Möglichkeit nicht die Zeile wechseln.

Darstellung, in welcher Reihenfolger die Felder abgearbeitet werden sollten: Grafik Array_Reihenfolge.png

Nach diesen Regeln würde man z.B. folgenden Output generieren (pro Spalte hier eine Zeile):
ab
ba
dc
ce
ef
fe
ef
fe
ef
fe
ehg
gi

was dann auf folgendes erweitert werden könnte und gleichzeitig das optimal sortierte Array wäre
aabb
bbaa
dddc
ceee
eeef
feee
eeef
feee
eeef
feee
ehgg
giii


Ich hoffe ich konnte die Aufgabenstellung anhand dieses Beispiel gut genug erklären.
Kennt ihr dafür einen Algorithmus?
Ist mein Ansatz über das Array "Vorkommen eines Wertes" ein richtiger Ansatz? Gibt es einen Algorithmus, um in diesem Array einen "Pfad" nach den oben beschriebenen Regeln (besonders Regel 3) zu finden?
Das Problem bei beiden Ansätzen dürfte ja sein, dass man ggf. zurückspringen und die bisherige Sortierung komplett über den Haufen werfen muss, um die optimale Sortierung zu erzielen.
Miniaturansicht angehängter Grafiken
array_vorkommen.png   array_reihenfolge.png  

Geändert von mariusbenz (16. Sep 2019 um 13:28 Uhr)
  Mit Zitat antworten Zitat
freimatz

Registriert seit: 20. Mai 2010
605 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#2

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 12:45
Nein, Sorry, ich versteh es nicht. Was sind denn Zuschnittbilder? Und was sind das für Paletten? Bei uns in der Firma gibt es auch Paletten, da wird nichts geschnitten. Und was man bei z.B. Euro-Paletten schneidet wüsste ich auch nicht.
Und was bedeuten die Zahlen? Länge, Breite, Höhe?
Und wie hoch ist die Anzahl der Bilder?
  Mit Zitat antworten Zitat
mariusbenz

Registriert seit: 6. Mär 2015
27 Beiträge
 
#3

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 13:27
Nein, Sorry, ich versteh es nicht. Was sind denn Zuschnittbilder? Und was sind das für Paletten? Bei uns in der Firma gibt es auch Paletten, da wird nichts geschnitten. Und was man bei z.B. Euro-Paletten schneidet wüsste ich auch nicht.
Und was bedeuten die Zahlen? Länge, Breite, Höhe?
Und wie hoch ist die Anzahl der Bilder?
Schade, dass du dich an der für die eigentliche Aufgabe unwichtigsten Stelle aufgehalten hast. Ich habe die Aufgabenstellung nun neu formuliert.
  Mit Zitat antworten Zitat
jobo

Registriert seit: 29. Nov 2010
2.651 Beiträge
 
Delphi 2010 Enterprise
 
#4

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 14:41
Ich verstehe es auch nicht.
Wie erklärt sich der Wandel zwischen Beispielwerten im ersten Beispiel und im 2?
Aus 2 zeilen mit 4-5 Werten werden 15 Zeilen mit 1 Wert, oder ist abcd = 4 Werte?

Auch die Regeln von Dir kann ich nicht mit den Bildern und den Werten unter einen Hut kriegen.
Gruß, Jo
  Mit Zitat antworten Zitat
mariusbenz

Registriert seit: 6. Mär 2015
27 Beiträge
 
#5

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 15:41
Die beiden Beispiele sind unterschiedlich.
Jeder Buchstabe steht für eine Zahl, z.B. a = 1360, b = 2500, etc.

Aber ich muss das morgen wohl nochmal neu formulieren...
  Mit Zitat antworten Zitat
Benutzerbild von Sherlock
Sherlock

Registriert seit: 10. Jan 2006
Ort: Offenbach
3.344 Beiträge
 
Delphi 10.3 Rio
 
#6

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 16:05
Sieh es positiv, jede neue Formulierung des Problems könnte Dich selbst auf die Lösung bringen.

Sherlock
Geändert von Sherlock (Morgen um 16:78 Uhr) Grund: Weil ich es kann

Geändert von Sherlock (16. Sep 2019 um 16:09 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
7.073 Beiträge
 
Delphi 10.3 Rio
 
#7

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 16:33
Ein paar Gedanken zu dem Problem:

Jede Zeile (außer erster und letzter) hat eine Schnittmenge gemeinsamer Elemente mit der vorhergehenden und nachfolgenden Zeile. Sind diese Schnittmengen disjunkt oder mindestens eine davon leer, bildet diese Zeile die Grenze eines Optimierungsbereichs, bei der sich die angrenzenden Bereiche nicht beeinflussen. Man kann dann den Algorithmus auf die einzelnen Bereiche beschränken.

Es kann sein, daß es mehr als ein gleichwertiges Optimum gibt. Das wirft die Frage auf, ob der Algorithmus deterministisch sein soll - sprich, bei gleichen Eingabedaten immer dasselbe Ergebnis liefert. Eventuell kann man das durch zusätzliche Bedingungen für das Optimum erreichen.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Schokohase
(Gast)

n/a Beiträge
 
#8

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 17:01
So schwer zu verstehen ist es ja nun auch nicht, vor allem weil man zum Suchen nach der Lösung gar nicht alles verstehen muss.

Gegeben sei folgende Menge
Code:
{abababab}{abcabc}{dede}{aceace}
  • Die geschweiften Klammern beschreiben einen Block.
  • Die Buchstaben innerhalb eines Blocks dürfen beliebig angeordnet werden.
  • Die Blöcke dürfen beliebig angeordnet werden.
Ziel ist es eine Reihenfolge der Blöcke zu finden, wo es minimale Wechsel zwischen den Buchstaben gibt.

Die gegebene Menge zeigt im Übrigen das worst-case Szenario wo ständig Wechsel (23 Stück) erfolgen.

Eine mögliche optimale Lösung wäre
Code:
{dd|ee}{ee|cc|aa}{aaaa|bbbb}{bb|aa|cc}
mit 6 Wechseln (markiert durch |)
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
7.073 Beiträge
 
Delphi 10.3 Rio
 
#9

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 18:09
Gegeben sei folgende Menge
Code:
{abababab}{abcabc}{dede}{aceace}
  • Die geschweiften Klammern beschreiben einen Block.
  • Die Buchstaben innerhalb eines Blocks dürfen beliebig angeordnet werden.
  • Die Blöcke dürfen beliebig angeordnet werden.
Ziel ist es eine Reihenfolge der Blöcke zu finden, wo es minimale Wechsel zwischen den Buchstaben gibt.
Sieh mal an, das hatte ich ganz anders verstanden:
  • Die geschweiften Klammern beschreiben einen Block.
  • Die Buchstaben innerhalb eines Blocks dürfen beliebig angeordnet werden.
  • Die Reihenfolge der Blöcke ist vorgegeben.
Ziel ist es eine Reihenfolge der Buchstaben innerhalb jedes Blocks so zu verändern, das es sowohl innerhalb eines Blocks als auch von einem Block zum nächsten möglichst wenige Wechsel gibt.

Eine mögliche Lösung für das genannte Beispiel wäre dann:
Code:
{aaaabbbb}{bbaacc}{ddee}{eeaacc}
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Schokohase
(Gast)

n/a Beiträge
 
#10

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 18:23
Ja, da hast du Recht, die Zeilen (Blöcke) sollen anscheinend nicht vertauscht werden.

Dadurch wird es auch einfacher zu lösen.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:55 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf