## Philosophy Dictionary of ArgumentsHome | |||

| |||

Author | Item | Summary | Meta data |
---|---|---|---|

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. |
AI Research Norvig I Peter Norvig Stuart J. Russell Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010 |

Ed. Martin Schulz, access date 2020-09-26