Astart算法
初识A*算法
写这篇文章的初衷是应一个网友的要求，当然我也发现现在有关人工智能的中文站点实在太少，我在这里抛砖引玉，希望大家都来热心的参与。
还是说正题，我先拿A*算法开刀，是因为A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。
A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，我看还是先说说何谓启发式算法。
一、何谓启发式搜索算法
在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果（好象并不通俗哦）。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。
常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。
前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
f(n) = g(n) + h(n)
其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n)>>g(n)时，可以省略g(n),而提高效率。这些就深了，不懂也不影响啦！我们继续看看何谓A*算法。
二、初识A*算法
启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。哈！你懂了吗？肯定没懂！接着看！
举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。
再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。可难了，这就看你的了！
好了我的话也说得差不多了，我想你肯定是一头的雾水了，其实这是写给懂A*算法的同志看的。哈哈！你还是找一本人工智能的书仔细看看吧！我这几百字是不足以将A*算法讲清楚的。只是起到抛砖引玉的作用，希望大家热情参与嘛！
预知A*算法的应用，请看姊妹篇《深入A*算法》。
Sunway
深入A*算法
一、前言
在这里我将对A*算法的实际应用进行一定的探讨，并且举一个有关A*算法在最短路径搜索的例子。值得注意的是这里并不对A*的基本的概念作介绍，如果你还对A*算法不清楚的话，请看姊妹篇《初识A*算法》。
这里所举的例子是参考AMIT主页中的一个源程序，使用这个源程序时，应该遵守一定的公约。
二、A*算法的程序编写原理
我在《初识A*算法》中说过，A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。
如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）
搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。具体搜索过程如下：
1）初始状态：
OPEN=[A5]；CLOSED=[]；
2）估算A5，取得搜有子节点，并放入OPEN表中；
OPEN=[B4，C4，D6]；CLOSED=[A5]
3）估算B4，取得搜有子节点，并放入OPEN表中；
OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]
4）估算C4；取得搜有子节点，并放入OPEN表中；
OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]
5）估算H3，取得搜有子节点，并放入OPEN表中；
OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=[H3，C4，B4，A5] 6）估算O2，取得搜有子节点，并放入OPEN表中；
OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5] 7）估算P3，已得到解；
看了具体的过程，再看看伪程序吧。算法的伪程序如下：
Best_First_Search()
{
Open = [起始节点];
Closed = [];
while (Open表非空)
{
从Open中取得一个节点X，并从OPEN表中删除。
if (X是目标节点)
{
求得路径PATH；
返回路径PATH；
}
for (每一个X的子节点Y)
{
if (Y不在OPEN表和CLOSE表中)
{
求Y的估价值；
并将Y插入OPEN表中；
}
//还没有排序
else if (Y在OPEN表中)
{
if (Y的估价值小于OPEN表的估价值)
更新OPEN表中的估价值；
}
else //Y在CLOSE表中
{
if (Y的估价值小于CLOSE表的估价值)
{
更新CLOSE表中的估价值；
从CLOSE表中移出节点，并放入OPEN表中；
}
}
将X节点插入CLOSE表中；
按照估价值将OPEN表中的节点排序；
}//end for
}//end while
}//end func
啊！伪程序出来了，写一个源程序应该不是问题了，依葫芦画瓢就可以。A*算法的程序与此是一样的，只要注意估价函数中的g(n)的h(n)约束条件就可以了。不清楚的可以看看《初识A*算法》。好了，我们可以进入另一个重要的话题，用A*算法实现最短路径的搜索。在此之前你最好认真的理解前面的算法。不清楚可以找我。我的Email在文章尾。
三、用A*算法实现最短路径的搜索
在游戏设计中，经常要涉及到最短路径的搜索，现在一个比较好的方法就是用A*算法进行设计。他的好处我们就不用管了，反正就是好！^_*
注意下面所说的都是以ClassAstar这个程序为蓝本，你可以在这里下载这个程序。这个程序是一个完整的工程。里面带了一个EXE文件。可以先看看。
先复习一下，A*算法的核心是估价函数f(n)，它包括g(n)和h(n)两部分。g(n)是已经走过的代价，h(n)是n到目标的估计代价。在这个例子中g(n)表示在状态空间从起始节点到n节点的深度，h(n)表示n节点所在地图的位置到目标位置的直线距离。啊！一个是状态空间，一个是实际的地图，不要搞错了。再详细点说，有一个物体A，在地图上的坐标是(xa,ya)，A所要到达的目标b的坐标是(xb,yb)。则开始搜索时，设置一个起始节点1，生成八个子节点2- 9 因为有八个方向。如图：
仔细看看节点1、9、17的g(n)和h(n)是怎么计算的。现在应该知道了下面程序中
的f(n)是如何计算的吧。开始讲解源程序了。其实这个程序是一个很典型的教科书似的程序，也就是说只要你看懂了上面的伪程序，这个程序是十分容易理解的。不过他和上面的伪程序有一些的不同，我在后面会提出来。
先看搜索主函数：
void AstarPathfinder::FindPath(int sx, int sy, int dx, int dy)
{
NODE *Node, *BestNode;
int TileNumDest;
//得到目标位置，作判断用
TileNumDest = TileNum(sx, sy);
//生成Open和Closed表
OPEN = ( NODE* )calloc(1,sizeof( NODE ));
CLOSED=( NODE* )calloc(1,sizeof( NODE ));
//生成起始节点，并放入Open表中
Node=( NODE* )calloc(1,sizeof( NODE ));
Node->g = 0;
//这是计算h值
// should really use sqrt().
Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy);
//这是计算f值，即估价值
Node->f = Node->g+Node->h;
Node->NodeNum = TileNum(dx, dy);
Node->x = dx; Node->y = dy;
// make Open List point to first node
OPEN->NextNode=Node;
for (;;)
{
//从Open表中取得一个估价值最好的节点
BestNode=ReturnBestNode();
//如果该节点是目标节点就退出
// if we've found the end, break and finish break;
if (BestNode->NodeNum == TileNumDest)
//否则生成子节点
GenerateSuccessors(BestNode,sx,sy);
}
PATH = BestNode;
}
再看看生成子节点函数：
void AstarPathfinder::GenerateSuccessors(NODE *BestNode, int dx, int dy)
{
int x, y;
//哦！依次生成八个方向的子节点，简单！
// Upper-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy);
// Upper
if ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy);
// Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy);
// Lower
if ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy);
// Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
}
看看最重要的函数：
void AstarPathfinder::GenerateSucc(NODE *BestNode,int x, int y, int dx, int dy) {
int g, TileNumS, c = 0;
NODE *Old, *Successor;
//计算子节点的g 值
// g(Successor)=g(BestNode)+cost of getting from BestNode to Successor
g = BestNode->g+1;
// identification purposes
TileNumS = TileNum(x,y);
//子节点再Open表中吗？
// if equal to NULL then not in OPEN list, else it returns the Node in Old
if ( (Old=CheckOPEN(TileNumS)) != NULL )
{
//若在
for( c = 0; c < 8; c++)
// Add Old to the list of BestNode's Children (or Successors).
if( BestNode->Child[c] == NULL )
break;
BestNode->Child[c] = Old;
//比较Open表中的估价值和当前的估价值（只要比较g值就可以了）// if our new g value is < Old's then reset Old's parent to point to BestNode if ( g < Old->g )
{
//当前的估价值小就更新Open表中的估价值
Old->Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
}
}
else
//在Closed表中吗？
// if equal to NULL then not in OPEN list, else it returns the Node in Old
if ( (Old=CheckCLOSED(TileNumS)) != NULL )
{
//若在
for( c = 0; c< 8; c++)
// Add Old to the list of BestNode's Children (or Successors).
if ( BestNode->Child[c] == NULL )
break;
BestNode->Child[c] = Old;
//比较Closed表中的估价值和当前的估价值（只要比较g值就可以了）// if our new g value is < Old's then reset Old's parent to point to BestNode if ( g < Old->g )
{
//当前的估价值小就更新Closed表中的估价值
Old->Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
//再依次更新Old的所有子节点的估价值
// Since we changed the g value of Old, we need
// to propagate this new value downwards, i.e.
// do a Depth-First traversal of the tree!
PropagateDown(Old);
}
}
//不在Open表中也不在Close表中
else
{
//生成新的节点
Successor = ( NODE* )calloc(1,sizeof( NODE ));
Successor->Parent = BestNode;
Successor->g = g;
// should do sqrt(), but since we don't really
Successor->h = (x-dx)*(x-dx) + (y-dy)*(y-dy);
// care about the distance but just which branch looks
Successor->f = g+Successor->h;
// better this should suffice. Anyayz it's faster.
Successor->x = x;
Successor->y = y;
Successor->NodeNum = TileNumS;
//再插入Open表中，同时排序。
// Insert Successor on OPEN list wrt f
Insert(Successor);
for( c =0; c < 8; c++)
// Add Old to the list of BestNode's Children (or Successors).
if ( BestNode->Child[c] == NULL )
break;
BestNode->Child[c] = Successor;
}
}
哈哈！A*算法我懂了！当然，我希望你有这样的感觉！不过我还要再说几句。仔细看看这个程序，你会发现，这个程序和我前面说的伪程序有一些不同，在GenerateSucc 函数中，当子节点在Closed表中时，没有将子节点从Closed表中删除并放入Open表中。而是直接的重新的计算该节点的所有子节点的估价值（用PropagateDown函数）。这样可以快一些！另当子节点在Open表和Closed表中时，重新的计算估价值后，没有重新的对Open 表中的节点排序，我有些想不通，为什么不排呢？:-(，会不会是一个小小的BUG。你知道告诉我好吗？
好了！主要的内容都讲完了，还是完整仔细的看看源程序吧！希望我所的对你有一点帮助，一点点也可以。如果你对文章中的观点有异议或有更好的解释都告诉我。我的email 在文章最后！
https://www.wendangku.net/doc/8b11131088.html,/Program/Abstract/a8first_2.htm
课程设计报告-贪心算法：任务调度问题
数据结构课程设计报告 贪心算法：任务调度问题的设计 专业 学生姓名 班级 学 号 指导教师 完成日期
贪心算法：任务调度问题的设计 目录 1设计内容 (1) 2）输入要求 (1) 3）输出要求 (1) 2设计分析 (1) 2.1排序（将数组按照从小到大排序）的设计 (1) 2.2多个测试案例的处理方法的设计 (2) 2.3 for循环设计 (2) 2.4系统流程图 (2) 3设计实践 (2) 3.1希尔排序模块设计 (2) 3.2 多个测试案例的处理方法的模块设计 (3) 4测试方法 (4) 5程序运行效果 (4) 6设计心得 (6) 7附录 (6)
数据结构课程设计报告（2017） 贪心算法：任务调度问题的设计 1设计内容 有n项任务，要求按顺序执行，并设定第I项任务需要t[i]单位时间。如果任务完成的顺序为1，2，…，n，那么第I项任务完成的时间为c[i]=t[1]+…+t[i]，平均完成时间（ACT）即为（c[1]+..+c[n]）/n。本题要求找到最小的任务平均完成时间。 2）输入要求 输入数据中包含n个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n各非负整数t（t≤1000000000），每个数之间用空格相互隔开，以一个负数来结束输入。 3）输出要求 对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0，则对应输出一个空行。 2 设计分析 这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来安排的。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。在许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最有子结构性质。所谓贪心选择性只是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心算法可行的第一基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。当一个问题的最优解包含着它的子问题最优解时，称此问题具有最优子结构性质，这个性质是该问题可用贪心算法求解的一个关键特征。 2.1排序（将数组按照从小到大排序）的设计 排序的方法有很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都可以使用。这里采用希尔排序来实现。 它的基本思想是：先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=n》1），把数组的全部元素分成d1个组。所有距
圆锥曲线齐次式与点乘双根法教学内容
一，圆锥曲线齐次式与斜率之积（和）为定值 例1：12,Q Q 为椭圆22 2212x y b b +=上两个动点，且12OQ OQ ⊥，过原点O 作直线12Q Q 的垂 线OD ，求D 的轨迹方程. 解法一（常规方法）：设111222(,),(,)Q x y Q x y ，00(,)D x y ,设直线12Q Q 方程为y kx m =+， 联立22 2212y kx m x y b b =+???+=??化简可得: 22222222(2)42()0b k b x kmb x b m b +++-=，所以 22222221212222222 2()(2),22b m b b m b k x x y y b k b b k b +-==++ 因为12OQ OQ ⊥所以 222222222222 1212222222222()(2)2()2=0222121b m b b m b k m b m b k x x y y b k b b k b k k +---+=+=+++++ 22232(1)m b k ∴=+*L 又因为直线12Q Q 方程等价于为0000()x y y x x y -=--，即2 00000 x x y x y y y =-++对比于y kx m =+，则00200 x k y x y m y ? -=????+=??代入*中，化简可得：22 20023x y b +=.
解法二（齐次式）： 设直线12Q Q 方程为1mx ny +=，联立22 22222211 11022mx ny mx ny x y x y b b b b +=+=???? ???+=+-=???? 222 22()02x y mx ny b b +-+=化简可得:22222222202x y m x n y mnxy b b +---= 整理成关于,x y ,x y 的齐次式：2 2 2 22 2 2 (22)(12)40b n y m b x mnb xy -+--=，进而两边同时除以2 x ，则 222 2 2 2 22 1222 12(22)412022m b b n k mnb k m b k k b n ---+-=?=- 因为12OQ OQ ⊥12OQ OQ ⊥所以121k k =-， 22 2212122m b b n -=-- 22232()b m n ∴=+*L 又因为直线12Q Q 方程等价于为0000()x y y x x y -=--，即2 00000 x x y x y y y =-++对比于1mx ny +=，则0 2200022 00 x m x y y n x y ?=?+?? ?=?+?代入*中，化简可得：22 20023x y b +=. 例2：已知椭圆2 214 x y +=，设直线l 不经过点(0,1)P 的直线交于,A B 两点，若直线,PA PB 的斜率之和为1-，证明：直线l 恒过定点.
基于两点乘积及全波傅里叶算法的应用
2.两点乘积算法： 程序： %两点乘积算法,输入正弦波，取得电气角度相隔pi/2的采样时刻的数据值，计算出正弦量的有效值。 clear; N=12; %每周期采12个点 for n=0:48; t=0.02*n/N; y=sin(2*pi*n/N); %输入正弦波量y=sin(w*t) s(1,n+1)=y; %将y采样所得的值赋值给s if n>3 a=s(1,n-3); %输出相差0.5*pi的两点采样值 b=s(1,n); Ym=sqrt(a^2+b^2); Y=Ym/1.414; %输出正弦量的有效值 subplot(211) %绘制t-Y，即正弦量有效值与时间关系的图形 plot(t,Y,'-bo'); pause(0.005); xlim([-0.01,0.08]); ylim([0,1]); hold on end subplot(212); %绘制t-y，输入与时间关系的即图形 plot(t,y,'-bo'); pause(0.005); hold on end
基于两点乘积及全波傅里叶算法的应用 利用全波傅里叶算法和两点乘积算法计算 1.全波傅里叶算法： 程序： %全波傅里叶算法 clear N=24; %每周期采24个点 for n=0:96; t=0.02*n/N; y=sin(2*pi*n/N); %输入正弦波量y=sin(w*t) x1(1,n+1)=y; %将y采样所得的值赋值给x1 if n>24 X1s=0; X1c=0; for k=(n-24):(n-1) a1=x1(1,k); a2=a1*sin(2*k*pi/N); X1s=a2+X1s; end for j=(n-24):(n-1) b1=x1(1,j); b2=b1*cos(2*j*pi/N); X1c=b2+X1c; end X1s=(2/N)*X1s; %输出正弦系数 x1(2,n+1)=X1s; X1c=(2/N)*X1c; %输出余弦系数 x1(3,n+1)=X1c; X=sqrt(0.5*(X1s^2+X1c^2)); %求出基波分量有效值 x1(4,n+1)=X; end if n<24 X=0; end subplot(212); %绘制t-X，即基波分量有效值与时间关系的图形 plot(t,X,'-bo'); xlim([0,0.1]); ylim([0,1]); pause(0.0005); hold on subplot(211); %绘制t-y，即输入与时间关系的图形 plot(t,y,'-ok');
0018算法笔记——【动态规划】流水作业调度问题与Johnson法则
1、问题描述： n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 2、问题分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N={1，2，…，n}。S是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 设π是所给n个流水作业的一个最优调度，它所需的加工时间为 aπ(1)+T’。其中T’是在机器M2的等待时间为bπ(1)时，安排作业 π(2)，…，π(n)所需的时间。 记S=N-{π(1)}，则有T’=T(S,bπ(1))。 证明：事实上，由T的定义知T’>=T(S,bπ(1))。若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。
则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为 aπ(1)+T(S,bπ(1)) + = y 圆锥曲线齐次式与点乘双根法 一，圆锥曲线齐次式与斜率之积（和）为定值 x 2 y 2 例 1：Q 1 , Q 2 为椭圆 2b 2 + b 2 线OD ，求 D 的轨迹方程. = 1上两个动点，且OQ 1 ⊥ OQ 2 ，过原点O 作直线Q 1Q 2 的垂 解法一（常规方法）：设Q 1 (x 1 , y 1 ),Q 2 (x 2 , y 2 ) ， D (x 0 , y 0 ) ,设直线Q 1Q 2 方程为 y = kx + m ， ? y = kx + m ? 联立? x 2 ?? 2b 2 y 2 b 2 1 化简可得: (2b 2k 2 + b 2 )x 2 + 4kmb 2 x + 2b 2 (m 2 - b 2 ) = 0 ，所以 x 1x 2 = 2b 2 (m 2 + b 2 ) 2b 2k 2 + b 2 , y 1 y 2 = b 2 (m 2 - 2b 2k 2 ) 2b 2k 2 + b 2 因为OQ 1 ⊥ OQ 2 所以 2b 2 (m 2 + b 2 ) b 2 (m 2 - 2b 2k 2 ) 2(m 2 - b 2 ) m 2 - 2b 2k 2 x 1x 2 + y 1 y 2 = 2b 2k 2 + b 2 + 2b 2k 2 + b 2 = 2k 2 +1 + 2k 2 +1 =0 ∴3m 2 = 2b 2 (1+ k 2 ) * 又因为直线 Q Q 方程等价于为 y - y = - x 0 (x - x x x 2 ) ， 即 y = - 0 x + 0 + y 对比于 1 2 0 y 0 y 0 向量- 向量叉乘向量点乘 2010年07月28日星期三14:33 向量（Vector） 在几乎所有的几何问题中，向量（有时也称矢量）是一个基本点。向量的定义包含方向和一个数（长度）。在二维空间中，一个向量可以用一对x和y来表示。例如由点（1,3）到（5,1的向量可以用(4,-2）来表示。这里大家要特别注意，我这样说并不代表向量定义了起点和终点。向量仅仅定义方向和长度。 向量加法 向量也支持各种数学运算。最简单的就是加法。我们可以对两个向量相加，得到的仍然是一个向量。我们有： V1（x1, y1）+V2（x2, y2）=V3(x1+x2, y1+y2) 下图表示了四个向量相加。注意就像普通的加法一样,相加的次序对结果没有影响（满足交换律），减法也是一样的。 点乘（Dot Product） 如果说加法是凭直觉就可以知道的，另外还有一些运算就不是那么明显的，比如点乘和叉乘。点乘比较简单，是相应元素的乘积的和： V1( x1, y1) V2(x2, y2) = x1*x2 + y1*y2 注意结果不是一个向量，而是一个标量（Scalar）。点乘有什么用呢，我们有： A B = |A||B|Cos(θ) θ是向量A和向量B见的夹角。这里|A|我们称为向量A的模(norm)，也就是A的长度，在二维空间中就是|A| = sqrt(x2+y2)。这样我们就和容易计算两条线的夹角：Cos(θ) = A B /(|A||B|) 当然你知道要用一下反余弦函数acos()啦。（回忆一下cos(90)=0 和cos(0) = 1还是有好处的，希望你没有忘记。）这可以告诉我们如果点乘的结果，简称点积，为0的话就表示这两个向量垂直。当两向量平行时，点积有最大值 另外，点乘运算不仅限于2维空间，他可以推广到任意维空间。（译注：不少人对量子力学中的高维空间无法理解，其实如果你不要试图在视觉上想象高维空间，而仅仅把它看成三维空间在数学上的推广，那么就好理解了） 数据结构课程设计报告 实验一：计算器 设计要求 1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。 2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。 具体事例如下： 3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。 具体事例如下： 知识点：堆栈、队列 实际输入输出情况： 正确的表达式 对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决问题的整体思路： 将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。 解决本问题所需要的数据结构与算法： 用到的数据结构是堆栈。主要算法描述如下： A．将中缀表达式转换为后缀表达式： 1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况： 1）数字 2）小数点 3）合法操作符+ - * / % 4）左括号 5）右括号 6）非法字符 2. 首先为操作符初始化一个map 算法之多机调度问题 用贪心法解决多机调度问题 （1）问题的描述 设有n个独立的作业{1, 2,…, n}，由m台相同的机器{M1, M2,…, Mm}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 （2）算法设计思想 解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。 （3）数据及解题过程 设7个独立作业{1, 2, 3, 4, 5, 6, 7}由3台机器{M1, M2, M3}加工处理，各作业所需的处理时间分别为{2, 14, 4, 16, 6, 5, 3}。贪心法产生的作业调度如下： （4）程序使用C++运行测试 （5）代码如下： #include for (i=1;i<=n;i++) { for (j=1;j<=n-i;j++) { if (t[j] 电子设计工程 Electronic Design Engineering 第24卷Vol.24第23期No.232016年12月Dec.2016 收稿日期：2016-04-02 稿件编号：201604020 基金项目：国家自然科学基金项目（61379026）；陕西省教育厅项目（2013JK1124）作者简介：李竹林（1972—），女，陕西佳县人，博士，副教授。研究方向：数字图像处理。 图像分割是图像识别、跟踪、压缩、分析、理解以及立体匹配等处理的基础，是将图像表示为物理上有意义的连通区域的集合[1-2]。从第1个分割算法提出的1962年到2011年的半个世纪中，有关图像分割方法研究及的综述性的文献已达 7.7万多篇[3-4]，但尚没有一种适合所有图像的通用算法，同时 当给定一个实际应用后选择合适的分割算法仍是一个很麻烦的问题，且没有标准的方法[5-7]，所以图像分割算法一直是研究的热点和难点[8]。在实际的分割过程中，是将图像中有意义的特征部分提取出来，例如图像中的边缘、区域等。其中边缘特征是图像最基本的特征，经典的边缘检测方法有[9-10]：基于灰度直方图检测法、基于梯度检测法、Laplacian 检测法及 Canny 检测法。基于边缘的图像分割适用于不同区域之间的 边缘灰度值变化较大的情况，但难点是当图像的目标与背景对比度不大，灰度区域交叉又较多时，边缘检测的精度很难保证，不利于基于边缘检测的图像分割，而且边缘检测中的抗噪性与检测精度之间的矛盾也因此而变得更为尖锐 [11-12] 。 文中针对上述问题，提出了一种基于分段点乘运算的灰度图像分割算法，使得图像中暗的部分更暗、亮的部分更亮，提高了目标和背景的对比度，进而改善图像的分割效果。 1噪声去除 图像噪声是在图像拍摄和传输的过程中由于信号被干 扰而引起的，是很难避免的。在一幅灰度图像中，将图像信号按照二维亮度f （x ，y ）分布，则噪声可认为是对亮度的干扰，用n （x ，y ）来表示。噪声是随机的，估计它的概率密度分布函数是有一定的难度或根本进行。因此，往往用均值、方差、等相关函数来描述噪声统计特征。一般，用噪声平方的均值E [n 2（x ，y ）]来描述噪声的总功率，用噪声的方差E {（n （x ，y ）-E [n （x ，y ）]）2}描述噪声的交流功率，用噪声均值的平方{E [n （x ， y ）]}2描述噪声的直流功率[13]。 常见的噪声有：高斯噪声、椒盐噪声、均匀分布噪声、指数分布噪声等，其中高斯噪声与椒盐噪声在实际图像中比较常见[13]。 1.1高斯噪声 高斯噪声又被称作是正态噪声，其概率密度函数为式 （1），式中，z 是图像灰度值，μ是z 的期望值，σ是z 的标准差。 P （z ）= 12π姨σ e -（z-μ）2 /2σ2 （1） 一种基于滤波的分段点乘图像分割算法 李竹林，王静 （延安大学计算机学院，陕西延安716000） 摘要：图像分割的对图像识别、分析与理解具有重要的作用。文中针对含有噪声的图像，提出了一种分段点乘的图像分割算法。具体方法是首先根据灰度直方图确定图像的多灰度区域，然后实施分段点乘运算，使得图像中暗的部分更暗、亮的部分更亮，提高了目标和背景的对比度，突显了目标。最后用Canny 算子进行边缘线分割，得到了较好的分割效果。该方法思路清晰，容易实现，具有较强的实用价值。关键词：点乘运算；滤波；图像分割；Canny 算子中图分类号：TN713 文献标识码：A 文章编号：1674－6236（2016）23-0001-03 An algorithm of piecewise point multiplication for image segmentation based on filtering LI Zhu 鄄lin ，WANG Jing （Institute of Computer Science ，Yan ’an University ，Yan ’an 716000，China ） Abstract:Image segmentation is important to image recognition ，analysis and understanding.For noisy image ，the paper presents a subsection point multiplication method for gray image.Firstly ，the multi gray regions of the image are determined according to the gray level histogram.Then the piecewise point multiplications are implemented ，the piecewise point multiplication make the dark gray value becoming darker and the bright gray value becoming brighter ，improve the contrast between the target and the background ，and highlight the target.At last ，the Canny operator is used to segment the edge line and a good result is obtained.The method is clear and easy to implement ，and has a strong practical value.Key words:point multiplication ；filtering ；image segmentation ；canny operator －1－ 万方数据 课程设计 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期： 目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13) 摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。 一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 设计过程在硬件与软件方面进行同步设计。硬件方面从功能考虑，首先选择内部存储资源丰富的AT89C51单片机，输入采用4×4矩阵键盘。显示采用3位7段共阴极LED动态显示。软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C 语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C51芯片、汇编语言、数码管、加减乘除 目录 摘要 (01) 引言 (01) 一、设计任务和要求............................. 1、1 设计要求 1、2 性能指标 1、3 设计方案的确定 二、单片机简要原理............................. 2、1 AT89C51的介绍 2、2 单片机最小系统 2、3 七段共阳极数码管 三、硬件设计................................... 3、1 键盘电路的设计 3、2 显示电路的设计 四、软件设计................................... 4、1 系统设计 4、2 显示电路的设计 五、调试与仿真................................. 5、1 Keil C51单片机软件开发系统 5、2 proteus的操作 六、心得体会.................................... 参考文献......................................... 附录1 系统硬件电路图............................ 附录2 程序清单.................................. 一种改进的关键工序算法 刘智勇 徐昕 江苏科技大学经济管理学院，江苏 镇江 212003 摘要：针对max ///n m p F 问题，改进了关键工序法法，该算法同时注重关键工件与关键工序，通过对关键工件与非关键工件在关键工序前后的加工时间计算、比较来获得各工件加工的先后顺序，缩短最长流程时间。并将该启发式算法与关键工序法进行了对比分析，最后利用仿真的方法来验证所提出的方法的可行性。 关键词：Flow-shop 关键工件 关键工序 启发式算法 最长流程时间 0引言 Flow-shop 调度问题（flow shop scheduling problem,FSP ）是许多实际流水线生产调度问题的简化模型，它无论是在离散制造工业还是在流程工业中都具有广泛的应用，因此其研究具有重要的理论意义和工程价值。n/m/p/F max 问题是Flow-shop 调度问题中的一种特殊情况，即所有工件在各台机器上的加工顺序都相同，也称流水作业排列排序问题或同顺序排序问题。其求解方法有精确方法 [1]（分支定界法、穷举法等）、智能搜索法 [2,3,4]（神经网络法、遗传算法、蚁群算法等）、启发式算法[4,5,6,7]（Palmer 算法、C-D-S 法、关键工序法、最小排序系数法等）等等。由于Flow-shop 调度问题一般都属于NP 难题(nondeterministic polynomial)。精确方法只能求解小规模问题，对于大规模问题几乎被认为是无效算法，智能搜索法在求解上虽比启发式算法更接近最有解，但由于设计针对具体问题的智能搜索法对于许多人来说比较困难，特别是对于实际工程人员更是如此。所以启发式算法仍是用的很多的方法。主要的启发式算法有Palmer 算法、关键工序法和最小排序系数法等。其中，关键工序法贯穿着当前先进的管理思想，能够很好的对现实情况进行解释和分析。然而关键工序法所求的可行解很可能与最优解相差甚远，鉴于此，本文对其进行了改进。 1 max ///n m p F 问题描述 max ///n m p F 问题可以描述为：有n 个工件在m 台机器上加工，各工件有完全相 同的工艺路线，每一台机器上加工工件的先后顺序也完全相同；一个工件不能同时在不同的机器上加工；每台机器同时只能加工一个工件；各工件在加工完后立即送下一道工序；工件在机器上开始加工，必须一直进行到该工序完工，中途不允许停下来插入其它工件；所有工件在0时刻已准备就绪，机器调整时间包括在加工时间内； “齐次式”法解圆锥曲线斜率有关的顶点定值问题 定点问题是常见的出题形式，化解这类问题的关键就是引进变的参数表示直线方程、数量积、比例关系等，根据等式的恒成立、数式变换等寻找不受参数影响的量。直线过定点问题通法，是设出直线方程，通过韦达定理和已知条件找出k 和m 的一次函数关系式，代入直线方程即可。技巧在于：设哪一条直线如何转化题目条件圆锥曲线是一种很有趣的载体，自身存在很多性质，这些性质往往成为出题老师的参考。如果大家能够熟识这些常见的结论，那么解题必然会事半功倍。下面总结圆锥曲线中几种常见的几种定点模型： 例题、（07山东） 已知椭圆C ：13 42 2=+y x 若与x 轴不垂直的直线l 与曲线C 相交于A ，B 两点（A ，B 不是左右顶点），且以AB 为直径的圆过椭圆C 的右顶点。求证：直线l 过定点，并求出该定点的坐标。 解法一（常规法）：m kx y l +=:设1122(,),(,)A x y B x y ，由22 3412 y kx m x y =+??+=?得222(34)84(3)0k x mkx m +++-=， 22226416(34)(3)0m k k m ?=-+->，22340k m +-> 2121222 84(3) ,3434mk m x x x x k k -+=-?=++ 222 2 121212122 3(4) ()()()34m k y y kx m kx m k x x mk x x m k -?=+?+=+++=+ 以AB 为直径的圆过椭圆的右顶点(2,0),D 且1AD BD k k ?=-， 1212122 y y x x ∴?=---，1212122()40y y x x x x +-++=， （*） 222222 3(4)4(3)1640343434m k m mk k k k --+++=+++，（**） 整理得：2 2 71640m mk k ++=，解得：1222,7 k m k m =-=- ，且满足22 340k m +-> 当2m k =-时，:(2)l y k x =-，直线过定点(2,0),与已知矛盾； 当27k m =- 时，2 :()7 l y k x =-，直线过定点2(,0)7 综上可知，直线l 过定点，定点坐标为2 (,0).7 ◆方法总结：本题为“弦对定点张直角”的一个例子：圆锥曲线如椭圆上任意一点P 做相互垂直的直 线交圆锥曲线于AB ，则AB 必过定点)) (,)((2 222022220b a b a y b a b a x +--+-。（参考百度文库文章：“圆锥曲线的弦 对定点张直角的一组性质”） ◆模型拓展：本题还可以拓展为：只要任意一个限定AP 与BP 条件（如=?BP AP k k 定值或=+BP AP k k 定值），直线AB 依然会过定点。 此模型解题步骤： Step1：设AB 直线m kx y +=，联立曲线方程得根与系数关系，?求出参数范围； Step2：由AP 与BP 关系（如1-=?BP AP k k ），得一次函数)()(k f m m f k ==或者； Step3：将)()(k f m m f k ==或者代入m kx y +=，得定定y x x k y +-=)(。 方法评估：此方法求解过程中（*）（**）化简整理计算非常繁琐。下面介绍齐次式法。（上述方法改进还有“点乘双根法”） 解法二（齐次式法） 由以AB 为直径的圆过椭圆C 的右顶点P ，知PB PA ⊥，即1-=?PB PA k k 。（??????PB PA k k ?为定值） 负载调度算法 负载均衡（Load Balance），又称为负载分担，就是将负载（工作任务）进行平衡、分摊到多个操作单元上进行执行，例如Web服务器、FTP服务器、企业关键应用服务器和其它关键任务服务器等，从而共同完成工作任务。负载均衡建立在现有网络结构之上，它提供了一种廉价又有效的方法来扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性。 在调度器的实现技术中，IP负载均衡技术是效率最高的。在已有的IP负载均衡技术中有通过网络地址转换（Network Address Translation）将一组服务器构成一个高性能的、高可用的虚拟服务器，称之为VS/NAT技术。在分析VS/NAT 的缺点和网络服务的非对称性的基础上，提出通过IP隧道实现虚拟服务器的方法VS/TUN，和通过直接路由实现虚拟服务器的方法VS/DR，它们可以极大地提高系统的伸缩性。 在内核中的连接调度算法上，IPVS实现了以下几种调度算法： 1 轮叫调度 1.1 轮叫调度含义 轮叫调度（Round Robin Scheduling）算法就是以轮叫的方式依次将请求调度不同的服务器，即每次调度执行i = (i + 1) mod n，并选出第i台服务器。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。 轮叫是基站为终端分配带宽的一种处理流程，这种分配可以是针对单个终端或是一组终端的。为单个终端和一组终端连接分配带宽，实际上是定义带宽请求竞争机制，这种分配不是使用一个单独的消息，而是上行链路映射消息中包含的一系列分配机制。 1.2 轮叫调度算法流程 轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N（内部服务器个数），然后重新开始循环。在系统实现时，我们引入了一个额外条件，即当服务器的权值为零时，表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务（如屏蔽服务器故障和系统维护），同时与其他加权算法保持一致。所以，算法要作相应的改动，它的算法流程如下：假设有一组服务器S = {S0, S1, …, Sn-1}，一个指示变量i表示上一次选择的服务器，W(Si)表示服务器Si的权值。变量i被初始化为n-1，其中n > 0。 j = i; do { j = (j + 1) mod n; 微机课程设计报告 题目简易计算器仿真 学院（部）信息学院 专业通信工程 班级2011240401 学生姓名张静 学号33 12 月14 日至12 月27 日共2 周 指导教师（签字）吴向东宋蓓蓓 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C52芯片、汇编语言、数码管、加减乘除 生产调度问题及其优化算法（采用遗传算法与MATLAB编程） 信息014 孙卓明 二零零三年八月十四日 生产调度问题及其优化算法 背景及摘要 这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含M ( N)! 种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。 本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB 软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。 一．问题重述 某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工， 条件：1、每件产品必须按规定的工序加工，不得颠倒； 2、每台设备在同一时间只能担任一项任务。 （每件产品的每个工序为一个任务） 问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。 要求：给出每台设备承担任务的时间表。 注：在上面，机器 A，B，C，D 即为机器 1，2，3，4，程序中以数字1，2，3，4表示，说明时则用A，B，C，D 2015年10月21日 实验一 进程调度 1.实验目的： 通过对进程调度算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。 2.实验内容： （1）用C 语言（或其它语言，如Java ）实现对N 个进程采用某种进程调度算法（如先来先服务调度、短作业优先调度、优先权调度、时间片轮转调度、多级反馈队列调度）的调度。 （2）为了清楚地观察每个进程的调度过程，程序应将每个进程的被调度情况显示出来。 （3）分析程序运行的结果，谈一下自己的收获。 3.设计实现： 1）流程图 主流程图： choice!=1&&choice!=2 c hoice==2 c hoice==1 Y N 开 始 初始化参数 输入函数 输入chioce FCFS SJF 输入有误，请重新输入！ 是否继续？ 结束 输入函数流程图： 请输入进程个数：Num N Y i=0 N i=0 N 先来先服务流程图： i=0 N Y N Y 开始 Num>0&&Num<=100 i 短作业优先算法流程图： i =0 N i = 0 开始 计算第一次NowTime 和第一个进程的完成时间 输出 i 圆锥曲线齐次式与点乘双根法
向量 - 向量叉乘 向量点乘
数据结构课程设计计算器
算法之多机调度问题
一种基于滤波的分段点乘图像分割算法
操作系统短作业优先调度算法
简易计算器
求解调度问题的启发式算法(1)讲课教案
齐次式法与圆锥曲线斜率有关的一类问题
负载均衡调度算法
微机课设简易计算器
matlab生产调度问题及其优化算法
调度算法