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

被引：2

作者：

商文喜 ^{[1
]}

蔚承建 ^{[1
]}

王开 ^{[2
]}

刘凯 ^{[3
]}

机构：

[1] 南京工业大学电子与信息工程学院

[2] 东南大学信息科学与工程学院

[3] 解放军理工大学国防工程学院

来源：

计算机应用与软件 | 2014年 / 31卷 / 12期

关键词：

数独问题; 势博弈; 效用函数; 学习动力; 物理博弈;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

数独问题已被证明是一个NP完全问题。采用分布式势博弈方法求解该问题。首先建立其效用函数并证明数独问题可以转化为势博弈模型,然后使用学习动力逐步优化参与者的状态以达到势博弈的最优状态—纳什均衡点。同时势博弈现有大部分研究结果限于计算机仿真,为此给出数独问题一个物理的博弈实现,物理博弈过程参与者通过三个手机体现。实验结果表明新的解决方式能够快速收敛。

引用

页码：113 / 115

页数：3

共 11 条

[1] Distributed Welfare Games [J].

Marden, Jason R. ;

Wierman, Adam .

OPERATIONS RESEARCH, 2013, 61 (01) :155-168

[2]

An architectural view of game theoretic control[J] . Ragavendran Gopalakrishnan,Jason R. Marden,Adam Wierman. &nbspACM SIGMETRICS Performance Evaluation Review . 2011 (3)

[3] Metaheuristics can solve sudoku puzzles [J].

Lewis, Rhyd .

JOURNAL OF HEURISTICS, 2007, 13 (04) :387-401

[4] Potential games [J].

Monderer, D ;

Shapley, LS .

GAMES AND ECONOMIC BEHAVIOR, 1996, 14 (01) :124-143

[5]

Geometric particle swarm optimization for the Sudoku puzzle. Alberto Moraglio,Julian Togelius. Proceedings of the 9th annual conference on genetic and evolutionary computation . 2007

[6]

Knowledge-Based Intelligent Information and Engineering Systems. Zong Woo Geem. . 2007

[7]

A SAT-based Sudoku solver. Tjark Weber. The 12th International Conference on Logic for Programming,Artificial Intelligence,and Reasoning . 2005

[8]

Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. H.Peyton Young. Journal of Women s Health . 1998

[9]

Equilibrium, evolutionary stability and gradient dynamics. Sjur Didrik Fl?m. Int. Game Theory Rev . 2002

[10]

Complexity and Completeness of Finding Another Solution and Its Application to Puzzles. Yato, Takayuki,Seta, Takahiro. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences . 2003

← 1 2 →