有向图的特定模式搜索和优化
本文对有向图的特定模式搜索和优化进行了，背景知识，运用前景，开发思想，开发方案以及成果展示等进行了较为全面的介绍和论述。本次开发主要运用了java进行编写，设计了数据结构，算法设计与分析，离散数学，有向图，图的遍历等方面的知识，具有一定的学术性和应用性。18802
毕业论文关键词： 有向图 特定模式 搜索 优化 前驱和后继
Title Particular Pattern search and Optimization of Digraphs
Abstract
Particular Pattern search and Optimization of Digraphs is a directed graph according to specific patterns (Flow Pattern and Sequence Pattern) to search, the results will search out after optimization, re export into a not only retains the original relationship to logic, and more intuitive clearly, the digraph. This paper focuses on the search strategy, the precursor of subsequent node searching the same attribute to search optimization, proposed a new idea. Based on the graph model of specific search and optimization, background knowledge, application, development idea, development scheme and the results were comprehensively introduced and discussed in this paper. The development of the main java to program, design data structure, algorithm design and analysis, discrete mathematics, graph, graph traversal and other aspects of knowledge, have certain academic and application.
Keywords: digraphs particular patter search optimization OAL IAL
摘要: 3
1 引言 5
1．1 课题的目的及其意义 5
1．2 国内外研究现状 5
2 背景知识的补充及应用 6
2.1 SOA服务组合的应用以及市场需求 6
2.2基于有向图的服务组合及图论 8
2.3 本课题的切入点 10
3 有向图的特定模式搜索和优化 11
3．1 居于有向图的特定模式识别理论 11
3．1．1 FlowPattern的搜索和优化理论 11
3．1．2 SequencePattern的搜索和优化理论 12
3．2 删边优化理论 13
3．3 贪心理论的删边选择和NP难问题 15
3．4 最终的优化结果 19
4 设计与实现 20
4.1设计及功能介绍 20
4.1.1 被优化有向图的输入 20
4.1.2 优化后有向图的输出 22
4.2 程序整体框架图及组成部分 23
4.2.1 框架图及组成部分 23
4.2.2 程序中所有的活动类以及组成部分 26
4.3 程序的重要组件 27
4.3.1 搜索算法和优化组件 27
4.3.2 删边组件 30
4.4 应用分析 33
5总结与展望 37
6 致谢 38
参考文献39
毕业设计说明书（论文）中文摘要 1 引言
有向图是是一个二元组<V,E>，其中1.V是非空集合，称为顶点集。2.E是V×V的子集，称为弧集。有向图可以清晰的表示出每个顶点和对应子集直接的逻辑关系和继承关系，所以我们可以将很多的流程图都用有向图的形式表达出来。但是其中很大一部分流程图非常庞大，那么单纯的转换成有向图后，不仅占据很大的空间，并且我们分析起来也非常的困难，所以我的导师宋巍先生和我提出了一个新的思路，那就是——有向图的特定模式搜索和优化。