基于深度优先的分步分治算法研究-论文.pdf

《基于深度优先的分步分治算法研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第24卷第6期计算机技术与发展Vo1．24No．62014年6月C0MPUTERTECHNOI0GYANDDEVELOPMENTJune2014基于深度优先的分步分治算法研究郭双宙，徐济惠(宁波城市学院，浙江宁波315100)摘要：Top—k服务组合问题对于学术界和工业界来讲，都有实际的研究意义和应用场景。文中分析了理解top-k问题的关键所在解图，提出了基于深度优先的分步分治算法进行服务组合。该算法对用户请求的输出参数分别进行求解，该过程可并行处理，在求解结束后再进行合并。该方法可以支持分布式、并行处理框架，从而在应对大规模的服务集合时，能快速、高效地提供满足用户需求的

2、组合服务；提出了通过构造解图的方法进行搜索求解，通过求解“关键路径”和“非关键路径”与合并“关键路径”和“非关键路径”得到解图。关键词：服务组合；关键路径；服务筛选；top—k中图分类号：TP31l文献标识码：A文章编号：1673-629X(2014)06-0131-05doi：10．3969／j．issn．1673—629X．2014．06．033ResearchonAlgorithmBasedonDepthFirstSearchandTaskPartitionGUOShuang-zhou，XUJi—hui(NingboCityCollege，Ningbo315100，

3、China)Abstract：Top—kservicecompositionproblemhastheactualresearchsignificanceandapplicationscenariosforacademiaandindustry．Analy~thekeysolutiongraphsoftop-kproblemsinthispaper，proposeanalgorithmbasedondepthfirstsearchandtaskpartition．Thisalgorithmfirstsolvestheuserrequestseparatelywhichca

4、nbeparallelprocessing，andthenmergethissolutionstoprovideacompleteso-lutionfortheuserrequest．Thisalgorithmcansupportdistributeandparallelframework，quicklyandeficientlyprovidetheservicecom。positionsatisfiestheuserneedwhenfacinglargescaleservicesets．Proposethemethodtoconstructsolutiongraphst

5、osearchsolutions，throughsolvingcriticalpathandno-criticalpathandmergecriticalandno—criticalpathstogainsolutiongraph．Keywords：servicecomposition；criticalpath；servicefilter；top—kIJ引昌国外文献中，有论述服务本体关系图的基于接口近年来，web服务因其良好的跨平台性、可重用匹配的Web服务自动组合方法，该方法要解决图的规性得到了越来越广泛的应用。而通过组合一系列的模过大所造成的搜索空间膨胀问题。使用UM

6、L图Web服务来完成单个Web服务所不能完成的任务，也来表述以流程为中心的服务组合问题。文献[3—4]对得到了学术界和工业界的广泛关注。文中算法关注于图方法做了细致的论述，有很大的理论参考价值。将大规模Web服务情景下找出响应时间最优top—k解。服务组合问题建模为Petri网络模型为服务组合提供了新的思路。将服务组合问题转化为图搜索问题，再使用类似A搜索算法查找组合方案，也很值得1现有算法的分析与启示借鉴。在服务组合框架方面，文献[7—8]也做了论述。1．1基于图的服务组合算法该方法在搜索的某一层次，启发式地选取最有可用图来做服务组合的方法中，国内文献的论述中能的服务进

7、行搜索。所以该方法的效率与服务的启发有基于二分图、基于与或图、基于规约图，还有基于参选取有关。已知的该方法进行实验的服务集合比较数推导图，以及ASC图的，这些方法都用了特定的图小，所以难以推断在大规模服务集合下的性能表现。模型去求解服务组合问题，特别是ASC图的方法对加但是，因为该方法对组件服务有多次转换过程，所以．快搜索效率有很好的效果⋯。面对大规模的服务集合，转换过程的花费将是很大的。收稿日期：2013—09—02修回日期：2013—12—08网络出版时间：2014—02—24基金项目：宁波市自然科学基金资助项目(2010