” CS 440程序 写作、 辅导algorithm编程Computer Science Department – Rutgers University Spring 2021CS 440: This Maze is on Fire 16:198:440A maze will be a square grid of cells / locations, where each cell is either empty or occupied. An agent wishes totravel from the upper left corner to the lower right corner, along the shortest path possible. The agent can onlymove from empty cells to neighboring empty cells in the up/down direction, or left/right – each cell has potentiallyfour neighbors.Figure 1: Successful and Unsuccessful Maze Environments.Mazes may be Generated in the following way: for a given dimension dim construct a dim x dim array; given aprobability p of a cell being occupied (0 p 1), read through each cell in the array and determine at random ifit should be Filled or empty. When filling cells, exclude the upper left and lower right corners (the start and goal,respectively). It is convenient to define a function to generate these maps for a given dim and p.Figure 2: Maps generated with p = 0.1, 0.3, 0.5 respectively.1Computer Science Department – Rutgers University Spring 2021Preliminaries Problem 1: Write an algorithm for generating a maze with a given dimension and obstacle density p. Problem 2: Write a DFS algorithm that takes a maze and two locations within it, and determineswhether one is reachable from the other. Why is DFS a better choice than BFS here? For as large adimension as your System can handle, generate a plot of obstacle density p vs probability that S canbe reached from G. Problem 3: Write BFS and A algorithms (using the euclidean distance metric) that take a maze anddetermine the shortest path from S to G if one exists. For as large a dimension as your system canhandle, generate a plot of the average number of nodes explored by BFS – number of nodes explored byA vs obstacle density p. If there is no path from S to G, what should this difference be? Problem 4: Whats the largest dimension you can solve using DFS at p = 0.3 in less than a minute?Whats the largest dimension you can solve using BFS at p = 0.3 in less than a minute? Whats thelargest dimension you can solve using A at p = 0.3 in less than a minute?Consider, as you solve these three problems, simple diagnostic criteria to make sure you areon track. The path returned by DFS should never be shorter than the path returned by BFS.The path returned by A should not be shorter than the path returned by BFS. How big can andshould your fringe be at any point during these algorithms?However, we are are not just interested in solving static mazes – these mazes are on fire, actively burning down aroundyou. We model this in the following way: for every move the agent makes, the fire then advances (described below),and they alternate back and forth. The agent would like to exit the maze prior to running into the fire. Under thismodel, while an agent might utilize a search algorithm to generate an optimal path through the the current stateof the maze (analyzing the current state and planning a future path through it), it will not necessarily be valid forfuture states of the maze. This means that while the agent may plan a short path through the maze, whether or notit will be able to take that path depends on the fire. In this case, the environment is dynamic, changing over time.We model the advancement of the fire in the following way: any cell in the maze is either open, blocked, or onfire. Starting out, a Randomly selected open cell is on fire. The agent can move between open cells or choose tostay in place, once per time step. The agent cannot move into cells that are on fire, and if the agents cell catcheson fire it dies. But each time-step the agent moves move, the fire may spread, according to the following rules: Forsome flammability rate 0 q 1 If a free cell has no burning neighbors, it will still be free in the next time step. If a cell is on fire, it will still be on fire in the next time step. If a free cell has k burning neighbors, it will be on fire in the next time step with probability 1 (1 q)k.We might express this with the following pseudocode for advancing the fire one step:2Computer Science Department – Rutgers University Spring 2021def advance_fire_one_step(current maze):create a copy of the current mazefor every (x,y) in the current maze:if (x,y) is not on fire in current Maze and (x,y) is not an obstacle:count the number of neighbors of (x,y) in current maze that are on firestore that as kprob = 1 – (1-q)^kif random() = probmark (x,y) as on fire in maze copyreturn maze copyNote, for q = 0, the fire is effectively frozen in place, and for q = 1, the fire spreads quite rapidly. Additionally,blocked cells do not burn, and may serve as a barrier between the agent and the fire.How can you solve the problem (to move the agent from upper left to lower right, as before) in this situation?Consider the following base line strategies:Strategy 1) At the start of the maze, wherever the fire is, solve for the shortest path from upper left to lower right, andfollow it until the agent exits the maze or burns. This strategy does not modify its initial path as the firechanges.Strategy 2) At every time step, re-compute the shortest path from the agents current position to the goal position, basedon the current state of the maze and the fire. Follow this new path one time step, then re-compute. Thisstrategy constantly re-adjusts its plan based on the evolution of the fire. If the agent gets trapped with nopath to the goal, it dies.For each strategy, for as large a dimension as your system can handle, and obstacle density p = 0.3, generate a plotof average successes vs flammability q. Which is the superior strategy? For each test value of q, generate and solveat least 10 mazes, restarting Each 10 times with new initial fire locations. Note: Please discard any maze wherethere is no path from the start to the goal node. Additionally, please discard any maze where there is no path fromthe initial position of the agent to the initial position of the fire – for these mazes, the fire will never catch the agentand the agent is not in Danger. Your prior functions will be useful here.Come up with your own strategy to solve this problem (+5 points are available if you come up with a clever acronymfor your strategy), and try to beat both the above strategies. How can you formulate the problem in an approachableway? How can you apply the algorithms discussed? Note, Strategy 1 does not account for the changing state of thefire, but Strategy 2 does. But Strategy 2 does not account for how the fire is going to look in the future. How couldyou include that?A full credit solution must take into account not only the current state of the fire but potential future states of thefire, and compare the Strategy to Strategy 1 and Strategy 2 on a similar average successes vs flammability graph.Additionally, while your strategy may increase survivability, analyze the time costs of your strategy compared to theother two – in a Real burning maze, you have limited time to make your decisions about where to move next. Beclear and explicit in your writeup, presenting your reasoning and ideas behind your strategy.3Computer Science Department – Rutgers University Spring 2021 Problem 5: Describe your improved Strategy 3. How does it account for the unknown future? Problem 6: Plot, for Strategy 1, 2, and 3, a graph of average strategy success rate vs flammabilityq at p = 0.3. Where do the different strategies perform the same? Where do they perform differently?Why? Problem 7: If you had Unlimited computational resources at your disposal, how could you improve onStrategy 3? Problem 8: If you could only take ten seconds between moves (rather than doing as much computationas you like), how Would that change your strategy? Describe such a potential Strategy 4.Your report Needs to be clear to the point that the grader can understand and reconstruct yourstrategy from your description. If they cant, theyre justified in giving no credit, and youllhave to argue for it back later.如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
