Zadovoljavanje ograničenja
U veštačkoj inteligenciji i operacionom istraživanju, zadovoljavanje ograničenja je proces pronalaženja rešenja kroz skup ograničenja koja nameću uslove koje varijable moraju da zadovolje.[1] Rešenje je stoga dodeljivanje vrednosti varijablama koje zadovoljavaju sva ograničenja – to jest, tačka u izvodljivom regionu.
Tehnike koje se koriste za zadovoljenje ograničenja zavise od vrste ograničenja koja se razmatraju. Često se koriste ograničenja na konačnom domenu, do te mere da se problemi sa zadovoljenjem ograničenja obično poistovećuju sa problemima zasnovanim na ograničenjima na konačnom domenu. Takvi problemi se obično rešavaju pretragom, posebno putem vraćanja unazad ili lokalnom pretragom. Propagacija ograničenja je još jedna porodica metoda koje se koriste za takve probleme; većina njih je uopšteno nepotpuna, odnosno mogu rešiti problem ili pokazati da je nezadovoljiv, ali ne uvek. Metode propagacije ograničenja se takođe koriste zajedno sa pretragom kako bi se dati problem lakše rešio. Druge razmatrane vrste ograničenja su na realnim ili racionalnim brojevima; rešavanje problema na ovim ograničenjima se vrši putem eliminacije promenljivih ili simpleks algoritma.
Zadovoljstvo ograničenjima kao opšti problem nastao je u oblasti veštačke inteligencije tokom 1970-ih (vidi na primer Laurière 1978). Međutim, kada su ograničenja izražena kao multivarijantne linearne jednačine koje definišu (ne)jednakosti, ovo polje seže do Džozefa Furijea u 19. veku: pronalazak simpleks algoritma za linearno programiranje Džordža Danciga (poseban slučaj matematičke optimizacije) iz 1946. godine omogućio je određivanje izvodljivih rešenja za probleme koji sadrže stotine varijabli.
Tokom 1980-ih i 1990-ih, razvijeno je ugrađivanje ograničenja u programski jezik. Prvi jezik koji je izričito osmišljen sa intrinzičnom podrškom za programiranje ograničenja bio je Prolog. Od tada, biblioteke za programiranje ograničenja postale su dostupne na drugim jezicima, kao što su C++ ili Java (npr. Choco za Javu[2]).
Reference
уреди- ^ Tsang, Edward (13. 5. 2014). Foundations of Constraint Satisfaction: The Classic Text. BoD – Books on Demand. ISBN 978-3-7357-2366-6.
- ^ Choco: An Open-Source java library for constraint programming. https://choco-solver.org Accessed Dec 12, 2021.
Literatura
уреди- Apt, Krzysztof (2003). Principles of constraint programming
. Cambridge University Press. ISBN 978-0-521-82583-2. - Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 978-1-55860-890-0.
- Dincbas, M.; Simonis, H.; Van Hentenryck, P. (1990). „Solving Large Combinatorial Problems in Logic Programming”. Journal of Logic Programming. 8 (1–2): 75—93. doi:10.1016/0743-1066(90)90052-7
. - Freuder, Eugene; Mackworth, Alan, ур. (1994). Constraint-based reasoning. MIT Press. ISBN 978-0-262-56075-7.
- Frühwirth, Thom; Slim Abdennadher (2003). Essentials of constraint programming. Springer. ISBN 978-3-540-67623-2.
- Guesguen, Hans; Hertzberg Joachim (1992). A Perspective of Constraint Based Reasoning. Springer. ISBN 978-3-540-55510-0.
- Jaffar, Joxan; Michael J. Maher (1994). „Constraint logic programming: a survey”. Journal of Logic Programming. 19/20: 503—581. doi:10.1016/0743-1066(94)90033-7 .
- Laurière, Jean-Louis (1978). „A Language and a Program for Stating and Solving Combinatorial Problems”. Artificial Intelligence. 10 (1): 29—127. doi:10.1016/0004-3702(78)90029-2.
- Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3.
- Marriott, Kim; Peter J. Stuckey (1998). Programming with constraints: An introduction. MIT Press. ISBN 978-0-262-13341-8.
- Rossi, Francesca; Peter van Beek; Toby Walsh, ур. (2006). Handbook of Constraint Programming. Elsevier. ISBN 978-0-444-52726-4. Архивирано из оригинала 2012-10-04. г. Приступљено 2006-10-13.
- Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 978-0-12-701610-8.
- Van Hentenryck, Pascal (1989). Constraint Satisfaction in Logic Programming. MIT Press. ISBN 978-0-262-08181-8.
- Rashidi, Hassan.; Tsang, Edward. (2012). „Novel constraints satisfaction models for optimization problems in container terminals”. Journal of Applied Mathematical Modelling. 37 (6): 3601—34. doi:10.1016/j.apm.2012.07.042 .
Spoljašnje veze
уреди- CSP Tutorial
- Constraint Satisfaction Lecture by Dr Madhu Sharma (3:47)
- Introduction of Constraint Satisfaction Problems by Edward Tsang (7:34)
- Constraint Satisfaction Problems by Wheeler Ruml (9:18)
- Lecture on Constraint Satisfaction Problems by Indian Institute of Technology Madras (51:59)
- Lecture on CSPs (1:16:39)
- Lecture on Constraint Satisfaction Problems by Berkeley AI (1:17:38)
- Graduate Course in AI 5: Constraint Satisfaction by Prof Mausam (1:34:29)