讲解 program、辅导 Python设计程序
Now, Lee comprehends the seriousness of the task he has assigned to you. Consequently,
he has provided you with several alternative maps that can be utilized for the development of
the software. These maps are available in the check.py file, which also contains tests for
evaluating your software. Lee will only approve your work if your code successfully passes
all the tests. Additionally, to assess the robustness of your software, Lee may incorporate
additional tests that he is currently unwilling to disclose. These undisclosed tests will differ
from the ones he initially provided but are similar enough that your implementation, if correct,
should pass them as long as you avoid taking shortcuts (e.g., hardcoding, writing code
specifically tailored to pass the tests without implementing the desired algorithm, etc.).
Lee has equipped you with two types of maps. One type delineates the distance between
two user nodes in terms of hops (akin to degrees of separation), referred to as the distance
map. The other is derived from user activity data in FaceByte archives, encompassing
common friends, groups, liked posts, message activity to common friends, similar life events,
etc., between two user nodes. This map specifies similarity points, and we will term it the
time map. Admittedly, the naming is a bit unconventional. Some time maps, however, only
employ similarity points of 1, signifying a mere connection between two users without
measuring similarity.
Let's delve into how these maps will be employed for the app features. The "find friends"
feature enables a user to locate a friend by tracing a path between the user and a target
friend to reveal intermediate connections. This is expected to be accomplished by utilizing
BFS and DFS on the time maps, which solely indicate connections and not similarity.
Therefore, the desired outcome is the shortest path between two users. The "suggested
friends" feature is intriguing. FaceByte aims to experiment with the feature by tracing
connections between two users in a way that the intermediate users are as dissimilar as
possible. This diversifies one's connections by suggesting friends from those intermediate
users. Once again, the shortest path between two users is sought, as it minimizes the total
similarity points between them, an outcome expected from the A* algorithm.
For all three implementations (BFS, DFS, and A*), the main metric will be the similarity
points between user nodes, not hops. Therefore, the time maps are the ones to be used.
However, your A* function will also be provided with a distance map, as the A* algorithm
utilizes hops between user nodes as the heuristic. In other words, for A*, the distance from
the starting user node to the current user node will be "time-based," while the distance from
the current user node to the target user node will be "distance-based."
Other important considerations regarding the maps:
Certain tests use specific maps, so please be mindful of that when reviewing test
functions.
With DFS, once a node is searched and expanded, it should not be searched and
expanded again to avoid redundant work and cycles in the map. DFS maps don't
have loops, but BFS maps may contain loops.
The order in which children nodes are added to the fringe when a node is expanded
determines the traversal direction of the search tree. Either direction is acceptable.
While Lee would prefer each algorithm to find the shortest path, he understands it
may not always be possible. BFS and A* are likely to succeed, but DFS is not
guaranteed to find the shortest path.
In A*, if two or more nodes have the same f(n), use h(n) to break the tie. If h(n) is
also the same, pick the node that entered the open list first. If using a priority queue,
a separate variable may be needed to track the order due to sorting.