contest.tex

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

%-----------------------------------------------------------------------
% File    : contest.tex
% Contents: description of hamster programming contest
% Author  : Christian Borgelt
% History : 12.01.1998 file created
%           17.01.1998 first version completed
%-----------------------------------------------------------------------
%\documentstyle[german]{article}
\documentclass{article}
\usepackage{german}

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

\textwidth150mm
\oddsidemargin6mm
\evensidemargin6mm
\topmargin-7mm
\textheight227mm
\renewcommand{\topfraction}{0.8}
\renewcommand{\textfraction}{0.2}

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

\newenvironment{fndoc}[1]{\par\pagebreak[2]%
\vskip3.0ex plus.5ex minus.5ex\pagebreak[3]\noindent\ignorespaces
  {\large\tt #1}                \par\nopagebreak\noindent
  \rule[1.4ex]{\textwidth}{.3pt}\par\nopagebreak\vskip-.8ex
  \begin{list}{\hfill}{%
    \topsep0ex      \partopsep0ex   \parsep0ex         \itemsep.6ex
    \leftmargin25mm \rightmargin0pt \listparindent10pt
    \labelwidth25mm \labelsep0pt    \itemindent0pt
  }\nopagebreak
}{\end{list}\vspace{.5ex}\pagebreak[2]}

\def\name{\nopagebreak\item[Name\hfill]}
\def\synopsis{\item[Definition\hfill]}
\def\descript{\item[Beschreibung\hfill]}
\def\remark{\item[Bemerkung\hfill]}
\def\result{\item[Ergebnis\hfill]}

\newenvironment{genlist}[1]{\begin{list}{}{%
\itemsep2pt plus1pt minus1pt\topsep3\itemsep
\settowidth\labelwidth{#1}\settowidth\labelsep{.~}%
\leftmargin\labelwidth\advance\leftmargin\labelsep}
}{\end{list}}

\def\mouse#1{{\unitlength1pt
\def\lbut{\put( 0,0){\rule{7pt}{7pt}}}%
\def\mbut{\put( 7,0){\rule{7pt}{7pt}}}%
\def\rbut{\put(14,0){\rule{7pt}{7pt}}}%
\begin{picture}(21,7)
\multiput(0,0)(0,7){2}{\line(1,0){21}}
\multiput(0,0)(7,0){4}{\line(0,1){7}}
\csname #1but\endcsname
\end{picture}}}

\def\shift{Shift~}
\def\ctrl {\hbox to0pt{Ctrl\hss}\phantom{Shift}~}
\def\nokey{\phantom{Shift}~}

%-----------------------------------------------------------------------
\begin{document}

\title {\vskip-5ex Hamster \\ \rule{5cm}{0.5pt} \\[1ex]
        Der Programmierwettbewerb \\
        zur Vorlesung "`Algorithmen und Datenstrukturen"'}
\author{Christian Borgelt \\[2ex]
        Institut f"ur Wissens- und Sprachverarbeitung \\
        Otto-von-Guericke-Universit"at Magdeburg \\
        Universit"atsplatz 2, D-39106 Magdeburg}
\maketitle
\vfill
\tableofcontents

%-----------------------------------------------------------------------
\newpage

\section{Einleitung}
\label{sec.intro}

Gut zu programmieren, das ist eine alte Weisheit (die sicher nicht
nur f"ur diese F"ahigkeit gilt), lernt man nur, indem man es "ubt.
Das geht nat"urlich am besten, wenn das "Uben nicht einfacher Drill
handwerklicher Technik ist, sondern dadurch geschieht, da\3 man vor zwar
bew"altigbare, aber auch nicht zu leichte Herausforderungen gestellt
wird, bei denen man nach der L"osung selbst suchen mu\3. Dazu sind die
einfachen Programmieraufgaben, die man im Laufe der "Ubungen zu einer
Einf"uhrungsvorlesung der Informatik angeboten bekommt, nicht immer
geeignet. Zwar m"ogen auch sie f"ur diejenigen, die vorher noch keine
Programmiererfahrung gesammelt haben, als Herausforderung erscheinen,
da das "`algorithmische Denken"' erst gelernt werden mu\3. Doch f"ur
diejenigen, die schon "uber Programmiererfahrung verf"ugen, sp"ater aber
wohl f"ur alle, sind sie wenig reizvoll, da der L"osungsweg meist schon
in der Vorlesung behandelt wurde. Echte Herausforderungen stellen sie
daher oft nicht mehr dar.

Aus dieser "Uberlegung heraus bieten wir diesen Programmierwettbewerb
an. Das zu l"osende Problem ist, so hoffen wir, leicht verst"andlich.
Es ist so einfach, da\3 man auch mit geringen Kenntnissen und geringer
Programmiererfahrung eine L"osung finden kann. Aber es ist auch so
komplex, da\3 es eine immer weiter gehende Herausforderung darstellt,
denn eine nachweisbar optimale L"osung ist f"ur dieses Problem (soweit
wir wissen) nicht bekannt. Man kann also seinen Ideen freien Lauf
lassen. Gute Ideen sind bei diesem Problem sicher mehr wert als viel
Erfahrung. Au\3erdem hoffen wir, da\3 die durch einen Wettbewerb
geschaffene Konkurrenzsituation zus"atzlich motivierend wirkt.

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

\section{Das Hamsterproblem}
\label{sec.problem}

Ein Hamster, der seinen Wintervorrat an Getreide noch nicht gesammelt
hat, wird in einem Labyrinth ausgesetzt. In diesem Labyrinth ist eine
bestimmte Anzahl von Maisk"ornern in unterschiedlich gro\3en Haufen
verteilt Die Aufgabe des Hamsters ist es, m"oglichst viele Maisk"orner
zu sammeln und zu seinem Ausgangspunkt zu bringen. Dabei mu\3 er die
Sammelwege nat"urlich m"oglichst kurz halten, damit er bei seiner
T"atigkeit nicht schon den gr"o\3ten Teil der gesammelten Maisk"orner
als Nahrung verbraucht.

In diesem Programmierwettbewerb soll ein Programm geschrieben
werden, das den Hamster durch das Labyrinth steuert. Dazu steht eine
"uberschaubare Menge von Funktionen zur Verf"ugung, mit denen dem
Hamster bestimmte einfache Befehle gegeben werden k"onnen, z.B.\
"`Drehe Dich um $90^o$ nach links!"', "`Gehe ein Feld geradeaus!"',
"`Nimm drei Maisk"orner auf!"' etc.\
(siehe Abschnitt~\ref{sec.control}). Die Reihenfolge und die Anzahl
dieser Befehle wird durch das zu schreibende Steuerprogramm festgelegt.
Hier hat der Programmierer v"ollig freie Hand.

Wie gut ein Programm die Aufgabe gel"ost hat, wird anhand der Anzahl
der gesammelten Maisk"orner, der L"ange des beim Sammeln zur"uckgelegten
Weges und der Zahl der Zusammenst"o\3e mit W"anden des Labyrinthes
bestimmt (siehe Abschnitt~\ref{sec.eval}). Die auf der Grundlage
dieser Werte berechnete Punktzahl entscheidet schlie\3lich "uber die
Plazierung im Wettbewerb.

Eine genauere Beschreibung des Hamsters, seiner F"ahigkeiten
und des Labyrinthes, in dem er sich bewegt, findet sich in
Abschnitt~\ref{sec.control}.

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

\section{Das Hamsterprogramm}
\label{sec.prog} 

Das Hamsterprogramm besteht eigentlich aus zwei Programmen: Erstens
dem im folgenden so genannten {\em Labyrinthprogramm}, das das
Labyrinth verwaltet, in dem sich der Hamster befindet, und den Hamster
entsprechend der gegebenen Befehle in diesem Labyrinth bewegt. Zweitens
dem im folgenden so genannten {\em Steuerprogramm}, das dem Hamster
Befehle erteilt. Nur das letztere Programm ist (teilweise) vom
Wettbewerbsteilnehmer zu schreiben.

Das Labyrinthprogramm f"uhrt die vom Steuerprogramm an den Hamster
gegebenen Befehle aus, stellt sicher, da\3 der Hamster nicht "`durch
W"ande geht"', und berechnet die vom Hamster erreichte Punktzahl. In den
Versionen dieses Programms, die eine graphische Benutzerschnittstelle
besitzen, stellt dieses Programm au\3erdem die Bewegung des Hamsters
im Labyrinth in einem Fenster auf dem Bildschirm dar.

Das Labyrinthprogramm "ubernimmt jedoch keinerlei Steueraufgaben.
Diese liegen allein beim zu schreibenden Steuerprogramm. Es hat durch
das Aufrufen von Hamsterfunktionen (d.h.\ das Erteilen von Befehlen an
den Hamster) den Hamster zu bewegen und seine Sammelt"atigkeit zu
organisieren. Das Steuerprogramm hat keinen direkten Zugriff auf die
Daten des Labyrinthprogramms. Es kann nur "uber die festgelegte
Hamster-Befehlsschnittstelle mit dem Labyrinthprogramm kommunizieren.

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

\subsection{Installation des Hamsterprogramms}
\label{sec.inst}

Eine Installation des Hamsterprogramms ist nur notwendig, wenn nicht
im HP-Pool der Universit"at Magdeburg gearbeitet wird. Dort ist das
Programm bereits im Verzeichnis {\tt \~{}borgelt/src/hamster}
installiert. Wird im HP-Pool gearbeitet, kann daher dieser Abschnitt
"ubersprungen werden. Stattdessen wechselt man in das oben angegebene
Verzeichnis und f"ahrt mit dem in Abschnitt~\ref{sec.start}
beschriebenen Testlauf fort.

Zur Installation des Programms z.B.\ auf einem PC unter Linux oder
Windows 95/98/NT geht man folgenderma\3en vor: Das Entpacken der
Dateien des Programmpaketes sollte ein Verzeichnis {\tt hamster}
erstellt haben (im folgenden Wurzelverzeichnis genannt), in dem
sich die Verzeichnisse {\tt doc}, {\tt eiffel}, {\tt hamster},
{\tt mazes}, {\tt pascal}, {\tt unix} und {\tt windows} befinden.
Zur Installation des Programms ist in dieses Wurzelverzeichnis zu
wechseln.

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

\subsubsection{Installation unter Unix}
\label{sec.inst.unix}

Im Wurzelverzeichnis der Installation befindet sich die Datei
{\tt makefile}, die die "Ubersetzung des Hamsterprogramms unter Unix
steuert. Zum Erstellen ist daher einfach {\tt make all} einzugeben.
Es wird daraufhin der Gnu-C-Compiler aufgerufen, um die Quelldateien
zu "ubersetzen.

Gelingt die "Ubersetzung nicht, so liegt dies wahrscheinlich daran,
da\3 Header-Dateien oder Bibliotheken des X-Window-Systems (X11R5/R6)
nicht gefunden wurden. In der Datei {\tt makefile} ist ein
Standardpfad eingestellt, der oft (insbesondere f"ur Linux) zutrifft:
{\tt /usr/X11R6}. Ist das X-Window-System unter einem anderen Pfad
installiert (z.B.\ {\tt /usr/X11R5}, {\tt /usr/local/X11R6},
{\tt /usr/X11}, {\tt /usr/local/X11} o."a.), so sind in der Datei
{\tt makefile} die Definitionen der Pfadkonstanten {\tt X11INC}
und {\tt X11LIB} anzupassen. Ist die Programmierschnittstelle des
X-Windows-Systems nicht installiert (kann z.B.\ bei der
Linux-Standardinstallation der Fall sein: Serie {\tt x}, Paket
{\tt xdevel}), so ist diese Schnittstelle zuerst zu installieren,
da ohne sie eine "Ubersetzung unm"oglich ist.

Steht der Gnu-C-Compiler ({\tt gcc}) nicht zur Verf"ugung, kann auch
mit dem Systemcompiler ({\tt cc}) gearbeitet werden. In diesem Fall sind
in der Datei {\tt makefile} die Definitionen der Konstanten {\tt CC} und
{\tt CFLAGS} anzupassen.

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

\subsubsection{Installation unter Microsoft Windows}
\label{sec.inst.windows}

Im Wurzelverzeichnis der Installation befinden sich die Dateien
{\tt whamster.mdp} und {\tt whamster.mak}, die die "Ubersetzung
des Hamsterprogramms mit Microsoft~C~4.0, und die Dateien
{\tt whamster.dsw}, {\tt whamster.dsp} und {\tt chamster.dsp}, die
die "Ubersetzung des Hamsterprogramms mit Microsoft~C~5.0 steuern.
Die Datei {\tt whamster.mdp} bzw.\ die Datei {\tt whamster.dsw} ist
aus der Entwicklungsumgebung des Microsoft-C-Systems "uber
{\tt File > Open Workspace...} zu "offnen. Beide Teilprojekte,
{\tt whamster} und {\tt chamster}, m"ussen "ubersetzt werden.

Eine "Ubersetzung mit Borland C sollte ebenfalls m"oglich sein, doch
liegt hierf"ur keine Projektdatei vor. Es sind zwei Programme zu
erzeugen: {\tt bin\char92whamster.exe} und {\tt bin\char92chamster.exe}.
Zum ersten geh"oren die Quelldateien {\tt windows\char92whamster.c},
{\tt windows\char92whamster.rc}, {\tt windows\char92sprite.c},
{\tt hamster\char92server.c} und {\tt hamster\char92maze.c}, ggf.\
auch {\tt windows\char92whamster.def}, zum zweiten die Quelldateien
{\tt hamster\char92control.c} und {\tt hamster\char92client.c}. Als
zus"atzliche Include-Pfade sind im ersten Fall {\tt hamster} und
{\tt windows}, im zweiten nur {\tt hamster} anzugeben. Ersteres Programm
ist als Standard-Windows-Anwendung, letzteres als Konsolenanwendung zu
"ubersetzen.

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

\subsection{Starten des Hamsterprogramms}
\label{sec.start}

Um das Hamsterprogramm zu starten, ruft man unter Unix das Programm
{\tt xhamster} auf, das sich nach der "Ubersetzung im Verzeichnis
{\tt bin} befindet. Alternativ (und einfacher) kann man das Shellscript
{\tt xh} im Wurzelverzeichnis der Hamsterinstallation starten. Unter
Microsoft Windows startet man das Programm {\tt whamster.exe}, das sich
nach erfolgreicher "Ubersetzung ebenfalls im Verzeichnis {\tt bin}
befindet.

Es sollte ein Fenster mit dem Namen {\tt xhamster} (Unix) bzw.\
{\tt whamster} (Microsoft Windows) erscheinen, in dem ein zun"achst
leeres Labyrinth ohne W"ande angezeigt wird (also eigentlich ein
einfaches wei\3es Rechteck). In der unteren linken Ecke ist ein Feld
grau unterlegt. Dies ist das Feld, auf dem der Hamster startet.