代做program、代写Python设计程序

日期：2024-01-17 07:35

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.