我已经写了60 多行了，可以run 但是没有output 乌龟在n*n 的矩阵里乱走得最高分
As Eve has now passed level 1 of Turtle Dungeon Crawler, stage 2 comes with significantly more hazards, risks, and problems!
- The goal and start coordinates are now not at fixed locations anymore.
- The treasures and traps are now arbitrary scores.
- Eve can move in all 8 directions (N, NE, E, SE, S, SW, W, NW)
Heuristics
Heuristic techniques are widely used within the world of computing and mathematics to simplify decision-making processes for algorithms. Essentially, heuristics are small rules, guidelines, or rules of thumb that inform your algorithms in a quick and efficient manner to lead them to the goal.
An example of a heuristic may be the decision of selecting a career path. If you choose to become a lawyer, this may not pay well in the short term. However, (if things go well) the career path can lead to higher pay in the future. The underlying analysis involved in making this decision is an example of a heuristic that prioritises future success by making what seems to be a poor decision in the short term.
There are also heuristics that do not prioritise future gains but rather prefer immediate success. There may be many practical reasons for this sort of approach. Yes, in fact, you have already implemented a small heuristic for Greedy Search (Q3 Project 1), which follows the heuristic of making the locally optimal choice at each move (choose the move that yields the best score at the current position). In this project, you will be implementing a more informed heuristic for your algorithms to help guide Eve through more caves!
Yes, in fact, you have already implemented a small heuristic for Greedy Search (Q3 Project 1), which follows the heuristic of making the locally optimal choice at each move (choose the move that yields the best score at the current position). In this project, you will be implementing a more informed heuristic for your algorithms to help guide Eve through more caves!
Question 1 Overview
Your informed heuristic is defined as Score - <strong>(</strong>100 x ManhattanDistance<strong>)</strong> for Question 1, where:
- Score is the value of the coordinate being evaluated.
- Manhattan Distance is the sum of the absolute differences of two Cartesian coordinates.
- The Manhattan Distance equation is defined as:
- |x2−x1|+|y2−y1|
- where (x1,y1) is your current coordinate and (x2,y2) is the coordinate of the goal location.
Remarks
Do note that the heuristic being implemented in Questions 1 and 2 aren't exactly an ideal solution by any means. In fact, it has many quirks involved in its structuring that leads to the specific behavior that may not be ideal. You can investigate this by presenting complex scenarios and realise that it does not generate an optimal solution. You can tinker with this further to try and find a better heuristic.
There are also heuristics that do not prioritise future gains but rather prefer immediate success. There may be many practical reasons for this sort of approach. Yes, in fact, you have already implemented a small heuristic for Greedy Search (Q3 Project 1), which follows the heuristic of making the locally optimal choice at each move (choose the move that yields the best score at the current position). In this project, you will be implementing a more informed heuristic for your algorithms to help guide Eve through more caves!
也有一些启发式的做法，不把未来的收益放在首位，而是喜欢眼前的成功。这类方法可能有很多实际原因。是的，事实上，你已经实现了贪婪搜索的一个小启发式（Q3项目1），它遵循的是在每一步棋中做出局部最优选择的启发式（选择在当前位置产生最佳分数的棋步）。在这个项目中，你将为你的算法实现一个更明智的启发式，以帮助引导夏娃走过更多的洞穴!
Yes, in fact, you have already implemented a small heuristic for Greedy Search (Q3 Project 1), which follows the heuristic of making the locally optimal choice at each move (choose the move that yields the best score at the current position). In this project, you will be implementing a more informed heuristic for your algorithms to help guide Eve through more caves!
是的，事实上，你已经实现了贪婪搜索的一个小启发式（Q3项目1），它遵循的是在每一步棋中做出局部最优选择的启发式（选择在当前位置产生最佳分数的棋子）。在这个项目中，你将为你的算法实现一个更明智的启发式，以帮助引导Eve通过更多的洞穴!
Question 1 Overview
Your informed heuristic is defined as Score - (100 x ManhattanDistance) for Question 1, where:
- Score is the value of the coordinate being evaluated.
- Manhattan Distance is the sum of the absolute differences of two Cartesian coordinates.（我觉得就是当前的位置和下一个位置的距离）
- 得分是被评估坐标的值。
- - 曼哈顿距离是两个笛卡尔坐标的绝对差值之和。
The Manhattan Distance equation is defined as:公式
where (x1,y1) is your current coordinate当前坐标and (x2,y2) is the coordinate of the goal location.（我理解是矩阵里最右下那个位置，就是他最后结束的地方）
You are to write a function road_to_freedom(current_pos,goal_pos, matrix), where: 写一个def road_to_freedom(current_pos,goal_pos, matrix),
- current_pos 当前坐标is Eve's current coordinate in form (x, y);
- goal_pos is the goal coordinate in form (x, y);我理解是矩阵里最右下那个位置，就是他最后结束的地方）n*n 的矩阵就是（n,n）
- and matrix is the nested list representation you should be familiar with from Project 1.------[[0,1000,-500],[1500,1000,1000],[-500,0,1000]]
The function should return the next coordinate with the highest heuristic score.
- If a tie occurs, then precedence is given first to the coordinate closer to the goal location.
- If there is also a tie in the manhattan distance, then you should return the coordinate using the order of preference from North going clockwise (N, NE, E, SE, S, SW, W, NW).
该函数应返回下一个启发式得分最高的坐标。
如果出现了并列，那么优先考虑离目标位置较近的坐标。
如果在曼哈顿距离上也出现了并列，那么应该按照从北到顺时针的优先顺序返回坐标（N、NE、E、SE、S、SW、W、NW）。
PS:我理解诶的是：1.平分出现时，就是Manhanttan距离不变。最一开始的位置和最终位置之间的距离不变。2.要算的是next position 就是当前位置的下一个移动到的位置。要算next position 与goal position 就是最后结束位置的manhanttan距离,哪个位置更近。3. 因此next position 不同，与goalposition 的 距离也不同。The heuristic is:Score - (100 x ManhattanDistance)
求最高分！
For this question, you may assume the following:
You can assume that the input arguments are syntactically correct given the definitions, and will always be non-empty.
current_pos and goal_pos will always both exist within the matrix, and will never be on the same coordinate.
You can assume the grid passed through as matrix will always have dimensions or greater.
Refer to the previous slide for the heuristic definition.
对于本题，你可以假设以下几点。
你可以假设输入参数在语法上是正确的给定的定义，并将始终是非空的。
current_pos 和goal_pos 始终存在于矩阵中，并且永远不会在同一个坐标上。
你可以假设作为矩阵传递的网格总是有以下尺寸 或更大。
启发式定义请参考上一张幻灯片。
Here are example calls to your function:
>>> road_to_freedom((0,0),(2,2), [[0,1000,-500],[1500,1000,1000],[-500,0,1000]])
(0, 1)
>>> road_to_freedom((0,1),(2,0), [[1000,0,1500],[1000,1000,0],[-500,0,0]])
(0, 0)
>>> road_to_freedom((1,1),(1,2), [[1000,1000,1500],[1000,0,0],[1500,1000,1000]])
(0, 2)
Q2
Queues
A queue is a data structure that is heavily used within the field of computing. You can think of it as a list where we add elements to the back and remove elements from the front. Much the same as we join a queue to board a bus at the back of the queue, and board the bus once we reach the front of the queue. We call this concept FIFO (First In, First Out).
Priority Queues (PQ)
A priority queue is an extension of a queue and is used to keep track of things (such as coordinates) in some order based on some pre-defined priority. You can think of it as boarding a flight at an airport.
You may notice that priority is given to First Class, followed by Business Class, then Premium Economy, etc. This is an example of a PQ, where depending on your class of travel (priority), you are bumped further up into the queue so you can board earlier.
In the field of computing and mathematics, this concept is useful for graph search (such as Q3 and Q4 of Project 1) as it helps prioritize the coordinates you want to visit, by assigning a priority value to the coordinates and visiting higher priority coordinates first.
You are to write a function build_pq(current_pos, goal_pos,matrix), where:
- current_pos is Eve's current coordinate in form (x, y);
- goal_pos is the goal coordinate in form (x, y);
- and matrix is the nested list representation you should be familiar with from Project 1.
The function should use the heuristic function defined from Question 1 to score all possible coordinates the turtle can visit from current_pos. Your function should then return:
- a list of tuples;
- where each tuple includes the coordinate to visit and the heuristic score for that coordinate.
The returned list should be sorted in reverse score order(descending order). That is, the tuple with the highest scoring coordinate should be the first element in the list. If a tie occurs, then precedence is given to the larger coordinate (x and then y). For example:
- If (0,0) and (0,1) were tied for scores, then (0,1) should precede (0,0).
- If (1,0) and (0,1) were tied for scores, then (1,0) should precede (0,1) as the x value is larger.
This tie breaking system is only for this question.
A correct implementation of heuristic_score has been provided for you to use. The heuristic_score function takes in next_pos(next coordinate), goal_pos (goal coordinate), and a score (matrix score for the next_pos). If you wish to use your own, you may remove the import.
For this question, you may assume the following:
- You can assume that the input arguments are syntactically correct given the definitions, and will always be non-empty.
- current_pos and goal_pos will always both exist within the matrix, and will never be on the same coordinate.
- You can assume the grid passed through as matrix will always have dimensions 2×2 or greater.
- Remember, Eve can move in all 8 directions now!
Remember that this is an assessment task, and the work must be your own. It is illegal for others to do this work on your behalf.
>>> build_pq((0,0),(2,2), [[0,150,-10],[100,0,20],[1,1000,-10]])
[((1, 0), -150), ((1, 1), -200), ((0, 1), -200)]
>>> build_pq((1,1),(2,2), [[0,1000,-10],[100,0,1000],[1,1000,-10]])
[((2, 1), 900), ((1, 2), 900), ((1, 0), 700), ((2, 2), -10), ((0, 2), -199), ((0, 1), -200), ((2, 0), -210), ((0, 0), -400)]
>>> build_pq((2,2),(0,0), [[1000,1000,-10],[100,0,1001],[1,1000,0]])
[((2, 1), 701), ((1, 2), 700), ((1, 1), -200)]
from hidden import heuristic_score
def build_pq(current_pos, goal_pos, matrix):
# TODO: Implement this function (delete this comment when you begin)
