算法总结

沈业基

一、 动态规划和递推

dp一般的解题步骤：

分析问题，弄清题意——从原问题中抽象出模型——根据模型设计状态，要求状态满足最优子结构和无后效性——直接设计状态有难度的话则需要考虑转化模型——根据设计的状态考虑转移——如果过不了题目要求的数据范围，则需要考虑优化

由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧

Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解

关于DP的优化有两篇神级论文，放在附件里面了，写的非常好。

二、 图论及网络流

最小生成树：克鲁斯卡尔算法和普利姆算法，

——重要性质1：最小生成树上任意两点的路径的最大边最小

——重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题 生成树计数）

最短路：spfa算法、堆+迪杰斯特拉算法

Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环

——判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后这个条数>n-1则存在负权环

堆+迪杰斯特拉则是用了贪心的思想，不断扩大确定dist的集合，同时更新dist，如果边权有负值就不能做，复杂度是O((n+m)logn)的

拓扑排序：可以将有向图转化为一个线性的序列，满足一个点所有的前驱结点都出现在这个点在序列中的位置之前。可以判断这个有向图是否有环

——一个简单而实用的扩展：给树做类top排序，可以有类似的功能，即每次去掉叶子结点，将树转化为一个具有拓扑关系的序列

——再扩展：树同构判断，可用类top确定树根是谁，再最小表示法+hash即可

强连通分量、缩点：tarjan算法

…… …… 余下全文

算法学习报告

学习总结：

对于算法这门课，要善于给出算法的形式化表示，学会用一些算法分析的数学基础，原来的时间复杂度的分析，一般是采用一些数学的方法，有的时候计算起来比较繁琐，对于形如T(n)=a*T(n/b)+f(n)的递归方程，主定理的使用，只需要比较f(n)与n^longba的量级即可，可以快捷地求出时间复杂度的量级，同时我们还得到了如何改进有关算法的一些提示，当n^longba起主导作用时，可以从减少子问题的个数和减小子问题的规模两个方面来考虑，而当f(n)起主导作用时，这时候要着重改善子问题分解组合时的处理方法。

算法常用的技术有分治法，贪心法，周游法，回朔法，动态规划法，分支定界法。

分治法的要领就是将一个规模较大的问题分解为若干个规模较小的子问题，这些子问题与原问题同类。其分治法的精髓就是分、治、合。利用分治法可以解决求第k小元素问题，其主要思想是当元素个数小于50时可以用堆排序找到，但是当元素个数大于50时，五分化中项的中项m,将数组分成三部分，比它大的，比它小的以及与它相等的。寻找最近点对的问题，采用分治法的方法是将点对平分到两个部分，分治求出左半部分的最近点对，右半部分的最近点对，再求出点位于左半和右半的最近点对，为了减少比较的次数用到了检查落到带状区域内的每一个点检查其后的4个点。

动态规划法与分治法类似，但是有着不同，动态规划法解决的问题通常具有以下几个特点：最有子结构和高度的重复性。动态规划的指导思想是：在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优，不能保证全局最优，因为有些问题不符合最优性原理。如果二维数组中有相当一部分元素在整个计算过程中都没有用到则可以采用动态规划的变形—备忘录的方法，比如说是求解LCS问题；其他的一些动态规划问题比如说矩阵连乘、最优二分搜索树无需计算的子问题只有少部分或全部都要计算，采用递推的方式比较好。

…… …… 余下全文

什么是算法？

算法是指解决问题的一种方法或一个过程。更严格的讲，算法是若干指令的有穷序列。 算法的性质？

(1)输入：有零个或者多个由外部提供的量作为算法的输入。作为算法加工对象的量。值，通常体现为算法中的一组变量。(2)输出：算法产生至少一个量作为输出。它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

(3)确定性：组成算法的每条指令是清晰、无歧义的。对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行（可行性） 。并且在任何条件下，算法都只有一条执行路径。(4)有限性：算法中每条指令的执行次数是有限的，每条指令的执行时间也是有限的。

程序和算法的区别？

程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序，通过特定的算法来实现。该子程序得到输出结果后便终止。

算法分析

是对一个算法所消耗资源进行估算。资源消耗指时间、空间的耗费。算法分析的目的就是通过对解决同一问题的多个不同算法进行时空耗费这两方面的分析.比较求解同一问题的多个不同算法的效率。

一般情况下将最坏情况下的时间耗费的极限作为算法的时间耗费，称为时间复杂性。可操作性最好最有实际价值的是最坏情况下的时间复杂性。

渐进复杂性：当n单调增加且趋于∞时， T(n)也将单调增加且趋于∞。对于T(n)， 如果存在T~(n)，当n→∞时，(T(n)-T~(n) )/T(n) →0 ，称T~(n)是T(n)当N→∞时的渐近性态，或称为算法A当N→∞的渐近复杂性。

渐进意义下的记号O Ω θo：以下设f(N)和g(N)是定义在整数集上的正函数。O:如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)).这时还说f(N)的阶不高于g(N)的阶。根据符号O的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界，这个上界的阶越低，则评估就越精细，结果就越有价值。Ω：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N),则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N)).这时还说f(N)的阶不低于g(N)的阶。根据符号Ω的定义，用它评估算法的复杂性，得到的只是该复杂性的一个下界，这个下界的阶越高，则评估就越精细，结果就越有价值。Θ：定义f(N)=θ(g(N))，当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))，这时我们说f(N)与g(N)同阶。O:如果对于任意给定的ε>0,都存在正整数N0，使得当N≥N0时，有f(N)/g(N)<ε,则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g（N)）。 递归的基本要素

…… …… 余下全文

百度排名规则及算法总结

要想百度给你网站排名，只有三种理由，第一你给百度钱了，第二你是百度旗下的公司或产品，第三你提供有价值的内容，提高了百度搜索的用户体验了。除去这三个理由，你别想着要百度给你排名，那么我们围绕这三种理由，展开我们的分析。

百度竞价

百度竞价主要是根据关键词出价获得排名的，对于百度竞价我了解的不是很多，大致我清楚，当你出价1元一个点击，排名在第三位，那么人家想要超过你，人家就得出价1元以上，原理是这个样子的。

通常情况下，百度付费的广告排名控制在第2-3是最好的状态，排名在第一，基本是竞争对手在点击你的网站。所以控制在2-3是最佳的位置。

百度竞价最大的好处，就是排名时间块，马上投放广告，马上就有排名，所以不少的企业选择百度竞价做前期推广，而百度竞价的原理也非常简单，百度公司要赚钱生存，所以推出了这个百度付费推广的模式，通过他们的后台直接操作给你排名，你有排名可以赚到钱，但你得给他们钱，不可能永远依靠百度竞价来支撑，所以除了百度竞价，我们还可以这样去做。

百度旗下产品

百度旗下产品非常多，能够参与排名的也非常多，比如百度文库、百度知道、百度百科、百度经验、百度百家等等，这些百度产品只是一个平台，百度官方人员从来不会编辑里面的内容，这些平台里面的内容都是由第三方企业或个人编辑而成，既然要我们来编辑，那么推广的机会就来了。咱们还是先说说，他们排名算法以及规则吧。

百度旗下的产品是由百度自己开发而成，在排名上有很大的优势，优势在哪里呢，就是通过阿拉丁通道排名的，说白了就是走后门。

前面说到了付费竞价推广是通过后台直接给出排名，而百度旗下产品的平台与付费推广不一样，他们不属于推广，而是直接优先展示他们网站的排名。展现的形式还是与普通网站自然排名展现的形式一样。

但是这种阿拉丁通道的排名也是有规则的，第一他们没有收录规则，基本是审核通过的内容直接收录，所以收不收录就看你的内容是否会审核。但是他们的排名是有规则的，比如同一篇文章，在百度文库、各种BBS或者自己的博客上进行发布，最终你会发现排名在前的是百度文库；论权重新浪、搜狐等大型网站不比百度文库差，但是百度为了让自己旗下产品生存，获得流量，只有通过后门技术，直接用百度文库的页面来做排名。

…… …… 余下全文

关于百度算法的猜测，那是众说风云，最近因为百度算法计划内的大规模调整，众多从事SEM和SEO的爱好者更是对于百度算法议论纷纷，众志传媒搜索营销顾问蒋鑫鹏将近年来做SEO搜索引擎优化的实战经验做总结归纳，分享与此，与热爱网络营销的朋友们探讨……求拍砖，求吐槽，求碰撞出火花

!

一、百度基础算法分析：链接流行度核心算法+百度推广+框计算+开放平台

1.【链接流行度】和大多数关键词搜索引擎一样，页面URL地址链接的流行程度为核心的基础核心算法;

2.【百度推广】起先叫做百度竞价，后改为百度推广，包括关键词竞价算法和网盟推广算法两部分;

3.【框计算】语义分析、行为分析、智能人机交互、海量基础算法等。

二、百度收录流程

1.【页面的收录】搜索蜘蛛程序》已收录的页面链接》发现新的链接并爬行》新的页面及内容合格》收录快照并分类存储》建立页面基本数据(页面URL、页面关键词、页面标题描述、收录来源、收录时间、内容简述、页面权重、更新周期);

2.【百度免费产品】百度百科、百度文库、百度贴吧、百度知道、百度空间等百度自身免费产品的页面收录;

3.【百度开放平台】主要是站长提供的结构化数据(网站与百度的深度合作，如汽车网站的参数数据、百度知道接口等)和开发者提交的各种应用(开发者加入百度开发者中心并提交相关应用通过审核);

4.【百度竞价推广】网站主开通百度推广账户》预付费并通过网站审核》编辑关键词广告及推广计划》提交百度推广后台;

5.【百度网盟推广】网站主开通百度推广账户》预付费并通过网站审核》编辑网盟广告及推广计划》提交百度推广后台;百度联盟广告合作伙伴站长参与网盟推广并审核通过》预留广告位并做好网盟接口。(SEO顾问：蒋鑫鹏)

三、百度检索流程

搜索需求》语义分析》数据库检索》排名显示反馈

1.【百度搜索页面的检索】用户输入关键词并检索》框架算(语义分析及分词判断、行为分析、智能人机交互、海量基础算法)》框计算结果(开放平台的数据、传统搜索结果、百度推广结果、百度自身产品结果)》框计算结果排名。

…… …… 余下全文

第一章 绪论

1、重要特性

1.输入

2.输出

3.有穷性

4.确定性

5.可行性

2、描述算法的方法

1.自然语言：优点是直观易懂，缺点是容易出现二义性

2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言

3.程序设计语言：优点是计算机直接运行，缺点是抽象性差

4.伪代码：

3、递归算法分析

1.猜测技术

2.扩展递归技术

3.通用分治递归推式

第二章 NP完全理论

第三章 蛮力法

3.1 蛮力法的设计思想

蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;

关键——依次处理所有元素。

3.2 查找问题中的蛮力法

3.2.1 顺序查找O(n)

3.2.2串匹配问题

BF O(n*m)

BMP O(n+m)

BM O(n*m)

3.3 排序问题中的蛮力法

3.3.1 选择排序O(n²)

3.3.2 起泡排序O(n²)

3.4 组合问题中的蛮力法

3.4.1 生成排列对象O(n!)

3.4.2 生成子集O(2ⁿ)

3.4.3 0/1背包问题O(2ⁿ)

3.4.4 任务分配问题O(n!)

3.5 图问题中的蛮力法

3.5.1 哈密顿回路问题O(n!)

3.5.2 TSP问题O(n!)

3.6 几何问题中的蛮力法

3.6.1 最近对问题O(n²)

3.6.2 凸包问题O(n³)

3.7 实验项目——串匹配问题

第四章 分治法

4.1 分治法的设计思想

设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

…… …… 余下全文

模拟退火，遗传算法

在工程实践中，经常会接触到一些比较“新颖”的算法或理论，比如模拟退火，遗传算法，禁忌搜索，神经网络等。这些算法或理论都有一些共同的特性（比如模拟自然过程），通称为“智能算法”。它们在解决一些复杂的工程问题时大有用武之地。

这些算法都有什么含义？首先给出个局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻：

为了找出地球上最高的山，一群有志气的兔子们开始想办法。

1．兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。

2．兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。

3．兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。

4.兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。

智能优化算法的概述

智能优化算法要解决的一般是最优化问题。最优化问题可以分为

（1）求解一个函数中，使得函数值最小的自变量取值的函数优化问题和

（2）在一个解空间里面，寻找最优解，使目标函数值最小的组合优化问题。 典型的组合优化问题有：旅行商问题（Traveling Salesman Problem，TSP），加工调度问题（Scheduling Problem），0－1背包问题（Knapsack Problem），以及装箱问题（Bin Packing Problem）等。

优化算法有很多，经典算法包括：有线性规划，动态规划等；改进型局部搜索算法包括爬山法，最速下降法等，本文介绍的模拟退火、遗传算法以及禁忌搜索称作指导性搜索法。而神经网络，混沌搜索则属于系统动态演化方法。 优化思想里面经常提到邻域函数，它的作用是指出如何由当前解得到一个（组）新解。其具体实现方式要根据具体问题分析来定。

…… …… 余下全文