Bruteforce Optimierung

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

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

1

  for (int i=0; i<3; ++i)

2

  {

3

    for (int j=0; j<3; j++)

4

    {

5

      if(j!=i)

6

      {

7

        for (int k=0; k<3; k++)

8

        {

9

          if( k!=i && k!=j )

10

          {

11

            cout << i << j << k << endl;

12

          }

13

        }

14

      }

15

    }

16

  }

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.

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)

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?

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 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.

>
>

1

>   for (int i=0; i<3; ++i) {

2

>     for (int j=0; j<3; j++) {

3

>       for (int k=0; k<3; k++) {

4

>         cout << i << j << k << endl;

5

>       }

6

>     }

7

>   }

8

>

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

1

int constainsDuplicates( char * String )

2

{

3

  char * Check = String + 1;

4

5

  while( *String ) {

6

    Check = String + 1;

7

    while( *Check ) {

8

      if( *String == *Check )

9

        return 1;

10

      Check++;

11

    }

12

    String++;

13

  }

14

  return 0;

15

}

16

17

void Permute( int Length, char* String )

18

{

19

  if( Length == 3 ) {

20

    printf( "%s\n", String );

21

    return;

22

  }

23

24

  char c;

25

  for( c = 'A'; c < 'D'; ++c ) {

26

    String[Length] = c;

27

    String[Length+1] = '\0';

28

29

    if( !constainsDuplicates( String ) )

30

      Permute( Length + 1, String );

31

  }

32

}

33

34

int main()

35

{

36

  char Test[10];

37

38

  Permute( 0, Test );

39

40

  return 0;

41

}

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

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 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.