|
||||||||||||||||
|
PhD ThesesMethods for Reformulating Dynamic Programming Algorithms as Representatively Sampled AlgorithmsBy James Kilbride
The usage of Dynamic Programming for statisical problems has brought to light a new algorithm class related to Dynamic Programming. This method, dependent on calculating a representative sample of the solution space, rather than a single, optimal, solution, needs to be distinguished from Dynamic Programming. This thesis defines this class of algorithms and describes the basic differences between this new class and Dynamic Programming algorithms. Several Representatively Sampled Algorithms (R S A) have been developed from Dynamic Programming algorithms (DPA). This thesis provides a generic framework for reformulating a DPA as a R S A. The use of this framework is demonstrated with the Traveling Salesman algorithm. This framework greatly improves the ability to use and identify problems which can benefit from the use of representative samples over a single optimal solution. These benefits include additional power and flexibility as well as the ability to look at a variety of questions from a single solution set. This process leverages existing Dynamic Programming applications which can be identified as candiddates for reformulation. It will then be possible to build upon those existing algorithms to provide a representative sample instead of an optimal solution. These samples will provide more concrete information about confidence in predictions as well as allowing various components of an answer to be evaluated independently without additional computation. This will provide a method for opening up an array of statistical optimization algorithms to generate representative solutions and to describe the distribution of the entire solution space, instead of a single, albeit optimal, solution.
|
||||||||||||||||
Research
