contest.tex

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

Da ein Testlauf mit einem v"ollig leeren Labyrinth nicht sehr
interessant ist, sollte man das Labyrinth zun"achst initialisieren.
Dazu w"ahlt man den Men"ueintrag {\tt Actions > Randomize Maze...} aus.
Es erscheint eine Dialogbox, in der man die Wandwahrscheinlichkeit,
die Gesamtzahl zu verteilender Maisk"orner und die maximale Gr"o\3e
eines Maishaufens einstellen kann. F"ur einen ersten Test kann man
die voreingestellten Werte akzeptieren und einfach {\tt Ok} anw"ahlen.
Daraufhin wird das Labyrinth initialisiert. D.h.\ es werden zuf"allig
W"ande in einem quadratischen Raster gesetzt, wobei sichergestellt ist,
da\3 jedes Feld des Labyrinthes erreichbar bleibt. Au\3erdem werden
Kornhaufen verschiedener Gr"o\3e zuf"allig im Labyrinth verteilt und
als gelbe Kreise unterschiedlicher Gr"o\3e dargestellt. Schlie\3lich
wird noch das Startfeld aus der unteren linken Ecke auf ein zuf"alliges
Feld des Labyrinthes versetzt.

Auf dem initialisierten Labyrinth kann nun das Beispiel-Steuerprogramm
gestartet werden. Dazu w"ahlt man den Men"ueintrag
{\tt Actions > Start Hamster} aus. Der Hamster erscheint als roter
Kreis (in der Art eines "`Pacman"') auf dem Startfeld und beginnt seine
zuf"allige Wanderung durch das Labyrinth. Sollte statt des Hamsters
eine Fehlermeldung erscheinen, da\3 das Programm {\tt bin/chamster} oder
{\tt chamster} nicht gefunden/gestartet werden konnte, so mu\3 zun"achst
das Hamsterprogramm ausgew"ahlt werden. Dies geschieht "uber den
Men"ueintrag {\tt File > Select Hamster...}. Es erscheint dann eine
Dateiauswahlbox, in der das Programm {\tt chamster} (Unix) bzw.\
{\tt chamster.exe} aus dem Verzeichnis {\tt bin} ausgew"ahlt werden mu\3.
Danach kann der Hamster (wie oben) "uber {\tt Actions > Start Hamster}
gestartet werden.

Das Beispiel-Steuerprogramm ist, wie schnell deutlich wird, nicht
besonders intelligent. Der Hamster bewegt sich v"ollig orientierungslos
durch das Labyrinth. W"ahrend dieser Wanderung wird in der Men"uzeile
(Unix) bzw.\ der Titelzeile (Microsoft Windows) des Labyrinthfensters
die erreichte Punktzahl angezeigt. Nach 50 (Feld zu Feld) Schritten
endet das Beispiel-Steuerprogramm und es wird eine Ergebnis-Dialogbox
angezeigt, in der man ablesen kann, wie viele Maisk"orner der Hamster
eingesammelt, wie viele Z"uge er gemacht, wie oft er mit W"anden
zusammengesto\3en und welche Punktzahl er folglich erreicht hat.

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

\subsection{Die Funktionen des Labyrinthprogramms}
\label{sec.menu}

Die Funktionen des Labyrinthprogramms werden in den folgenden
Abschnitten~\ref{sec.menu.file} bis \ref{sec.menu.help} anhand der
Men"ustruktur erl"autert. Danach folgt in Abschnitt~\ref{sec.mouse}
eine Beschreibung, wie man mit Hilfe der Maus ein Labyrinth manuell
erzeugen oder "andern kann.

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

\subsubsection{Das Men"u "`File"'}
\label{sec.menu.file}

Im Men"u {\tt File} finden sich Eintr"age zum Laden und Speichern von
Labyrinthen und zum Ausw"ahlen eines Hamster-Steuerprogramms. Au\3erdem
enth"alt dieses Men"u, dem Standard entsprechend, einen Eintrag, mit dem
das Programm verlassen werden kann.

\begin{genlist}{\tt Set Hamster Speed...~~}
\item[\tt Reload Maze...\hfill] Das zuletzt mit {\tt Load Maze...}
     geladene oder mit {\tt Save Maze As...} gespeicherte Labyrinth
     wird erneut geladen. So k"onnen leicht mehrere Testl"aufe auf dem
     gleichen Labyrinth ausgef"uhrt werden. Wurde noch kein Labyrinth
     geladen oder gespeichert, so wird eine Dialogbox angezeigt, in
     der eine Datei ausgew"ahlt werden kann, aus der ein Labyrinth
     geladen werden soll. \par
       Dieser Men"ueintrag kann nicht angew"ahlt werden, w"ahrend ein
     Ham\-ster-Steuerprogramm l"auft.
\item[\tt Load Maze...\hfill] Es wird eine Dialogbox angezeigt, in der
     eine Datei ausgew"ahlt werden kann, aus der ein Labyrinth geladen
     werden soll. Die zu ladende Labyrinthdatei sollte "uber den
     Men"upunkt {\tt Save Maze...} erzeugt worden sein. Das im
     Labyrinthfenster angezeigte Labyrinth wird nur ersetzt, wenn das
     Laden erfolgreich verlief. Anderenfalls wird eine Fehlermeldung
     ausgegeben. \par
       Dieser Men"ueintrag kann nicht angew"ahlt werden, w"ahrend ein
     Ham\-ster-Steuerprogramm l"auft.
\item[\tt Save Maze...\hfill] Das aktuelle Labyrinth wird in der Datei
     gespeichert, die beim letzten Aufruf einer der Men"upunkte
     {\tt Load Maze...} oder {\tt Save Maze As...} ausgew"ahlt wurde.
     Wurde noch kein Labyrinth geladen oder gespeichert, so wird eine
     Dialogbox angezeigt, in der eine Datei ausgew"ahlt werden kann,
     in der das aktuelle Labyrinth gespeichert werden soll. \par
       Dieser Men"ueintrag kann nicht angew"ahlt werden, w"ahrend ein
     Ham\-ster-Steuerprogramm l"auft.
\item[\tt Save Maze As...\hfill] Es wird eine Dialogbox angezeigt,
     in der eine Datei ausgew"ahlt werden kann, in der das im
     Labyrinthfenster angezeigte Labyrinth gespeichert werden soll.
     Das Labyrinth wird genau in der Form abgespeichert, in der es
     angezeigt wird, nicht in der Form, in der es geladen oder erzeugt
     wurde. Daher sollte man, wenn man ein Hamster-Steuerprogramm mehr
     als einmal auf dem gleichen Labyrinth testen m"ochte, dieses
     Labyrinth {\em vor\/} dem ersten Testlauf abspeichern. \par
       Dieser Men"ueintrag kann nicht angew"ahlt werden, w"ahrend ein
     Ham\-ster-Steuerprogramm l"auft.
\item[\tt Select Hamster...\hfill] Es wird eine Dialogbox angezeigt,
     in der ein Hamster-Steuerprogramm ausgew"ahlt werden kann. Indem
     Hamster-Steuerprogramme vom Labyrinthprogramm aus ausgew"ahlt
     werden k"onnen, kann man (nacheinander) mehrere Hamsterprogramme
     testen, ohne das Labyrinthprogramm verlassen zu m"ussen. \par
       Dieser Men"upunkt kann nicht angew"ahlt werden, w"ahrend ein
     Ham\-ster-Steuerprogramm l"auft.
\item[\tt Quit\hfill] Durch Anwahl dieses Men"upunktes wird das
     Labyrinthprogramm verlassen. Dieser Men"upunkt kann auch
     angew"ahlt werden, w"ahrend ein Ham\-ster-Steuerprogramm l"auft.
     In diesem Fall wird sowohl das Labyrinthprogramm als auch das
     Steuerprogramm beendet. Anders als beim Stoppen eines Hamsters
     "uber {\tt Actions > Stop Hamster} wird keine Dialogbox mit
     dem bisher erzielten Ergebnis angezeigt.
\end{genlist}

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

\subsubsection{Das Men"u "`Actions"'}
\label{sec.menu.actions}

Im Men"u {\tt Actions} finden sich Eintr"age zum Initialisieren und
Ver"andern des Labyrinthes, zum Einstellen der Bewegungsgeschwindigkeit
des Hamsters, sowie zum Starten und Anhalten des Hamsters.

\begin{genlist}{\tt Set Hamster Speed...~~}
\item[\tt Redraw\hfill] Das Labyrinthfenster wird neu gezeichnet.
     Dieser Men"upunkt ist wahrscheinlich nur unter Windows notwendig,
     da dort, wenn bei laufendem Hamster ein Fenster verschoben wird,
     "`Geisterbilder"' des Hamsters zu\-r"uckbleiben k"onnen. Durch
     Ausw"ahlen dieses Men"upunktes werden diese gel"oscht. \par
       Dieser Men"ueintrag kann auch angew"ahlt werden, w"ahrend ein
     Hams\-ter-Steuerprogramm l"auft.
\item[\tt Set Maze Size...\hfill] Mit diesem Men"ueintrag kann die
     Gr"o\3e des Labyrinthes ver\-"an\-dert werden. In der bei Anwahl
     dieses Men"ueintrages erscheinenden Dialogbox k"onnen die
     $x$-Ausdehnung (horizontale/West-Ost-Ausdehnung) und die
     $y$-Aus\-deh\-nung (vertikale/S"ud-Nord-Ausdehnung) in
     Feldeinheiten eingetragen werden. Das Labyrinth mu\3 mindestens
     8 Felder breit (wegen der Men"uzeile des Fensters) und mindestens
     1 Feld hoch sein. Die maximale Ausdehnung betr"agt 64 Felder in
     jede Richtung. \par
       Dieser Men"ueintrag kann nicht ausgew"ahlt werden, solange
     ein Ham\-ster-Steuerprogramm l"auft.
\item[\tt Randomize Maze...\hfill] Das Labyrinth wird (zuf"allig)
     initialisiert. In der bei Anwahl dieses Me\-n"u\-eintrages
     erscheinenden Dialogbox k"onnen die Wandwahrscheinlichkeit,
     die Anzahl insgesamt zu verteilender Maisk"orner und die
     maximale Gr"o\3e eines Kornhaufens eingestellt werden. Nach
     Dr"ucken des "`Ok"'-Knopfes wird das Labyrinth entsprechend
     initialisiert. Au\3erdem wird das Startfeld auf ein zuf"alliges
     Feld des Labyrinthes versetzt. \par
       Dieser Men"ueintrag kann nicht ausgew"ahlt werden, solange
     ein Ham\-ster-Steuerprogramm l"auft.
\item[\tt Clear Maze\hfill] Das Labyrinth wird gel"oscht, d.h.\
     alle W"ande und alle Maisk"orner werden entfernt und das
     Startfeld wird in die linke untere Ecke gesetzt. \par
       Dieser Men"ueintrag kann nicht ausgew"ahlt werden, solange
     ein Ham\-ster-Steuerprogramm l"auft.
\item[\tt Set Hamster Speed...\hfill] In der bei Anwahl dieses
     Men"ueintrages erscheinenden Dialogbox kann die gew"unschte
     Geschwindigkeit des Hamsters in Labyrinthfeldern pro Sekunde
     eingetragen werden. Der kleinste Wert dieser Geschwindigkeit
     betr"agt 0.1, der gr"o\3te 100 Felder pro Sekunde. Bei
     100 Feldern pro Sekunde wird die Darstellung des Hamsters
     ausgeschaltet. In diesem Fall wird lediglich bei Ablauf
     des Hamster-Steuerprogramms die Endsituation des Labyrinthes
     (Maiskornverteilung) angezeigt. Wie der Hamster den Mais
     einsammelt, kann dagegen nicht verfolgt werden. \par
       Dieser Men"ueintrag kann auch angew"ahlt werden, w"ahrend
     ein Steuerprogramm l"auft. Die ge"anderte Hamstergeschwindigkeit
     wird wirksam, wenn der Hamster seinen aktuellen Bewegungsschritt
     abgeschlossen (seine Drehung beendet oder sein Zielfeld erreicht)
     hat.
\item[\tt Start/Stop Hamster\hfill] Mit diesem Men"ueintrag kann
     ein Hamster-Steuerprogramm gestartet oder beendet werden (je
     nachdem, ob gerade ein Hamster-Steuer\-programm l"auft oder nicht).
     Gestartet wird das Steuerprogramm, das vorher "uber den
     Men"ueintrag {\tt File > Select Hamster} ausgew"ahlt \linebreak
     wurde. Bei Start des Labyrinthprogramms ist das Beispielprogramm
     {\tt bin/chamster} (Unix, abgestimmt auf einen Aufruf des
     Labyrinthprogramms "uber das Shellscript {\tt xh}) bzw.\
     {\tt chamster.exe} (Microsoft Windows) ausgew"ahlt. \par
     Wird ein Hamster-Steuer\-pro\-gramm "uber diesen Men"ueintrag
     beendet, so wird eine Ergebnisdialogbox mit den bis zum Zeitpunkt
     des Abbruchs gesammelten Maisk"ornern, durchgef"uhrten Schritten,
     Anzahl Wandzusammenst"o\3en und folglich erreichten Punkten
     angezeigt.
\end{genlist}

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

\subsubsection{Das Men"u "`Help"'}
\label{sec.menu.help}

Unter diesem Men"ueintrag findet sich leider keine echte Hilfe zur
Benutzung des Hamsterprogramms, sondern nur ein Eintrag, der bei Anwahl
zur Anzeige einer Dialogbox ("`About"'-Dialogbox) f"uhrt, in der
allgemeine Informationen zum Hamsterprogramm ausgegeben werden.

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

\subsubsection{Labyrinthkonstruktion mit der Maus}
\label{sec.mouse}

Solange kein Hamster-Steuerprogramm l"auft, l"a\3t sich das im
Labyrinthfenster angezeigte Labyrinth mit Hilfe der Maus ver"andern.
Folgende Funktionen stehen zur Verf"ugung (die Zeichen \mouse{l},
\mouse{m} und \mouse{r} bedeuten ein Dr"ucken der linken, mittleren
bzw.\ rechten Maustaste):
\begin{genlist}{\ctrl\mouse{l}}
\item[\nokey\mouse{l}] Setzen/Entfernen einer Wand. Es wird an dem
     Rand eines Labyrinthfeldes, der dem Mauszeiger am n"achsten liegt,
     eine Wand gesetzt (falls sich dort keine Wand befindet) oder
     entfernt (falls sich dort eine Wand befindet).
\item[\ctrl \mouse{l}] Alle W"ande, die das Labyrinthfeld umgeben, auf
     das der Mauszeiger zeigt, werden entfernt.
\item[\shift\mouse{l}] Das Startfeld, d.i.\ das Feld, auf dem der
     Hamster im Labyrinth ausgesetzt wird, wird auf das Labyrinthfeld
     versetzt, auf das der Mauszeiger zeigt.
\item[\nokey\mouse{m}] Die Gr"o\3e des Maiskornhaufens auf dem
     Labyrinthfeld, auf das der Mauszeiger zeigt, wird um ein
     Maiskorn verringert.
\item[\shift\mouse{m}] Die Gr"o\3e des Maiskornhaufens auf dem
     Labyrinthfeld, auf das der Mauszeiger zeigt, wird um f"unf
     Maisk"orner verringert.
\item[\ctrl \mouse{m}] Alle Maisk"orner, die auf dem Labyrinthfeld
     liegen, auf das der Mauszeiger zeigt, werden entfernt.
\item[\nokey\mouse{r}] Die Gr"o\3e des Maiskornhaufens auf dem
     Labyrinthfeld, auf das der Mauszeiger zeigt, wird um ein
     Maiskorn erh"oht.
\item[\shift\mouse{r}] Die Gr"o\3e des Maiskornhaufens auf dem
     Labyrinthfeld, auf das der Mauszeiger zeigt, wird um f"unf
     Maisk"orner erh"oht.
\item[\ctrl \mouse{r}] Alle Maisk"orner, die auf dem Labyrinthfeld
     liegen, auf das der Mauszeiger zeigt, werden entfernt.
\end{genlist}
Mit Hilfe dieser Funktionen und des Men"ueintrags {\tt Actions >
Set Maze Size...} lassen sich offenbar beliebige Labyrinthe
konstruieren. Es wird nicht gepr"uft, ob durch die mit der Maus
gesetzten gesetzten W"ande einige Felder das Labyrinthes vom Startfeld
aus unerreichbar werden. Daher lassen sich auch Labyrinthe mit nicht
rechteckigem Grundri\3 erzeugen, n"amlich einfach dadurch, da\3 man
durch W"ande bestimmte Bereiche unzug"anglich macht.

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

\section{Die Steuerung des Hamsters}
\label{sec.control}

Dieser Abschnitt enth"alt eine genauere Beschreibung des Labyrinthes,
des Hamsters, der Befehle, die ihm erteilt werden k"onnen, und wie
er sich in dem Labyrinth, in dem er sich befindet, orientieren kann.
Abschnitt~\ref{sec.ctrl.general} enth"alt allgemeine Erl"auterungen
zur Steuerung des Hamsters. Die Abschnitte~\ref{sec.ctrl.c} und
\ref{sec.ctrl.eiffel} sind programmiersprachenabh"angig. Ersterer
beschreibt die Programmierschnittstelle f"ur die Programmiersprache~C,
letzterer die Schnittstelle f"ur die Programmiersprache Eiffel. Eine
Programmierschnittstelle f"ur Pascal wird zur Zeit noch entwickelt.

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

\subsection{Allgemeine Erl"auterungen}
\label{sec.ctrl.general}

Der Hamster wird in einem Labyrinth mit rechteckigem Grundri\3
ausgesetzt. Dieses Labyrinth hat ein quadratisches Raster, d.h.\
das Rechteck, das den Grundri\3 bildet, ist in quadratische Felder
eingeteilt. Das Labyrinth kann in $x$-Richtung (West-Ost-Richtung)
zwischen 8 und 64 Feldern, in $y$-Richtung (S"ud-Nord-Richtung)
zwischen 1 und 64 Feldern gro\3 sein. Auf den R"andern dieser Felder
k"onnen W"ande stehen und auf den Feldern k"onnen Haufen von