Entwickler-Ecke :: Thema anzeigen

Tino - Di 11.06.02 10:57
Titel: Algorithmen

Algorithmen

Autor: Tomac
E-Mail: tomac@gmx.at
Quelle: http://www.coder-area.de

ALGORITHMEN -- TEIL 1

ITERATIVE Algorithmen
Iterative Algorithmen dienen dazu, Probleme mit Hilfe einer Schleifenkonstruktion zu lösen. Die Lösung erhält man dadurch, indem eine Schleife etliche Male durchalufen wurd, wobei es sich aber entweder um eine von den Durchläufen (=Iterationen) her endliche Schleife oder um eine Schleife mit einer Abbruchbedingung handeln kann. Man kann also sagen, dass alle Probleme mit eine Schleife gelöst werden können, allerdings ist das in manchen Fällen relativ umständlich. Und aus diesem Grund verwendet man andere Methoden.

Fibonacci-Zahlen
Die Fibonacci-Zahlen sind eine Zahlenkette, bei er das nächste Element jeweils aus der Summe der beiden Vorgänger- Elemente berechnet wird.
Die Fibonacci-Zahlen sind ein gutes Beispiel für eine Schleifenfunktion, weil man gut sehen kann, wie Probleme auf verschiedene Arten angegangen werden können.

Die Reihe sieht also so aus:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

x1 = 0
x2 = 1
x3 = x1+x2 = 0+1 = 1
x4 = x2+x3 = 1+1 = 2
x5 = x3+x4 = 1+2 = 3
x6 = x4+x5 = 3+2 = 5
x7 = x5+x6 = 5+3 = 8

Die resultierende Reihe sieht folgendermaßen aus:

Delphi-Quelltext

1:	0-1-1-2-3-5-8-13-21-34-55-89-144-...

Unser Problem ist nun, die ersten 20 Zahlen dieser Kette darzustellen. Die ersten beiden Glieder (0, 1) sind von vornherein vorgegeben. So ist es ganz einfach, die Fibonacci-Zahlen mittels einer Schleife zu berechnen:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

procedure FibonacciIter(Anzahl: integer);
var
  Fib: array of integer;
  j: integer;
Begin
  SetLength(Fib, Anzahl);
  Fib[0]:=0;
  Fib[1]:=1;
  For j:= 2 to Anzahl-1 do
    Fib[j]:=Fib[j-1]+Fib[j-2];
End;

So wird das Problem also iterativ gelöst. Diese Lösung ist im Vergleich zur rekursiven (Wird weiter unten besprochen) Lösung eindeutig die bessere.

REKURSIVE Algorithmen
Man kann dieses Problem auch anders angehen, nämlich indem man eine rekursive Lösung programmiert. Rekursiv bedeutet, die Funktion wird solange aufgerufen, bis der Endwert erreicht ist. Rekursive Funktionen rufen sich selbst auf, es werden innerhalb der Funktion oder Prozedur Werte berechnet, die dann der Prozedur beim Aufruf übergeben
werden. Da die Werte bei jedem Aufruf dieser Prozedur/ Funktion verändert werden, wird irgendwann ein Wert erreicht, der dem endgültigen Ergebnis entspricht - Die rekursive Schleife wird verlassen!

Doch es gibt dabei eine Gefahr, auf die man achten muss. Und zwar die Abbruchbedingung. Es muss wirklich sicher sein, dass sie auch wirklich aufgerufen wird, ansonsten gerät man in eine Endlosschleife, und ihr wisst ja sicher alle, was das bedeuten würde.

Um noch mal auf die Fibonacci- Zahlen zurückzukommen, unser Problem ist nun, diese Zahlen in eine rekursive Form zu bringen. Mathematisch sieht das ganze ja so aus:

Delphi-Quelltext

1:	f(x) = f(x-1) + f(x-2) mit f(1) = 0 und f(2) = 1

Die rekursive Funktion sieht daher so aus:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

Function TForm1.Fiboncci(Index: integer): integer;
Begin
  if Index < 2 then
    result:=Index // Weil der Index unter 2
  // gleich dem Ergebnis ist
  else
    result:=Fibonacci(Index-1)+Fibonacci(Index-2);
End;

ALGORITHMEN -- TEIL 2

BACKTRACKING
Backtracking- Algorithmen sind eine völlig andere Art von Algorithmen.
Sie arbeiten nach einem interessanten Prinzip, welches vergleichbar mit der Lernfähigkeit von Affen ist *g*, sie arbeiten mit Versuch und Irrtum .
Dennoch ist es eine einfache Möglichkeit, alle möglichen vorkommenden Aspekte eines Problems durchzuspielen.

Jetzt wird's interessant. Ich gehe jetzt das Dame-Problem an.

Das Dame-Problem
Zuerst eine Kurze Beschreibung: Es geht darum, auf einem Schachbrett acht Damen so zu platzieren, dass keine Dame eine andere bedroht. Nebenbei kann man auch noch herausfinden, wie viele Lösungsmöglichkeiten es git.

Wenn ihr euch das mal durch den Kopf gehen lasst, werdet ihr merken, dass es doch eigentlich relativ einfach zu lösen ist. Denn wenn keine Dame die andere bedrohen darf, dürfen sie nicht übereinander oder nebeneinander stehen. Das Schachbrett hat acht Spalten, es darf also nur je eine Dame in einer Spalte sein, dann muss überprüft werden, ob sie eine andere bedroht (In diesem Fall wird sie eine Zeile weitergezogen) und dann muss die nächste kontrolliert werden. Ist aber eine Dame schon ganz unten am Schachbrett, ohne dass es eine Position ohne Bedrohung gab, muss die vorherige Dame eins weiter gezogen und konntrolliert werden.
So muss es irgendwann zu einer Lösung kommen, wie schon erwähnt durch Versuch und Irrtum.

So, fürs erste genug erklärt. Hier die Funktion, weiter unten werde ich sie dann genauer Besprechen:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

TYPE
  TDameArray = ARRAY[1..8] OF Byte;

{...}

Procedure TForm1.Dame;
Var
  Damen: TDameArray;
  i: integer;
  act_Dame: Byte;
Begin
  For i:= 1 to 8 do
    Damen[i.] := 0;
  act_Dame := 1; //Erste Dame bearbeiten
  Loesung := 0; //Null Lösungen
  //Dame-Funktion
  REPEAT;
    REPEAT;
      inc(Damen[Act_Dame]);
      IF Damen[Act_Dame]<9 THEN
        BEGIN;
          IF NoCollision(Damen,Act_Dame) THEN
            IF Act_Dame<8 THEN
              inc(Act_Dame)
            ELSE
              inc(Loesung); //Lösung gefunden
        END;
    UNTIL Damen[Act_Dame]>8; //Alle Felder durchgespielt
    Damen[Act_Dame] := 0;
    Dec(Act_Dame);
  UNTIL (Act_Dame=0); //Bis keine Dame mehr übrig
END;

Ich möchte nun zuerst auf die Funktionsweise der Funktion eingehen. Zuerst werden alle Werte auf einen Grundwert gesetzt. Die erste Dame, die bearbeitet wird, ist Dame Nummer 1. Die Anzahl der Lösungen wird auf 0 gesetzt, ebenso die Position aller Damen.

Der Algorithmus selbst arbeitet folgendermaßen, wie oben schon kurz erklärt: Es wird mit der ersten Dame begonnen und sie wird auf das erste Feld ihrer Spalte gesetzt. Wenn es keine Bedrohung gibt, wird die nächste Dame genommen und auf ein Feld gesetzt. Nun wird ihr Feld so lange erhöht, bis keine Bedrohung mehr vorhanden ist oder sie auf dem letzten Feld landet. Gibt es keine Bedrohung einer Dame, wird natürlich wieder die
nächste genommen...

Ist eine Dame auf dem letzten Feld angekommen und es gab in allen Positionen eine Bedrohung, wird bei der Vorgängerdame eine Position verändert. In diesem Fall wird die Position unserer Dame wieder auf Null gesetzt, damit sie von oben anfangen kann. Die Position der Vorgängerdame wird so lange um 1 erhöht, bis es keine Kollision mehr gibt oder sie auf dem letzten Feld angekommen ist. Gibt es keine Kollision, wird zur nächsten Dame gesprungen und sie wird ein Feld weitergesetzt. Gibt es eine Kollision, naja, dann beginnt das ganze von vorne!

Am einfachsten zu verstehen ist das ganze, wenn ihr es zu Hause auf einem echten Schachbrett ausprobiert.

ALGORITHMEN -- TEIL 3

Das ist nun der letzte Teil dieses "Kurses". Es geht jetzt nur noch um die Kontrolle der Kollisionen bei der Programmierung des Dame Problems. Wer möchte, dem kann ich ein Beispielprogramm schicken!

Die Kontrolle der Kollisionen

Zuerst mal der Code:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

FUNCTION TForm1.collision(Damen: TDameArray; Anz: Integer): boolean;
var
  i:integer;
BEGIN
  Result:=true;
  if Anz>1 then begin
    For i:=Anz-1 downto 1 do
      if (Damen[i.]=Damen[Anz]) then
        result:=false;
  end;
  if Result and (Anz>1) then begin
    for i:=Anz-1 downto 1 do
      if abs(Damen[i.]-Damen[Anz])= abs(i-anz) then
        result:=false;
  end;
end;

Eigentlich sollte diese Funktion für die meisten kein Problem darstellen. Übergeben wird das Array mit den Positionen der Damen und die Variable Anz, die angibt, wieviele Damen kontrolliert werden müssen.

In der Funktion wird kontrolliert, ob es eine Kollision in horizontaler oder diagonaler Richtung gibt. Vertikal braucht man nicht zu prüfen, da ja sowieso jede Dame in einer eigenen Spalte sitzt. Im Falle einer Kollision gibt die Funktion false zurück, wenn es keine gibt, true.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!