资源均匀占有的算法设计

Algorithm Design of Resource Uniform Possession

提出了一种资源均匀占有问题,结合归约和递归理论将占有问题转化为受限的资源分配问题,设计了一种用于求解此类问题的LORUP算法。算法的基本思想是参与者依次对资源进行局部最优化选择,直至最后一人选择完毕,以获得新问题的一个资源分配方案。运用数学归纳法证明了该算法所得到的分配方案是一个纳什均衡,证明了一个纳什均衡点对应由算法生成的一个分配方案。由非均衡分配可有限次优化改进为均衡分配,得到了均衡分配都是最优分配OPT。论文提出的局部最优占有算法可对资源均匀占有问题进行有效求解。

This theris proposed a resource uniform possession, combined with the reduction and recursion theory have ehenged the occupy problem into a constrained resource allocation problem, and have designed a LORUP algorithm solving this problems. The basic idea of the algorithm is participant optimizes the selection of local resources in sequence and do the selection until the last participant finished this. So, we can get a new idea of resource uniform possession. The resource dis- tribution got before is a Nash equilibrium proved by mathematical induction. Also, it is a resource distribution in which Nash equilibrium points are generated by the algorithm. Non-equilibrium distribution can be improved into equilibrium distribution limited. We obtained equilibrium distribution is optimal distribution of OPT. The local optimal possession algorithm given in this thesis can solve the uniform resource possession effectivelv.