Monday, October 17, 2011

PROBLEM SOLVING







REVISED: Wednesday, February 4, 2015


I. What is a Problem?

A. An Initial State

B. A Function Actions

Actions takes a state as input and returns a set of possible actions the agent can execute when the agent is in this state.

C. A Function Result

Result takes as input a state and an action, and delivers as its output, a new state.

D. A Function Goal Test

Goal Test takes as input a state, and delivers as its output, a Boolean value, true or false, telling us this state is a goal or not.

E. A Path Cost Function

The Path Cost Function takes a path, a sequence of state/action transitions, and returns a number which is the cost of that path. The path cost function is additive, the sum of the cost of the individual steps. The step cost function takes a state, an action, and the resulting state from that action, and returns a number n which is the cost of that action.

II. Search Algorithms

A. Breadth-First

We always expand first the shortest paths.

Breadth-First will find the optimal shortest path.

Even if the tree is infinite, Breadth-First will find a goal placed at any finite level.

B. Cheapest-First

We always expand first the path with the lowest total cost.

Cheapest-First will find the optimal cheapest path.

Even if the tree is infinite, Cheapest-First will find a goal placed at any finite level.

C. Depth-First

Which is the opposite of Breadth-First search.

In Depth-First search we always expand first the longest path.

Depth-First will not find the optimal shortest path.

If the tree is infinite, Depth-First will not find a goal placed at any finite level.

D. Greedy Best-First

Our search is directed towards the goal.

E. A*

The A* works by always expanding the path that has a minimum value of the function f which is defined as a sum of the g plus h components. The function g(path) is just the path cost. The function h(path) equals h(s) which is the final state of the path which is equal to the estimated distance to the goal.

The result is the best possible search strategy. It finds the shortest length path while expanding the minimum number of paths possible.

It could be called "Best Estimated Total Path Cost First."

It finds the lowest cost path if: h(s), the h function for a state, is less than or equal to the true cost. In other words, we want the h to never overestimate the distance to the goal. h is optimistic. h is admissable to use it to find the lowest cost path.

III. Heuristics

h1 equals the number of misplaced blocks.

h2 equals the sum of the distances each block would have to move to get to the right position.

h2 is always greater than or equal to h1.   An A* search using h2 will always expand fewer paths than one using h1.

IV. Problem-Solving Technology

Problem-solving technology is guaranteed to work when the following set of conditions is true:

A. Observable Domain

The domain must be fully observable. We must be able to see what initial state we start out with.

B. Known Domain

The domain must be known. We have to know the set of available actions to us.

C. Discrete Domain

The domain must be discrete. There must be a finite number of actions to choose from.

D. Deterministic Domain

The domain must be deterministic. We have to know the result of taking an action.

E. Static Domain

The domain must be static. There must be nothing else in the world that can change the world except our own actions.

V. Linked List Node

Each node in a linked list is a data structure and it has four fields.

A. State Field

State field indicates the state of the field at the end of the path.

B. Action Field

Action field indicates the action it took to get there.

C. Cost Field

Cost field indicates the total cost.

D. Parent Field

Parent field is a pointer to another node.

Elcric Otto Circle



--> --> -->




How to Link to Elcric Otto Circle's home page!

It will appear on your website as:

Link to: "ELCRIC OTTO CIRCLE's Home Page".




No comments:

Post a Comment