ConSolve: 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

  1. in jeder Spalte nicht mehr als eine Dame befinden,
  2. in jeder Zeile nicht mehr als eine Dame befinden und
  3. 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. 

Kontakt

Haben Sie Interesse an unseren Produkten?

Mitglied im

Software-Cluster
United Web Solutions

Das Unternehmen

Die SIEDA GmbH entwickeln und vertreibt Standardsoftware zur unternehmensweiten Ressourcenplanung.

Kernprodukt ist unsere Software zur Dienstplanung und Zeiterfassung OC:Planner, die von mehr als 400 Kunden insbesondere in Kliniken, Pflege- und Betreuungseinrichtungen, Rettungsdiensten und Feuerwehren verwendet wird. Personaleinsatzplanung und Arbeitszeitmanagement mit OC:Planner steigert nachweisbar die Effizienz unserer Kunden und reduziert ihre Kosten.