Bruteforce Optimierung

[Karl (Gast)]

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?

[Läubi .. (laeubi)]

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

[Karl (Gast)]

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?

[Klaus W. (mfgkw)]

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?

[Karl (Gast)]

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.

[Klaus W. (mfgkw)]

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;
          }
        }
      }
    }
  }

[Klaus W. (mfgkw)]

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.

[Karl (Gast)]

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.

[Arc N. (arc)]

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)

[Klaus W. (mfgkw)]

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?

[Klaus W. (mfgkw)]

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!

[Karl H. (kbuchegg)]

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

[Läubi .. (laeubi)]

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

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

[mr. mo (Gast)]

also hier ist was ganz interessantes dazu :

http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_006.htm#mjf7d6e5fb93d300365b9df366326bcc13

[Karl H. (kbuchegg)]

mr. mo schrieb:
> also hier ist was ganz interessantes dazu :
>
> 
http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_006.htm#mjf7d6e5fb93d300365b9df366326bcc13



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.

[D. I. (Gast)]

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-Thomas-H-Cormen/dp/0262533057/ref=sr_1_1?ie=UTF8&qid=1293225360&sr=8-1