Greedy algorithm

From Computer Science Wiki
Jump to: navigation, search

Exclamation.png This is student work which has not yet been approved as correct by the instructor

Case studyDevote time and attention to gaining knowledge of (an academic subject), especially by means of books notes[1]

Introduction

The solving of complex multi-step problems by finding smaller individual solutions and hoping it will overall be a good solution. This involves breaking it down into smaller components and finding the best solution there locally for each one.

The main idea with the algorithm is that by breaking the problem into smaller parts, it is easier and more straight-forward to get a solution for each part. However once each small solution is reached, it is never reconsidered.

Advantage: Easier to find solutions to small problems, so more straight-forward to process rather than doing it as the whole complex problem. Disadvantage: All the small solutions might not mean the best solution overall.

Example of disadvantage: https://upload.wikimedia.org/wikipedia/commons/8/8c/Greedy-search-path-example.gif

Designed to find highest sum, it will do this at each level of the tree. Therefore the algorithm will not know about the coming step which has a 99, and will instead pick the 12 branch.

A real life usage of greedy algorithm is in interval scheduling, where certain tasks take a certain amount of time, and you want to fit the most tasks into a given amount of time. A greedy algorithm finding the earliest finishing time, ignoring all tasks overlapping with that and then repeating will find both locally and globally the best solution.

 <ref> http://whatis.techtarget.com/definition/greedy-algorithm </ref>
 

How does it work or a deeper look

  • If you are discussing a THING YOU CAN TOUCH, you must explainGive a detailed account including reasons or causes. how it works, and the parts it is made of. Google around for an "exploded technical diagram" of your thing, maybe like this example of an MRI It is likely you will reference outside links. Please attribute your work.
  • If you are discussing a PROCESS OR ABSTRACT CONCEPT (like fuzzy logic) you must deeply explainGive a detailed account including reasons or causes. how it works.

Examples

Please include some example of how your concept is actually used. Your example must include WHERE it is used, and WHAT IS BENEFIT of it being used.

Pictures, diagrams

Pictures and diagrams go a LONG way to helping someone understand a topic. Especially if your topic is a little abstract or complex. Using a picture or diagram is a two part process:

  1. upload a file
  2. use the file on a wiki page

External links

  • It would be helpful
  • to include many links
  • to other internet resources
  • to help fellow students
  • Please make sure the content is good
  • and don't link to a google search results, please

References