摘要
数独问题已被证明是一个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.
出处
《计算机应用与软件》
CSCD
北大核心
2014年第12期113-115,共3页
Computer Applications and Software
基金
江苏省自然科学基金项目(BK2011060
BK2010240)
教育部博士点基金项目(20100092120012)
关键词
数独问题
势博弈
效用函数
学习动力
物理博弈
Sudoku problem
Potential game
Utility function
Learning rule
Physical game
