Dynamic programming is an important optimization technique, but designing efficient dynamic programming algorithms can be difficult even for professional programmers. Motivated by this point, we propose a synthesizer namely MetHyl, which automatically synthesizes efficient dynamic programming algorithms from a possibly inefficient program in the form of relational hylomorphism. MetHyl consists of a transformation system and efficient synthesis algorithms, where the former transforms a hylomorphism to an efficient dynamic programming algorithm via four synthesis tasks, and the latter solves these tasks efficiently. We evaluate MetHyl on 37 tasks related to 16 optimization problems collected from Introduction to Algorithm. The results show that MetHyl achieves exponential speed-ups on 97.3% tasks and the time complexity of the standard solutions on 70.3% tasks with an average time cost of less than one minute.
翻译:动态编程是一种重要的优化技术,但即使对专业程序设计员来说,设计高效动态编程算法也可能很困难。 我们为此提出一个合成器,即MetHyl(MetHyl),该合成器自动合成一个可能效率低下的程序的高效动态编程算法,其形式是关系性环形。 MetHyl(MetHyl)包含一个转换系统和高效合成算法,前者通过四个合成任务将环形转换为高效动态编程算法,而后者则有效解决了这些任务。我们评估了MetHyl(MetHyl)的37项任务,涉及从Agorithm(Agorithm)入门收集到的16个优化问题。结果显示MetHyl(MetHyl)在97.3%的任务和70.3%的标准解决方案的时间复杂性上实现了快速加速增长,平均时间成本不到一分钟。