addressalign-toparrow-leftarrow-rightbackbellblockcalendarcameraccwcheckchevron-downchevron-leftchevron-rightchevron-small-downchevron-small-leftchevron-small-rightchevron-small-upchevron-upcircle-with-checkcircle-with-crosscircle-with-pluscrossdots-three-verticaleditemptyheartexporteye-with-lineeyefacebookfolderfullheartglobegmailgooglegroupsimageimagesinstagramlinklocation-pinm-swarmSearchmailmessagesminusmoremuplabelShape 3 + Rectangle 1outlookpersonJoin Group on CardStartprice-ribbonImported LayersImported LayersImported Layersshieldstartickettrashtriangle-downtriangle-uptwitteruseryahoo

Let's finish up ch. 6 with tree decomposition of CSPs (AIMA ch. 6).

It turns out that, by looking at the structure of a problem, we can find ways to solve it more efficiently; in particular, we can decompose a graph into a series of trees connected by a so-called "cutset". Trees can be solved (by topological sort) in linear time; fix the cutset, therefore, and solve the trees separately.

The cutset, on the other hand, can be n - 2 nodes in the worst case; so the actual savings are dependent on the topology of the problem.

Join or login to comment.

  • Ryan H.

    I ended up making some very significant improvements in the efficiency of my graph-based algorithm since I presented last week. In fact, there was a 99% decrease in run-time!

    I doubt that I will be able to find time to tackle another aspect of CSP before we close out the subject. However if anyone is interested in propositional logic, we'll be journeying through SAT. It appears that while very closely related CSP and SAT are oddly orthogonal. Our notions of constraints and variables are almost reversed. However both are NP-Complete, and one can encode a CSP as a SAT or a SAT as a CSP. In the context of logic systems SAT looks to be more concise, but it seems unnatural for real-world expressive problems.

    Here is a paper that exhaustively compares various mappings between the two:
    http://www.cs.toronto.edu/~fbacchus/csc2512/Lectures/2012Readings/Walsh_SATvCSP.pdf

    July 27, 2013

    • Ryan H.

      Also, the paper I showed quickly on the conversion of Non-Binary to Binary CSP indicates that it can in fact be done automatically, but that more research is necessary to determine when it may be beneficial. I dislike the graph they use to show it, but it seems that the conversion is definitely worthwhile if there are fewer constraints or if the constraints are exceptionally constrictive - at least for their problem.

      https://cs.uwaterloo.c...­

      July 27, 2013

    • Peter D.

      Fantastic, man; can't wait to see it.

      July 27, 2013

5 went

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy