数学建模常用算法—组合算法

百年孤独

组合算法， 学过组合与数据结构的这些意识应该都有；也比较简单，是基础知识
组合算法概论(A Brief Introduction to Combinatorial Algorithm)
组合算法是算法分析学当中非常重要的一个分支，关于它在计算机科学的地位我就不敖述了，下面为大家整理了整个材料，算法是我收集的，只是分门别类简单介绍一下，然后把我的材料做了个整理，大家收藏吧，感觉挺有用的，费了我好长时间和精力呀，我现在准备考研了，没有太多时间发很多经典文章了，这片算是大部头了。 关于组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法等。下面我们着重谈谈几个有代表性的组合算法：
单纯形法：

这是一种线性规划算法，由G.B.Dantzig在1947年提出，后来由他和其他的学者又提出了单纯形法的变形和改进。这些被实践证明都是行之有效的，线性规划研究线性目标函数在一组线性等式与线性不等式约束下的极值问题。这本来是连续问题，Dantzig发现线性规划问题的可行解集（即满足约束条件的点的全体）是一个超多面体。如果它的最优解存在，那么这个最优解一定可以在超多面体的一个顶点取到。由于超多面体的顶点只有有限个，从而使线性规划成为一个组和优化问题。单纯形法是按照一定的规则，从可行解集的一个顶点转移到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。尽管单纯形法一直使用得很好，但是在最坏情况下它需要指数运行时间，从而使线性规划问题是否属于P类一度成为人们关心的问题。后来的椭球算法和投影算法都很好的解决了这个问题。
排序和检索：

这两部分应当是大家比较熟悉的，所谓排序，就是将给定的元素序列按照某种顺序关系重新排列成有序序列。例如将n个数组成的序列按照从小到大的顺序重新排列；将n个英语单词组成的的序列按照字典顺序重新排列。所谓检索，就是在给定的集合中查找某个特定的元素或是元素组。排序和检索已经成为计算机科学技术中最基本、使用最频繁的算法。下面我们专门谈谈排序算法（sorting algorithm）。
在讨论此种算法时，数据通常是指由若干记录组成的文件，每个记录包含一个或多个数据项，其中能够标志该记录的数据项称为键码。给定一文件的n个记录{R1,R2,…,Rn}及其相应的键码的集合{K1,K2,…,Kn}。所谓排序算法就是在数据处理中将文件中的记录按键码的一定次序要求排列起来的算法。若待排序的文件能够同时装入计算机的主存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，有一部分必须放在外存上，则称此类排序问题为外部排序。当待排序的文件中包含有一些相同键码的记录时，如果经过排序后这些相同的键码的记录的相对次序仍然保持不变，则相应的排序算法是稳定的，否则为不稳定的。如果排序算法设计成单处理机完成的，则此排序算法称为串行（或顺序）排序算法；如果排序算法时设计成多处理机实现的，则称为并行排序算法。
首先谈谈内部排序：内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。

使有序区中记录的数目增加一个或几个的操作称为一趟排序。 逐步扩大记录有序序列长度的方法大致有下列几类：
一．插入排序
假设在排序过程中，记录序列R[1..n]的状态为：
则一趟直接插入排序的基本思想为：将记录R
插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。
显然，完成这个“插入”需分三步进行：
1．查找R的插入位置j+1；
2．将R[j+1..i-1]中的记录后移一个位置；
3．将R复制到R[j+1]的位置上。
[I]直接插入排序
利用顺序查找实现“在R[1..i-1]中查找R的插入位置”的插入排序。
注意直接插入排序算法的三个要点：
1．从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；
R[0] = R; // 设置“哨兵”
for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找
return j+1; // 返回R的插入位置为j+1
2．对于在查找过程中找到的那些关键字不小于R.key的记录，可以在查找的同时实现向后移动；
for (j=i-1; R[0].key<R[j].key; --j);
R[j+1] = R[j]
3．i = 2，3，…, n, 实现整个序列的排序。
template<class Elem>
void InsertionSort ( Elem R[], int n)
{
// 对记录序列R[1..n]作直接插入排序。
for ( i=2; i<=n; ++i )
{
R[0] = R; // 复制为监视哨
for ( j=i-1; R[0].key < R[j].key; --j )
R[j+1] = R[j]; // 记录后移
R[j+1] = R[0]; // 插入到正确位置
}
} // InsertSort
时间分析：
实现排序的基本操作有两个：
（1）“比较”序列中两个关键字的大小；
（2）“移动”记录。
对于直接插入排序：
[II]折半插入排序
因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R的插入位置”，如此实现的插入排序为折半插入排序。其算法如下：
template<class Elem>

void BiInsertionSort (Elem R[]， int n)
{
// 对记录序列R[1..n]作折半插入排序。
for ( i=2; i<=L.length; ++i )
{
R[0] = R; // 将R暂存到R[0]
low = 1; high = i-1;
while (low<=high)
{ //在R[low..high]中折半查找插入的位置
m = (low+high)/2; // 折半
if (R[0].key < R[m].key))
high = m-1; // 插入点在低半区
else
low = m+1; // 插入点在高半区
}
for ( j=i-1; j>=high+1; --j )
R[j+1] = R[j]; // 记录后移
R[high+1] = R[0]; // 插入
}
} // BInsertSort
折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。
[III]表插入排序 为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。
算法描述如下：

template<class Elem>
void LInsertionSort (Elem SL[]， int n)
{
// 对记录序列SL[1..n]作表插入排序。
SL[0].key = MAXINT ;
SL[0].next = 1; SL[1].next = 0;
for ( i=2; i<=n; ++i )
for ( j=0, k = SL[0].next;
SL[k].key <= SL.key ; j = k, k = SL[k].next )
{ SL[j].next = i; SL.next = k; }
// 结点i插入在结点j和结点k之间
}// LinsertionSort
关于如在排序之后调整记录序列：
算法中使用了三个指针:
其中：p指示第i个记录的当前位置；
i指示第i个记录应在的位置；
q指示第i+1个记录的当前位置
template<class Elem>
void Arrange ( SLinkListType SL[ ], int n ) {
// 根据静态链表SL中各结点的指针值调整
// 记录位置，使得SL中记录按关键字非递减
// 有序顺序排列
p = SL[0].next;// p指示第一个记录的当前位置
for ( i=1; i<n; ++i ) {
// SL[1..i-1]中记录已按关键字有序排列，
// 第i个记录在SL中的当前位置应不小于i
while (p<i) p = SL[p].next;
// 找到第i个记录，并用p指示
// 其在SL中当前位置
q = SL[p].next; // q指示尚未调整的表尾
if ( p!= i ) {
SL[p]←→SL; // 交换记录，使第i个
// 记录到位
SL.next = p; // 指向被移走的记录，
// 使得以后可由while循环找回
}
p = q; // p指示尚未调整的表尾，
// 为找第i+1个记录作准备
}
} // Arrange
二． 交换排序

通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;
[I]起泡排序
假设在排序过程中，记录序列R[1..n]的状态为：n-i+1
则第i趟起泡插入排序的基本思想为：借助对无序序列中的记录进行“交换”的操作，将无序序列中关键字最大的记录“交换”到R[n-i+1]的位置上。
算法描述：

template <class Elem>
void BubbleSort(Elem R[], int n)
{
// i 指示无序序列中最后一个记录的位置
i = n;
while (i > 1) {
lastExchangeIndex = 1;
for (j = 1; j < i; j++) {
if (A[j+1] < A[j]) {
Swap(A[j],A[j+1]);
lastExchangeIndex = j;
} //if
} // for
i = lastExchangeIndex;
} // while
} // BubbleSort
起泡排序的结束条件为：最后一趟没有进行“交换”。
从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。我们可以设想，若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。
排序算法在组合算法中已写。其他的参阅数据结构即可。
floyd算法，matlab编写，十分简单
%floyd.m
%采用floyd算法计算图a中每对顶点最短路
%d是矩离矩阵
%r是路由矩阵
function [d,r]=floyd(a)
n=size(a,1);
d=a;
for i=1:n
for j=1:n
r(i,j)=j;
end
end
r
for k=1:n
for i=1:n
for j=1:n
if d(i,k)+d(k,j)<d(i,j)
d(i,j)=d(i,k)+d(k,j);
r(i,j)=r(i,k)
end
end
end
k
d
r
end搜索算法
一、回溯算法 　回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构，其相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。具体的算法描述如下： [非递归算法]
＜Type＞ 　Node(节点类型)＝Record
　Situtation:TSituation（当前节点状态）;
　Way-NInteger（已使用过的扩展规则的数目）;
End
＜Var＞
　List(回溯表):Array[1..Max(最大深度)] of Node;
　pos(当前扩展节点编号):Integer;
＜Init＞
　List＜-0;
　pos＜-1;
　List[1].Situation＜-初始状态;
＜Main Program＞
　While (pos＞0(有路可走)) and ([未达到目标]) do
　Begin
　　If pos＞=Max then (数据溢出,跳出主程序);
　　　List[pos].Way-N=List[pos].Way-No+1;
　　If (List[pos].Way-NO＜=TotalExpendMethod) then (如果还有没用过的扩展规则)
　　Begin
　　　If (可以使用当前扩展规则) then
　　　Begin
　　　　(用第way条规则扩展当前节点)
　　　　List[pos+1].Situation:=ExpendNode(List[pos].Situation,List[pos].Way-NO);


　　　　List[pos+1].Way-N=0;
　　　　pos:=pos+1;
　　　End-If;
　　End-If
　　Else Begin
　　　pos:=pos-1;
　　End-Else
　End-While;
　　[递归算法]

Procedure BackTrack(Situation:TSituation;deepth:Integer);

Var I :Integer;
Begin
　If deepth＞Max then (空间达到极限,跳出本过程);
　If Situation=Target then (找到目标);
　For I:=1 to TotalExpendMethod do
　　Begin
　　　BackTrack(ExpendNode(Situation,I),deepth+1);
　End-For;
End;
　范例：一个M*M的棋盘上某一点上有一个马，要求寻找一条从这一点出发不重复的跳完棋盘上所有的点的路线。

　评价：回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。

　　二、深度搜索与广度搜索

深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构.

　[广度搜索]

＜Type＞

　Node(节点类型)＝Record
　Situtation:TSituation（当前节点状态）;
　Level:Integer(当前节点深度);
　Last :Integer(父节点);
End
＜Var＞
　List(节点表):Array[1..Max(最多节点数)] of Node(节点类型);
　open(总节点数):Integer;
　 close(待扩展节点编号):Integer;
　New-S:TSituation;(新节点)
＜Init＞
　List＜-0;
　open＜-1;
　close＜-0;
　List[1].Situation＜- 初始状态;
　List[1].Level:=1;
　List[1].Last:=0;
＜Main Program＞
　While (close＜open(还有未扩展节点)) and
　　(open＜Max(空间未用完)) and
　　(未找到目标节点) do
　Begin
　　 close:=close+1;
　　For I:=1 to TotalExpendMethod do（扩展一层子节点）
　　Begin
　　　New-S:=ExpendNode(List[close].Situation,I);
　　　If Not (New-S in List) then
　　　　(扩展出的节点从未出现过)
　　　Begin
　　　　open:=open+1;
　　　　List[open].Situation:=New-S;
　　　　List[open].Level:=List[close].Level+1;
　　　　List[open].Last:=close;
　　　End-If
　　End-For;
　End-While;


　　[深度搜索]
＜Var＞

　Open:Array[1..Max] of Node;(待扩展节点表)
　Close:Array[1..Max] of Node;(已扩展节点表)
　openL,closeL:Integer;(表的长度)
　New-S:Tsituation;(新状态)
＜Init＞
　Open＜-0; Close＜-0;
　OpenL＜-1;CloseL＜-0;
　Open[1].Situation＜- 初始状态;
　Open[1].Level＜-1;
　Open[1].Last＜-0;
＜Main Program＞
　While (openL＞0) and (closeL＜Max) and (openL＜Max) do
　Begin
　　closeL:=closeL+1;
　　Close[closeL]:=Open[openL];
　　openL:=openL-1;
　　For I:=1 to TotalExpendMethod do（扩展一层子节点）
　　Begin
　　　New-S:=ExpendNode(Close[closeL].Situation,I);
　　　If Not (New-S in List) then
　　　(扩展出的节点从未出现过)
　　　Begin
　　　　openL:=openL+1;
　　　　Open[openL].Situation:=New-S;
　　　　Open[openL].Level:=Close[closeL].Level+1;
　　　　Open[openL].Last:=closeL;
　　　End-If
　　End-For;
End;
　范例：迷宫问题，求解最短路径和可通路径。

评价：广度搜索是求解最优解的一种较好的方法，在后面将会对其进行进一步的优化。而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。

第二部分　搜索算法的优化

一、双向广度搜索
广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。
范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。
　问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点
所连接的两条路径所拼成的路径就是最优解。

百年孤独

对广度搜索算法的改进：

　1、添加一张节点表，作为反向扩展表。

　2、在while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for循环。
　3、在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时与之相同。
　对双向广度搜索算法的改进：

　　略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。

　二、分支定界
　分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。
范例：在一个商店中购物，设第I种商品的价格为Ci。但商店提供一种折扣，即给出一组商品的组合，如果一次性购买了这一组商品，则可以享受较优惠的价格。现在给出一张购买清单和商店所提供的折扣清单，要求利用这些折扣，使所付款最少。
问题分析：显然，折扣使用的顺序与最终结果无关，所以可以先将所有的折扣按折扣率从大到小排序，然后采用回溯法的控制结构，对每个折扣从其最大可能使用次数向零递减搜索，设A为以打完折扣后优惠的价格，C为当前未打折扣的商品零售价之和，则其预期值为A+a*C，其中a为下一个折扣的折扣率。如当前已是最后一个折扣，则a=1。

　　对回溯算法的改进：

　1、添加一个全局变量BestAnswer，记录当前最优解。

2、在每次生成一个节点时，计算其预期值，并与BestAnswer比较。如果不好，则调用回溯过程。