The temporal constraint satisfaction problem (CSP) offers a formalized way to reason about in which order tasks should be accomplished. Using this we can model a wide set of specific problems from scheduling to AI. In this thesis we present two algorithms, Algorithm A and Algorithm B, to solve temporal CSPs focused on improving the worst case time complexity. The first algorithm solves temporal CSPs by an exhaustive search of all weak orderings. The time complexity is in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathcal%7BO%7D((0.53n)%5E%7Bn%7D%20%5Ccdot%20poly(n))" />, thus within a polynomial factor of the corresponding Ordered Bell Number. We also show that it can solve CSP in Allen’s algebra within a polynomial factor of the corresponding number of relations between intervals on a line, thus in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathcal%7BO%7D((0.75n)%5E%7B2n%7D%20%5Ccdot%20poly(n))" /> time. The second algorithm also solves temporal CSPs but where the constraints have a bounded number of disjuncts. It will assume some order and then make a backtracking search guided by the constraints. In this case the time complexity will be in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathcal%7BO%7D(n!%20%5Ccdot%20poly(n))%20=%20%5Cmathcal%7BO%7D((0.37n)%5E%7Bn%7D%20%5Ccdot%20poly(n))" />. Finally we will show that this also improves the time complexity of CSP in Allen’s to <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathcal%7BO%7D((2n)!%20%5Ccdot%20poly(n))%20=%20%5Cmathcal%7BO%7D((0.74n)%5E%7B2n%7D%20%5Ccdot%20poly(n))" />.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-129778 |
| Date | January 2016 |
| Creators | Stockman, Peter |
| Publisher | Linköpings universitet, Institutionen för datavetenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds