构造移动通信中降低能耗的前缀码的动态规划加速

动态规划是一种常用的寻找问题最优解的算法设计方案。当将动态规划中的各个子问题考虑成有向图上的节点时,我们可以将动态规划看作是一个有向无圈图。一些问题的动态规划的有向无圈图有着特殊的结构,我们可以利用这些结构加速动态规划。本文考虑了一种从基站将能源"转移"到移动通信宿主的二进制编码方案构造时采用的动态规划。移动通信中,常常需要考虑优化通信编码方案来降低移动通信宿主的能耗。本文研究的编码方案通过以下方式降低能耗:基站猜测移动通信宿主所要发出的信息并询问宿主,而宿主则在一定的情况下才做出回应,以此来降低宿主发送信息的能耗。对于有n个单词的编码,我们的算法比之前提出的算法降低了O(n2)的时间复杂度。