CMPS140, Winter 2012, Section 01: Lecture 6

NP-complete.  
Note: No finite size problem (like 8-puzzle 15 puzzle) is NP-complete!

NP-hard means at least as hard as NP-complete.
NP-complete means  exponential of possible solutions
that can be each checked in polynomial time.  A large group of problems have been shown to be essentially equivalent incomplexity.


NP-hard problems are probably exponential (not polynomial) in the worst case
but that has never been proven...

For the 8-puzzle, the problem is finding a shortest path solution.
Is there a simple rule?



SATISFIABILITY
===========================================================================
Problem 1:
~(E implies F) and (F or (D implies ~E)). Is this satisfiable?
In conjunctive normal form:
(E) and (~F) and (F or ~D or ~E).  (use relationship p implies q to reduce to.
                             ~p or q, use De Morgans laws and others.)

In boolean matrix (with *s) form: (rows are clauses, columns are variables)
   DEF
   ---
   *1*
   **0
   001

Problem 2:
 ~((D&E) implies F) and (F or (D implies ~E)). Is this satisfiable?

In conjunctive normal form:
   (D) and (E) and (~F) and F or ~D or ~E.

   DEF
   ---
   1**
   *1*
   **0
   001

Satisfiability question is whether or not we can find a row of 0 and
1 that matches every other row in one or more places.

In problem 1, YES:010. In problem 2: NO.

NOTE: it is enough to answer the question "yes" or "no"! but
most algorithms (as below) will actually need to find a satisfying assigment to say
"yes".

--------------------------------------------------------






Tradeoff between risk and reward. Generally to achieve higher expected
reward one must take higher risk (standard deviation).

Commitment in search: cutoff one or more potential solutions without
examiningg them.

Aggressive = commital = risky

Conservative = non-committal = not risky

Manhattan Distance for tile puzzles = sum of the distance each
tile is from the goal.

Gaschnig's heuristic = optimal solution length given any tile
can swap with the blank.


Search Algorithms to Look Forward to:

 UNINFORMED:  (given legalmove black box, and goalp blackbox).
       Breadth-first-search
       Uniform-Cost Search
       Depth-first search
       Depth Bounded
       Depth First Iterative Deepening
       Bidirectional
 INFORMED:  (also given a function h that estimates distance to the goal).
       Best-First Search   
       A*
       A*-admissible
       A*-consistent
          Theorems/Proofs  (know basic ideas)

   MULTI_AGENT (games)
       Minimax
       Minimax Alpha-Beta
       How computers play chess.