I've been thinking about the following problem for quite a while and tried multiple solutions, but I'm having difficulty telling the difference between a greedy algorithm and an inefficient naive algorithm, as well as how to go about the problem in general. Any guidance on how I should approach this would be much appreciated!
In ancient times, messages were sometimes transmitted using smoke or fire signals. A fire was lit on a tower and the smoke was seen up to 10 miles away. To communicate over longer distances,a relay station would pick up the signal and then light another fire.
Assume you want to build a communication network of this type on a group of islands. Your goal is to reach all islands with a minimum number of towers. The right graph contains an edge between each pair of islands whose distance is less than 10 miles.
–Describe a greedy algorithm (in your own words or in pseudocode) that finds a solution to this problem, taking a graph (such as the one in the right figure) as an input. What is the running time of your algorithm? Which solution does your algorithm find?
–Show an example map and graph on which the greedy algorithm will not find an optimal solution.
–Describe a naive but inefficient algorithm that finds an optimal solution.
Best Answer
Greedy means that you look only locally and make what looks like the best choice at the moment. "Symptoms" of a greedy algorithm are things like: pick the vertex with highest/lowest degree and then... pick an edge/vertex of minimum/maximum weight and then...
The idea for greedy is that you have some "heuristic" in mind that says: vertices of large (or small) degree are good (for whatever reason) so pick all the good vertices first. The thing to remember about greedy algorithms is that sometimes they may give you an optimal answer (depending on the algorithm and input) and sometimes they only give approximations to the answer.
Naive/Brute Force A naive/brute force algorithm will give you the "right" answer. But, requires a lot of work. For example, you might say: Inspect every subset of the vertices and pick the set which accomplishes the goal (the best). For example, if you're trying to find a minimum weight spanning tree of a graph on $n$ vertices with $e$ (weighted) edges, you might say: pick every set of $n-1$ edges (from $e$), $\binom{e}{n-1}$ ways to do this, then for each set, decide if it is a tree and compute the weight. Of all the sets chosen, keep the one with smallest weight that is a tree. This algorithm clearly works, but is far more difficult to implement (in terms of runtime). Incidentally, Prim and Kruskal's algorithm for finding a minimum spanning tree are greedy (but guaranteed to give optimal solutions).