Design and Analysis of Algorithms
Problem Statement
We are provided with a group of Satellites each covering a set of locations on the Globe. But to cover the globe even when satellite fails, each data point or location is to be covered with more than one satellite, there may be some common locations covered in between Satellites. From this setup, we need to find the minimum number of satellites needed to cover all the locations on the Globe at least twice. This at least twice constraint is added because if at any time a satellite failure occur then the remaining satellites should be able to cover all the locations .So we need to find the minimum number of satellites covering entire Globe such that each and every location is covered at least twice.
Algorithm
The approach used in solving the problem is the Greedy Method. Select the satellite which cover maximum points first then the next maximum and then continue this process and find the minimum number of satellites needed to cover the Globe once.
Now to find the second cover, We first find the points that are covered at least twice in the first cover then from that we get the uncommon points of the satellites covered in first round and now try to find the satellite among the remaining satellites which will cover the maximum points of the remaining set. Algorithm is iteratively processed until we are left with a Null set to give the final result.
Pseudo code
- Let D be the list of data points , S be satellite array
- while(dataset D != NULL)
{
- Now choose the satellite covering the maximum points in the dataset and add to the result.
- Find the remaining set as difference (dataset, locations covered by chosen satellite) and
- Add it to form a new dataset
- Remove the chosen satellite from the satellite list
}
Now we have result set of satellites covering the entire dataset once.
To cover the dataset at-least twice, we use following logic
- Find the set S= all the common locations covered by satellites chosen in above algorithm .
- Now do difference (dataset,S) and store the result in fresh_dataset.
- while (fresh_dataset ! = NULL)
{
- For all the remaining satellites find the satellites which has the most common locations with that of the fresh_dataset and select the maximum among them as the next satellite.
- Add this to the result.
- Update fresh_dataset = difference (fresh_dataset, locations covered by chosen satellite)
- Remove the chosen satellite from satellite list.
}
- Algorithmends giving by adding minimum satellites covering entire locations at least twice.
Source Code :
For single Cover :
[java]
while(remainingset.isEmpty()==false)
{
count++;
Set<Integer>tempset = newHashSet<Integer>();
for(i=0;i<as.size();i++)
{
if(as.get(i).getValue()!=0)
{
tempset=obj[as.get(i).getKey()].cover;
tempset=<em>difference</em>(remainingset,tempset);
if(tempset.isEmpty()==true)
setdiff.put(as.get(i).getKey(), 0);
else
setdiff.put(as.get(i).getKeytempset.size());
}
}
[/java]
Continuing in Other function recursively for Second Cover of the Globe.
[java]
if(duplicate_dataset.isEmpty())
{
System.out.println(resultant);return;
}
resultant.add(as.get(0).getKey());
for(int count1=1;count1<as.size();count1++)
{
if((difference(duplicate_dataset,obj[as.get(count1).getKey()].cover )).isEmpty())
{
resultant.add(as.get(count1).getKey());
duplicate_dataset=difference(duplicate_dataset, obj[as.get(count1).getKey()].cover);
System.out.println(resultant);return;
}
}
System.out.println("New Resultant is:"+resultant);
sc_length.put(as.get(0).getKey(), 0);
System.out.println(sc_length);
satlltFailureManagement(); //Recursive Call
}
<strong>
[/java]
Sample Input and Output
Input Contain Two Files
- Datapoints.txt: This file will contain the location points of globe indicated by numbers separated by space.
1 2 4 5 6 3 7 8 9 10 {All space separated}
- Satellite_Info.txt : This file contain the Satellite name and locations covered by each satellite
1 2 3 5 8 9:S0
10 4 6 5 1 9 2 7:S1
7 2 6 8 4 3:S2
1 2 4 5 6 7 9 8 10 3:S3
In above input the Satellite name is the part that is present after: and all the numbers indicate the locations covered by the satellite
Output:
Shows the Minimum Number of Satellites needed to cover the Globe twice , along with the name of the Satellites.
Minimum Number of the Satellites needed for covering twice is: 3
S3 S1 S0
Algorithm also finds optimal solution in the Counter Example given by TA.
Proof of Correctness
We can view the Satellite Covering problem as set covering problem, where all the locations of the globe are considered as the elements in the Set S . And the satellite covering points as the subsets of the Set S.If we can prove that Greedy algorithm finds optimal fro set cover then it implies that Greedy Algorithm can find optimal in Satellite Covering as well.
Set Covering is an NP Complete Problem.We this algorithm tries finding the optimal solution using Greedy approach in 2 ways.
- Use the Satellite which covers maximum points. (Used to cover at least one time)
- Use the Satellite which cover the maximum points which are not repeated by the satellites selected in the step 1. (Used to cover at least two times)
Thus using above proof, covering the globe (all points once) using greedy approach solves the problem. But to cover the globe even when satellite fails, each datapoint or location is to be covered with more than one satellite. To do that , we find the less common elements that are present in the remaining Fresh_Set and the satellite is accordingly added making globe covered at-least twice.
Thus using the statements above, the proof for correctness is established.
Time Complexity Analysis
- For covering globe entirely at-least one time , we tried to find the MAXIMUM locations covered by each satellite and added that to Result until the globe is covered. So finding MAX n times is done with a time Complexity of O(nlogn)
- For covering globe locations second time , we tried to find the satellite covering MAXIMUM locations uncovered by previous satellites. This also needed sorting of satellites remaining based on the number of differences between the dataset and satellite cover, which needed Complexity of O (nlogn)
- Thus the total Complexity for Covering the Globe atleast twice with minimum satellites need O(nlogn).
Download the attached project code.