CS607 HANDOUTS PDF

Link to this post 22 Nov Download VU Artificial Intelligence – CS VU Lecture Handouts. Artificial Intelligence – CS Handouts Lecture 1 – · Artificial. Artificial Intelligence – CS VU Video Lectures. Watch Online Artificial Intelligence – CS VU Video Lectures. Artificial Intelligence – CS VU Lecture. Artificial Intelligence CS Download Complete Lectures Artificial VU Projects · Video Lectures · Handouts · Past Papers · Quizzes.

Author: Tygojar Zologami
Country: Saint Kitts and Nevis
Language: English (Spanish)
Genre: Video
Published (Last): 18 September 2013
Pages: 413
PDF File Size: 18.40 Mb
ePub File Size: 15.3 Mb
ISBN: 596-2-76892-422-1
Downloads: 9859
Price: Free* [*Free Regsitration Required]
Uploader: Tuzuru

Search the history of over billion web pages on the Internet. We select H which is the best of them. At last from H we find L as the best. Hence best first search is a greedy approach will looks for the best amongst the available options and hence can sometimes reduce hadouts searching time.

All these heuristically informed procedures are considered haneouts but they do not guarantee the optimal solution, as they are dependent on the quality of heuristic being used.

Both have their advantages and disadvantages. But one thing that lacks in both is that whenever they find a solution they immediately stop. They never consider that their might be more than one solution to the problem and the solution that they have ignored might be the optimal one. This approach is analogous to the brute force method and is also called the British museum procedure.

But in reality, exploring hahdouts entire search space is xs607 feasible and at times is not even possible, for instance, if we just consider the tree corresponding to a game of chess we will learn about game trees laterthe effective branching factor is 16 and the effective depth is The number of branches in an exhaustive survey would be on the order of 10 Hence a handouhs amount of computation power and time is required in solving the optimal search problems in a brute force manner.

One such cs60 is called branch-and-bound method. The simple idea of branch and bound is the following: The length of the complete path from S to G is 9. Also note that while traveling from S to B we have already covered a distance of 9 units.

So traveling further from S D A B to some other node will make the path longer.

So we ignore any further paths ahead of the path S D A B. We convert the map to a tree as shown below. We proceed in a Best First Search manner.

Starting at S we see that A is the best option so we explore A. Among these, D the child of S is the best option. So we explore D. Hence we block all the further sub-trees along this path, as shown in the diagram below.

We then move to F as that is the best option at this point with a value 7. We see that C is a leaf node so we bind C too as shown in the next diagram. The basic idea was to reduce the search space by binding the paths that exceed the path length from S to G. We will discuss the two most famous ways to improve it. Dynamic Programming The idea of estimates is that we can travel in the solution space using a heuristic estimate. By using “guesses” about remaining distance as well as facts about distance already accumulated we will be able to travel in the solution space more efficiently.

Hence we use the estimates of the remaining distance.

A problem here is that if we go with an overestimate of the remaining distance then we might loose a solution that is somewhere nearby. Hence we always travel with underestimates of the remaining distance. We will demonstrate this improvement with an example. The second ahndouts is dynamic programming. The simple idea behind dynamic programming is that if we can reach a specific node through more than one different path then we shall take the path with the minimum cost.

  ARAPSKO BOSANSKI RJENIK PDF

There is no need to look at any other paths to or from Expanded f Never Expanded In the diagram you can see that we can reach node D directly from S with a cost of 3 and via S A D with a cost of 6 hence we will never expand the path with the larger cost of reaching the same node.

We will discuss the technique with the same example as that in branch-and- bound. The values on handout nodes shown in yellow are the underestimates of the distance of a handout node from G. The values on the edges are the distance between two adjacent cities. We construct the tree hanoduts to the graph above.

We start with a tree with goodness of every node mentioned on it. Standing at S we observe that the best node is A with a value of 4 so we move to 4. As all the sub-trees emerging from B make our path length more than 9 units so we bound this path, as shown in the next diagram. Hence using dynamic programming we will ignore the whole sub-tree beneath D the child of A as shown in the next diagram. Now A and E are equally good nodes so we arbitrarily choose amongst them, and we move to A.

We proceed in this manner.

CS Artificial Intelligence Handouts List VU Courses for MCS – Master of Computer Science

Next we visit E, then we visit B the child of E, we bound the sub-tree below B. We visit F and finally we reach G as shown in the subsequent diagrams.

In many applications there might be multiple agents or persons searching for solutions in the same solution space. Such scenarios usually occur in game playing where two opponents also called adversaries are searching for a goal. Their goals are usually contrary to each other. For example, in a game of tic-tac-toe player one might want that he should complete a line with crosses while at the same time player two wants to complete a line of zeros.

Hence both have different goals. Notice further that if player one puts a cross in any box, player-two will intelligently try to make a move that would leave player-one with minimum chance to win, that is, he will try to stop player- one from completing a line of crosses and at the same time will try to complete his line of zeros. Many games can be modeled as trees as shown below. We will focus on board games for simplicity The rode is a game tree represent board configuration and the branches indicate how moves can connect them.

To develop this stance he uses a look ahead thinking strategy. That is, before making a move he looks a few levels down the game tree to see that what can be the impact of his move and what options will be open to the opponent once he has made this move.

To clarify the concept of adversarial search let us discuss a procedure called the minimax procedure. Here we assume that we have a situation analyzer that converts all judgments about board situations into a single, over all quality number. Positive numbers, by convention indicate favor to one player. Negative numbers indicate favor to the other player.

Artificial Intelligence – CS607 VU Video Lectures

The player hoping for positive numbers is called maximizing player or maximizer. The other player is called minimizing player or minimizer. The maximizer fs607 to keep in view that what choices will be available to the minimizer on the next step. The minimizer has to keep in view that what choices will be available to the maximizer on the next step. Consider the following diagram. The maximizer wishes to maximize the score so apparently 7 being the maximum score, the maximizer should go to C and then to G.

  AND EK-6100I PDF

Hence maximizer will end up with a score of 2 if he goes to C from A. On the other hand, if the maximizer goes to B from A the worst which the minimizer can do is that he will force the maximizer hanfouts a score of 3. Now, since the choice is between scores of 3 or 2, the maximizer will go to node B from A. Fortunately there is a procedure that reduces both the tree branches that must be generated and the number of evaluations.

This procedure is called Alpha Beta pruning which “prunes” the tree branches thus reducing the number of static evaluations. We use the following example to explain the notion of Alpha Beta Pruning.

Suppose we start of with a game tree in the diagram below.

Only two leaf nodes have been evaluated so far. Now after observing the other side of the tree, this score will either increase or will remain the same as this level is for the maximizer.

When he evaluates the first leaf node on the other side of ce607 tree, he will see that the minimizer can force him to a score of handokts than 3 hence there is no need to fully explore the tree from that side. Hence the right most branch of the tree will be pruned and won’t be evaluated for static evaluation.

Full text of “Artificial Intelligence CS Handouts Lecture 9 10”

We have discussed a detailed example on Alpha Beta Pruning in the lectures. We have shown the sequence of steps in the diagrams below. The readers are required to go though the last portion of Lecture 10 for the explanation of this example, if required. Its early in the morning and assume that no other person is awake in the town who can guide him on the way. He has to drive on his car but doesn’t know the way to air port.

Clearly identify the four components of problem solving in the above statement, i. Should he follow blind or heuristic search strategy? Try to model the problem in a graphical representation.

Q3 Given the following tree. Show the state of the data structure Q and the visited list clearly at every step. S is the initial state and D is the goal state. Support your answer with examples of a few trees. Q5 Discuss the problems in Hill Climbing.

Suggest solutions to the commonly encountered problems that are local maxima, plateau problem and ridge problem.

Given the following tree, use the hill climbing procedure to climb up the tree. Use your suggested solutions cz607 the above mention problems if any of them are encountered. K is the goal state and numbers written on each node is the estimate of remaining distance to the goal. Q6 Discuss how best first search works in a tree. Support your answer with an example tree.