中文摘要：

Web服务的自包含、自描述和模块化的特性使之迅速受到工业界和学术界的极大关注，其中，服务组合是研究的热点和难点．然而Web服务的海量性、服务描述的异构性以及服务的动态变化性等因素决定了web服务组合的困难性．本文提出了一种能够求出满足用户请求的所有组合方案的Web服务组合算法．双向算法，且算法的时间复杂度控制在多项式级别．通过预处理，该算法首先建立了输入参数与Web服务之间的关联关系，然后根据用户输入通过前向搜索，找出所有可能参与组合的服务，并建立了他们之间的可达关系，最后根据用户期望的输出，结合前向搜索得到的服务及可达关系，通过后向搜索得到所有的组合方案．

英文摘要：

Due to their characteristics as self-containment, self-description, and modularization, Web services have received much in- terest in both industry and academia, and service composition is the hotspot and difficulty of study, and also is the true potential of Web service. However, the mass of Web services, the heterogeneity of service description, the dynamic changes of Web service and other factors determine the difficulty of Web service composition. In this paper, we present a polynomial-level Web service composi- tion algorithm - Bidirectional algorithm which can find all compositions that meet user＇s request. Through the pretreatment, the algo- rithm firstly establishes the relationship between the input parameters and Web services. Forward algorithm secondly finds out all the Web services that might be involved in the composition and establishes the reachability relationship between Web services starting from user＇s input. Finally, according to user＇s output, backward algorithm finds out all the compositions combining to the Web serv-ices and reachability relationship that are got in forward algorithm.