Podsumowanie (16 czerwca, wykład 15)

Na zakończenie wykładu z Programowania w Logice chciałbym dokonać krótkiego podsumowania.

  1. Omówiony został jeden z ciekawszych języków programowania, który wywodzi się bezpośrednio z logiki, a dokładniej z rachunku predykatów pierwszego rzędu [1].
  2. Prolog jest przykładem języka deklaratywnego, w którym opisuje się problem bez podawania algorytmu jego rozwiązania [2].
  3. Dostępne implementacje Prologu dostarczają nie tylko maszynę abstrakcyjną i kompilator na tę maszynę ale również liczne moduły ułatwiające praktyczne zastosowania tego języka (grafika, dostęp do baz danych, serwer/klient HTTP, parser SGML/XML, programowanie ograniczeń, przetwarzanie języka naturalnego, sieci semantyczne, obsługa SSL, …).
  4. Szczególnie interesujące są moduły CLPFD, CLPB, CLPQ, CLPR i CHR, które dostarczają programowanie ograniczeń, w istotny sposób przyspieszające znajdowanie rozwiązań.
  5. Programowanie ograniczeń dostarczane jest w postaci bibliotek i rozszerzeń dla wielu języków programowania. Należy jednak pamiętać, że po raz pierwszy opracowano je dla języka Prolog jako CLP (Constraint Logic Programming), w naturalny sposób rozszerzając deklaratywność tego języka (pierwsze implementacje to Prolog III, CLP(R) i CHIP).
  6. Między innymi firma IBM dostarcza komercyjną bibliotekę IBM ILOG CP Optimizer dla języków C++ i Java [3]. Biblioteka ta jest omawiana na kursie Technologia więzów (kurs wybieralny na studiach drugiego stopnia).

Przykłady z biblioteki IBM ILOG CP Optimizer

Język C++

// -------------------------------------------------------------- -*- C++ -*-
// File: ./examples/src/cpp/color.cpp
// --------------------------------------------------------------------------
// Licensed Materials - Property of IBM
//
// 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5725-A06 5725-A29
// Copyright IBM Corporation 1990, 2014. All Rights Reserved.
//
// Note to U.S. Government Users Restricted Rights:
// Use, duplication or disclosure restricted by GSA ADP Schedule
// Contract with IBM Corp.
// --------------------------------------------------------------------------

/* ------------------------------------------------------------

Problem Description
-------------------

The problem involves choosing colors for the countries on a map in
such a way that at most four colors (blue, white, yellow, green) are
used and no neighboring countries are the same color. In this exercise,
you will find a solution for a map coloring problem with six countries:
Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands.

------------------------------------------------------------ */

#include <ilcp/cp.h>

const char* Names[] = {"blue", "white", "yellow", "green"};

int main(int , const char * []){
IloEnv env;
try {
IloModel model(env);
IloIntVar Belgium(env, 0, 3, "B"), Denmark(env, 0, 3, "DK"),
France(env, 0, 3, "F"), Germany(env, 0, 3, "D"),
Luxembourg(env, 0, 3, "L"), Netherlands(env, 0, 3, "NE");
model.add(Belgium != France);
model.add(Belgium != Germany);
model.add(Belgium != Netherlands);
model.add(Belgium != Luxembourg);
model.add(Denmark != Germany );
model.add(France != Germany);
model.add(France != Luxembourg);
model.add(Germany != Luxembourg);
model.add(Germany != Netherlands);
IloCP cp(model);
if (cp.solve())
{
cp.out() << std::endl << cp.getStatus() << " Solution" << std::endl;
cp.out() << "Belgium: " << Names[cp.getValue(Belgium)] << std::endl;
cp.out() << "Denmark: " << Names[cp.getValue(Denmark)] << std::endl;
cp.out() << "France: " << Names[cp.getValue(France)] << std::endl;
cp.out() << "Germany: " << Names[cp.getValue(Germany)] << std::endl;
cp.out() << "Luxembourg: " << Names[cp.getValue(Luxembourg)] << std::endl;
cp.out() << "Netherlands: " << Names[cp.getValue(Netherlands)] << std::endl;
}
}
catch (IloException& ex) {
env.out() << "Error: " << ex << std::endl;
}
env.end();
return 0;
}

/*
Feasible Solution
Belgium: yellow
Denmark: blue
France: blue
Germany: white
Luxembourg: green
Netherlands: blue
*/


Język Java

// ---------------------------------------------------------------*- Java -*-
// File: ./examples/src/java/Color.java
// --------------------------------------------------------------------------
// Licensed Materials - Property of IBM
//
// 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5725-A06 5725-A29
// Copyright IBM Corporation 1990, 2017. All Rights Reserved.
//
// Note to U.S. Government Users Restricted Rights:
// Use, duplication or disclosure restricted by GSA ADP Schedule
// Contract with IBM Corp.
// --------------------------------------------------------------------------

/* ------------------------------------------------------------

Problem Description
-------------------

The problem involves choosing colors for the countries on a map in
such a way that at most four colors (blue, white, yellow, green) are
used and no neighboring countries are the same color. In this exercise,
you will find a solution for a map coloring problem with six countries:
Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands.

------------------------------------------------------------ */

import ilog.cp.*;
import ilog.concert.*;

public class Color {
public static String[] Names = {"blue", "white", "yellow", "green"};
public static void main(String[] args) {
try {
IloCP cp = new IloCP();
IloIntVar Belgium = cp.intVar(0, 3);
IloIntVar Denmark = cp.intVar(0, 3);
IloIntVar France = cp.intVar(0, 3);
IloIntVar Germany = cp.intVar(0, 3);
IloIntVar Luxembourg = cp.intVar(0, 3);
IloIntVar Netherlands = cp.intVar(0, 3);


cp.add(cp.neq(Belgium , France));
cp.add(cp.neq(Belgium , Germany));
cp.add(cp.neq(Belgium , Netherlands));
cp.add(cp.neq(Belgium , Luxembourg));
cp.add(cp.neq(Denmark , Germany));
cp.add(cp.neq(France , Germany));
cp.add(cp.neq(France , Luxembourg));
cp.add(cp.neq(Germany , Luxembourg));
cp.add(cp.neq(Germany , Netherlands));

if (cp.solve())
{
System.out.println();
System.out.println( "Belgium: " + Names[(int)cp.getValue(Belgium)]);
System.out.println( "Denmark: " + Names[(int)cp.getValue(Denmark)]);
System.out.println( "France: " + Names[(int)cp.getValue(France)]);
System.out.println( "Germany: " + Names[(int)cp.getValue(Germany)]);
System.out.println( "Luxembourg: " + Names[(int)cp.getValue(Luxembourg)]);
System.out.println( "Netherlands: " + Names[(int)cp.getValue(Netherlands)]);
}
} catch (IloException e) {
System.err.println("Error " + e);
}
}
}



Język CPO (modele dla programu CPoptimizer)

// Decision variables:
Belgium = intVar(1..4);
Denmark = intVar(1..4);
France = intVar(1..4);
Germany = intVar(1..4);
Luxembourg = intVar(1..4);
Netherlands = intVar(1..4);

/* Constraints: */
Belgium != France;
Belgium != Germany;
Belgium != Netherlands;
Belgium != Luxembourg;
Denmark != Germany;
France != Germany;
France != Luxembourg;
Germany != Luxembourg;
Germany != Netherlands;

parameters {
SearchType = DepthFirst;
}


Dziękuję wszystkim za udział w kursie. Życzę powodzenia podczas sesji i udanego odpoczynku podczas wakacji. Mam nadzieję, że spotkamy się w październiku na uczelni, a nie tylko zdalnie przez sieć.


Bibliografia

  1. John Wylie Lloyd. Foundation of Logic Programming. Springer-Verlan, 1993.
  2. Robert Kowalski. Logika w rozwiązywania zadań. WNT, 1989. (PDF)
  3. IBM ILOG CPLEX Optimization Studio. CP Optimizer User's Manual.

blog comments powered by Disqus