|Norvig I 108
Problem/artificial intelligence/AI research/Russell/Norvig: A problem consists of five parts: the initial state, a set of actions, a transition model describing the results of those actions, a goal test function, and a path cost function. The environment of the problem is represented by a state space. A path through the state space from the initial state to a goal state is a solution. >Belief-State.
Norvig I 222
(…) the only way we can possibly hope to deal with the real world is to decompose it into many [independent] subproblems. (>Constraint Satisfaction Problems/CSP/Norvig.)
Independence: Independence can be ascertained simply by finding connected components of the
constraint graph. Each component corresponds to a subproblem CSPi. If assignment Si is a solution of CSPi, then Ui Si is a solution ofUi CSPi. Why is this important? Consider the following: suppose each CSPi has c variables from the total of n variables, where c is a constant. Then there are n/c subproblems, each of which takes at most dc work to solve,
Norvig I 223
where d is the size of the domain. Hence, the total work is O(dcn/c), which is linear in n; without the decomposition, the total work is O(dn), which is exponential in n. Let’s make this more concrete: dividing a Boolean CSP with 80 variables into four subproblems reduces the worst-case solution time from the lifetime of the universe down to less than a second. Completely independent subproblems are delicious, then, but rare. Fortunately, some other graph structures are also easy to solve. For example, a constraint graph is a tree when any two variables are connected by only one path._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010