Читать книгу Simulation and Analysis of Mathematical Methods in Real-Time Engineering Applications - Группа авторов - Страница 16

Several problem-solving tasks can be formulated as a state-space search. A state space is made up of all the domain states and a set of operators that transform one state into another. In a connected graph, the states can best be thought of as nodes and the operators as edges. Some nodes are designated as target nodes, and when a path from an initial state to a goal state has been identified, a problem is said to be solved. State spaces can get very big, and different search methods are necessary to monitor the effectiveness of the search [7].

A) Problem Reduction: To make searching simpler, this strategy requires transforming the problem space. Examples of problem reduction include: (a) organizing in an abstract space with macro operators before getting to the real operator details; (b) mean-end analysis, which tries to reason backwards from a known objective; and (c) sub-goaling.

B) Search Reduction: This approach includes demonstrating that the solution to the problem cannot rely on searching for a certain node. There are several explanations why this may be true: (a) There can be no solution in this node’s subtree. This approach has been referred to as “constraint satisfaction” and includes noting that the circumstances that can be accomplished in the subtree below a node are inadequate to create any minimum solution requirement. (b) In the subtree below this node, the solution in another direction is superior to any possible solution. (c) In the quest, the node has already been investigated elsewhere.

C) Use information of domains: The addition of additional information to non-goal nodes is one way to monitor the quest. This knowledge could take the form of a distance from a hypothetical target, operators that can be applied to it usefully, possible positions of backtracking, similarities to other nodes that could be used to prune the search, or some general formation goodness.

D) Adaptive searching techniques: In order to extend the “next best” node, these strategies use assessment functions. The node most likely to contain the optimal solution will be extended by certain algorithms (A ^*). The node that is most likely to add the most information to the solution process will be expanded by others (B ^*).