Algorithmus gesucht: Menge diskreter Werte kombinatorisch zu einem bestimmten Wert zusammenfügen

Neue Frage »

delirio Auf diesen Beitrag antworten »
Algorithmus gesucht: Menge diskreter Werte kombinatorisch zu einem bestimmten Wert zusammenfügen
Hallo zusammen,

vorne weg, Entschuldigung vielmals für diesen unmöglichen Themen Titel.
Wüsste ich die richtige Bezeichnung meines Problems, wäre vielleicht auch die Lösungssuche einfacher geworden.

Folgendes,

ich besitze eine Menge an diskreten Werten und möchte damit bestmöglich einen bestimmten Summenwert erstellen.

Wie umschreib ich mir ein solches Szenario mathematisch.

Vergleichbar wäre denk ich der Ansatz eines Geldrückgabe Systems welches aus der Auswahl 10c,20c,50c,1EUR die richtige Wahl trifft um einen bestimmten Betrag zu realisieren.


Vielleicht hilft jemandem eine genauere Beschreibung der späteren Anwendung.
Ich besitze eine Auswahl an 16 Drahtstücken, deren Länge binär gestuft ist.
Sprich,







Mit Hilfe dieser Auswahl möchte ich durch Hintereinanderschaltung einen Draht mit einer beliebigen Gesamtlänge im Wertebereich



realisieren.

Wie erschlage ich mit Hilfe eines Algorithmus dieses Problem.


Bzw. würde mir vielleicht ein Denkanstoß in die Richtung der Formulierung meines Problems helfen.


Vielen vielen Dank
mit freundlichen Grüßen

Mazze Auf diesen Beitrag antworten »

Ich würde so vorgehen :

Restlänge n = Länge des drahtes.

Repeat

wähle längstes Drahtstück was nicht größer als n ist
reduziere n um die Länge dieses drahtstücks

until n = 0

Das Ganze funktioniert aber nur, wenn jede Länge durch deine Drahtstücke erreicht werden kann.
Booker Auf diesen Beitrag antworten »

Hallo,

vornweg: Der Titel ist ist wenigstens aussagekräftig und zehnmal besser als "Dringend Hilfe gesucht!!!"

Ich würde in einer Schleife alle Drähte in absteigender Reihenfolge testen, ob sie kleiner gleich der Gesamtlänge sind. Also immer den längsten Draht bestimmen, der noch reinpasst, wenn keiner mehr reinpasst, bist du am Ziel...

Hoffe du kannst nachvollziehen was ich meine, hab grad nicht die Zeit das in ordentlichem Deutsch zu formulieren...

Gruß Booker
delirio Auf diesen Beitrag antworten »

Oh,

Danke Ihr beiden !


Dann war der Ansatz doch einfacher als ursprünglich gedacht.

Eure beiden Vorschläge, bzw. entsprechen sie ja der gleichen Vorgehensweise
sind im Grunde doch als
GREEDY Algorithmus
zu interpretieren wenn ich das richtig verstehe, oder?

Ich dachte zuerst nicht das ich es so einfach an gehen kann, zumindestens weiß ich nun bereits wie ich mir das ganze in Software implementieren kann.

Was mir noch gut weiterhelfen würde wenn ich wüsste wie ich das ganze mathematisch beschreibe, leider fehlts da an den nötigen Grundlagen.
Wenn mir einer vielleicht noch einen Wink in die richtige Richtung geben würde, wäre ich daher sehr dankbar.
Mazze Auf diesen Beitrag antworten »

Du hast eine Menge von Zahlen , eine Zahl a und suchst eine Zahl so dass

für gilt.

Hier wird es im Allgemeinen keine eindeutige Lösung geben. Ob ich obigen Algorithmus als Greedy einstufen würde ist mir nicht ganz klar. Schließlich suchen wir ja nur irgendeine Zerlegung und nicht die "beste", haben daher auch kein Maß für gut oder schlecht, was der Greedy ja braucht.
delirio Auf diesen Beitrag antworten »

Zitat:
Original von Mazze
Du hast eine Menge von Zahlen , eine Zahl a und suchst eine Zahl so dass

für gilt.

Hier wird es im Allgemeinen keine eindeutige Lösung geben. Ob ich obigen Algorithmus als Greedy einstufen würde ist mir nicht ganz klar. Schließlich suchen wir ja nur irgendeine Zerlegung und nicht die "beste", haben daher auch kein Maß für gut oder schlecht, was der Greedy ja braucht.


Vielen Dank. smile
Aber
Hmm... wenn ich das richtig verstehe summierst du sukszessiv ab der geringsten Leitungslänge auf, bis du eine obere Schranke erreichst welche dann eben dem Wert entsprechen sollte.
Damit eine Lösung zu finden ist ja eher unwahrscheinlich oder?


Geh ich richtig davon aus das mein Problem eher einem "Minimierungsproblem" entspricht?

Vergleich -wiki Algorithmus Minimierungsproblem...

Leider stehe ich bei der gezeigten Wikipedia Darstellung auf dem Schlauch und mir fehlt die richtige Interpretation unglücklich
 
 
Mazze Auf diesen Beitrag antworten »

Folgende Fragen :

Ist die Anzahl der Drähte beschränkt?

Gibt es Drähte mit Längeneinheit 1 ?

Wenn die Antwort auf Frage 1 ja und auf Frage 2 nein ist, dann wird das Ganze ein Suchproblem. Ob man daraus ein Minimierungsproblem konstruieren kann sehe ich nicht sofort.

Klassische Lösungalgorithmen hierführ :

Breitensuche/Tiefensuche/Backtracking/optimiertes Backtracking usw.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »