辅导COSC 320编程课程、写作CS，Java

” 辅导COSC 320编程课程、写作CS，JavaCOSC 320 001Analysis of Algorithms2020 Winter Term 2Project Topic Number: 5Analysis of the algorithm: An Informed Search StrategyBefore we talk about the pseudo-code, we form the question almost same as the wedid in the first milestone, specifically:States: Each state is basically representing a city on the map.Initial state: Whatever the user decides to be.Actions: A set of flights originating from the current city. For each flight, we haveflight fee, flight time, and waiting time.Transition Model: (Referring to the definition) The action of taking P from Awould result in B.Goal Test: If we are at the Final location (the destination).Path Cost: The result would be a set of actions, namely p = {P1, P2, } that wouldtransfer the initial state to the goal state. Hence, the Path Cost would be the totalfinancial cost, waiting time between flights, and flight time. Different from Lasttime, the Path Cost (g(n)) would work with a consistent heuristic function,namely h(n), to decide which node to expand.We call the function() = () + (): the estimated cost of cheapest pathcost from initial state to the goal state at node n.A Consistent Heuristic:We would use the same an artificial dataset that contains random statistics as theprevious milestone is, but we would add another matrix, namely D, to provide the extrainformation to derive the h(n). In particular, the matrix defines the real distancesbetween any two cities., , , , .Pseudo-codeThis time, we approach the problem using A* Search. Similar to Uniform CostSearch, we use a priority queue to help us decide the path. This time, we use theestimation g(n) instead of path cost.define node with the state as problems initial state, path cost zero //initializationdefine PriorityQueueNode frontier to store all the nodes and sort by the estimatedcostdefine Set explored //to be filledwhile(true)if frontier is empty then return failure //no solutionpop frontier and set node to it //now node is the lowest cost in frontierif node is at goal state then return solution //there is optimal solutionadd the state of node to the explored listnow iterate through all available actions at nodedefine child as the successor we are looking at in this iterationif childs state is not in frontier or explored then add it in to the frontierelse if childs state is in frontier and child has a lower estimated cost// noticethat we use an estimated cost instead of path cost herethen update the frontier with the child //to get optimal solutionProof of Correctness:A* Search provides an optimal solution if such solution exists.But, before we prove the correctness, lets prove that the heuristic function h(n) isconsistent. In other words, the cost of any node n to its predecessor, namely n, plusits estimated cost is Always greater or equal to ns estimated cost.() (, ,, ) + ()Proof:Recall that we define the path cost to be a sum of three terms:(, ,, ) = 1 1 + 2 2 + 3 3 1 1 , 2, 3 0 1, 2, 3 , From this, we can derive that:1(, ) 1 1 + 2 2 + 3 3 = (, , , ) (0)Now, according to the triangular inequality:() 1(, ) + ()Take in Statement 0 yields this:() (, , , ) + ()Lastly, add the g(n) on both sides, we have completed the proof:() = () + () = () + (, ,, ) + () () + ()Now that we have proved the heuristic function is consistent, we have basicallyderived that the values of estimations are always increasing along the path). See this: S , () () + ()Now lets prove with induction that whenever the A* search expanded a node, itexpands the node with an optimal path. (Notice that this is not exactly same asproving A* search yields the optimal solution. What we are going to prove containsthe statement.)Base Case: The first node is always expanded with an optimal cost of 0.Inductive Step: We argue by contradiction.We assume the IH holds that all the nodes up to 0 are expanded with anoptimal cost. However, it would be absurd if we assume that 0 is not expandedwith an optimal cost. Since there would have been another sitting on thepresumably more optimal path that would have been selected by the priorityqueue in the first place.Hence, ~ 0 0 Conclusion: By the principle of Strong Induction, we have derived that all nodesin A* search are expanded with optimal solution.Hence, A* search provide optimal solution to a graph search problem.Running Time: A* searchs time complexity is determined by the heuristic. Thenumber of nodes extended in the worst case of an unbounded search space isexponential in the depth of the solution (the shortest path) d: (), where b is thebranching factor (the average number of successors per state). This assumes that agoal state exists at all, and is reachable from the start state; if it is not, and the statespace is infinite, the algorithm will not terminate.The time complexity is polynomial when the search space is a tree, there is a singlegoal state, and the heuristic function h meets the following condition:where h* is the optimal heuristic, the exact cost to get from x to the goal. In otherwords, the error of h will not grow faster than the logarithm of the perfectheuristic h* that returns the true distance from x to the goal. [2]Data Structure.A priority queue is commonly used in A* implementations to perform the repeatedcollection of minimum (estimated) cost nodes to extend. The open set, also known asthe fringe, is a priority queue. The node with the lowest f(x) value is removed fromthe queue at each step of the algorithm, and its neighbors f and g values are modifiedaccordingly, and these Neighbors are returned to the queue. The algorithm continuesuntil a target node is found (the node with the lowest F value of all fringe nodes).Since h at the target is zero in a consistent heuristic, the F value of that goal is also thecost of the shortest path. [3]Unexpected Cases/Difficulties.One of the difficulties is the dataset: how are we defining the path cost and estimatedcost matrix exactly? Same as what weve mentioned in the last milestone, when wedefine a path cost P, we define it as x1*f1+ x2*f2+ x3*f3 where f is in the unit of CADor hours and x is empirically determined.However, when we look at the heuristic function, we are measuring the distancedirectly. It guarantees the function to be consistent, while it does not incorporate timeelements. One reason is that flight time and wait time estimations are untrivial toderive when we try to look at two cities that do not have any available flight inbetween. In fact, we cannot provide any coefficient k based on existing factors suchthat: 1, () = () + (), () We will look into this problem again when we implement the function. If it turns outsuch k can be derived, We will modify the pseudo-code and provide the proof ofcorrectness again.Task Separation and Responsibilities.Jack Wang did the first draft of the Second Milestone including Data Structure andRunning Time.Larry Gu revised the first draft, specifically, he:rewrote the Analysis of the algorithmprovided explanations For the heuristic functionprovided the Pseudo-coderewrote the Proof of Correctnessrewrote the Unexpected Cases/Difficulties.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp

“