1、.103.3The basic idea.113.4Features.113.5Steps .12Chapter 4 Practice Of Dynamic programming.134.1 Matrix chain problem .134.1.1 Question .134.1.2 The nature of the optimal solution.144.1.3 Optimal value.154.1.4 Get optimal value .154.1.5 Get optimal solution .174.2 Missile intercepting problem .174.2
2、.1 Question .174.2.2 The nature of the optimal solution.184.2.3 Optimal value.184.2.4 Get optimal value .194.2.5 Get optimal solution .20Chapter 5 Compare.215.1 Compare to search algorithm .215.2 Compare to memorandum algorithm.22Chapter 6 Optimize The Dynamic Programming.256.1 Optimize the time com
3、plexity.256.1.1Reduce the state .256.1.2 Reduce the state transition.286.1.3 Reduce the time of state transition.306.2 Optimize the space complexity.326.2.1 Example 1 .326.6.2 Example 2 .35Chapter 7 Summarize .36Acknowledgement .37References.38动态规划算法应用及其规划1第一章 问题的引入天才设题，智者解题对于绝大多数没有数据结构和算法知识的编程人员，穷举
4、搜索法经常成了克敌制胜的关键法宝，它也似乎是可以解决一切问题的万能钥匙。如今计算机的处理器不是号称一秒钟可以处理好多亿条指令，那么穷举搜索法好像是没有什么好担心的了。事实真的如此吗，先来看看下面这个例子。1.1问题描述如下所示为一个数字三角形：73 88 1 02 7 4 44 5 2 6 5请编写一个程序计算从顶至底的某一条路径，使该路径所经过的数字的总和最大，要求满足一下三个条件：每一步可沿直线向下或右斜线向下走；1 = 三角形行数 = 100；三角形中的数字为整数 0，1，99。1.2穷举搜索法解题分析上面的题目，要计算所有路径中所经过数字总和最大的路径，那么可以穷举出所有可能的路径，然
5、后从中选出总和最大的路径。要怎么实现对所有路径的穷举呢，使用深度搜索可以很好的完成任务。用搜索法写出如下的算法程序：动态本 科 毕 业 论 文分布式网络爬虫的设计与实现爬虫节点程序的设计与实现The Design and Implementation of Distributed Web Crawler The Design and Implementation of Crawler Node姓 名： 学 号：学 院：软件学院系：软件工程专 业：软件工程年 级：指导教师： 年 月摘 要搜索引擎是从互联网上快速而有效地获取信息资源的捷径。网络爬虫是搜索引擎的重要组成部分，它在搜索引擎中负责网络信
6、息采集，是搜索引擎数据库中原始信息唯一的来源。本文围绕着网络搜索这一前沿技术，深入研究了网络爬虫的工作原理和相关技术，并在这些研究工作的基础之上设计实现了一个高性能分布式网络爬虫系统。本文研究了搜索引擎的发展历程，从中了解了网络爬虫的应用意义和实际价值，而后又对网络爬虫的历史和发展现状进行了学习和研究，总结前人的经验，为自身的研究奠定好坚实的基础。在对网络爬虫研究背景有了较深的了解之后，开始着手研究和分析分布式网络爬虫节点现有的实现技术，包括爬行的策略、网页的测评算法、HTML 网页文档的分析、多线程的使用、不同网页编码转换、爬虫的优雅爬行等等。并将这些关键技术应用于分布式网络爬虫节点当中。完
7、成了对理论知识的理解和掌握，接下来就是应用到实际的工作当中。主要对分布式网络爬虫节点进行基础的逻辑分析；对爬虫节点进行了功能模块的划分，使得各个模块的功能都有了详细的分配；然后对爬虫节点的工作流程进行详尽的设计；最后综合设计思想，完成对爬虫节点具体类结构的设计工作。最终实现了一个分布式网络爬虫的程序原型，通过在互联网上进行实验，检验了网络爬虫节点的运行效果，由此验证了分布式网络爬虫的可行性和有效性。关键词：并行；网络爬虫节点；信息采集； AbstractA search engine is a shortcut to access to information resources. As an
8、 important component of a search engine, web crawler is responsible for web information collection, which is the only source of original information in search engine database. This paper revolves around the cutting-edge web search technology, reptile-depth study of the theory and related technologie
9、s of web crawler. A high performance distributed web crawler is designed and implemented based on this knowledge.This paper research the development of search engines, understanding the application meaning and real value of the web crawler from the research. And then learning and research the histor
10、y and development of the web crawler. Summing up the experience of their predecessors, lay a solid foundation for the research.With deeper understanding of the research background of the web crawler, I then start to research and analyze the technology of the distirbuted web crawler node, including c
11、rawl strategy, web page evaluation, HTML web document analysis, using multithreading, change web page coding, polite crawl etc. And use the key technology in the implementation of the distirbuted web crawler node.When understand and mastery of theoretical knowledge, the next is applied to the actual
12、 work. Analyze the base logic of the distributed web crawler node; partition the function of each module of the carwler node, make the distribution of the functions for each module in details; detailed design the work process of the web crawler node; finally, integrated the design, complete the deta
13、iled design of the class structure.Impplement a prototype of the distributed web carwler system, through the experiment in the internet, tested the operation of the distributed web crawler node, testify the feasibility and effectiveness of the distributed web crawler.Key words: parallel; web crawler
14、 node; information retrieval; 目 录第一章 绪论 .11.1 课题研究背景 .11.1.1 搜索引擎的发展 .11.1.2 网络爬虫的研究及应用意义 .41.2 工作的目的与意义 .51.3 主要工作内容简述 .61.4 本文组织结构 .6第二章 网络爬虫相关知识研究与关键技术概述 .82.1 网络爬虫相关知识研究 .82.1.1 网络爬虫的研究历史 .82.1.2 网络爬虫的发展现状 .92.2 网络爬虫关键技术概述 .112.2.1 网络爬虫的爬行策略 .112.2.2 网页评测算法 .122.2.3 网页解析 .142.2.3.1HTML 语法分析 .142
15、.2.3.2 页面链接的提取 .172.2.4 优雅采集 .172.2.5 多线程技术 .192.2.5.1 多线程概述 .192.2.5.2 线程带来的问题和解决办法 .192.2.5.3 多线程在网络爬虫节点中的使用 .202.2.6 消除重复网页 .212.2.7 网页的存储 .22第三章 分布式网络爬虫节点设计详解 .243.1 分布式网络爬虫节点基础逻辑设计 .243.2 分布式网络爬虫节点结构设计 .253.2.1 下载模块 .273.2.2 网页解析模块 .283.2.2.1 主要解析流程 .283.2.2.2 网页编码转换 .293.2.3 数据库存储模块 .303.2.4 优
16、雅采集模块 .313.2.5 任务定位模块 .323.2.6 节点通信模块 .323.3 分布式网络爬虫节点详细程序设计 .333.3.1 整体框架 .333.3.2 爬行节点详细流程 .343.3.3 分布式网络爬虫节点类结构设计 .363.3.3.1 爬虫节点类的整体设计 .363.3.3.2 主要类的职责和详细工作内容 .37第四章 系统实现与测试分析 .394.1 软件系统实现说明 .394.2 软件实验测评分析 .43第五章 结束语 .46参考文献 .47致谢 .50ContentsChapter 1 Introduction.11.1 Research background .11
17、.1.1 Development of search engine .11.1.2 Research and application significance of Web crawler .41.2 The purpose and significance of work .51.3 Outlined the main work .61.4 The organizational structure .6Chapter 2 Research of web crwaler knowledge and key technology .82.1 Research of web crawler kno
18、wledge.82.1.1 History of web crawler research .82.1.2 Development Status of web crawler .92.2 An overview of key technologies.112.2.1 Crawl strategy .112.2.2 We page evaluation algorithm.122.2.3 Web page analytic .142.2.3.1 HTML parsing .142.2.3.2 Extraction of page links .172.2.4 Polite crawl.172.2
19、.5 Multi-threading technology.192.2.5.1 Overview of multi-threading technology.192.2.5.2 The problems and solutions of using threads.192.2.5.3 Using multi-threading in the web crawler .202.2.6 The elimination of duplication of the page .212.2.7 Web page storage .22Chapter 3 Distributed web crawler n
