ABSTRACT
A greedy algorithm can be seen as a direct descent from the root to a leaf in the tree traversed by the “Generate and test” technique. More precisely, at each node of this tree, a greedy algorithm applies a choice rule allowing to select a value of the domain of the considered variable, before moving on to the next node, until meeting a leaf. The advantage of greedy algorithms is obviously their low temporal complexity (polynomial), since they are based on the scan of an array or a queue. Therefore, attention will be paid more to the exact or optimal character of the considered algorithms than to their complexity. The integration of the proof into the construction aims at establishing that the algorithm makes a “lead run” from start to finish in the sense of the optimality criterion. Binary coding of symbols is the subject of international standards. The codes thus defined are usually of fixed length.
