基于深度优先的分步分治算法研究

Top-k服务组合问题对于学术界和工业界来讲,都有实际的研究意义和应用场景。文中分析了理解top-k问题的关键所在解图,提出了基于深度优先的分步分治算法进行服务组合。该算法对用户请求的输出参数分别进行求解,该过程可并行处理,在求解结束后再进行合并。该方法可以支持分布式、并行处理框架,从而在应对大规模的服务集合时,能快速、高效地提供满足用户需求的组合服务;提出了通过构造解图的方法进行搜索求解,通过求解＂关键路径＂和＂非关键路径＂与合并＂关键路径＂和＂非关键路径＂得到解图。

Research on Algorithm Based on Depth First Search and Task Partition

Top-k service composition problem has the actual research significance and application scenarios for academia and industry.Analyze the key solution graphs of top-k problems in this paper,propose an algorithm based on depth first search and task partition.This algorithm first solves the user request separately which can be parallel processing,and then merge this solutions to provide a complete solution for the user request.This algorithm can support distribute and parallel framework,quickly and efficiently provide the service composition satisfies the user need when facing large scale service sets.Propose the method to construct solution graphs to search solutions,through solving critical path and no-critical path and merge critical and no-critical paths to gain solution graph.