greedy propertyとは 意味・読み方・使い方

名詞

greedy property

1. (computer science) The property of being globally solvable optimally by making optimal decisions locally.
   • 2013, Steven Halim; Felix Halim, Competitive Programming 3: The New Lower Bound of Programming Contests., page 89:

     It has the greedy property (difficult to prove in time-critical contest environment!). If we make a choice that seems like the best at the moment and proceed to solve the remaining subproblem, we reach the optimal solution. We will never have to reconsider our previous choices.

   • 2012, Betsy George; Sangho Kim, Spatio-temporal Networks: Modeling and Algorithms (SpringerBriefs in Computer Science), Springer Science & Business Media, →ISBN, page 25:

     Developing efficient algorithms for computing shortest paths in a time varying spatial network is challenging because these journeys do not always display greedy property or optimal substructure, making techniques like dynamic programming inapplicable.