“Greedy Algorithm”的概念、定义、习题解题方法及翻译-数学辞典

单词

Greedy Algorithm

释义

Greedy Algorithm

An algorithm used to recursively construct a Set of objects from the smallest possible constituent parts.

Given a Set of Integers (, , ..., ) with , a greedyalgorithm can be used to find a Vector of coefficients (, , ..., ) such that

(1)

where

is the Dot Product, for some given Integer

. This can be accomplished by letting

for

, ...,

and setting

(2)

Now define the difference between the representation and

(3)

at any step, a representation has been found. Otherwise, decrement the Nonzero

term with least

, set all

for

, and build up the remaining terms from

(4)

for

, ..., 1 until

or all possibilities have been exhausted.

For example, McNugget Numbers are numbers which are representable using only . Taking and applying the algorithm iteratively gives the sequence (0, 0, 3), (0, 2, 2), (2, 1, 2), (3,0, 2), (1, 4, 1), at which point . 62 is therefore a McNugget Number with

(5)

If any Integer can be represented with or 1 using a sequence (, , ...), then this sequenceis called a Complete Sequence.

A greedy algorithm can also be used to break down arbitrary fractions into Unit Fractions in a finite numberof steps. For a Fraction , find the least Integer such that , i.e.,

(6)

where

is the Ceiling Function. Then find the least Integer

such that

.Iterate until there is no remainder. The Algorithm gives two or fewer terms for

and

, three or fewer termsfor

, and four or fewer for

Paul Erdös and E. G. Strays have conjectured that the Diophantine Equation

(7)

always can be solved, and W. Sierpinski conjectured that

(8)

can be solved.

See also Complete Sequence, Integer Relation, Levine-O'Sullivan Greedy Algorithm, McNugget Number,Reverse Greedy Algorithm, Square Number, Sylvester's Sequence, Unit Fraction

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。