硬币问题的一种新的通用算法的研究
A new universal algorithm for coins problem
摘要
在图像压缩、模式识别、筛选等工业应用中提出了搜索坏硬币的最优化问题,即用尽可能少的测试次数检测出坏硬币并确定轻重。对这一问题,可采用AO*算法、遗传算法等国际通用算法求解,但这些算法的时间复杂度和空间复杂度过大。因此提出了一种新的解决此类问题的通用算法,并用C++将其实现和测试。测试结果表明:算法的时间、空间和成功率均达到了理论极限。
出处
《制造业自动化》
北大核心
2012年第13期28-31,共4页
Manufacturing Automation
基金
国家自然基金(41161065)
参考文献10
-
1朱福喜,卓识.十二硬币问题的进一步求解[J].计算机工程与应用,2001,37(21):132-135. 被引量:1
-
2阎庆旭,姚立,刘喜波.一类非标准球选取的最优过程[J].数学的实践与认识,2001,31(2):185-189. 被引量:4
-
3RichardJohnsonbaugh,DiscreteMathematics[M].电子工业出版社.2006:243-245.
-
4Nils J Nilsaon.Artificial lntdligenee: A New Syntheis[M]. Morgan Ka --ufann, 1998.
-
5L Wes, L theoremproving 1965--1970 in The Autemation of Reasoning: Collected papers from 1957--1970[M]. Jorg Siekmann, Grabsl Wrightsoned. Springer--Verlag, NewYork 1983.
-
6Hwang F K., A tale of two coins[J]. Amer. MathMonthly, 1987,94:121 - 129.
-
7Chang XM., Hwang F K., Weng J. F., Group testingwith two and three defectives[A]. First-China-U.S.A. International conference in graph theory and its applications[C]. 1990.
-
8Aiger, M.. Combinatorial Search [M]. New York-Stuttgrat: Wiley-Teubner, 1988.
-
9Hwang F K., Updating a tale of two coins. Graph theory and its applications[J]. Annals of the New York Academy of Science, 1989, 76: 259-265.
-
10Chang X M, Huang F K, Weng J F. Optimal detection of two defectives with a parity check device[J]. SIAM J Discr Math, 1998(1): 38-49.
二级参考文献5
-
1[1]Hwang F K. A tale of coins. Amer Math Monthly,1987,94(2):121~129.
-
2[2]Bellman R. Dynamic programming. Princeton Univ Press, Princeton, 1957.
-
3[3]Bellman R, Gluss B. On various versions of the defective coin problem. Information and Control,1961,4:118~131.
-
4周祥和(译),自动推理引论及其应用,1987年
-
5朱福喜,余亮,黄干平.用AO*算法求解一个智力难题[J].计算机工程与应用,2001,37(3):69-70. 被引量:1
共引文献3
-
1阎庆旭,邓燕,何勇强.论数学教学的两个环节——课堂习题处理与课后思考题的设置[J].中国地质教育,2004,13(3):46-48. 被引量:1
-
2高晶,闫笑梦.八硬币集中四坏硬币的最优测试方法[J].数学的实践与认识,2008,38(8):192-195. 被引量:1
-
3闫笑梦,高晶,赵芃.十硬币集中四坏硬币的最优测试方法[J].数学的实践与认识,2009,39(4):184-188.
-
1郭春,郭健.故障诊断的概率方法[J].计算机工程与科学,2001,23(4):93-95. 被引量:1
-
2郭学品,钟声.基于模块关联性的测试用例维护方法[J].电脑编程技巧与维护,2011(10):37-38.
-
3闫笑梦,高晶,赵芃.十硬币集中四坏硬币的最优测试方法[J].数学的实践与认识,2009,39(4):184-188.
-
4高晶,闫笑梦.八硬币集中四坏硬币的最优测试方法[J].数学的实践与认识,2008,38(8):192-195. 被引量:1
-
5马力,邱志洋,陈彦萍,赵璟.基于QoS的语义Web服务选择[J].计算机科学,2017,44(3):226-230. 被引量:4
-
6张永宏,曹健,王丽华.基于51单片机与nRF24L01无线门禁控制系统设计[J].江苏科技大学学报(自然科学版),2013,27(1):64-69. 被引量:36
-
7郑先容,汤浪平.两类常见问题大规模求解的算法探讨[J].湖南城市学院学报(自然科学版),2005,14(3):72-74.
-
8侯俊伟,周受钦,王海林,杨小明,韩争,傅涛.食品冷链配送中温度采集系统的设计与试验[J].物联网技术,2013,3(12):9-12.
-
9郭明威,倪世宏,朱家海.基于相关性模型的BIT诊断策略技术研究[J].计算机应用研究,2011,28(10):3753-3755. 被引量:3
-
10常红.生物计算机[J].百科知识,2008(20):28-29.