Automatsko rešavanje konstruktivnih problema u geometriji

Abstract

Konstruktivni problemi u geometriji su problemi kod kojih je potrebno pomoću lenjira i šestara konstruisati neku geometrijsku figuru, pod pretpostavkom da su zadati neki njeni elementi. Pored značaja u matematičkom obrazovanju, ovakvi problemi u poslednje vreme postaju značajni i u računarstvu, pre svega u kontekstu automatizacije procesa njihovog rešavanja. Sa računarskog aspekta, ovakvi problemi spadaju u probleme pretrage, te je za njihovo rešavanje pogodno koristiti metode i alate veštačke inteligencije. U ovom izlaganju razmatramo dva različita pristupa ovom problemu. Prvi pristup podrazumeva razvoj specifičnog algoritma pretrage za rešavanje konstruktivnih problema. Ovaj pristup nam pruža mogućnost prilagođavanja domenu primene, kao i upotrebe specifičnih efikasnih heuristika prilikom pretrage. Kao ilustracija ovog pristupa, biće razmotren konstrukcijski rešavač ArgoTriCS [ 1], razvijen u programskom jeziku Prolog. Drugi pristup podrazumeva upotrebu postojećih alata veštačke inteligencije koji su veoma efikasni u rešavanju problema kombinatorne pretrage uopšte. U ovom pristupu na nama je samo da konstruktivne probleme modelujemo na odgovarajući način i njihovo rešavanje prepustimo gotovom alatu. Kao ilustraciju ovog pristupa, razmotrićemo upotrebu rešavača ograničenja nad konačnim domenima, kao i modelovanje konstruktivnih problema na jeziku MiniZinc [ 2]. Ova dva pristupa biće upoređena na Vernikovom korpusu [ 3] konstruktivnih problema, kod kojih je cilj konstruisati trougao, pod pretpostavkom da su date lokacije triju značajnih tačaka trougla.