计算机理论与算法图形匹配算法在公式发现理论FDD中的应用张颖冯金花关永(首都师范大学信息丄程学院，北京，100037)摘要：传统的经验公式发现理论FDD(FormulaDiscoveryfromData)虽采用启发式搜索，但随若函数库的扩大，仍存在函数的组合爆炸现象。根据复合函数曲线仍然具有原函数图形特征的性质,本文提出了从函数曲线的图形特征入手，采用图形匹配的新方法，将各类初等两数的曲线图形作为搜索库元素，用Hausdorff距离匹配法将目标函数曲线与搜索库元素进行匹配。实验表明：该方法能够快速冇效地搜索到原型函数，提高了算法的搜索效率。关键字：经验公式发现算法启发式搜索图形匹配初等函数曲率Hausdorff距离中图法分类号：TP301.6TP391.4文献标识码：A：TheapplicationoftheGraphicsMatchingAlgorithmintheFormulaDiscoveryfromDataZhangHaoFeng激nhuaGuanYong(CollegeofInformationEngineering,CapitalNormalUniversity,Bei激ng,100037)AbstractThetraditionaltheoryoftheFormulaDiscoveryfromDatausedheuristicsearch,withthefunctionsLibraryexpanded,therewasstillacombinationoffunctionexplosionphenomena・Baseonthecompositefunctioncurvestillhasaprimaryfunctiongraphicsfeatures,thepaperstartedfromthefunctioncurve'scharacters,usedthematchingmethodofgraphics,madethevariousprimaryfunction'scurvesasanelementofthesearchlibrary.MatchingtheobjectivefunctionsandthecurvesinthelibraryusedthematchingmethodofHausdorffdistanee,Experimentsshowthatthismethodcansearchtheprototypefunctionsquicklyandefficiently,improvetheefficiencyofthewholesystemalgorithm・KeywordsFDDHeuristicSearchGraphicmatchingPrimaryfunctionCurvaturesHausdorffdistanceo引言随着现代信息技术少计算机技术的飞速发展，人工智能技术已经成为信息技术发展的重要方向Z—。机器发现技术作为人工智能的一个垂要分支，也成为近几年的研究热点。冃前,世界各国都在积极开展基于机器发现理论的智能仪器的研究工作，彳甲能型仪器的发展方向是智能化和小型化。智能化主要是指通过机器的发现学习，帮助研究人员分析实验数据、发现潜在规律、验证设计者的设想。目前，世界上只冇美国德州仪器公司成功开发了手持式的、具冇知识发现能力的智能仪器一一图形化计算仪。但是，它在公式发现上仍然采用的是传统的数据拟合技术，这种方法存在一个明显的“病态问题”，即当线性方程组系数行列式元素发牛微小变化就会引起解的显著变化。而且，这种图形化计算仪发掘出来的公式只有多项式一种类型，难以看出数据间的周期性规律及函数的变化趋势等特征，知识表示形式单一、可理解性、可用性较差。1经验公式发现理论FDD国防科技人学的陈文伟教授捉出的基于数据驱动的经验公式发现理论FDD(FormulaDiscoveryfromData),它将人工智能中的机器发现理论与数值计算中的曲线拟合技术相结---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---合，能够从大量试验数据中搜索经验公式，实现对自然规律的发现和验证⑴。经验公式发现理论町以帮助研究人员从试验数据中快速地搜索出比较直观的经验公式,例如：给出一组实验数据,其中变量x为从10到20步长为0.05的201个值,变量y满足关系式y=sin(x)o利用传统的图形化计算仪，拟合出来的公式为：y'=6.9488xl05x7-0.007667x6+0.35669x5-9.0619x4+135.7k3门、-(1)—1197.6兀$+5766%-116889形式为高次多项式形式，变量x与变量y本來是满足正弦函数规律的，且具有周期性,但从得到经验公式屮无法得到肓观表征周期性等特征的数学规律，使用者很难建立起变最之间直观的木质规律。为了解决这个问题，人们提出了基于人工智能启发式捜索的初等函数经验公式发现方法，利用这种方法可以寻找到具有最佳线性逼近关系的、由初等函数原型构成的经验公式。1.1FDD的设计思想对某一变量取初等函数和另一变量的初等函数或原始数据进行线性组合，即从原型库中选取逼近效果最好的少数几个初等函数作为基函数，并进一步形成组合函数，直至找到最后的目标函数⑵。FDD1...