You have an army of n robots at your disposal that you can program to collective

Question

You have an army of n robots at your disposal that you can program to collectively do various tasks. The robots use wireless communication to communicate with each other. Two robots are connected if they are within a distance d (range of wireless device) of each other. Thus, as the robots move around the territory, the robot network (graph) is changing. You want the robot network to stay connected while individual robots explore as much of the “territory" as possible. You have come up with the following rule: At any given time, each robot must be able to communicate with at least n/2 other robots.

Given a graph G that is comprised of a vertex set V = {V1, V2, V3, V4, …, Vm} and edge set E = {E1, E2, E3, …, En} with weights {W1, W2, W3, …, Wn}, write an algorithm that determines at any point in time whether your rule is satisfied. What is the time complexity of the algorithm?

Explanation / Answer

dict_edge_weights = {E[i]: W[i] for i in range(len(E))}

edge_weight = sorted(dict_edge_weights.items(), key=lambda x: x[1])

for vertex in V:

    ctr = 0

    for i in range len(edge_weight):

        if vertex in edge_weight[i][0].vertices:

            ctr += 1

    if ctr<=n/2:

        print "Doesn't satisfy the rule."

        break

Time complexity of the algorithm = O(nm)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.