Philosophy Dictionary of ArgumentsHome
| |||
|
| |||
| Problems: A problem is a negative situation that requires attention and effort to resolve. It can be a challenge, obstacle, or difficulty that prevents someone from achieving their goal. See also Problem solving, Goals, Thinking, Cognition._____________Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments. | |||
| Author | Concept | Summary/Quotes | Sources |
|---|---|---|---|
|
Peter Norvig on Problems - Dictionary of Arguments
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. Translations: Dictionary of Arguments The note [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition. |
Norvig I Peter Norvig Stuart J. Russell Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010 |
||
Ed. Martin Schulz, access date 2024-04-19