数独问题的一个分布式物理博弈求解  

A DISTRIBUTED SOLUTION OF PHYSICAL GAME TO SUDOKU PROBLEM

作　　者：商文喜 蔚承建[1] 王开[2] 刘凯[3] 

机构地区：[1]南京工业大学电子与信息工程学院,江苏南京210009 [2]东南大学信息科学与工程学院,江苏南京210018 [3]解放军理工大学国防工程学院,江苏南京210007

出　　处：《计算机应用与软件》2014年第12期113-115,共3页Computer Applications and Software

基　　金：江苏省自然科学基金项目(BK2011060;BK2010240);教育部博士点基金项目(20100092120012)

摘　　要：数独问题已被证明是一个NP完全问题。采用分布式势博弈方法求解该问题。首先建立其效用函数并证明数独问题可以转化为势博弈模型,然后使用学习动力逐步优化参与者的状态以达到势博弈的最优状态—纳什均衡点。同时势博弈现有大部分研究结果限于计算机仿真,为此给出数独问题一个物理的博弈实现,物理博弈过程参与者通过三个手机体现。实验结果表明新的解决方式能够快速收敛。Sudoku problem has been proved to be an NP complete problem.We use a distributed potential game method to solve the problem.Firstly, the utility function of the problem is established and the Sudoku problem is proved to be able to convert to a potential game model, and then the learning rule is used to gradually optimise the status of the players in order to achieve the optimal state of potential game which is Nash equilibrium point.Meanwhile, most of the existing research results of potential game are limited to computer simulation.We present a game implementation of Sudoku problem in physical form.Participants in the process of physical game are embodied by three mobile phones.Experimental results show that the new solution can converge quickly.

关 键 词：数独问题 势博弈 效用函数 学习动力 物理博弈 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]