Einführungskurs/Binäre Suche

Wiki-Quelltext dieser Seite.

<language>Java</language>
== Raten einer Zahl ==

Wir kennen das einfache Spiel zum Raten einer Zahl <math>z</math> im Intervall <math>1 \le z \le max</math>:<br />
Aus einem zuvor vereinbarten Intervall denkt sich ein Spieler eine Zahl, die sein Mitspieler erraten muss. Nach jedem Versuch erhält der Mitspieler den Hinweis, ob seine vermutete Zahl kleiner bzw. größer als die erdachte Zahl ist oder sogar mit ihr übereinstimmt. Die erdachte Zahl soll so mit einem Minimum an Versuchen erraten werden.<br />
Zunächst spielen wir gegen den Computer und erraten eine Zufallszahl:

<code id="4d17b66196be3" hidden>
public Object ZahlenRaten(int max) {
 int ZufZahl = (int)(Math.random()*max+1);
 int Anzahl = 0;

 JLabel myLabel1 = new JLabel("Deine Zahl:"); 
 JLabel myLabel2 = new JLabel();
 JTextField myTextField = new JTextField();
 JButton myButton1 = new JButton("Zahl raten");
 JButton myButton2 = new JButton(" Beenden ");
 JPanel myPanel1 = new JPanel();
 JPanel myPanel2 = new JPanel();
 JPanel myPanel3 = new JPanel();

 myTextField.setColumns(8);

 myFrame = new JFrame("Zahlenraten");
 myFrame.setSize(300, 125);
 myFrame.setLocationRelativeTo(null);

 myPanel1.add(myLabel1);
 myPanel1.add(myTextField);
 myPanel2.add(myLabel2);
 myPanel3.add(myButton1);
 myPanel3.add(myButton2);

 myFrame.getContentPane().setLayout(new BorderLayout());
 myFrame.getContentPane().add(myPanel1, BorderLayout.NORTH);
 myFrame.getContentPane().add(myPanel2, BorderLayout.CENTER);
 myFrame.getContentPane().add(myPanel3, BorderLayout.SOUTH);
 myFrame.setResizable(false); 
 myFrame.setVisible(true);
    
 myButton1.addActionListener(this);
 myButton2.addActionListener(this);
    
 private void actionPerformed(ActionEvent Ereignis) {
  int RatZahl = 0;
  if (Ereignis.getSource() == myButton1)
   try {
    RatZahl = Integer.parseInt(myTextField.getText());
   }
   catch (NumberFormatException Ereignis) {
    myLabel2.setText("Eingabefehler!");
   }
  else if (Ereignis.getSource() == myButton2)
   myFrame.dispose();
  else
   myFrame.dispose();
  if (RatZahl > 0) {
   Anzahl++;
   if (RatZahl < ZufZahl)
    myLabel2.setText("Die Zahl "+RatZahl+" ist zu klein.");
   else if (RatZahl > ZufZahl)
    myLabel2.setText("Die Zahl "+RatZahl+" ist zu groß.");
   else
    myLabel2.setText("Du hast die Zahl "+RatZahl+" mit "+Anzahl+" Versuch(en) erraten!");
  }
 }

 return this;
}

public void SpielerRaten(int max) {
 Object myZahlenRaten = ZahlenRaten(max);
 System.out.println("ok");
}
</code>

<run id="4d17b66196d46">
SpielerRaten(100);
</run>

== Computerraten einer Zahl ==

Natürlich ist ein Erraten der Zahl durch sequenzielle Suche möglich. Allerdings wissen wir, dass die Suche durch Intervallhalbierung wesentlich effizienter ist.<br />
Das Raten einer Zahl soll nun der Computer übernehmen. Dazu wollen wir selbstverständlich die ''effizientere'' Spielstrategie umsetzen:

 ComputerRaten(47, 100);
 --> 5

Die zu implementierende Funktion <tt>ComputerRaten</tt> soll die Anzahl der benötigten Versuche zurück geben. 

<code id="4d149f713676d" hidden>
public int ComputerRatenLsg(int zahl, int max) {
 int anz = 0;
 private int Suche(int li, int z, int re) {
  anz++;
  int mi = (re+li)/2;
  if (z == mi)
   return anz;
  else if (z < mi)
   return Suche(li, z, mi);
  else
   return Suche(mi, z, re);
 }
 return Suche(1, zahl, max+1);
}
</code>

<code id="4d149f713688a">
public int ComputerRaten(int zahl, int max) {
 int anz = 0;
 // Implementation der effizienten Spielstrategie
 return anz;
}
</code>

<check>
int Diff = 3;
return ((Math.abs(ComputerRaten(47, 100) - ComputerRatenLsg(47, 100)) < Diff) 
        && (Math.abs(ComputerRaten(12345, 55555) - ComputerRatenLsg(12345, 55555)) < Diff));
</check>

<run id="4d14945f71b09">
ComputerRaten(47, 100);
</run>

Diese Strategie scheint tatsächlich schnell zum Erfolg zu führen, da in jedem weiteren Programmdurchlauf die Suche auf das halbe Suchintervall reduziert wird.<br /> 
Man bezeichnet einen derartigen Suchalgorithmus als ''binäre Suche''.<br />
Wir testen unseren Algorithmus mit Zufallszahlen:

<code id="4d16210a13d64">
public int ZufallsZahl(int max) {
 return (int)(Math.random()*max+1);
}
</code>

<run id="4d16210a13f7f">
ComputerRaten(ZufallsZahl(100000), 100000);
</run>

== Effizienz beim Raten einer Zahl ==

Wie viele Versuche sind mit binärer Suche im Mittel in einem vorgegebenen Intervall notwendig?<br />
Bei unseren weiteren Überlegungen wollen wir davon ausgehen, dass jeder Versuch genau einem "Zeittakt" entspricht.<br />

=== Empirische Effizienzuntersuchungen ===

Nun können wir empirische (empirisch: aus der Erfahrung oder Beobachtung) Effizienzuntersuchungen vornehmen.<br />
Dazu definieren wir zweckmäßigerweise eine Funktion <tt>ComputerRatenN</tt>, die im Gegensatz zu <tt>ComputerRaten</tt> die Anzahl der benötigten Versuche als arithmetisches Mittel mehrerer Versuche zurück gibt. Dabei werden die Zufallszahlen im mit <tt>max</tt> begrenzten Intervall "erraten":

<code id="4d237ee6329dd" hidden>
public double ComputerRatenNLsg(int max, int anzahl) {
 double summe = 0;
 for(int i = 1; i <= anzahl; i++)
  summe = summe+ComputerRaten(ZufallsZahl(max), max);
 return summe/anzahl;
}
</code>

<code id="4d17021418ff7">
public double ComputerRatenN(int max, int anzahl) {
 double wert = 0;
 // Implementation der Mittelwertbildung
 return wert;
}
</code>

<check>
double relDiff = 0.2;
return ((Math.abs(ComputerRatenN(1000, 100)-ComputerRatenNLsg(1000, 100))/ComputerRatenNLsg(1000, 100) < relDiff)
        && (Math.abs(ComputerRatenN(5432, 123)-ComputerRatenNLsg(5432, 123))/ComputerRatenNLsg(5432, 123) < relDiff));
</check>

<run id="4d237ee632ca9">
ComputerRatenN(100000, 100);
</run>

=== Experimente ===

Wir automatisieren nun das Raten einer Zahl in mehreren Intervallen. Dazu soll die obere Grenze des Suchintervalls von <tt>min</tt> zu <tt>max</tt> in einer frei wählbaren <tt>schrittweite</tt> variiert werden. Der Parameter <tt>anzahl</tt> beschreibt wieder, wie viele Suchvorgänge in jedem Intervall durchgeführt werden. Die Untersuchungsergebnisse werden in einem Balkendigramm veranschaulicht:

<code id="4d276362d3fad" hidden>
public Object BalkenDiagramm(Object canvas, Object turtle) {
 double Rand = 50;
 double MaxBreite = 400-2*Rand;
 double MaxHoehe = 300-2*Rand;

 private double[] MinMax(double[] liste) {
  double[] Ergebnis = {0, 0};
  for (int i = 0; i < liste.length; i++) {
   if (Ergebnis[0] > liste[i]) Ergebnis[0] = liste[i];
   if (Ergebnis[1] < liste[i]) Ergebnis[1] = liste[i];
  }
  return Ergebnis;
 }

 private void Balken(double hoehe, double breite) {
  turtle.forward(breite); turtle.left(90); 
  turtle.forward(hoehe); turtle.left(90);
  turtle.forward(breite); turtle.left(90);
  turtle.forward(hoehe); turtle.left(90);
  turtle.forward(breite); 
 }

 public void Darstellung(double[] liste) {
  double[] ExtremWert = new double[2];
  ExtremWert = MinMax(liste);
  double Min = ExtremWert[0];
  double Max = ExtremWert[1];
  double Breite = MaxBreite/liste.length; 
  canvas.clear();
  turtle.hide();
  turtle.move(Rand, Rand+Max/(Max-Min)*MaxHoehe);
  turtle.right(90);
  for (int i = 0; i < liste.length; i++)
   Balken(liste[i]/(Max-Min)*MaxHoehe, Breite);
 }

 return this;
}
</code>

<code id="4d2797086dc2e">
public void Experiment(int min, int max, int schrittweite, int anzahl) {
 int n = (max-min)/schrittweite+1;
 double[] liste = new double[n];
 for (int i = 0; i < n; i++) {
  liste[i] = ComputerRatenN(min+i*schrittweite, anzahl);
  System.out.println("f("+(min*i+schrittweite)+") = "+liste[i]);
 }
 Object BalkenDiagramm1 = BalkenDiagramm(canvas1, turtle1);
 BalkenDiagramm1.Darstellung(liste);
}
</code>

<canvas w="400" h="300"></canvas>

<run id="4d2797086de8a">
Experiment(200, 10000, 200, 1000);
</run>

'''Ergebnisse:'''<br />

<ul>
<li>
Die binäre Suche führt im Vergleich zur sequenziellen Suche wesentlich schneller zum Erfolg.
</li>
<li>
Der Zeitaufwand wächst bei zunehmender Problemgröße (Suchintervall) langsamer an.<br />
Offensichtlich ist dieser Algorithmus bei umfassender Problemgröße sehr effizient.
</li>
</ul>

== Aufgaben ==

<ol>
<li>
Ermitteln Sie für das Raten einer Zahl die mögliche funktionale Abhängigkeit
<math>\mbox{Zeitaufwand} = f(\mbox{Problemgr\"o\ss e)}</math>.<br />
Testen Sie dazu geeignete Regressionsmodelle mit der Tabellenkalkulation oder einem grafikfähigen Taschenrechner.
</li>
<li>
Die Nullstellensuche durch Intervallschachtelung ist eine typische Anwendung der binären Suche.<br />
Verallgemeinern Sie das Raten einer Zahl und die Nullstellensuche zu einer Problemklasse, auf die eine binäre Suche anwendbar ist.
</li>
</ol>

== Zum Weiterarbeiten ==

=== Extremwertsuche nach dem Verfahren des Goldenen Schnitts ===

Die binäre Suche muss nicht zwingend zur Intervallhalbierung führen.<br />
Ein interessanter Algorithmus ist die Extremwertsuche nach dem Verfahren des Goldenen Schnitts. Dabei werden die Suchintervalle asymmetrisch geteilt.<br />
Wir betrachten das Verfahren zunächst für die Suche eines lokalen Minimums:

<table border="0">
<tr>
<td align="center">
[[Bild:Extremwert.gif]]<br />
Animation: Minimumsuche nach dem Verfahren des Goldenen Schnitts
</td>
<td>'''Algorithmus''' (Minimumsuche):
<ul>
<li>Lege ein Suchintervall durch zwei äußere Intervallgrenzen fest.</li>
<li>Zerlege dieses Suchintervall durch einen ''zweimaligen'' Goldenen Schnitt in 3 Teilintervalle.</li>
<li>Berechne die Funktionswerte an beiden Schnittstellen.</li>
<li>Das neue Suchintervall wird aus der Schnittstelle mit dem größeren der beiden Funktionswerte und einer der äußeren Intervallgrenzen derart gebildet, dass die Schnittstelle mit dem ''kleineren'' Funktionswert ''eingeschlossen'' wird.</li>
<li>Führe im neuen Suchintervall den Goldener Schnitt durch, der wieder zu 3 Teilintervallen führt.</li>
<li>Wiederhole das Verfahren solange, bis das Suchintervall einer hinreichend kleinen &epsilon;-Umgebung genügt.</li>
<li>Der Funktionswert eines Arguments aus dieser &epsilon;-Umgebung entspricht dem gesuchten Minimum.</li>
</ul>
</td>
</tr>
</table>

Implementieren Sie den Algorithmus zur binären Suche lokaler Extremwerte (Minima <u>und</u> Maxima!) einer zuvor definierten mathematischen Funktion.<br />
Legen Sie dazu unter Ihrem PWiki-Zugang eine neue Seite mit der Bezeichnung <tt>&lt;PWiki-Name&gt;/Extremwertsuche</tt> an.<br />

Zum [[Einführungskurs/Extremwertsuche|Erwartungsbild]].