Suche zu einfachem Problem einen schnellen Algorithmus

Hi, habe ein einfaches Problem..finde aber keinen Algorithmus, welcher für große Werte auch noch recht schnell erfolgreich ist *heul
Dachte ich poste hier ins C++-forum, weil ich denke, dass hier die fähigsten Leute für die Lösung meines Problems sind.

Problem:

Ich habe eine bestimmte Länge x. Nun habe ich 6 verschieden lange Gegenstände.
Ich muss nun die geringste Mögliche Anzahl an Gegenständen finden, welche
die Länge ausfüllen. Bei der Aneinanderreihung der Gegenstände ist zu beachten, das Diese sich mindestens zu einem Wert MIN überlappen müssen und maximal zu einem Wert MAX überlappen dürfen. Auch muss die Länge x nicht vollständig ausgefüllt werden, sondern es kann bis zum maximalen Wert y Platz frei bleiben! Das sieht auf den ersten Blick einfach aus, aber ich komme auf keinen SCHNELLEN Algorithmus. Meiner hat viel zu hohe exponentielle Laufzeit!

Ich habe folgende Lösung verwendet:

Zuerst habe ich rekursiv alle möglichen Kombinationen ausgerechnet , welche in die Länge passen oder auch etwas überlappen. Alle Kombinationen werden in eine Liste gespeichert. Danach habe ich die Liste nach den oben genannten Restriktionen ausgewertet. Das Problem ist, das die Liste schon bei etwas größeren Werten für x mehrere Millionen Einträge umfasst. So dauert die Auswertung und Erstellung der Liste ewig. Ich muss einen anderen Grundansatz finden. Vielleicht könnt Ihr mir dabei helfen das Problem zu lösen. Habe schon nach dem "Rucksackproblem" geschaut, nur ist bei mir das Problem, dass sich ja die Gegenstände MIN überlappen müssen und die Überlappung kann variabel bis MAX sein. So hätte ich Praktisch das Rucksackproblem mit Gegenständen, welche sich zum Teil Variabel bis MAX verkleinern lassen ?!

Hier mein Algorithmus zur Erstellung der Liste (VB-Pseudocode!)
Er findet alle Kombinationen, welche Kanditaten für die Lösung sein könnten.

Aufruf: calcCandidats(3000, 0)

Public Sub calcCandidats(länge As Double, vorherigeLänge As Double) 
    Dim i As Double            'Zähler 
    Dim l As Double            'Länge der Kombination an Gegenständen 
    Dim Überlapp As Double     'Überlappung 

    For i = 0 To 5 
        l = LängeGegenstand(i) + vorherigeLänge 

        If (l < länge) Then 
            Call calcCandidats(länge, l) 
            bigListe(bigIndex) = speichere l 
            bigIndex = bigIndex + 1 
        Else 
            Überlapp = l - länge  'Überlappung berechnen 
            l = l - Überlapp      'l auf Länge setzen   
            bigListe(bigIndex) = speichere l und Überlapp 
            bigIndex = bigIndex + 1 
        End If 
    Next i 
End Sub

Aufruf: calcCandidats(WERT, 0)

Gruss und vielen Dank im vorraus

Finalbrain

Gast221212

Da eignet sich nichts besser als genetische Algorithmen sind eigentlich ganz leicht.

Das standardbeispiel für gen. Algorithmen ist ein "Rucksack-packen", d.h. du hast 100 Sachen mit jeweils Gewicht und Nutzen, und du sollst einen möglichst nützlichen rucksack packen, der weniger als 25 KG wiegt.

Such mal nach genetischen/genetic algorithmn/algorithms Rucksack/backpack.

Keine Angst, ist wirklich leicht (< 20 Zeilen Code) und melde dich wieder wenns geklappt hat!

Gast221212

Oh, hätte ich erst mal ganz lesen sollen... Das Rucksackproblem hast du ja auch schon erkannt.

Also, wenn sich alle Gegenstände MIN überlappen sollen, kannst du doch auch sagen:

länge jedes Gegenstands = länge - MIN.

und wenn sie sich alle MAX überlappen dürfen, dann, falls länge immer > (MAX-MIN), kannst du sagen, dass

x zwischen x und x+(MAX-MIN)*Anzahl_Teile liegen darf.

'(MAX-MIN)*Anzahl' muss nicht bekannt sein, dass kann ja die Evaluierungsfunktion prüfen, und alle Kombinationen, die größer 'x+(MAX-MIN)*Anzahl' sind killen.

Vertexwahn

ich komme auf keinen SCHNELLEN Algorithmus

veilleicht gibt es halt keinen schnellen Algorithmus für dieses Problem - ich vermutte mal dein Problem ist NP vollständig

Vielen Dank für eure schnelle Hilfe

hmmm...also dazu käme dann noch der mögliche Freiraum y in x.
Und ein einziges Teil hat keine Überlappung.

Mein Aussortierungsverfahren würde dann nach folgender Bedingung
aussortieren:

Wenn (AktuelleCombo >= (x - y) und AktuelleCombo <= x + (max-min)*(Anzal_Teile-1)) Dann schreibe in Liste als Kandidat.

Fällt euch denn noch ein, wie ich die aktuellenCombos schnellstmöglichst finde ?

...der Tip mit den genetischen Algorithmen ist gut..mein Prob ist nur..das ich enorm Zeitdruck habe und mich nicht so schnell in so eine neue komplexe Materie einarbeiten kann. Ich probiere erstmal so eine etwas schnellere Lösung zu finden. Vielleicht hat Vertexwahn recht..aber ich glaube immer noch daran..das es auf jedenfall schneller als MEIN amtaeurhafter Algorithmus geht.
Weiss jemand sonst noch was helfen könnte

Gast221212

finalbrain__xp schrieb:

Vielleicht hat Vertexwahn recht..

Natürlich hat Vertexwahn Recht und das Problem is NP-Vollständig. Brute-Force kommst du da nicht weit; Vorschläge wären:

Genetísche Algorithmen,
Simulated Annealing,
Ants

Aber Genetísche Algorithmen sind echt nicht schwer, kannst du dich ruhig dran versuchen.

Danke nochmal

Das Problem ist..das ich Morgen Das Prog an ne Firma verticken muss und da keine Zeit habe mich EBEN in genetische Algorithmen einzuarbeiten...das dauert nen Paar Stündchen und die brauche ich noch für die GUI

..habe aber einen Algorithmus gefunden (Dank deiner Hilfe@Gast), welcher wenigstens in "moderater" Laufzeit läuft. Die Laufzeit ist nun vollkommen ausreichend für die Werte die ich benötige. Echt vielen Dank für deine Hilfe

Wens interessiert:

Option Explicit
Global ArrayVal(6) As Double
Global min As Double
Global max As Double
Global maxFree As Double
Global lComboAnzStack As Double
Public Sub calcCandidatsNew(länge As Double, comboLen As Double, comboAnz As Double, way As String)
    Dim i As Double
    Dim lComboAnz As Double
    Dim lComboLen As Double
    Dim lWay As String

    lComboAnz = comboAnz + 1

    For i = 0 To 5
        lComboLen = comboLen + ArrayVal(i)
        lWay = way + CStr(i)

        If (lComboLen >= länge - maxFree And lComboLen <= länge + max *(lComboAnz - 1)) Then

            If (lComboAnz <= lComboAnzStack) Then
                lComboAnzStack = lComboAnz
                Form1.List1.AddItem CStr(lComboLen) + "|" + lWay
            End If
        Else
            If comboLen < (länge - maxFree) Then
                Call calcCandidatsNew(länge, lComboLen, lComboAnz, lWay)
            End If
        End If

        lComboLen = lComboLen - ArrayVal(i)
        lWay = Left(lWay, lComboAnz - 1)
    Next i
End Sub

Gruss an Alle

Finalbrain

Konrad Rudolph

Nur mal zwei Worte zum VB-Code:

'Global' => 'Public' ('Global' ist veraltet)
'Left' => 'Left$' (gerade, wenn Du auf Geschwindigkeit Wert legst!)

Und der größte Teil der Zeit geht, soweit ich das jetzt sehe, sowieso bei den zahlreichen String-Konkatenationen verloren, wenn diese Funktion also zeitkritisch ist, würde ich da eine Stringbuilder-Klasse verwenden.

PS: was macht diese Frage eigentlich in einem C++-Forum?

EDIT: Das mit der Stringbuilder-Klasse ist Quatsch. Aber diese ganze Funktion ist ziemlich komisch. Was z.B. soll die letzte Zeile in der Schleife? 'lWay' wird doch am Schleifenanfang wieder überschrieben.

volkard

Konrad Rudolph schrieb:

PS: was macht diese Frage eigentlich in einem C++-Forum?

das sagte er.

Dachte ich poste hier ins C++-forum, weil ich denke, dass hier die fähigsten Leute für die Lösung meines Problems sind.

im prinzip können wir auch in c++ oder java antworten. er wird es umsetzen. ihm ging es um den klugen algo.
was er nicht wußte, ist daß die c++-leute in diesem forum, die sich für algos interessieren, auch "Rund Um Die Programmierung" in diesem forum immer lesen. es sei ihm mal verziehen.

falls ich den knopf finde, verschieb ich den thread mal. aber heute nicht mehr.

nervig ist natürlich, daß die java-leute, die sich für algos interessieren, diese hochinteressante problem nicht sehen.

Vielen Dank für eure Postings

@Konrad

hmm...du magst ja recht haben das ich ein paar Ticks mehr bekomme, wenn ich deine Tipps mache, aber das ist leider nur der Boden der Flasche.
Ausserdem wollen wir doch nicht hier sowas wie "...Global ist veraltet.."
anfangen! Ich bin kein VB'ler sondern ein C'ler und weiss sehr wohl was Zeit kostet und was nicht. Der Code ist nicht komisch, sondern RECHT komplex,
und hättest du Ihn verstanden, dann hättest du nicht gefragt, warum
lway in der letzen Zeile um eine Stufe zurückgesetzt wird! Befass dich mehr damit und du wirst sehen, das er gut durchdacht ist. Wenn du einen besseren findest, dann nehme ich diesen sehr, sehr gerne an...weil das meine eigentliche Intension von diesem Posting ist. Ich hatte es hierhin gepostet,
weil ich denke das C++'ler mehr trainiert auf High-Level Denken sind
und das Problem ja nun nicht wirklich Low-Level ist
Volkard hat recht, die Java-Leute sind noch Optimaler dafür
Ach ja...hatte dieses Posting bereits in "Rund um die Programmierung" vorher gestellt, aber hatte dort keine Antwort bekommen...um die These von Volkard zu wiederlegen Das Problem ist wirklich hochinteressant...wenn wir das Problem in Perfekter Laufzeit lösen könnten, dann könnten wir uns auf die faule Haut legen. Aber ich lass noch nicht locker. Die "ungelösten" Primzahlenprobleme
wurden entgegen der Landläufigen Meinung bereits vor kurzemvon Plichta gelöst...vielleicht löst man ja dieses Problem ja auch irgendwann

Gruss

Finalbrain

Der Flaschenhals liegt klar in den Millionen Rekursion die gemacht werden müssen. Und dieses Problem ist nicht anders lösbar.

..sorry hast recht...in dem VB-Code den ich hier gepostet habe sind noch
l's zuviel drinnen. Teste Ihn das nächste mal, wenn ich Hier was Poste

Gruss

Finalbrain