 |
Beschreibungssprache - ConStrukt Das ConSolve®-System löst kombinatorische Optimierungsprobleme. Dazu werden die Problemstellungen in der speziellen Beschreibungssprache ConStrukt formuliert und dann dem ConSolve®-Laufzeitsystem übergeben.
Die Sprache ConStrukt wurde entworfen, um logische und kombinatorische
Probleme möglichst einfach formulieren zu können ("domänenspezifische
Sprache"). Auf diese Weise kann die Formulierung sehr nahe an der
Problemstellung gehalten werden, sie ist übersichtlich und die Arbeit
daran wenig fehlerträchtig. Darüber hinaus ist es möglich, relativ
schnell zu einer Formulierung für ein Problem zu gelangen.
In
der Sprache ConStrukt werden keine Lösungswege beschrieben, sondern
lediglich Problemstellungen formuliert. Die Auswahl der zur
Problemlösung verwendeten Algorithmen geschieht durch das
ConSolve®-Laufzeitsystem. Somit handelt es sich zugleich um eine
"deklarative Sprache".
Anhand des N-Dame-Problems soll die Sprache ConStrukt beispielhaft eingeführt werden:
Positioniere n Damen eines Schachspieles so auf einem Spielbrett der
Größe n*n, dass sich die Damen nicht gegenseitig schlagen können.
01 // Das N-Damen-Problem in ConStrukt
02 export Damebrett, Groesse > c,cpp;
03
04 // In diesem Bereich darf der Parameter liegen.
05 Groesse : {4..100};
06
07 // Verwendete Brettgroesse, sofern nicht anders spezifiziert
08 Groesse := 8;
09
10 concept Damebrett
11 : [this[{1..Groesse:Z}] : {1..Groesse :Z}];
12 begin
13 entail
14 forall spalte:{1..Groesse :Z}
15 ensure alldiff this[spalte];
16 entail
17 forall spalte:{1..Groesse :Z}
18 ensure alldiff this[spalte] + (spalte-1);
19 entail
20 forall spalte:{1..Groesse :Z}
21 ensure alldiff this[spalte] - (spalte-1);
22 end Damebrett;
Über "export... > c,cpp" werden die Konzepte "Damebrett" und
"Groesse", die im weiteren Verlauf des Beispiels eingeführt werden, für
den Zugriff aus einer C/C++-Anwendung heraus freigegeben. Die Lösungen
können über einen sogenannten Iterator aus dem Anwendungssystem heraus
aufgezählt werden. In unserem Beispiel kann zusätzlich die Größe des
Spielbrettes zur Laufzeit festgelegt werden.
Das Spielbrett
wird im Konzept "Damebrett" in Zeile 11 als eindimensionales Feld von
Spalten definiert. Jede Variable definiert die Zeilenposition einer
Dame in der entsprechenden Spalte.
Die eigentliche
Problemstellung wird im Konzept "Damebrett" in den Zeilen 13 bis 21
definiert. Um das N-Dame-Problem zu erfüllen darf sich - in jeder Spalte nicht mehr als eine Dame befinden,
- in jeder Zeile nicht mehr als eine Dame befinden und
- ausgehend von jeder Dame keine weitere Dame auf den Diagonalen befinden.
Die erste Bedingung ist bereits durch die Modellierung des Problems im
Konzept "Brett" erfüllt. Die zweite Bedingung wird durch die Zeilen 13
bis 15 sichergestellt. Die dritte Bedingung wird durch die Zeilen 16
bis 21 festgelegt.
Das N-Damen-Problem ist nun mit der
obenstehenden Problemformulierung in der Sprache ConStrukt skalierbar
beschrieben und kann in eine Anwendung integriert werden.
|
|
Impressum
