Rajoitusohjelmointi

Rajoitusohjelmointi (tai rajoitusohjelmointi ) on ohjelmointiparadigma , jossa muuttujien väliset suhteet määritellään rajoitusten muodossa. Rajoitukset eroavat imperatiivisten ohjelmointikielten yleisistä primitiiveistä siinä, että ne eivät määrittele suoritettavien vaiheiden sarjaa, vaan etsittävän ratkaisun ominaisuuksia, mikä tekee tällaisesta ohjelmoinnista deklaratiivisen ohjelmoinnin muodon . Erityyppiset rajoitukset ovat mahdollisia: ne, joita käytetään rajoitteiden tyytyväisyysongelmissa (esimerkiksi "A tai B on totta"), rajoitukset, jotka ratkaistaan ​​simpleksialgoritmilla (esimerkiksi " ") ja muut. Rajoitukset on yleensä sisäänrakennettu ohjelmointikieleen tai toteutettu erillisten ohjelmistokirjastojen kautta .

Rajoitusohjelmointi liittyy läheisesti rajoitteiden tyytyväisyysteoriaan , joka tarjoaa kätevän laitteen ja yksinkertaisen muodollisen mallin kombinatoristen tekoälyongelmien esittämiseen ja ratkaisemiseen . Rajoitettujen ohjelmointityökalujen ratkaisemien ongelmien joukossa ovat elektronisten piirien varmistus, ajoitus , ajoitus ja monet kombinatoriset ongelmat.

Historiallisesti ensimmäinen muoto on rajoitettu logiikkaohjelmointi., joka perustuu logiikkaohjelmointiin , ilmestyi vuonna 1987 Prolog-II:n erityisenä rajoitusluokkana. Ensimmäiset toteutukset olivat Prolog III, CLP (R) ja CHIP. Nykyaikaisista tulkeista rajoitettua logiikkaa ohjelmointia tukee erityisesti GNU Prolog .

Rajoitukset voidaan myös sekoittaa toiminnalliseen ohjelmointiin , termien uudelleenkirjoitukseen ja pakolliseen kieleen . Ohjelmointikielet, joissa on sisäänrakennettu tuki rajoituksille, ovat Oz (toiminnallinen ohjelmointi) ja Kaleidoscope (pakollinen ohjelmointi). Useimmiten rajoitukset toteutetaan pakollisilla kielillä rajoitettujen ongelmanratkaisutyökalujen kautta, jotka ovat erillisiä kirjastoja olemassa oleville pakollisille kielille.

Kirjallisuus

• Apt KR:n rajoitusohjelmoinnin periaatteet. New York: Cambridge University Press, 2003. 407 s.
• Rossi F., van Beek P., Walsh T. (toim.) Handbook Of Constraint Programming. Elsevier, 2006. 978 s.
• Ushakov D. M., Telerman V. V. Rajoitetut ohjelmointijärjestelmät (arvostelu) // Järjestelmäinformatiikka: la. tieteellinen tr. Novosibirsk: Nauka, 2000. Numero 7: Teorian ja metodologian ongelmat rinnakkaisten ja hajautettujen järjestelmien luomiseksi. s. 275-310.
• Shcherbina O. A. Rajoitustyytyväisyys ja rajoitusten ohjelmointi , preprint, 2012.
• Antoni Niederlińskin lempeä opas rajoituslogiikkaohjelmointiin ECLiPSen kautta , kolmas painos, 2014, 570 sivua, ISBN 978-83-62652-08-2

Linkit