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

動態規劃是一種常用的尋找問題最優解的算法設計方案。當將動態規劃中的各個子問題考慮成有向圖上的節點時,我們可以將動態規劃看作是一個有向無圈圖。一些問題的動態規劃的有向無圈圖有著特殊的結構,我們可以利用這些結構加速動態規劃。本文考慮了一種從基站將能源"轉移"到移動通信宿主的二進制編碼方案構造時采用的動態規劃。移動通信中,常常需要考慮優化通信編碼方案來降低移動通信宿主的能耗。本文研究的編碼方案通過以下方式降低能耗:基站猜測移動通信宿主所要發出的信息并詢問宿主,而宿主則在一定的情況下才做出回應,以此來降低宿主發送信息的能耗。對于有n個單詞的編碼,我們的算法比之前提出的算法降低了O(n2)的時間復雜度。 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.