动态规划是一种常用的寻找问题最优解的算法设计方案.当将动态规划中的各个子问题考虑成有向图上的节点时,我们可以将动态规划看作是一个有向无圈图.一些问题的动态规划的有向无圈图有着特殊的结构,我们可以利用这些结构加速动态规划.本文考虑了一种从基站将能源"转移"到移动通信宿主的二进制编码方案构造时采用的动态规划.移动通信中,常常需要考虑优化通信编码方案来降低移动通信宿主的能耗.本文研究的编码方案通过以下方式降低能耗:基站猜测移动通信宿主所要发出的信息并询问宿主,而宿主则在一定的情况下才做出回应,以此来降低宿主发送信息的能耗.对于有n个单词的编码,我们的算法比之前提出的算法降低了O(n~2)的时间复杂度.%Dynamic programming is a common paradigm to design algorithms for finding optimal solutions. When we consider each subproblem in dynamic programming as the vertex in a directed graph, we can model the whole problem into a problem on a directed acyclic graph(DAG). For some problems, their corresponding DAGs have some special properties, which we can utilize to speed up the dynamic programming. In this paper, we consider a dynamic programming which is used to build a code to save energy in the mobile environment. This code saves energy by "transfer" energy from a mobile support station to the mobile host: the station guesses the message that the host wants to send and asks the host to verify. The host responds to the mobile station if only a certain condition is met. We have found some special properties of this dynamic programming and improve the old algorithm by an O(n~2) factor, given n symbols to encode.
展开▼
