2005 - Marie-Curie

Marie – Curie – Gymnasium
Städt. Gymnasium Recklinghausen
Abitur 2005
GK Informatik
Vorschlag II
Aufgabe
Bahnplanungsmethoden in der Informatik dienen z.B. dazu, Pfade für bewegte Elemente
(Verkehrsmittel, Personen, Roboter o.ä.) zu ermitteln, die unbewegten Elementen (Hindernissen,
Bauteilen, Naturgegebenheiten u.ä.) ausweichen müssen. Eine der Vorplanungsmethoden im
zweidimensionalen Raum besteht in der Diskretisierung der benutzten Fläche durch ein Gitter aus
Zellen, die entweder Teil eines Hindernisses oder ‚begehbar’ sind. Die Angabe eines möglichen
Pfades von einem vorgegebenen Start zu einem Ziel besteht damit in der Angabe einer Folge von
begehbaren Zellen, die miteinander benachbart sind und vom Start zum Ziel führen. Eine mögliche
Konkretisierung des Begriffs ‚Nachbarschaft’ ist die so genannte 4er-Nachbarschaft, die nur die vier
rechts oder links bzw. oben oder unten existierenden Zellen (schraffiert) als Nachbarn definiert.
Die Pfade von einem Punkt zu einem anderen Punkt entlang solcher Nachbarzellen führt demnach
über waagerechte bzw. senkrechte ‚Straßen’. Die hierdurch bestimmte Entfernung hat in Anlehnung
an die Straßensituation in New York den Namen manhattan-distance, die direkte (Luftlinien)Verbindung der Punkte die mit Pythagoras berechnete Euklidische-Distanz. Die Punkte (3,5) und
(2,7) hätten demnach die manhattan-distance von 3 und die euklidische Distanz von
5.
a) Implementiere in Delphi die beiden Funktionen:
1) function manhattan_distance(P1,P2 : TPoint):Integer;
2) function euklid_distance(P1,P2 : TPoint):Real;
und begründe kurz, dass für beliebige Punkte P1,P2 gilt: manhattan_distance(P1,P2) ≥
euklid_distance(P1,P2)
b) Grundlage für die Diskretisierung der Fläche
soll ein StringGrid mit 50 x 50 Zellen sein, in
dem ein Start- und ein Zielpunkt und zwei
Hindernisse (rechteckige Gitterbereiche auf
gleicher Höhe) gekennzeichnet sind.
mögliche Situation:
Beschreibe umgangssprachlich den Algorithmus,
der einen (möglichst kurzen) begehbaren Pfad
zwischen dem Start- und dem Zielpunkt
bestimmt, dessen (manhattan-)Länge berechnet
und eine mögliche (begehbare)
Direktverbindung (evtl. in mehreren Teilstücken) einzeichnet.
c) Zur Umsetzung eines Teils des in b) beschriebenen Algorithmus soll die folgende
Datenstruktur benutzt werden:
Planfeld_Stg : TStringGrid;
Start, Ziel : TPoint;
Hindernis
: array [1..2] of
record
linksoben, rechtsunten : TPoint;
end;
Trasse
: array of TPoint;
//dynamisches array
Marie – Curie – Gymnasium
Städt. Gymnasium Recklinghausen
Abitur 2005
GK Informatik
Vorschlag II
mögliches Startformular:
Implementiere die
procedure Trasse_BClick,
die aufgrund der zufällig vorgegebenen Anfangssituation die Punkte der kürzesten Trasse
generiert, die Länge dieser Trasse ausgibt und die Trassenzellen darstellt. Kommentiere dabei
sämtliche Teile, Unterprozeduren und benutzte zusätzliche Variablen.
Es kann davon ausgegangen werden, dass die beiden sich auf gleicher Höhe befindlichen
Hindernisse auf mindestens einer der Seiten oder zwischen sich eine begehbare Spalte freilassen
und dass sich der Startpunkt oberhalb und der Zielpunkt unterhalb der Hindernisse befindet. Zur
Darstellung der Trassengitterzellen kann ohne Implementation die Procedure
Zelle_zeichnen(P: TPoint, f : TColor); benutzt werden.
mögliches Endformular:
d) Beschreibe, wie man evtl. den obigen Algorithmus mit dazu benutzen könnte, nach der
Bestimmung der ‚Manhattan-Trasse’ eine Verkürzung der Trasse durch (euklidische)
Direktverbindungen zu erhalten, so dass ein möglicher Trassenvorschlag gegeben wäre durch: