mikrocontroller.net

Forum: PC-Programmierung Bruteforce Optimierung


Autor: Karl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich habe mich schon länger gefragt, wie man am besten ein Programm 
schreibt, dass alle Möglichkeiten durchprobiert. Wenn man z.B. eine 
Matrix m x n .In der Matrix steht irgendwas, was entweder maxi- oder 
minimiert werden soll (Summe, Produkt etc.). Nun muss ich ja alle 
Möglichkeiten durchprobieren, wobei in jeder Zeile nur ein Feld 
verwendet werden darf. Hier mal ein Beispiel
9  1  1  1
1  9  1  1
1  1  9  1
1  1  1  9

Hier ist ja klar, dass man in jeder Zeile jeweils das Feld mit der 9 
nimmt. Aber wenn da noch andere Zahlen stehen wird es ja komplizierter. 
Und wenn man das für 100x100 Matrizen optimieren soll ist es ja per Hand 
fast unmöglich.
Solche Optimierungen treten ja in der Praxis denke ich recht oft auf. 
Außer Brute-Force fällt mir gerade gar nichts anderes ein. Aber wie 
würde man den Bruteforce Algorithmus aufbauen? Ich scheitere gerade 
daran alle Möglichkeit durchzuprobieren. Der Rest ist denke ich Recht 
einfach. Ich nehme ein Ergebnis Array. Darin speichere ich die Folge der 
Spalten. Und würde in der Schleife immer schauen, ob die Aktuelle 
Kombination besser ist, und wenn ja die in dieses Array schreiben. Aber 
an der Schleife scheitert es eben. Hat da jemand einen Tipp, wi man das 
ganze am effizientesten macht?

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nicht unbedingt immer "effizient" dafür effektiv, hängt stark davon ab 
wie gut man das Abbruchkriterium definieren kann:
http://de.wikipedia.org/wiki/Backtracking

Autor: Karl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das lese ich mir mal durch. Also im Prinzip gibt es ja bei meinem 
Problem m! Möglichkeiten wenn man von einer m x m Matrix ausgeht. Ich 
Versuche jetzt erst einmal ein Programm zu schreiben, was aus einem 
Alphabet (A,B,C) alle Möglichkeiten ausgibt, was ja genau mein Problem 
darstellt.

Die Ausgabe müsste ja irgendwie so sein:

ABC
ACB
BAC
BCA
CBA
CAB
#include <iostream>

using namespace std;
int main (int argc, char * const argv[]) {
  char buch[]= {'A','B','C'};
  return 0;
}

Hast du eine Idee, wie man da die Schleife für die m! Möglichkeiten 
gestalten könnte?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du musst soviele Schleifen inienanderschachteln, wie du Variablen hast.
Hier also 3 (1., 2., 3. Stelle).

In der innersten Schleife rechnest du den Wert der Zielfunktion aus
(wie gut oder schlecht ist die aktuelle Kombination).
Falls sie besser ist als alle bisherigen, dann merken.

Wo ist jetzt das Problem, außer daß die Rechenzeit beliebig hoch geht,
je nach Anzahl der Kombinationsmöglichkeiten?

Autor: Karl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mein Problem ist, dass es keine Dopplungen geben darf. Also AAA ist 
nicht erlaubt. Wie filtere ich das heraus.
  for (int i=0; i<3; ++i) {
    for (int j=0; j<3; j++) {
      for (int k=0; k<3; k++) {
        cout << i << j << k << endl;
      }
    }
  }

Schön wäre natürlich eine Rekursive Lösung.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl schrieb:
> for (int i=0; i<3; ++i) {
>     for (int j=0; j<3; j++) {
>       for (int k=0; k<3; k++) {
>         cout << i << j << k << endl;
>       }
>     }
>   }
  for (int i=0; i<3; ++i)
  {
    for (int j=0; j<3; j++)
    {
      if(j!=i)
      {
        for (int k=0; k<3; k++)
        {
          if( k!=i && k!=j )
          {
            cout << i << j << k << endl;
          }
        }
      }
    }
  }

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl schrieb:
> Schön wäre natürlich eine Rekursive Lösung.

Wenn du es mit Schleifen schon nicht schaffst, wieso soll es dann
unbedingt rekursiv sein? Schneller oder besser wird das davon auch
nicht.

Autor: Karl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke. So eine Lösung hatte ich auch schon. Das Problem dabei sind nur 
die ganzen Prüfungen auf Gleichheit bzw. die vielen Schleifen. Wenn man 
jetzt z.B. eine 100 x 100 Matrix hat ist das ja sehr unflexibel.

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Darf's C++ sein?
Dann könnte das mit next_permutation
http://www.sgi.com/tech/stl/next_permutation.html  und einer passenden 
Sortierung/Filterung gelöst werden.

(funktionale Sprachen sind bei so etwas deutlich im Vorteil)

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl schrieb:
> Mein Problem ist, dass es keine Dopplungen geben darf. Also AAA ist
> nicht erlaubt. Wie filtere ich das heraus.
>   for (int i=0; i<3; ++i) {
>     for (int j=0; j<3; j++) {
>       for (int k=0; k<3; k++) {
>         cout << i << j << k << endl;
>       }
>     }
>   }

Karl schrieb:
> Danke. So eine Lösung hatte ich auch schon.

Und wieso fragst du dann danach?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Arc Net schrieb:
> Darf's C++ sein?
> Dann könnte das mit next_permutation
> http://www.sgi.com/tech/stl/next_permutation.html  und einer passenden
> Sortierung/Filterung gelöst werden.
>
> (funktionale Sprachen sind bei so etwas deutlich im Vorteil)

Ja, mit C++ könnte man hier wahrscheinlich vieles reißen.
Aber auch da wird man vorher wissen müssen, was man will und das
auch formulieren können.

Je nachdem, ob wirklich die beste Lösung nötig ist (was ohne
zusätzliches Wissen vom Problem an irgendeiner Form von brute
force nicht vorbeiführen wird) oder nur eine sehr gute nahe der
besten reicht, kann man auch ganz andere Algorithmen in Betracht
ziehen. Aber wer weiß das schon!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl schrieb:
> Mein Problem ist, dass es keine Dopplungen geben darf. Also AAA ist
> nicht erlaubt. Wie filtere ich das heraus.

Im Allgemeinen Fall dadurch, dass du dir eine Funktion schreibst, die 
die aktuell untersuchte Lösung auf Zulässigkeit prüft. Ist die Lösung 
nicht zulässig, dann wird sie gleich wieder verworfen.

>
>
>   for (int i=0; i<3; ++i) {
>     for (int j=0; j<3; j++) {
>       for (int k=0; k<3; k++) {
>         cout << i << j << k << endl;
>       }
>     }
>   }
> 
>
> Schön wäre natürlich eine Rekursive Lösung.

Und damit bist du dann beim allgemeinen Backtracking Ansatz

void Untersuche( Aufgabenparameter )
{
  if( ist die Lösung komplett( Aufgabenparameter ) ) {

    eventuell:
    if( Lösung mittels( Aufgabenparameter ) ist besser als
        bisherige Lösungen )
      Aufgabenparameter als bisher beste Lösung peichern

    ansonsten
      Lösung ausgeben
  }

  else {
    variiere Aufgabenparameter systematisch in allen
    Möglichkeiten für einen etwas längeren Lösungsversuch {

      if( ist zulässig( Aufgabenparameter ) )
        Untersuche( Aufgabenparameter );
    }
  }
}

An deinem Beispiel, kanonisch umgesetzt
int constainsDuplicates( char * String )
{
  char * Check = String + 1;

  while( *String ) {
    Check = String + 1;
    while( *Check ) {
      if( *String == *Check )
        return 1;
      Check++;
    }
    String++;
  }
  return 0;
}

void Permute( int Length, char* String )
{
  if( Length == 3 ) {
    printf( "%s\n", String );
    return;
  }

  char c;
  for( c = 'A'; c < 'D'; ++c ) {
    String[Length] = c;
    String[Length+1] = '\0';

    if( !constainsDuplicates( String ) )
      Permute( Length + 1, String );
  }
}

int main()
{
  char Test[10];

  Permute( 0, Test );

  return 0;
}

Für einzelne Aufgabenstellungen gibt es des öfteren Vereinfachungen, wie 
zb in dieser Aufgabenstellung. Aber darum ging es mir nicht. Ich wollte 
absichtlich die Backtracking-Idee einfach 1:1 in ein Programm umsetzen.

Der kanonische Backtracking-Ansatz funktioniert allerdings immer. Er 
funktionioniert so gut, dass eine ganze Programmiersprache darum herum 
gebaut wurde: Prolog

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ansonsten gibt es auch noch dies hier:
http://de.wikipedia.org/wiki/Lineare_Optimierung

Allerdings fand ich im Studium Backtracing irgendwie eingänglicher ;)

Autor: mr. mo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
also hier ist was ganz interessantes dazu :

http://openbook.galileocomputing.de/c_von_a_bis_z/...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
mr. mo schrieb:
> also hier ist was ganz interessantes dazu :
>
> 
http://openbook.galileocomputing.de/c_von_a_bis_z/...



Vorsicht: "Brute Force"
ist kein Name eines Algorithmuses, sondern bedeutet einfach nur 'Rohe 
Gewalt'.
Gemeint ist, dass man ein Problem löst, indem man einfach rohe 
Rechengewalt darauf loslässt. Also nicht algorithmisch elegant an ein 
Problem rangehen, überlegen, Zusammenhänge suchen, sondern einfach mit 
der vollen Rechenpower die man zur Verfügung hat das Problem knacken. In 
gewissen Sinne so, wie einst Alexander den gordischen Knoten gelöst hat: 
Nicht lange nach dem Schnurenden suchen sondern mit dem Schwert 
draufhauen.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gerade bei Optimierungsproblemen sollte man sich Gedanken über 
dynamische Programmierung machen, meist kommt da was schlaues bei rum, 
was deutlich effizienter ist als Brute Force.
Noch dazu kommt dass es Probleme gibt, bei denen man nicht mit einem 
Greedy-Ansatz das Optimum findet und man dann auch zu dynamischer 
Programmierung greift.

Einfaches Einsteigerbeispiel:

Gegeben sei eine Kette von Matrixmultiplikationen (Gültigkeit 
vorausgesetzt) und die Dimensionen der einzelnen Matrizen:

A x B x C x D x ... x Z

Wie muss man klammern um die minimale Anzahl an Operationen zu 
erreichen? Ginge auch Brute Force, aber eben brutal langsam ;)

Beispiel:

A = 1000x1000
B = 1000x900
C = 900x2
D = 2x400

Wie klammert man A x B x C x D so dass ich möglichst wenig rechne?

((A x B) x (C x D))
(((A x B) x C) x D)
(A x (B x (C x D)))
((A x (B x C)) x D)
(A x ((B x C) x D))

wären da die Möglichkeiten.

Gute Lektüre dazu:

http://www.amazon.de/Introduction-Algorithms-Thoma...

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.