PDA

View Full Version : CS607 Assignment 2 Solution May 8,2010



viki
05-08-2010, 07:35 PM
Question No. 1:

Answer:

A goal tree describes a situation in which a goal can be satisfied by solving sub goals. If there is more than one method available, an algorithm may have to try several before finding one that works. This brings about a search problem. The nodes of a goal tree are of two types. Or nods, which represent choices; and And nodes, which represent simultaneous goals that must have compatible solutions. The tree ends at success nodes, which solve the smallest chunks of the problem.
Proving a theorem may be thought of as engendering a goal tree. Here the goal is the theorem to be proved. There may be more than one approach to proving it, so it is an Or node. Each approach may require proving several lemmas, so it is an And node. Each lemma is an Or node all over again. The leaves of the tree are goals that are identical to things that don’t have to be proved. A solution corresponds to a proof.


Question No. 2:


Answer:

The generate and test method involves generating alternative courses of action, often in a random fashion, and then determining for each course whether it will solve the problem. In generate and error, one selects a possible answer, applies it to the problem and, if it is not successful, selects or generates another possibility that is subsequently tried. The process ends when a possibility yields a solution. This method is described as exhaustive because all the options are exhausted.

Question No. 3:

Answer:

Complexity:
In artificial intelligence the search problems like in DFS the complexity is: the graph to be searched is often either too large to visit in its entirety or even infinite, and DFS may suffer from non-termination when the length of a path in the search tree is infinite. Therefore, the search is only performed to a limited depth, and due to limited memory availability one typically does not use data structures that keep track of the set of all previously visited vertices.

Completeness:
In artificial intelligence the search method like Breadth-first search will be complete if there is a solution, breadth-first search will find it regardless of the kind of graph. However, if the graph is infinite and there is no solution breadth-first search will diverge. If the shallowest goal node is at some finite depth say d, breadth-first search will eventually find it after expanding all shallower nodes.

Optimality:
In search methods the meaning of optimality is that the average cost of looking up an item is minimized. Search methods like binary search tree will be optimal if we know exactly how often each item will be accessed. Similarly breadth-first-search is optimal for unit step cost.


Question No. 4:

Answer:

These principles are playing an important role in parallel search methods to make the method efficient. In parallel search methods there is question that how to efficiently distribute the nodes of an irregular search tree among a large set of heterogeneous and volatile processors. The importance of these principles is stated as under:

Task Distribution:
A search algorithm implemented on a parallel system requires a balanced division of work between contributing processors to reduce idle time and minimize redundant or wasted effort. An alternative parallel search approach relies on distributing the tree among the processors. With this approach, the root node of the search space is given to the first processor and other processors are assigned sub trees of that root node as they request work.

Load Balancing:
When a problem is broken into disjoint subtasks the workload will likely vary among processors. Because one processor may run out of work before others, load balancing is used to activate the idle processor. In such a way it is very useful to imply in parallel search methods as it share work load to other idle processors and speed up the application.

Tree Ordering:
Problem solutions can exist anywhere in the search space. Using search method, the children are expanded in a depth-first manner from left to right, bounded in depth by the cost threshold. If the solution lies on the right side of the tree, a far greater number of nodes must be expanded than if the solution lies on the left side of the tree. If information can be found to re-order the operators in the tree from one search iteration to the next, the performance of application can be greatly improved.



Question No. 5:

Answer:

Mini-max is a two-pass search, one pass is used to assign heuristic values to the nodes at the ply depth and the second is used to propagate the values up the tree. Whereas, Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. Alpha-beta pruning is a sound optimization in that it does not change the result of the algorithm it optimizes.

viki
05-08-2010, 08:22 PM
is there is any prob to the members of the site plz feel free to ask i will try my level best to reply u