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 2 von 3     12 3   
Delphi-Laie

Registriert seit: 25. Nov 2005
1.431 Beiträge
 
Delphi 10.1 Berlin Starter
 
#11

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 16. Sep 2019, 23:22
Ich suche nur nach einem zuverlässigen Algorithmus.
Gib es auch unzuverlässige Algorithmen?

Soweit ich die Anfrage verstand, geht es um das Sortieren zweidimensionaler Arrays.

Dazu suchte ich auch schon mal, fand aber nichts. Offensichtlich ist das spezieller als das Sortieren "linearer" Datenmengen.

Eigene Beschäftigung zeigte mir, daß das auch deutlich anspruchsvoller als "lineares Sortieren" ist. Einfach in beiden Dimensionen, abwechselnd und ggf. wiederholt zu sortieren, reicht ggf. nicht - das wäre / ist nämlich unzuverlässig.

Eine Beruhigung kann ich jetzt schon geben: Ein zweidimensionaler Sortieralgorithmus wäre / ist garantiert zuverlässig, denn ein unzulässiger Sortieralgorithmus ist keiner!
  Mit Zitat antworten Zitat
Schokohase
(Gast)

n/a Beiträge
 
#12

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 17. Sep 2019, 07:59
Soweit ich die Anfrage verstand, geht es um das Sortieren zweidimensionaler Arrays.
Darum geht es eigentlich gar nicht.

Jeder Block/Zeile hat mehrere unterschiedliche gültige Anordungen wo es nun gilt ein Optimum zu finden.

Sortieren - Nein
Array - eindimensional (der Block/die Zeile) aber unerheblich, mittels Permutation iterieren wir über die möglichen Anordnungen und wird bei der Lösungssuche als Einheit betrachtet
Array - die Auflistung der Blöcke ist auch eindimensional und bleibt statisch - also auch unerheblich

Ok, ganz am Schluß kommt es darauf an, bei welcher Konstellation es die wenigsten Wechsel gibt ...

Geändert von Schokohase (17. Sep 2019 um 08:22 Uhr)
  Mit Zitat antworten Zitat
Jumpy

Registriert seit: 9. Dez 2010
Ort: Mönchengladbach
1.567 Beiträge
 
Delphi 6 Enterprise
 
#13

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 17. Sep 2019, 09:46
Mal ein anderer Ansatz (Bruteforce?), muss nicht unbedingt sinnvoller sein:

1. Man sortiert zunächst jeden Block für sich, so dass gleiche "Buchstaben"/"Größen" zusammen stehen.
2. Anschließend bildet man eine Liste aller Kombinationen von Permutationen in allen Blöcken.
3. Dann ermittelt man, bei welcher Kombination die wenigsten Wechsel stattfanden.
4. Für "Stabilität" müsste man bei mehreren Konfigurationen mit gleich wenig Wechseln, ein weiteres Kriterium angeben, das diese gewichtet?
Ralph
  Mit Zitat antworten Zitat
Benutzerbild von Sherlock
Sherlock

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

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 17. Sep 2019, 10:05
Gib es auch unzuverlässige Algorithmen?
Ja, meine

Sherlock
Geändert von Sherlock (Morgen um 16:78 Uhr) Grund: Weil ich es kann
  Mit Zitat antworten Zitat
Schokohase
(Gast)

n/a Beiträge
 
#15

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 17. Sep 2019, 10:54
4. Für "Stabilität" müsste man bei mehreren Konfigurationen mit gleich wenig Wechseln, ein weiteres Kriterium angeben, das diese gewichtet?
Die Stabilität bekommst du durch die Sortierung innerhalb des Blocks.

Nehmen wir mal folgenden Block
Code:
abcdeabcdeabcde
Wenn wir den sortieren, dann erhalten wir
Code:
aaabbbcccdddeee
und das stabil.

Bei der Permutation des Blocks ist nur der Anfang und das Ende interessant. Die Anordnung in der Mitte ist unerheblich.
Code:
aaabbbcccdddeee
oder
Code:
aaacccbbbdddeee
ist für die gesuchte Optimierung gleich.

Die Permutation von diesem intern sortierten Block bekommt man durch folgenden Pseudocode
Code:
parts = block.split() // aaabbbcccdddeee => aaa,bbb,ccc,ddd,eee
foreach first in parts
  foreach last in parts.except(first)
    permutation = first + parts.except(first).except(last) + last
Und diese Permutation ist stabil.
Code:
aaacccdddeeebbb
aaabbbdddeeeccc
aaabbbccceeeddd
aaabbbcccdddeee
bbbcccdddeeeaaa
bbbaaadddeeeccc
bbbaaaccceeeddd
bbbaaacccdddeee
cccbbbdddeeeaaa
cccaaadddeeebbb
cccaaabbbeeeddd
cccaaabbbdddeee
dddbbbccceeeaaa
dddaaaccceeebbb
dddaaabbbeeeccc
dddaaabbbccceee
eeebbbcccdddaaa
eeeaaacccdddbbb
eeeaaabbbdddccc
eeeaaabbbcccddd
BTW: Die Anzahl der Elemente dieser Permutation ist
Code:
n*(n-1) für n=Anzahl der unterschiedlichen Buchstaben
Für die Optimierung ist der Wechsel innerhalb des Blocks völlig unerheblich, denn diese Wechsel sind immer da, egal wie die Anordnung ist. Man braucht also nur schauen, ob es einen Wechsel zwischen benachbarten Blöcken gibt.

Im Vorfeld kann man dabei schon das theoretisch bestmögliche Ergebnis ermitteln, was man dann als Abbruchkriterium nehmen kann (wenn man nur an einer optimalen Lösung interessiert ist).

Dazu schaut man sich die Blöcke an und ermittelt, ob diese Blöcke überhaupt ohne Wechsel zusammengefügt werden können.

Keine Wechsel zwischen den Blöcken
Code:
abcd
defg
ghij
Keine Optimierung möglich, denn es muss immer zwischen den Blöcken gewechselt werden.
Code:
abc
def
ghi
Natürlich gibt es auch Konstellationen, wo das so ermittelte theoretisch beste Ergebnis nicht erreicht werden kann
Code:
abc
cde
cfg

Geändert von Schokohase (17. Sep 2019 um 11:05 Uhr)
  Mit Zitat antworten Zitat
freimatz

Registriert seit: 20. Mai 2010
611 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#16

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 17. Sep 2019, 12:41
Ich suche nur nach einem zuverlässigen Algorithmus.
Gib es auch unzuverlässige Algorithmen?
Ja. Es kommt drauf an was man unter unzuverlässig versteht. Gefragt ist hier eine Lösung mit den wenigsten Wechseln. Unzuverlässig wäre ein Algorithmus der zwar wenig Wechsel hat, aber nicht am wenigsten.
Einen zuverlässigen Algorithmus wird es hier schon geben, zumindest der Brute Force wäre einer.
Es kann jedoch sein, dass dieser Algorithmus nicht brauchbar wäre. Das wäre zum Beispiel der Fall wenn man um einige Wechsel mit je 5 Sekunden zu sparen fünf Stunden benötigt um die optimal Lösung zu finden.
(Das Problem hat auch jedes Navigationsgerät.)

Deswegen fragte ich auch nach der Anzahl der Blöcke. Sind es zum Beispiel maximal 20, dann Brute Force und gut ist.
Wenn es 1000 sind fürchte ich, gibt es keine brauchbare zuverlässige Lösung. Aber meistens reicht auch eine nahezu zuverlässige Lösung.
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.431 Beiträge
 
Delphi 10.1 Berlin Starter
 
#17

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 17. Sep 2019, 15:47
So, ich habe es jetzt hoffentlich verstanden.

Ein Sortieralgorithmus läßt sich m.E. aber nur auf die jeweiligen einzelnen Zeilen anwenden. Danach ist wohl die Zeit für "brute force" gekommen: Die einzelnen Blöcke mit gleich(groß)en Elementen innerhalb der Zeilen so permutieren, daß die Zusatzbedingung ("möglichst wenige Wechsel") erfüllt ist.
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.431 Beiträge
 
Delphi 10.1 Berlin Starter
 
#18

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 17. Sep 2019, 15:49
Ich suche nur nach einem zuverlässigen Algorithmus.
Gib es auch unzuverlässige Algorithmen?
Ja. Es kommt drauf an was man unter unzuverlässig versteht. Gefragt ist hier eine Lösung mit den wenigsten Wechseln. Unzuverlässig wäre ein Algorithmus der zwar wenig Wechsel hat, aber nicht am wenigsten.
Das ist aber kein Algorithmus, der die Aufgabenstellung löst! Der ist also nicht nur unzuverlässig, sondern hinsichtlich des Zielens unbrauchbar/untauglich/nutzlos/wertlos o.ä..
  Mit Zitat antworten Zitat
mariusbenz

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

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 20. Sep 2019, 14:12
Hallo nochmal,

ich habe das Thema etwas ruhen lassen, deshalb melde ich mich jetzt erst wieder.
Da unsere Azubis diesen Algorothmus später umsetzen sollen, habe ich sie mit etwas Unterstützung erst mal selbst grübeln lassen.

Ich bin auf jeden Fall froh, dass Uwe und Schokohase die Aufgabe trotz fehlender Umformulierung verstanden haben.

Evtl. werden wir es auch mal mit BruteForcing probieren, therotisch kämen bis zu 60 Blöcke je 13 Werten zu Stande, in der Praxis wären es aber grob 20 Blöcke mit je 5 Werten.
Ebenso sind wir schon auf Uwes Idee mit der gemeinsamen Schnittmenge gekommen.

Den Ansatz (der mit den Bildern beschrieben ist) habe ich übrigens komplett verworfen, leider kann ich nun den Post aber nicht mehr bearbeiten.
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.510 Beiträge
 
#20

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 20. Sep 2019, 18:19
Ich hatte da noch eine Idee: Vielleicht könnten man das Problem als Graph umformulieren und dann über einen Standard-Algorithmus zur Lösung kommen.

Jeden Block kann man als Paar von Knoten auffassen, mit dem Anfangs- und Endbuchstaben. Die Pfade zwischen den beiden Knoten geben an, welche Kombinationen möglich sind. Vom zweiten Knoten gehen dann wieder viele Pfade zum ersten Knoten des nächsten Blocks.

Es ergeben sich sehr viele Pfade, die daher nach Möglichkeit nicht am Anfang alle erstellt werden sollten. Jeder Pfad hat dann ein Gewicht (0/1) je nachdem, ob die Buchstaben identisch sind. (Im Bild: Rot=1)
Miniaturansicht angehängter Grafiken
beispiel.png  
  Mit Zitat antworten Zitat
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:53 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