第一篇：蚁群算法与粒子群算法优缺点个人精华篇
蚁群算法与粒子群算法优缺点
蚁群算法(ACO)是受自然界中蚂蚁搜索食物行为的启发，是一种群智能优化算法。它基于对自然界真实蚁群的集体觅食行为的研究，模拟真实的蚁群协作过程。算法由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。蚁群算法作为通用随机优化方法，已经成功的应用于TSP等一系列组合优化问题中，并取得了较好的结果。但由于该算法是典型的概率算法，算法中的参数设定通常由实验方法确定，导致方法的优化性能与人的经验密切相关，很难使算法性能最优化。
蚁群算法中每只蚂蚁要选择下一步所要走的地方，在选路过程中，蚂蚁依据概率函数选择将要去的地方，这个概率取决于地点间距离和信息素的强度。
(ｔ+ｎ)=(t)+ Δ(ｔ+ｎ)上述方程 表示信息素的保留率，1－ 表示信息素的挥发率，为了防止信息的无限积累，取值范围限定在0～1。Δ ij 表示蚂蚁k在时间段t到(t +n)的过程中，在i到j的路径上留下的残留信息浓度。
在上述概率方程中，参数α和β:是通过实验确定的。它们对算法性能同样有很大的影响。α值的大小表明留在每个节点上信息量受重视的程度，其值越大，蚂蚁选择被选过的地点的可能性越大。β值的大小表明启发式信息受重视的程度。这两个参数对蚁群算法性能的影响和作用是相互配合，密切相关的。但是这两个参数只能依靠经验或重复调试来选择。
在采用蚁群－粒子群混合算法时，我们可以利用PSO对蚁群系统参数α和β的进行训练。具体训练过程：假设有n个粒子组成一个群落，其中第i个粒子表示为一个二维的向量 xi =(xi1 , xi2), i = 1, 2, ⋯,n，即第i个粒子在搜索空间的中的位置是xi。换言之，每个粒子的位置就是一个潜在的解。将xi带入反馈到蚁群系统并按目标函数就可以计算出其适应值，根据适应值的大小衡量解的优劣。
蚁群算法的优点：
蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性（对基本蚁群算法模型稍加修改，便可以应用于其他问题）和搜索较好解的能力。
蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。蚁群算法很容易与多种启发式算法结合，以改善算法性能。
蚁群算法存在的问题：
TSP问题是一类经典的组合优化问题，即在给定城市个数和各城市之间距离的条件下，找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果，但是也存在一些不足：（1），如果参数α和β设置不当，导致求解速度很慢且所得解的质量特别差。（2），基本蚁群算法计算量大，求解所需时间较长。（3），基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环数的条件下很难达到这种情况。
另一方面，在其它的实际应用中，如图像处理中寻求最优模板问题，我们并不要求所有的蚂蚁都找到最优模板，而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。
蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法一般需要较长的搜索时间，其复杂度可以反映这一点；而且该方法容易出现停滞现象，即搜索进行到一定程度后，所有个体发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。
粒子群优化具有相当快的逼近最优解的速度，可以有效的对系统的参数进行优化。粒子群算法的本质是利用当前位置、全局极值和个体极值3个信息，指导粒子下一步迭代位置。其个体充分利用自身经验和群体经验调整自身的状态是粒子群算法具有优异特性的关键。PSO算法的优势在于求解一些连续函数的优化问题。
PSO算法存在的问题：
问题最主要的是它容易产生早熟收敛（尤其是在处理复杂的多峰搜索问题中）、局部寻优能力较差等。PSO算法陷入局部最小，主要归咎于种群在搜索空间中多样性的丢失。
不同算法的混合模型主要分为两类：（1）全局优化算法与局部优化算法混合；（2）全局优化算法与全局优化算法混合。纵观各种与PSO算法相关的混合算法，大多数基本上采用一种策略对其改进，要么与其他算法，要么加入变异操作，同时采用两种策略的混合算法较少。
上述策略中，两者之间有一定的矛盾性，全局算法与局部算法相混合，尽管可以提高局部收敛速度，但也加剧了陷入局部极小的可能；全局算法与全局算法的混合，算法的局部细化能力仍然没有改善。但如果只加入变异操作，则算法的探测能力得到提高，但也损害了其局部开发能力。
因此如果将局部搜索和变异操作同时混合到PSO算法中，通过适当的调节，发挥各自的优点，提高算法的开发能力，增加变异操作防止算法早熟，来共同提高PSO算法的全局寻优能力。
融合策略：
（1）针对蚁群算法初始信息素匮乏的缺点，采用其他算法生成初始信息素分布，利用蚁群算法求精确解，从而提高时间效率和求解精度。（使用的其他算法的求解结果以什么规则转换成蚁群算法的信息素初值，需要通过多次实验）
（2）将其他算法（如遗传算法）引入到蚁群算法系统的每次迭代过程中。以蚁群系统每一代形成的解作为其他算法的初始种群，然后经过其他算法的多次迭代，试图寻找更好的解，从而加快蚁群系统的收敛速度，提高求解速率。
（3）蚁群算法中α，β的选取往往是通过经验来取得的，而选取不当时会造成算法的性能大大降低，因此可以利用其他算法对蚁群系统参数α，β进行训练。
（4）对于蚁群算法出现过早收敛于非全局最优解以及时间过长的缺点，可以通过使用蚁群算法进行搜索，然后用其他算法对蚁群算法得到的有效路由路径，通过选择、交叉、变异等优化过程，产生性能更优的下一代群体。
（5）PSO算法由于局部寻优能力较差，因此可以在搜索过程中融入确定性局部搜索算法。
第二篇：基于改进粒子群优化算法的分布式电源规划
基于改进粒子群优化算法的分布式电源规划
摘 要：针对目前配电网中存在的分布式电源规划问题，在最大化电压静态稳定性、最小化配电网损耗以及最小化全年综合费用三个方面建立了分布式电源规划的优化模型。在规划模型的基础上，采用拥挤距离排序的多目标量子粒子群优化算法（MOQPSO-CD）以及基于量子行为特性的粒子群优化算法（QPSO），来更新和维护外部存储器中的最优解，通过对全局最优最小粒子的选择引导粒子群能够对分布式电源的配置容量与接入点位置的真实Pareto最优解集进行查找，获得对多个目标参数进行合理优化。最后采用IEEE33节点的配电系统，在模拟仿真实验过程中获得了分布式电源容量配置以及介入位置的合理方案，验证了优化算法的可行性。
【关键词】分布式电源规划 Pareto最优解 配电网
分布式电源（Distributed Generation，DG）由于其在减少环境污染、节约成本、发电方式灵活、减少发电输送中的线路损耗、改善电网中的能源质量以及提高电网供电稳定性等方面具有优点，在配电网中发展迅速。然而，在配电网中加入分布式电源会使电网中原有的结构发生改变，从而导致节点电压、线路损耗与网络损耗产生了不同程度的变化。如果分布式电源注入容量与接入点位置的配置出现问题，会加大电网中线路与网络等损耗，并且会对电网供电的可靠性产生严重影响，因此，针对这一现象，对DG的容量与配置参数进行合理的优化具有重要意义。
国内外许多学者曾对DG的参数配置优化问题进行了较为深入的研究并取得了一定进展。文献[1]针对分布式电源中的地址定容问题采取了单一目标的优化方法，但是该方法在实际电网中的可行性存在问题。文献[2]采用传统的模糊理论提出将电网中具有多目标优化方案转变为只有单一目标的优化方法，并且采用遗传算法，优化了分布式电源中的容量与位置。文献[3]对于配电网中DG的容量与选址通过改进遗传算法进行优化，但是该方法存在计算时间长、算法过于复杂有时会计算得出局部的最有求解等缺点。文献[4]通过改进的自适应遗传算法，搭建了基于DG环境效益与政府关于可再生能源补贴的最小化经济模型。
在实际应用中，对于配电网中分布式电源的优化需要考虑许多变量，一般都具有比较复杂的目标函数，对其进行优化时将多个目标函数转化为单一函数非常困难，因此必须采取有效措施节约分布式电源多目标模型建立中的相关问题。本文以分布式电源的配置容量及其在配电网中的接入位置为两个切入点进行研究，建立配电网在单位年中的费用最小、电网网络以及线路损耗最低、静态电压在最优系统中的稳定性3个目标函数的分布式电源优化模型。在粒子群优化（QPSO）算法中量子行为特性的理论上加入拥挤距离排序技术，维护与更新外部存储器中的最优解，将生成分布式电源的最优配置方案问题转化为求解全局最优的领导粒子问题。最后，运用Matlab仿真软件对本文所提出的方案进行验证。配电网中DG的多目标规划模型
1.1 目标函数
1.1.1 网络损耗最小目标函数为
那么，求解出配电网中电压稳定指标的最小值minL即可知最大化静态电压的稳定裕度。
1.2 约束条件
1.2.1 等式约束
约束方程可以用潮流方程表示为：
式中，Pdi、Qdi为配电网中第 台发电机的有功、无功输出，PDGmax为分布式电源有功输出上限，PDGmin为分布式电源有功输出下限，QDGmax为分布式电源无功输出上限，QDGmin为分布式电源无功输出下限，Uimax为节点i电压上限Uimin为节点i电压下限，SDGi为配电网中拟接入的第i个DG的容量大小，SDGmax为配电网中可以接入的DG最大装机容量，Pl为线路l的传输功率。基于拥挤距离排序的粒子群优化算法
2.1 量子行为特性的粒子群优化算法
传统的粒子群优化（PSO）算法在求解方面具有不同程度的缺点，如容易陷入局部求解最优，收敛精度低等。为了防止粒子群算法进入早熟，并且尽可能加快算法的收敛减少计算时间，文献[10-11]给出了改进粒子群算法，使得具有量子行为特性的粒子群算法的实用性大大提高，在局部精度方面得到明显的提高，并且与PSO相比较仅具有一个位移更新公式。在本文中基本粒子群的集合设定为不同负荷节点处DG的输入功率，因此得到的集合为：
其中，i（i=1，2，???，P）为粒子群中的第i个粒子，j（j=1，2，???，N）为粒子在粒子群中的第j维，N为搜索空间的维数；ui，j（t）和φi，j（t）均为在区间[0，1]上随机均匀分布的数值，t为进化代数，xi（t）为在t代进化时粒子i的当前位置，pi（t）为在t代进化时粒子i的个体吸引子位置，yi（t）为在t代进化时粒子i的个体最好粒子位置，为群体在t代进化时的最好位置，C（t）为粒子在第t代进化时的平均最好位置，定义为全部粒子个体位置最好时的平均位置；α为扩张-收缩因子，是在迭代次数与除群体规模以外的唯一参数。
2.2 MOQPSO-CD算法
由于粒子群算法具有记忆特性，利用这一特性可以解耦特性粒子的解空间，求出解空间后可以适时调整控制策略，并能够通过记忆功能对当前动态进行搜索，同时具有优良的鲁棒特性和在全局范围内的搜索能力。然而，QPSO收敛的速度过快，导致了算法收敛过快，因此Pareto的解不具有多样性特点。为了寻找该问题的解决方案，本文通过利用外部存储器储存Pareto在求解过程中所产生的非劣解，从而可以较快地达到Pareto前沿。这样可以达到减少计算时间，更快获得领导粒子的目的。由于领导粒子是在所有粒子中表现最好的个体中得到的，它可以体现出整体粒子群体的认知能力，对于群体在搜索中的方向起着引导作用。为了即时更新外存储器中的非劣解，本文所采用的拥挤距离排序算法属于第2代非支配排序遗传算法（NSGA-II），通过对其进行操作，可以尽快地通过领导粒子找到Pareto的最优解。与此同时，为了使多样性在粒子种群中得到丰富，基于此算法的基础上加入高斯变革算子对粒子种群寻优过程中解的多样性进行扩充。
2.2.1 领导粒子的选择
在领导粒子选择的过程中即时对新外部存储器中粒子集进行维护更新是很有必要的。其目的在于保证粒子群的多样性，并能确保Pareto最优解集的合理分布。在此算法条件下，外部存储器中的粒子集必然会存在当前代数最优的粒子，然后通过拥挤距离值算法计算器内部粒子集中每个个体距离值，通过计算拥挤距离值的方法，将粒子集合内的个体进行量化，当出现拥挤距离值最大的粒子时，表明在目标空间中该粒子成为领导粒子可能性增加。当有两个或多个领导粒子的拥挤距离值相等时，领导粒子将会在之对应的最优粒子中随机选取。
2.2.2 拥挤距离值的计算
拥挤距离排序方法描述了在一个最优解周围分布其他最优解的密度情况。以下简单阐述了本文所用到的拥挤距离计算方法，具体实现可参考文献[13]。Gj（i）（j=1，2，3）依次表示网络损耗、年综合费用和静态电压稳定指标3个目标函数值；P为粒子群集合的大小，亦可描述可行解的数量。首先，对于存储在外外部存储器的全部最优粒子，在所有需要优化目标上的函数取值进行升序排列，然后可以得到在所有优化空间上与最优粒子相接近的其它最优粒子，然后可以计算得出在统一空间内两个优化粒子的距离；最后最优粒子的拥挤距离可以通过所有最优粒子距离的求和方式得出。以本文为例详细说明拥挤距离值的特征，逐一计算并遍历相邻最优粒子的空间距离，粒子i和相邻粒子i+1在优化目标空间的距离：
2.2.3 外部存储器更替算法
在本文中人为设定两条存储器更新规则，以便满足外部存储器中存在最优粒子的目的，规则如下：
（1）位于存储器中的粒子被新生成的粒子支配时；
（2）如若外部存储器已满，则需运用拥挤距离排序算法对其内部所有进行重新排序，根据公式（16）计算所有粒子的拥挤距离值，并且按照计算出数值的大小进行排列。
2.2.4 算法实施步骤
本文选用借鉴第2代非支配排序遗传算法的基于量子行为特性的粒子搜索解空间算法对配电网中的分布式电源进行优化配置，图1所示为算法具体流程，计算过程为：
（1）初始化起始数据，数据内容为事先已规划内容，初始化算法基本参数（粒子群的规模、粒子群的初始位置、并设定最大迭代次数），系统对分布式电源位置，以及初始粒子群数据集进行随机采样。
（2）依照步骤（1）中设置的规则，对外部存储器中的粒子进行初始化设置。
（3）需要对粒子进行排位，排位的算法由公式（1）～（4）给出，可以计算出目标函数值，同时，根据公式（16）可以计算出拥挤距离值，根据以上两个参数进行排位。“2.2.1节”的方法选出粒子群中的领导粒子，最后利用QPSO位移更新方程对每个粒子进行重置。以上计算过程将会计算采样粒子集合内任意粒子的拥挤距离值。评价其是否达到Gauss变异算法条件，若达到该算法条件，则进行Gauss变异操作（Gauss mutation operator），否则转到步骤④。
（4）对③中运用QPSO位移更新算法计算出的所有粒子进行评价，并算出所有粒子的潮流数值，将其接入位置以及配置容量用数值量化，并对比量化后的函数值，按照柏拉图最优解定律计算出个体最优粒子及外部存储器最优粒子集。与计算出的上一个最优粒子相比较，新产生的粒子群中某粒子更优，则将新出现粒子作为最优粒子；若二者不能相互支配，那么二者中任意一个将被选为最优粒子，并将其放入外部存储器，然后转步骤⑤；否则舍弃更新后的粒子并转⑥。
（5）对已进入外部存储器中的粒子，按照公式（16）对其进行计算，已达到随时更新存储器中粒子的目的。通过步骤（5）可以达到将最优粒子存入外部存储器的目的。
（6）计算进化代数，若满足终止代数，则将存储器中现有的粒子作为输出，此时输出的粒子集就是所寻找的柏拉图最优输出集；否则转步骤③。算例分析
利用本文建立的模型，对IEEE 33节点配电系统进行模拟仿真，配电网系统如图2所示，对分布式电源的位置以及其容量进行重新配置。该配电系统中，额定电压为12.66kV，有功负荷的取值为3715kW，总无功负荷的取值2300kVar，总节点数为33个，总支路数为32条（其中5条为联络开关）。配电系统基准容量设为10MVA，其中平衡节点选在0号节点，分布式电源接入比例小于30%，安装节点集合为?x1，2，???，31?y（图2中的32节点将不会接入分布式电源中，因为该节点是尾端节点，并且同变压器支路侧相连，因此不需接入）。根据文献[3]可知，在计算分布式电源时，可以将其近似看成负的PQ节点，根据经验公式，选取功率因数值为0.9。初始采样粒子群集合规模为90，进行100次迭代。
按照本文所搭建的数学模型及算法计算出分布式电源配置的柏拉图最优解，及其目标函数的空间分布，如图3所示。根据图3可知，计算出的所有解相互独立分布，每个不同解均可表示出当前条件下的配置效果。以图中所列出的解
1、解2及解3为例，说明不同情况下的DG配置结果。解1情况下电压稳定指标大于0.02，相比其他两种情况最不稳定，网络损耗为80kW，损耗过大，但是年综合用最小；解3和解2相比较而言，解3在网络损耗和电压稳定性方面要优于解2，然而解3在年综合费方面是三种情况中最大的；对于解2来说，无论是年综合费用或者网络损耗以及电压稳定性指标这三个参数指标适均介于解1和解3之间，因此，考虑综合因素以解2最好。表1所示为解
1、解2和解3的DG配置方案，3个解分别与3个方案对应。
通过对比表1中的方案配置可以看出，不同DG配置方案会对年综合费用、网损和电压稳定性产生影响。在对电源在辐射线路中放置位置的分析后发现，放置位置越靠前，线路潮流受到的影响就越小。根据表1配置DG方案接入配电网，配电网络损耗将会有一定幅度下降，同时电压稳定性指标也会达到满意的效果，按照该配置方案规划，最为突出的优点是电网网络损耗方面，按照方案3配置后，电网网络损耗下降了80%。
结语
以减少电网网络损耗及年综合费用为优化目标，同时兼顾静态电压稳定性为原则，建立了DG规划的模型，在计算方面选取具有量子行为特性的粒子群优化算法（QPSO），以及基于拥挤距离排序的多目标量子粒子群优化算法（MOQPSO-CD），同时采用模拟仿真对33节点配电系统进行优化，得出了基于DG配置的Pareto最优解集，由此实现了对DG优化规划的目的。并得出以下结论：为了尽可能的降低电网损耗，同时提高电压稳定性，需要将DG配置在主变电站远端位置，即馈线末端，此时DG配置收益最高。
参考文献
[1]QIAN Ke-jun，ZHOU CHENG-KE，ALLAN MALCOLM，et al.Effect of load models on assessment of energy losses in distributed generation planning[J].Electrical Power and Energy Systems，2011，33：1243-1250.[2]陈海焱，陈金富，杨雄平，等.配电网中计及短路电流约束的分布式发电规划[J].电力系统自动化，2006，30（21）：16-21.[3]邱晓燕，夏莉丽，李兴源.智能电网中分布式电源的规划[J].电网技术，2010，34（4）：7-10.[4]李德泉，徐建政，罗永.含分布式电源的配电网扩展规划[J].电力系统及其自动化学报，2012，（5）.[5]孙俊.量子行为粒子群优化算法研究[D].无锡：江南大学信息工程学院，2009.[6]武晓朦，刘建，毕棚翔.配电网电压稳定性研究[J].电网技术，2006，30（24）：31-35.[7]KENNEDY J，EBERHART R C.Particle swarm optimization[C].IEEE IntConf of Neural Networks.Perth，1995：1942-1948.[8]ABGELINE P J.Using selection to improve particleswarm optimization[C]/Proc IEEE CongrEvolComput.Anchorage.AK.USA"IEEE Service Center，1998：84-89.[9]MIRANDA V，FONSECA N New evolutionary particle swarm algorithm applied to voltage control[C].Proc 14th Power SystComputConf.Spain：IEEE Service Center，2002：1865-1873.[10]LIjun-jun，WANGxi-huai.Amodified particle swarm optimization algorithm[J].Intelligent Control and Automation，2004，1：354-356.[11]候云鹤，鲁丽娟，熊信艮，等.改进粒子群算法及其在电力系统经济负荷分配中的应用[J].中国电机工程学报，2004，24（7）：95-100.[12]DEB K，PRATAP A，AGRAWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Trans on Evolutionary Computation，2002，6（2）：182-197.[13]张君则，艾欣.基于粒子群算法的多类型分布式电源并网位置与运行出力综合优化算法[J].电网技术，2014，38（12）：3372-3377.[14]刘幸.基于量子粒子群算法的分布式电源多目标优化[D].北京：华北电力大学，2012.[15]ROUHANI A，HOSSEINI S H，RAOOFAT M.Composite generation and transmission expansion planning considering distributed generation[J].International Journal of Electrical Power & Energy Systems，2014，62（11）：792-805.[16]叶德意，何正友，臧天磊.基于自适应变异粒子群算法的分布式电源选址与容量确定[J].电网技术，2011，（06）：155-160.[17]BJELIC I B，CIRIC R M.Optimal distributed generation planning at a local level-A review of Serbian renewable energy development[J].Renewable & Sustainable Energy Reviews，2014，39（6）：79-86.[18]朱艳伟，石新春，但扬清，等.粒子群优化算法在光伏阵列多峰最大功率点跟踪中的应用[J].中国电机工程学报，2012，32（4）.[19]黄平.粒子群算法改进及其在电力系统的应用[D].广州：华南理工大学，2012.[20]施展，陈庆伟.基于QPSO和拥挤距离排序的多目标量子粒子群优化算法[J].控制与决策，2011，26（4）：540-547.[21]ZHANG L G，ZUO H.Pareto optimal solution analysis of convex multi-objective programming problem[J].Journal of Networks，2013（02）.[22]李中凯，李艾民，朱真才.拥挤距离排序的多目标文化粒子群优化算法[J].控制与决策，2012，27（09）：1406-1410.[23]慕彩红.协同进化数值优化算法及其应用研究[D].西安：西安电子科技大学，2010.作者单位
沈阳农业大学信息与电气工程学院 辽宁省沈阳市 110866
第三篇：数据结构与算法个人总结
数据结构与算法
重点内容：排序运算的算法、检索运算的算法，本部分所占分值较高，在11分左右； 考试点：数据顺序存储与链式存储、栈与队列的操作、二叉树的存储及遍历（或周游）、霍夫曼算法及其应用、各类排序算法；
知识部分： 1.数据结构的内容：
数据的逻辑结构：分为线性结构和非线性结构
数据的存储结构: 是数据的逻辑结构在存储器里的实现；
数据的运算：插入、删除、排序、查找等； 2.数据的存储结构分为：顺序存储结构和链式存储结构。3.单链表与双链表的插入与删除这里不再赘述，百度一下吧！
4.栈与队列的基本运算有：插入、删除、读取头元素到变量中，原栈或队列保持不变、判断是否为空、将栈或队列置为空
5.串的基本运算有：链接、赋值、求长度、全等比较、求子串、求子串的位置及替换等。6.广义表：广义表是线性表的推广，也称列表。
广义表的特点：
广义表的元素可以使字表，且字表的元素还可以是字表；
广义表可以被其他广义表所共享；
广义表可以是递归的表，机本身的一个字表；
7.多维数组与稀疏矩阵的存储比较复杂，请用百度查找相关内容，不再赘述；
8.树：树并不重要，重要的知识点是二叉树，对树理解不透彻的同学，请用百度搜索。9.二叉树：
二叉树的重点内容包括：
二叉树的遍历：中序遍历、前序遍历、后续遍历；（重点考察）完全二叉树（定义）：在一棵二叉树中，若最多只有最下面两层的节点数可小于2，且最下面一层的节点集中于最左边的位置，则称此二叉树为完全二叉树； 树的先根次序周游对应于二叉树的前序周游（遍历），树的后根次序周游对应于二叉树的中序周游（遍历）
10.二叉树的存储结构：链式存储结构与顺序存储结构。
二叉树的链式存储：
是指二叉树的各节点随机存储在内存空间中，节点之间的关系用指针标示；
二叉树链表的节点包括三个：左指针，数据域，右指针；其中左指针指向左子节点，有指针指向右子节点；也可以是指一个父指针（parent）用于指向父节点； 二叉树链表的重要知识点：一个n节点的二叉树链表，有n+1个空指针域；
二叉树的顺序存储：
二叉树的顺序存储就是按一定的次序，用一组地址连续的存储单元存储二叉树的节点元素；
完全二叉树的顺序存储的性质：
用数组A[1….n]顺序存储完全二叉树的各节点，则当i>0,且i<=[(n-1)/2]时，节点A[I]的右子女是节点A[2i+1],否则节点A[I]没有右子女；同理当i>0且I<=[n/2],节点i的左子女节点是2i，否则没有！11.哈夫曼树： 基本定义术语：
节点的路径长度：从根节点到该节点的路径上分支的数目；
树的路径长度：树中所有的节点的路径长度之和；
哈夫曼树：在有n个叶子节点，并带有相同权值的二叉树中，必定存在一个二叉树，使其带权路径长度最短，这样的二叉树被称为“最优二叉树”或“哈夫曼树”
如下图：
12.排序算法：
常考的排序算法有：插入排序、冒泡排序、选择排序、快速排序、堆排序
插入排序: 首先先建立一个空列表，然后放入一些已排序的有序数列（自定），然后然后从原列表中取出一个数，并放入新列表，仍使新列表保持有序；重复这个动作直到原列表为空；
冒泡排序：顾名思义，就像冒泡一样（可以从小到大，也可以从大到小），大的升上去，小的降下来。首先将所有元素放入工作列表中，从列表的第一位数字到倒数第二位数字，逐个比较一个数和它的下一位，如果这个数大于它的下一位，则将它和它的下一位交换，重复该 步骤，直到不能交换
选择排序：设数组中存储了n个待排序数字，从数组中找到最小值和最大值分别放在数组的最左边和最右端，然后选出次小值和次大值放到左数第二位和右数第二位，……，最后建立完整的顺序；
快速排序：这是一种高效排序方法：
实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而“保证列表的前半部分都小于后半部分”就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。
堆排序:与前面的算法都不同，它是这样的：
首先新建一个空列表，作用与插入排序中的“有序列表”相同。
找到数列中最大的数字，将其加在“有序列表”的末尾，并将其从原数列中删除。
重复2号步骤，直至原数列为空。
堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得“找到数列中最大的数字”这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。
看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。
算法的时间复杂度：
平均时间复杂度
插入排序 O(n2)
冒泡排序 O(n2)
选择排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
基数排序 O(n)
希尔排序 O(n1.25)
第四篇：算法设计与实现个人课程总结
算法课程总结
指导教师 所在院（系）班 级 学生姓名 学 号
一、算法概述
1.什么是算法？
算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。
2.算法的五个重要特性：确定性、能行性、输入、输出、有穷性/有限性。
1）确定性：算法每种运算必须有确切定义，不能有二义性。
2）能行性：算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。
3）输入：每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域
4）输出：一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。
5）有穷性/有限性：一个算法总是在执行了有穷步的运算之后终止。
3.计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。
4.准确理解算法和计算过程的区别：不能终止的计算过程：操作系统；算法是“可以终止的计算过程”；算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行。
5.算法的语言主要有：自然语言，流程图，盒图，PAD图，伪代码，计算机程序设计语言。6.算法分类：
1)多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：Ο(1)< Ο(logn)< Ο(n)< Ο(nlogn)< Ο(n2)< Ο(n3)2）指数时间算法：计算时间用指数函数限界的算法。常见的指数时间限界函数：Ο(2n)< Ο(n！)< Ο(nn)7.算法基本工具：循环与递归，算法与数据结构，优化算法的数学模型。
8.主要算法：迭代算法，蛮力法，分治法，动态规划法，贪婪算法，图搜索基础。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。
①算法最基本的设计方法包括分治法，动态规划法，贪婪算法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。
贪婪算法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。
回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。
分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。
这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。
三、重点学习
1.贪婪算法
贪婪+其他算法：由于贪婪往往能大幅化简状态，利用问题的某些“单调性”，加上贪婪的思想，往往能是问题大幅简化，从而结合其他算法解决问题经典例题：田忌赛马，利用贪婪来确定状态。2.分治法
分而治之的思想在信息学竞赛中是非常重要的，下面主要介绍一下分治的经典应用
1)二分查找
思想很简单，功能很强大，边界要注意，负数要特判（NOI2010 PIANO）在非负数范围内的二分一般写法
如果是l := mid1 或 +1则 mid :=(l + r + 1)div 2 2)快速幂
a^b =(a^(b div 2))^2 + ord(odd(b))*a取模也适用 3）快速排序，归并排序
任何一本算法书上都会讲的，这里就略过了，值得一提的是快排记得加上随机化
k := a[random(rg(x)*ans = 0 重构权，将f(i)-g(i)*ans作为新权值，用相应算法求出一个“最小值”，判断是否>=0，接着二分即可
5)树的分治
一般用来解决树上的路径或统计类问题，每次只考虑跟树根有关的信息，然后递归分治处理
树的分治通常有基于点或基于边的分治，基于点的难合，基于边的复杂度太高，这里只介绍基于点的分治
步骤：处理跟当前树根有关的信息，重新计算子树大小，在子树中选择重心为根，递归到相应子树处理。
因为每次选了重心，所以递归总共logn层，每层O(n)的复杂度，总复杂度就是O(nlogn)6)二分搜索
直接搜的复杂度是指数级的的话，一般是40左右的数据量，hash一半，搜一半，搜后面的时候利用之前的hash信息合并出原问题的解。
而直接搜的复杂度达到阶乘级的话n一般就不超过20了，做法一般差不多 经典例题：POI02szy，NOI2001方程的解数。3.搜索
作为信息学竞赛中的所谓“万能算法”，搜索可以说是计算机学科所具有的最大特点了，自然地，搜索算法的应用自然也是非常之广泛，除了专门的搜索题，搜索一般可以用来部分预处理，打表找规律，当然还有骗分。
搜索的一般步骤：确定状态——选择搜索方式（dfs、bfs）——确定产生式规则——开始搜索。搜索的常见优化方式：
1)改变状态表示
这个需要根据题目而定，确定一个漂亮的状态表示，可能就有希望转向记忆化了，即使不行，搞出一个漂亮的状态表示是解决一道麻烦题的最重要的一步，再者，调试起来也会容易许多。
2）优化搜索顺序
这个优化在多数搜索中能起到摧枯拉朽的提速效果，通常我们选择枝叶较少的儿子先扩展，例如大名鼎鼎的dancing Links，除了利用双向十字链表去除冗余状态，每次选择可扩展数最少的儿子扩展同样给它的神速创造了条件。
3）可行性剪枝以及最优性剪枝
这是非常常用的剪枝思路之一，因题目而异，在迭代加深搜索中尤为重要 一般思路：考虑每次解最多变优多少，从当前的层数来看还有多少改进空间，如果已经不可能成为解或更新答案则可以剪枝了
——A*及IDA*算法：本质就是给搜索加上一个满足相容性的估价函数，然后用估价函数剪枝，理论上很牛B，实际上不常用，因为考场上很难想出满足那么多条件的估价函数，但记得一些常见模型的估价函数还是有价值的。例如15数码的估价函数就可以选择除了0之外每个元素到自己该到的位置的曼哈顿距离之和，因为每次最多使一个数距离减少1，所以这个估价函数是相容的，再例如求k短路的A*算法就是用个堆维护 min{ f(s)+ g(s)}估价函数就是从汇点反搜的“反向最短路”的长度。
四、总结
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。
经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。
第五篇：实验一线性表的创建与访问算法设计
内蒙古工业大学信息工程学院
四、编译程序：
#include
typedef char ElemType;typedef struct LNode
//定义单链表结点类型 {
ElemType data;
struct LNode *next;}LinkList;
LinkList *CreatlinkR(LinkList *L)
//用尾插法建立带头结点的单链表 {
LinkList *s, *r;char ch;r =(LinkList *)malloc(sizeof(LinkList));
//创建头结点
L = r;s = r;r->next = NULL;printf(“单链表元素值为单个字符, 连续输入，$为结束字符:”);while((ch = getchar())!= '$'){
r =(LinkList *)malloc(sizeof(LinkList));
//创建新结点
r->data = ch;
r->next = NULL;
s->next = r;
s = r;
} r->next=NULL;
//终端结点
return(L);}
void Sort(LinkList *h)
//单链表元素排序 { LinkList *p=h->next,*q,*t;
if(p!=NULL){
t=p->next;
p->next=NULL;
p=t;
while(p!=NULL)
{
t=p->next;
q=h;
第 页
内蒙古工业大学信息工程学院
while(q->next!=NULL&&q->next->data
data)
q=q->next;
//在有序表中找插入*p的前驱结点*q
p->next=q->next;
//将*p插到*q之后
q->next=p;
p=t;
} } }
void DispList(LinkList *L)
//输出单链表L {
LinkList *p=L->next;
while(p!=NULL){
printf(“%c ”,p->data);
p=p->next;} }
LinkList *Union(LinkList *La,LinkList *Lb,LinkList *Lc)
{ LinkList *pa=La->next,*pb=Lb->next,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;while(pa!=NULL&&pb!=NULL){
if(pa->data
data)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
}
else if(pa->data>pb->data)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pb->data;
tc->next=s;
tc=s;
pb=pb->next;
}
else
{
第 页
//求两有序集合的并集 //复制结点
内蒙古工业大学信息工程学院
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
//重复元素只复制一个
pb=pb->next;
} } if(pb!=NULL)
//复制余下结点
pa=pb;while(pa!=NULL){
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
} tc->next=NULL;return(Lc);}
LinkList *InsterSect(LinkList *La,LinkList *Lb,LinkList *Lc)
//求两有序集合的交集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL){
pb=Lb->next;
while(pb!=NULL&&pb->data
data)
pb=pb->next;
if(pb!=NULL&&pb->data==pa->data)
//若pa结点值在pb中
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;}
tc->next=NULL;return(Lc);
第 页
内蒙古工业大学信息工程学院
}
LinkList *Subs(LinkList *La,LinkList *Lb,LinkList *Lc)
//求两有序集合的差集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL){
pb=Lb->next;
while(pb!=NULL&&pb->data
data)
pb=pb->next;
if(!(pb!=NULL&&pb->data==pa->data))
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;} tc->next=NULL;return(Lc);}
void main(){
LinkList *La,*Lb,*Lc;
int num=0,loop,j;loop=1;La=CreatlinkR(La);Lb=CreatlinkR(Lb);Sort(La);Sort(Lb);
printf(“有序集合A＝{ ”);
DispList(La);
printf(“}n”);
printf(“有序集合B＝{ ”);
DispList(Lb);printf(“}n”);while(loop){
printf(“请选择您要执行的操作：1.求并集
scanf(”%d“,&j);printf(”n%d“,j);
第 页
//若pa结点值不在pb中 2.求交集
3.求差集n”);
内蒙古工业大学信息工程学院
if(j>=1&&j<=3)
switch(j)
{
case 1: Lc=Union(La,La,Lc);
printf(“集合A与集合B的并集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
case 2: Lc=InsterSect(La,Lb,Lc);
printf(“集合A与集合B的交集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
case 3: Lc=Subs(La,Lb,Lc);
printf(“集合A与集合B的差集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
} printf(“0.结束
1.继续n”);scanf(“%d”,&loop);printf(“n”);} }
五、运行结果：
1．输入两个无序集合，排序后输出：
第 页
内蒙古工业大学信息工程学院
2．求集合的并集：
3．选1继续：
第 页
内蒙古工业大学信息工程学院
4．求集合的交集：
5．求集合的差集：
第 页
内蒙古工业大学信息工程学院
6．选0结束：
第 页
点击咨询 