BFS .广度优先搜索算法
一般来说，可以采用搜索算法解决的这类问题的特点是：
1.有一组具体的状态，状态是问题可能出现的每一种情况。全体状态所构成的状态空间是有限的，问题规模较小。
2.在问题的解答过程中，可以从一个状态按照问题给定的条件，转变为另外的一个或几个状态。
3.可以判断一个状态的合法性,并且有明确的一个或多个目标状态。
4.所要解决的问题是：根据给定的初始状态找出目标状态，或根据给定的初始状态和结束状态，找出一条从初始状态到结束状态的路径。
采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。根据问题所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。
广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，...对长度为n+1的任一结点进行扩展之前，必须先考虑长度为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。
广度优先搜索算法中，为了便于进行搜索，要设置一个表存储所有的结点，为了满足先生成的结点先扩展的原则，存储结点的表一般设计成队列的数据结构。搜索过程中不断地从队列头取出结点进行扩展。对生成的新结点，要检查它是否已在队列中存在，还要检查它是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，并且未曾在队列中出现过，则将它加入到队列尾，否则将它丢弃，再从队列头取出结点进行扩展......。最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。
如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。
对于不同的问题，用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否目标结点和是否重复结点的判断等方面则有所不同，对具体的问题需要进行具体分析。
二.广度优先搜索算法的算法框架
Private Type TNode '定义一个结点数据类型
.... '根据具体问题确定所需的数据类型
End Type
Dim State() As TNode '定义TNode类型的数组，作为存储结点的队列
Private Sub BFS() 'BFS算法主程序
Dim Temp As TNode 'TNode型临时结点
Dim Head As Integer,Tail As Integer '队列头指针和尾指针
ReDim State(0)
InputData '从文件中读入数据进行初始化
Head=0
Tail=0 ' 队列头指针和尾指针都指向队列头
Do While Head<=Tail '队列非空时循环
'根据具体问题确定一个结点怎样扩展
Temp= State(0) '取队列头的结点
If Extend Then '如果该结点可以扩展则产生一个新结点
If Not Repeat Then '如果新结点未曾在队列中出现过
Tail=Tail+1 ' 将新结点加入队列尾
ReDim Preserve State(Tail)
State(Tail) =Temp
State(Tail) .Sire=Head '记录父结点标识
If Found Then ' 如果新结点是目标结点
Tail=Tail+1 ' 将队列尾结点的父结点指针指向队列尾
ReDim Preserve State(Tail)
State(Tail) =Tail-1
PrintPath '输出路径
Exit Sub '退出程序
End If
End If
End If
Head=Head+1 '队列头的结点扩展完后出队，取下一结点扩展
Loop
End Sub
-
排序
排序的基本概念
所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来. 其确切定义如下:
输入: n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn.
输出: Ril,Ri2,…,Rin,使得Ki1 ≤ Ki2 ≤ … ≤ Kin.(或Ki1 ≥ Ki2 ≥ … ≥ Kin.)
二排序的分类
1. 按是否涉及数据的内、外存交换分为
内部排序: 内部排序(简称内排序),是带排序纪录存放在计算机内存中进行的排序过程. 细分又可为插入排序、选择排序、交换排序、归并排序和基数排序.
外部排序: 外部排序(简称外排序),是带排序纪录的数量很大,以至于内存一次不能容纳全部纪录,在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的存放顺序的排序方法.
2. 按策略划分内部排序方法
可以分为五类: 插入排序、选择排序、交换排序、归并排序和基数排序.
三排序算法的基本操作
1. 比较两个关键字的大小
2. 改变指向记录的指针或移动记录本身
注意: 第2种基本操作的实现依赖于待排序记录的存储方式.
四排序算法的性能评价
1. 评价排序算法好坏的标准
(1)执行时间和所需的辅助空间
(2)算法本身的复杂程度
2. 排序算法的空间复杂度
若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-Place Sort). 非就地排序一般要求的辅助空间为O(n).
3. 排序算法的时间开销
大多数排序算法的时间开销主要是关键字之间的比较和记录的移动. 有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态.
1 插入排序
1.1 直接插入排序
定义: 直接插入排序(Straight Insertion Sort)是一种最简单的排序方法. 它的基本操作是将一个记录插入到一个长度为m(假设)的有序表中,使之仍保持有序,从而得到一个新的长度为m＋1的有序表.
算法思路: 设有一组关键字{K1,K2,…,Kn},排序开始就认为K1是一个有序序列,让K2 插入上述表长为1的有序序列,使之成为一个表长为2的有序序列,然后让K3插入上述表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为 n-1的有序序列,得一个表长为n的有序序列.
算法时间复杂度: 此算法外循环n-1次,在一般情况下内循环平均比较次数的数量级为Ｏ(n),所以算法总时间复杂度为Ｏ(n^2).
直接插入排序的稳定性: 直接插入排序是稳定.的排序方法
具体算法:
/* 比较数据函数模板 */
template<class Type>
typedef bool __stdcall (*PFunCustomCompare)(const Type *Data_1, const Type *Data_2) ;
// InsertSort
template<class Type>
void InsertSort (TypeArray[], int n, PFunCustomComparepfCompare)
{
int i , j ;
for (i = 2 ; i <= n ; i ++) // 进行n-1趟插入
{
Array[0] = Array[i] ; // Array[0]为监视哨,也可作下边循环结束标志
j = i - 1 ;
while ( pfCompare(Array[j], Array[0]) )
{
Array[j+1] = Array[j] ;
j -- ;
}
Array[j+1] = Array[0] ; // 将r[0]即原r[i]记录内容,插到r[j]后一位置
}
}
// 或者:不需要监视哨
template<class Type>
void __stdcall InsertSort(TypeArray[], int Num, PFunCustomComparepfCompare)
{
for (int i = 1 ; i < Num ; i ++)
{
Typetemp = Array[i] ;
int j ;
for (j = i-1 ; j >= 0 && pfCompare(temp, Array[j]) ; j --)
Array[j+1] = Array[j] ;
Array[j+1] = temp ;
}
}
例1 设有一组关键字序列{55,22,44,11,33},这里n = 5,即有5个记录. 请将其按由小到大的顺序排序. 排序过程如下所示:
第一趟: [55] 22 44 11 33
第二趟: [22 55] 44 11 33
第三趟: [22 44 55] 11 33
第四趟: [11 22 44 55] 33
第五趟: [11 22 33 44 55]
1.2 折半插入排序
定义: 当直接插入排序进行到某一趟时,对于r[i].key来讲,前边i-1个记录已经按关键字有序.此时不用直接插入排序的方法,而改为折半查找,找出r[i].key应插的位置,然后插入. 这种方法就是折半插入排序(Binary Insertion Sort).
具体算法:
// BinarySort
template<class T>
void BinarySort(Ta[], int n)
{
int i , j , l , h , mid ;
for (i = 2 ; i <= n ; i ++)
{
a[0] = a[i] ;
l = 1 ; h = i-1 ; // 认为在a[1]和a[i-1]之间已经有序
while (l <= h) // 对有序表进行折半查找
{
mid = (l+h) / 2 ;
if(a[0].key < a[mid].key)
h = mid-1 ;
else
l = mid+1 ;
}
// 结果在mid位置
for(j = i-1 ; j >= mid ; j --)
a[j+1] = a[j] ;
a[mid] = a[0] ;
}
}
算法时间复杂度: 折半插入排序,关键字的比较次数由于采用了折半查找而减少,数量级为O (n*log(n)),但是元素移动次数仍为Ｏ(n^2). 故折半插入排序时间复杂度仍为Ｏ(n^2).
折半插入排序的稳定性: 折半插入排序方法是稳定.的
1.3 2路插入排序
1.4 表插入排序
