contest.tex

数据挖掘中de一个算法 hamster的实例

\begin{fndoc}{move}
\name     ``move hamster forward'' --- Vorw"artsbewegen des Hamsters
\synopsis {\tt move: INTEGER }
\descript Der Hamster wird in seiner aktuellen Blickrichtung um ein
          Feld vorw"arts bewegt. Dies gelingt nat"urlich nur, wenn sich
          vor dem Hamster keine Wand befindet.
\result   Falls sich vor dem Hamster keine Wand befindet und er folglich
          vorw"arts bewegt werden kann, ist das Ergebnis~0. Anderenfalls
          wird -1 zur"uckgegeben.
\end{fndoc}

\begin{fndoc}{turn}
\name     ``turn hamster'' --- Drehen des Hamsters
\synopsis {\tt turn (t: INTEGER) }
\descript Der Hamster wird um $90^o$ in die Richtung gedreht, die der
          Parameter {\tt t} angibt. F"ur diesen Parameter sind in der
          Datei {\tt hamster.e} folgende symbolische Konstanten
          definiert: \\[1ex]
          \begin{tabular}{ll}
          \tt pos   & Drehen im mathematisch positiven Sinn.       \\
          \tt neg   & Drehen im mathematisch negativen Sinn.       \\
          \tt left  & Drehen von der Blickrichtung aus nach links. \\
          \tt right & Drehen von der Blickrichtung aus nach rechts.
          \end{tabular}\\[1ex]
          Die Werte {\tt pos} und {\tt left} entsprechen (bei Blick
          von oben) einem Drehen gegen den Uhrzeigersinn, die Werte
          {\tt neg} und {\tt right} einem Drehen im Uhrzeigersinn.
\end{fndoc}

\begin{fndoc}{take}
\name     ``take some corn'' --- Aufnehmen einiger Maisk"orner
\synopsis {\tt take (amount: INTEGER) }
\descript Der Hamster nimmt so viele Maisk"orner auf, wie der Parameter
          {\tt amount} angibt. Dazu m"ussen nat"urlich auf dem
          aktuellen Feld gen"ugend viele Maisk"orner liegen, sonst
          werden entsprechend weniger Maisk"orner aufgenommen.
          Au\3erdem mu\3 der Hamster noch mindestens {\tt amount}
          Maisk"orner aufnehmen k"onnen. Ist die aktuelle Maiskornlast
          des Hamsters vermehrt um {\tt amount} gr"o\3er als die in der
          Datei {\tt hamster.e} definierte Konstante {\tt max\_load},
          so werden ebenfalls entsprechend weniger K"orner aufgenommen.
\result   Die Zahl der tats"achlich aufgenommenen Maisk"orner.
\end{fndoc}

\begin{fndoc}{drop}
\name     ``drop some corn'' --- Ablegen einiger Maisk"orner
\synopsis {\tt drop (amount: INTEGER): INTEGER }
\descript Der Hamster legt so viele Maisk"orner ab, wie der Parameter
          {\tt amount} angibt. Dazu mu\3 der Hamster nat"urlich
          mindestens {\tt amount} Maisk"orner tragen. Tr"agt er weniger,
          werden auch entsprechend weniger Maisk"orner abgelegt.
          Au\3erdem darf durch die abgelegten K"orner der Maiskornhaufen
          auf dem aktuellen Feld nicht gr"o\3er als {\tt max\_corn}
          Maisk"orner werden ({\tt max\_corn} ist in der Datei
          {\tt hamster.e} definiert). Anderenfalls werden entsprechend
          weniger K"orner abgelegt. Letztere Regelung gilt nicht f"ur
          das Startfeld. Auf diesem k"onnen beliebig viele Maisk"orner
          abgelegt werden.
\result   Die Zahl der tats"achlich abgelegten Maisk"orner.
\end{fndoc}

%-----------------------------------------------------------------------

\subsubsection{Die Steuerfunktion}

Die in diesem Abschnitt beschriebene Methode, die nicht zur
Hamsterklasse sondern zur Steuerklasse geh"ort, ist nur in einer
trivialen Form zur Funktionspr"ufung (Drehen des Hamsters auf dem
Ausgangsfeld) vorgegeben. Sie ist vom Wettbewerbsteilnehmer zu
schreiben und soll den Hamster durch das Labyrinth steuern.

\begin{fndoc}{control}
\name     ``control hamster'' --- Steuern des Hamsters
\synopsis {\tt control (hamster: HAMSTER) }
\descript Diese Funktion soll den Hamster steuern. Sie ist vom
          Wettbewerbsteilnehmer zu schreiben. Sie wird aufgerufen (von
          der Methode {\tt make} der Basis-Steuerklasse {\tt CLIENT}),
          wenn der Hamster auf dem Startfeld im Labyrinth ausgesetzt
          wurde. Der zu steuernde Hamster {\tt hamster} ist eine Instanz
          der Klasse {\tt HAMSTER} und verf"ugt demzufolge "uber alle in
          den beiden vorhergehenden Abschnitten beschriebenen Methoden.
          So bedeutet z.B.\ {\tt hamster.turn(hamster.left)}, da\3 sich
          der Hamster um $90^o$  nach links drehen soll. Diese Methode
          sollte erst dann beendet werden, wenn so viele Maisk"orner
          gesammelt wurden wie m"oglich.
\end{fndoc}

%-----------------------------------------------------------------------

\subsection{Programmierschnittstelle f"ur Pascal}
\label{sec.ctrl.pascal}

Die Programmierschnittstelle f"ur Pascal ist zur Zeit noch in der
Entwicklung und wird daher hier noch nicht beschrieben. Sie wird
der Programmierschnittstelle f"ur C analog sein.

%-----------------------------------------------------------------------

\section{Wie man ein Hamster-Steuerprogramm schreibt}
\label{sec.myhamster}

%-----------------------------------------------------------------------

\subsection{Das Beispielprogramm}
\label{sec.exprog}

In diesem Abschnitt wird beschrieben, wie man ein eigenes
Hamster-Steuerprogramm schreibt, "ubersetzt und auf einem Labyrinth
ausf"uhren l"a\3t.

Dem Hamster-Programmpaket ist ein Beispielprogramm beigef"ugt, das
zeigt, wie ein Ham\-ster-Steuerprogramm aussehen kann. Nat"urlich ist
dieses Programm keine gute L"osung des gestellten Problems (sondern
sogar eine sehr schlechte). Aber dieses Programm soll ja auch nur
deutlich machen, wie man ein Hamster-Steuerprogramm schreibt, und
nicht schon die L"osung mitliefern. Um ein eigenes Steuerprogramm zu
schreiben, geht man am besten von diesem Beispielprogramm aus, das
f"ur die Programmiersprache~C in Abschnitt~\ref{sec.exprog.c} und f"ur
die Programmiersprache Eiffel in Abschnitt~\ref{sec.exprog.eiffel}
beschrieben ist. Die "Ubersetzung eines eigenen Programms wird in
Abschnitt~\ref{sec.compile} gezeigt. Abschnitt~\ref{sec.exec}
schlie\3lich erl"autert, wie man das "ubersetzte Programm im
Labyrinthprogramm startet.

%-----------------------------------------------------------------------

\subsubsection{Das Beispielprogramm in C}
\label{sec.exprog.c}

Das Beispielprogramm, das in Abbildung~\ref{fig.exprog.c} gezeigt ist,
steuert den Hamster auf einem mehr oder minder zuf"alligen Weg f"unfzig
Z"uge lang durch das Labyrinth. W"ahrend dieser Wanderschaft werden
so viele Maisk"orner gesammelt wie m"oglich. Wenn zuf"allig das
Ausgangsfeld wieder erreicht wird, werden die gesammelten Maisk"orner
abgelegt.

\begin{figure}[t]
\begin{verbatim}
/*----------------------------------------------------------------------
  File    : control.c
  Contents: hamster control program
  Author  : Christian Borgelt
  History : 16.10.1997 file created
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "hamster.h"

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

void hms_ctrl (HAMSTER *hms)
{                               /* --- hamster control function */
  int x, y;                     /* coordinates of current field */
  int movecnt = 0;              /* number of moves made */
  int turn;                     /* turn direction (HMS_POS/HMS_NEG) */

  while (movecnt < 50) {        /* make 50 (field to field) moves */
    hms_pos(hms, &x, &y);       /* get current position in maze */
    if ((x == 0) && (y == 0))   /* if we are at home (initial pos.), */
      hms_drop(hms, HMS_MAXLOAD);    /* drop all the corn we have */
    else if (hms_corn(hms))     /* if there is corn on the field, */
      hms_take(hms, HMS_MAXLOAD);    /* take as much as we can carry */
    if ((hms_look(hms) == HMS_WALL)  /* if the way is blocked */
    ||  (RAND_MAX/4 -rand() > 0)) {  /* or just because it's funny */
      turn = (RAND_MAX/2 -rand() > 0) ? HMS_POS : HMS_NEG;
      do { hms_turn(hms, turn); /* turn hamster in random direction */
      } while (hms_look(hms) == HMS_WALL);
    }                           /* until no wall blocks the way */
    hms_move(hms); movecnt++;   /* move the hamster forward */
  }                             /* and count the move made */
}  /* hms_ctrl() */
\end{verbatim}
\caption{Ein Beispiel-Steuerprogramm in C, das dem Programmpaket
         beigef"ugt ist. Es steuert den Hamster f"ur 50 (Feld zu Feld)
         Z"uge auf zuf"allige Weise durch das Labyrinth. W"ahrend seiner
         Wanderung nimmt der Hamster so viele Maisk"orner auf wie er
         kann und legt sie ab, wenn er zuf"allig wieder das Ausgangsfeld
         erreicht.\label{fig.exprog.c}}
\end{figure}

%-----------------------------------------------------------------------

Das Beispielprogramm besteht aus einer {\tt while}-Schleife, in der
bei jedem Durchlauf ein (Feld zu Feld) Zug des Hamsters ausgef"uhrt
wird. Der mitgef"uhrte Zugz"ahler, der in jedem Schleifendurchlauf
erh"oht wird, stellt sicher, da\3 genau 50 Z"uge ausgef"uhrt werden.

Am Anfang der Schleife wird die Position des Hamsters im Labyrinth
durch einen Aufruf der Funktion {\tt hms\_pos} ermittelt. Die Parameter
{\tt x} und {\tt y} m"ussen mit dem Adressoperator {\tt \&} versehen
sein, da die Funktion {\tt hms\_pos} sich nicht f"ur den Inhalt der
Variablen {\tt x} und {\tt y} interessiert, sondern wissen mu\3, an
welche Stellen sie die Positionskoordinaten zu schreiben hat (vgl.\
die bekannte Funktion {\tt scanf}).

Anschlie\3end wird gepr"uft, ob beide Koordinaten den Wert 0 haben.
Die Position $(0,0)$ ist, siehe Abschnitt~\ref{sec.control}, das
Startfeld. Auf diesem sollen alle gesammelten Maisk"orner abgelegt
werden. Folglich wird versucht, durch einen Aufruf der Funktion
{\tt hms\_drop} so viele Maisk"orner abzulegen, wie der Hamster
h"ochstens tragen kann. Falls er weniger tr"agt, werden ja (siehe
die Beschreibung der Funktion {\tt hms\_drop}) entsprechend weniger
abgelegt. Nach diesem Aufruf sind die Backen des Hamsters auf jeden
Fall leer.

Falls sich der Hamster nicht auf dem Startfeld befindet, wird durch
einen Aufruf der Funktion {\tt hms\_corn} gepr"uft, ob sich auf dem
Feld Maisk"orner befinden. Hier kann auf eine genaue Abfrage der Zahl
verzichtet werden, da nur interessiert, ob sich auf dem Feld Mais
befindet oder nicht. Nun wird die Zahl 0 in C als falsch, jede andere
Zahl als wahr gewertet. Folglich kann das Ergebnis der Funktion
{\tt hms\_corn} einfach als Wahrheitswert interpretiert werden.

Befindet sich Mais auf dem Feld, wird durch einen Aufruf der Funktion
{\tt hms\_take} versucht, so viele Maisk"orner aufzunehmen, wie der
Hamster h"ochstens tragen kann. Falls seine Backen bereits (teilweise)
voll sind, so werden die "uberz"ahligen K"orner einfach liegengelassen.
Wenn sich weniger Maisk"orner auf dem Feld befinden als der Hamster noch
tragen k"onnte, werden nur diese aufgenomen (siehe die Beschreibung der
Funktion {\tt hms\_take}).

Nachdem Korn aufgenommen oder abgelegt wurde, wird die Richtung
bestimmt, in die sich der Hamster bewegen soll. Dazu wird zun"achst
durch einen Aufruf der Funktion {\tt hms\_look} gepr"uft, ob der
Hamster vor einer Wand steht. Ist dies der Fall, mu\3 er auf jeden
Fall seine Richtung wechseln. Aber auch wenn der Weg frei ist, wird
"uber einen Zufallsmechanismus mit der Wahrscheinlichkeit 1/4 ein
Richtungswechsel ausgel"ost. Dieses zuf"allige Ausl"osen geschieht mit
Hilfe der Bibliotheksfunktion {\tt rand} (definiert in {\tt stdlib.h}).
Diese Funktion liefert bei jedem Aufruf einen Wert zwischen 0
(einschlie\3lich) und {\tt RAND\_MAX} (einschlie\3lich, ebenfalls
in {\tt stdlib.h} definiert). Die zur"uckgelieferten Werte sind "uber
diesen Zahlenbereich statistisch gleichverteilt. Mit Wahrscheinlichkeit
1/4 sind sie daher kleiner als {\tt RAND\_MAX/4}.

Mu\3 (oder soll) ein Richtungswechsel durchgef"uhrt werden, so wird
zun"achst eine Drehrichtung festgelegt, und zwar mit gleicher
Wahrscheinlichkeit eine mathematisch positive (gegen den Uhrzeigersinn)
oder negative Drehung (im Uhrzeigersinn). Dann wird der Hamster in
einer Schleife durch Aufrufe der Funktion {\tt hms\_turn} so lange in
dieser Richtung gedreht, bis sich vor ihm keine Wand (mehr) befindet,
was wieder durch Aufrufe der Funktion {\tt hms\_look} festgestellt
wird.

Durch den Test in der vorhergehenden {\tt if}-Anweisung oder durch die
Drehschleife ist sichergestellt, da\3 sich der Hamster nicht vor einer
Wand befindet. Er kann sich folglich auf das vor ihm liegende Feld
bewegen, was durch einen Aufruf der Funktion {\tt hms\_move} erreicht
wird. Dieser Zug wird im Z"ahler {\tt movecnt} gez"ahlt.

Ein eigenes Hamsterprogramm schreibt man vielleicht am besten, indem
man das oben beschriebene Beispielprogramm kopiert und dann "Anderungen
an dieser Kopie vornimmt. Man k"onnte z.B.\ zun"achst versuchen, eine
andere Abbruchbedingung f"ur die Sammelt"atigkeit des Hamsters zu
finden, so da\3 er auch mehr als nur 50 Z"uge machen kann.

%-----------------------------------------------------------------------

\subsubsection{Das Beispielprogramm in Eiffel}
\label{sec.exprog.eiffel}

Das Beispielprogramm, das in Abbildung~\ref{fig.exprog.eiffel} gezeigt
ist, steuert den Hamster auf