Brute-Force & Backtracking-Algorithmus

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Brute-Force & Backtracking-Algorithmus

    Hi, ich hab folgendes Problem:

    als ich neulich hier die Frage stellte, wie ich aus 32 Einzelflächen errechnen kann, welche 20 Einzelflächen mich genau auf meine gesuchte Gesamtfläche bringen, so wurde mir geantwortet ich soll das ganze mit einem Brute-force oder einem Backtracking-Algorithmus realisieren.
    Allerdings habe ich keine Ahnung was ein Brute-Force ist und auch nen Backtracking-Algorithmus kenn ich noch nicht. Daraufhin schrieb man mir einen "Pseudocode", mit welchem ich leider nichts anfangen kann, da er mir etwas zu ungenau ist.

    Jetzt meine Frage: Kann mir jemand anhand eines Beispielcodes (den man auch verstehen kann) erklären, was mit Brute-force und Backtracking-algorithmus gemeint ist?
    Das Genie überblick das Chaos!

  • #2
    http://www.educeth.ch/informatik/vor.../backtracking/

    hth!
    Ich denke, also bin ich. - Einige sind trotzdem...

    Kommentar


    • #3
      Danke, Begriff Back-tracking ist jetzt klar, allerdings denke ich wäre eine Function die alle möglichen Lösungen durchrechnet angebrachter. So weit ich informiert bin heisst man soetwas Brute-force. Kann mir jemand einen Beispielcode geben?
      Das Genie überblick das Chaos!

      Kommentar


      • #4
        wie wäre es dafür mit Rekursion, dürfte mit 5-10 Zeilen erschlagen sein
        TBT

        Die zwei wichtigsten Regeln für eine berufliche Karriere:
        1. Verrate niemals alles was du weißt!


        PHP 2 AllPatrizier II Browsergame

        Kommentar


        • #5
          schriebst du nicht im ersten thread, dass das was für die schule sei?

          wenn du nicht selber auf eine lösung kommst, dann sag deinem lehrer, dass du es mit dem was du dort bisher gelernt hast nicht lösen kannst, aber lass uns nicht hier deine hausaufgaben machen, um sie nachher stolz als dein werk zu präsentieren.
          I don't believe in rebirth. Actually, I never did in my whole lives.

          Kommentar


          • #6
            Hey wahsaga, nur damit eins klar ist, ich sagte das ist für die Schule, ich sagte jedoch nicht, dass wir in der Schule PHP programmieren oder?
            Wir haben die Aufgabe für Erdkunde herauszufinden, wie die Fläche zu stande kommt, welche Hilfsmittel wir hierfür verwenden bleibt uns überlassen.
            Das Genie überblick das Chaos!

            Kommentar


            • #7
              Auch wenn du alle Lösungen suchst, ist Backtracking schneller als brute force. Denn wenn die Flächensumme zu groß wird, geht das backtracking einen oder mehrere Schritte zurück.
              Das ist natürlich ein wenig schwieriger zu implementieren als die Variante, die nur eine Lösung findet.

              Ein paar Tipps zur Implementation:

              1. Sortier die Werte absteigend; damit kriegst du eine möglichst kurze Kombination
              und verhindest zu aufwendiges Zurueckgehen - mehr als ein Schritt wird bei der eine-Lösung-Variante nie nötig sein.

              2. Du solltest dir beim Sortieren dir Indizes merken, aus deren Werten du deine Testsumme zusammen setzt. arsort ist dafür gut.

              Die an sich schönen Array-Funktionen kannst du für das wandern im Werte-Array nicht gebrauchen, da dabei die Schlüssel verloren gehen.
              Und du brauchst zwei Stacks (einen für Keys, den anderen für die Werte);
              auf denen arbeitest du mit array_push und array_pop.


              Die alle-Lösungen-Variante kannst du beschleunigen, indem du Teilsummen suchst, die dem Wert eines anderen Elements entsprechen.
              Ist dieser Wert in einer Lösung enthalten, so findet man weitere Lösungen, indem man ihn durch die Elemente der Teilsummen ersetzt.


              Außerdem kannst du für allgemeinere Aufgaben noch ein paar Sonderfälle abfangen:
              - Summe aller Werte = gesuchter Wert: nur eine Lösung, und zwar die maximale
              - Summe aller Werte < gesuchter Wert: keine Lösung
              mein Sport: mein Frühstück: meine Arbeit:

              Sämtliche Code-Schnipsel sind im Allgemeinen nicht getestet und werden ohne Gewähr auf Fehlerfreiheit und Korrektheit gepostet.

              Kommentar


              • #8
                noch eins: Solltest du mal negative Werte dabei haben (bei diesem Problem nicht, aber wer weiß ), dann findet reines Backtracking unter Umständen keine einzige Lösung.
                Auch die beiden Sonderfälle fallen weg.

                Aber es geht immer noch schneller als mit brute force - man teile die Werte auf in zwei Arrays (eins mit positiven, eins mit negativen Werten); dann gibt es weitere Lösungswege:

                z.B. brute force und backtracking gemischt
                Man nehme das kleinere Array mit roher Gewalt vor:
                alle möglichen Kombinationen werden in ein drittes Array gepackt, das nach der Summe der Werte aufgeschlüsselt ist.
                diffsumme => array(kombi1, kombi2, ...)

                dann sucht man für jede Summe+Differenzsumme die Lösungen im größeren Array per Backtracking.

                z.B. geschachteltes Backtracking
                Backtracking im großen Array wie gehabt, aber:
                Ist die Summe zu groß, geht es erst einen Schritt zurück, wenn die Differenz zum gesuchten Betrag größer ist als die Summe der Werte im kleinen Array.
                Bis dahin wird im kleinen Array nach Lösungen für die Differenz gesucht - natürlich auch per Backtracking.
                Die Ergebnisse werden dann im oben erwähnten dritten Array gespeichert, für den Fall dass diese Differenz noch einmal auftritt.
                mein Sport: mein Frühstück: meine Arbeit:

                Sämtliche Code-Schnipsel sind im Allgemeinen nicht getestet und werden ohne Gewähr auf Fehlerfreiheit und Korrektheit gepostet.

                Kommentar


                • #9
                  Vielen Dank für die ausführlich Antwort, ich denke jetzt bekomm ichs hin.
                  Das Genie überblick das Chaos!

                  Kommentar

                  Lädt...
                  X