Greedy Algorithm

Overview

Our Greedy algorithm works on the same basis as DFS ie. traversing through the state space tree, choosing only the locally best solution at the time, until a complete schedule has been found, but rather than traversing back up the tree and slowly building a better more optimal schedule, greedy finishes.

At each iteration, greedy chooses to add one task out of all the different possible tasks it could add at that point, that will give it the smallest schedule size. The final schedule will not be optimal, but it will also not be the worst possible schedule that can be made.

Usage

Greedy algorithm runs on a graph object and produces a schedule which can be retrieved via the method

public Schedule getCurrentBest() {...}

from the schedule object returned, the total time of the schedule can be found using

int scheduleTime = schedule.getEndTime();

which can be used as a first-estimate upper bound.

This comes especially useful in A* as a first estimate upper bound is needed.