Srching:Man has ability to find things and best solutions for satisfying own desires but one thing which we never rlized and that is our srching power to find anything which is most useful and helpful for us. Whenever we face any problem we do srch for best solution. As when we srch we got lot of options to solve our problems but we select best one and most of the people says the actual problem arise when we have lot of options and select best one but in Artificial lice Different Srching Aorithms help us to select best choice from many and AI major use in Srching Aorithms. The main theme of this assignment also based on Srching Aorithms of AI. There are four major characteristics to analyze Srching strategy on which base we can say our srching aorithm is best and we got our solution in most efficient manner. Below is the four major characteristics to analyze Srching strategy
Completeness:
The given srching aorithm has ability to complete whole srch and give best solution in end.Time Complexity: How much Time will be consumed to get proper solution by following srching technique.Space Complexity: How much sources will utilize during srching process.Optimality: Find out best quality solution from many.Without above mentioned Srch strategy we can’t find best Srching Aorithm.egories of Srching Strategy• Uninformed/Blind• Informed/Heuristic• Any Path/Non-optimal• Optimal PathQ#1:You have to analyze aorithms under blind/uninformed srch egory i.e. Brdth First Srch, Depth First Srch, Depth Limited Srch and Iterative Deepening. You must have to discuss all four characteristics for ch aorithm ONE BY ONE.
Uninformed/Blind srch is same like work with blank mind but this also implement using some strategy. In this srch there is no proper information about how many steps or path cost required to rched desired goal that’s why it also called Blind srch. Six Uninformed srch strategies are as follow• Brdth First Srch• Depth First Srch• Depth Limited Srch• Iterative Deepening Srch• Bidirectional Srch• Uniform Cost Srch
1.Brdth First Srch:Brdth First Srch is one of the simplest srch strategy by expanded the root Node and then erated other nodes from Root in this way got successors. This srch can also implemented by calling eral Srch Aorithm. In this manner a queuing function is used which puts the newly erated states at the end of the queue. This aorithm works at level wise mn level to level goal find and this is best systematic srching technique in which goal can find sily and quickly. This is also time saving because brdth first srch always find shallowest goal state first. Now below is the Characteristics of Srching Strategy to see wther Brdth First Srch fulfill all four characteristics or notCompleteness: If goal exist in finite depth then terminate.Time Complexity: Not time saving because as your level of srch incrsing your time will also incrse which will become major hdache to solve problemSpace Complexity: Take lot of memory because all the lf nodes must be maintained in memoryOptimality: Brdth First Srch considered good for optimality because if you goal exist in upper level then you can sily find and rched.
2.Depth First Srch:In this Blind Srch aorithm move from root to left most successors node. It is best use of memory because it store only one path from root to lf node. If goal not find then move to siblings if they exist but with same strategy to move left node/link. One of the most important thing which should be follow when applying this strategy, alrdy visited/explore or write node will not visited again so best way is to discard all visited nodes. In many Problems srching Depth First Srch considered faster than Brdth First Srch because it uses best technique by exploring small portion of whole tree for finding solution.Completeness: Completeness effect in two ways if the desired goal gain at shallowest level then terminate otherwise the srching continue and in big tree structure its most difficult. So in short its not Complete.Time Complexity: Depth First Srch take less time because in this technique specific path follow instd of flowing whole tree and just move downward so less time required.Space Complexity: Best use of resources because in this technique on root to lf node path is saved and if goal not found then visited nodes will discard so it is modest way to use memory.Optimality: One of the major drawback of depth first srch is that it may get stuck on different states because if goal not found and control move deep to deep node then its difficult to find goal because you away from rl goal as the rl goal may exist at upper level so in this way it is not optimal.
3.Depth Limited Srch:This srching aorithm works same like Depth First srch as its time and space complexity is same like Depth first srch but with little modifiion as its name suggest Limited srch and this can be done through eral srch aorithm. As is alrdy discussed in DFS the goal can’t find if srches down with infinite length tree so in this way DFS not guaranteed to find the solution that’s why it not fulfill the characteristic of Completeness so for solving this problem of DFS introduced DLS. DLS guaranteed to find solution with in given depth limit but its not sure to find most optimal path so its not optimal. Completeness: It is complete srch strategy.Time Complexity: Just move root to lf so sy take less time as compared to others srching aorithms.Space Complexity: Less space required no need to store extra nodes which visited alrdy.Optimality : Not optimal
4.Iterative Deepening SrchIterative Deepening Srch is the combination of Depth First Srch and Brdth First Srch. In short this combine the best part of both aorithms like IDS is complete and optimal like Brdth First Srch with use of less memory like Depth First Srch. If take its time then its not better than Brdth First Srch because if goal not found then nodes expanded on ch low level. Iterative Deepening is the best srch technique work in large srch space with unknown depth solution.Completeness: yes! Follow BFS best technique so it is complete srching aorithm. So when goal achieved terminateTime Complexity: Its not time saving in other words its most worse than BFS in matter of time.Space Complexity: Use less space by using technique of DFS.Optimality : yes! Find goal by using best technique so it become sy to rch desired goal by srching best method
Q#2:Compare these aorithms with ch other and discuss with rsons/examples that which aorithm is better then other and in what situations/environments.
The above mentioned srching aorithms in Answer 1 has some special characteristics which make them differ from ch other. Some aorithms are best in some environment and some are best in other environment these both depend on their characteristics. According to the above discussed unique characteristics of four srching aorithms we can compare them. These aorithms compare according to Characteristics of srching strategy which are completeness, time complexity, space complexity and optimality.
Brdth First Srch & Depth First SrchThese both are most important and simple in implementation Uninformed/Blind srch aorithms and both has opposite characteristics. If we discuss according to their performance and faster srching then BFS said to be faster because it uses shallowest srching technique and works at level wise and on other hand DFS srching to depth so if your goal exist in upper level like Goal may be at level 2 then BFS find it fast and show result but if tree is long then DFS srch depth and may b just srching on depth level and got stuck.Example 1:If our Goal is UOG and we move from Jhelum then we have many paths to rch UOG and some may be not take us at UOG so which we select?If apply BFS then we will got our Goal at level 3 and terminate but if we apply DFS then srch start from jhe then sar,mad,kal,lal so its not optimal way to find path.
Depth First Srch & Depth Limited SrchDepth Limited srch is use to eliminate the problems of DFS because in DFS goal may not be find if length of tree infinite so with DLS we can overcome from this problem by setting the limit and the srch process start and do work until limit value become false. Limit value set according to given problem like in below example Limit value will be l = 3Example 2: In the above our Goal is 4 then the DLS works well because in this lst one goal state at a depth which less than l, so in this way this aorithm guaranteed to find goal. If apply DFS then that goal move to left most node with depth so its become difficult to rched our goal.
Iterative Deepening Srch VS DFS,BFS & DLSIDS is combine with the best characteristics of DFS and BFS. IDS is basically use to overcome the problem of DLS because in DLS if we don’t have id about the lowest depth of a goal state then always find the best limit l by trying all possible depths for l until we achieved a goal state. But this technique become wasteful because all the DLS for limit l less than the goal level are not useful and its may be possible many states are expanded many times. So in DLS srching time may be spent at the deepest level of the srch tree. So this Srching aorithm works well and in optimal way.Example 3:If we assume we don’t have any goal in above example and perform srch to find goal that not exist in above example like D so the iteration will be start from Depth 0 where just one start state A which is not the goal so we expand A and got two child B and C as one thing in mind perform DFS and BFS properties and then we see our goal on ch depth and expand further in this way our iterations will beAABCABEFCGIABEJFKCGLIMIn this way whole tree will be srched and it is Complete and Optimal like BFS because all Nodes expanded on ch level and it is also modest memory requirements like DFS because just store the result of goal and other visited nodes discard mn not visit again and again.So now if Compare all Four aorithms in terms of Characteristics of Srching Strategy then result will be
Completeness:BFS: Goal exist in finite depth then terminateDFS: Mostly problem srching its not completed and got stuckDLS: Provide complete srch strategyIDS: Best technique for complete srch
Time Complexity:BFS: Not Time SavingDFS: Take less time in some situation but most of time also show opposite rctionDLS: Take less timeIDS: Not time saving because its time complexity equal to BFS
Space Complexity:BFS: Using lot of memory so not good for resourcesDFS: Save lot of memory best for utilizing resourcesDLS: Less space requiredIDS: Use technique of DFS so less space use
Optimality:BFS: Provide optimal solutionDFS: Not give optimal solutionDLS: Not optimal for finding solutionIDS: Best! Provide optimal solutionSo, in short best one aorithm is IDS but other also best depend on their problem situation as discussed above comparison.
Q#3:Explain how we can improve the performance of all said aorithms?
Before choosing the Srching Aorithm first analyze the problem carefully because without any proper knowledge and understanding about problem we can’t move further and select best srching technique. As in above two questions briefly explain their advantages and disadvantages which gives according to the four basic pillars of srching in AI those are the Characteristics. And the Aorithm which satisfied the maximum characteristics of srching strategy is Iterative Deepening Srch. As we can’t brk the rules which defined in above four srching aorithms so the best way is to improve their performance is chose best srching aorithm according to problem. Analyze the problem carefully and see which aorithms satisfied maximum characteristics and then apply srch.
Q#4:Convert following graph in tree and apply Brdth First Srch. You have to apply step by step process and show status of OPEN and CLOSE queues.Answer 4:Root Node: 0
Q#5: Convert following graph in tree and apply Depth First Srch. You have to apply step by step process and show status of OPEN and CLOSE queues.Answer 5:
Directed
Open State
Undirected:As it has lot of branches so it has lot of Open[] and Close[]
No comments:
Post a Comment