[算法]数学建模的十大算法[收藏]

dskongenius 发表于 2007/10/24 21:34:56

　数学建模的十大算法
发信站: 自在心语 BBS 站 (Fri Dec 23 10:37:29 2005), 站内

1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法）
2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）
3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现）
4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备）
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）
6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题

 [杂类技术]MS 面试题　

dskongenius 发表于 2007/10/24 21:32:48

微软亚洲技术中心的面试题

1．进程和线程的差别。
2．Heap与stack的差别。
3．Windows下的内存是如何管理的？
4．介绍.Net和.Net的安全性。
5．客户端如何访问.Net组件实现Web Service？
6．C/C++编译器中虚表是如何完成的？
7．谈谈COM的线程模型。然后讨论进程内/外组件的差别。
8．谈谈IA32下的分页机制
9．给两个变量，如何找出一个带环单链表中是什么地方出现环的？
10．在IA32中一共有多少种办法从用户态跳到内核态？
11．如果只想让程序有一个实例运行，不能运行两个。像winamp一样，只能开一个窗口，怎样实现？
12．如何截取键盘的响应，让所有的‘a’变成‘b’？
13．Apartment在COM中有什么用？为什么要引入？
14．存储过程是什么？有什么用？有什么优点？
15．Template有什么特点？什么时候用？
16．谈谈Windows DNA结构的特点和优点。

 [算法]动态规划的理论模型

dskongenius 发表于 2007/10/24 21:26:53

动态规划 Dynamic Programming

by Starfish


【摘要】

本文介绍了动态规划的基本思想和基本步骤，通过实例研究了利用动态规划设计算
法的具体途径，讨论了动态规划的一些实现技巧，并将动态规划和其他一些算法作
了比较，最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。

（说明：这是我中学时候写的一篇小论文，因为公式和图比较多，
为了能在bbs上贴出来做了不少删节）


【目录】
一。引言
二。动态规划的基本思想
三。动态规划算法的基本步骤
四。动态规划的适用条件
五。动态规划的实例分析
六。动态规划的技巧——阶段的划分和状态的表示
七。动态规划实现中的问题
八。动态规划与其他算法的比较
九。动态规划的理论模型


一。引言

动态规划(dynamic programming)是

阅读全文(1421) | 回复(0) | 编辑 | 精华 | 删除

 [算法]贪心法，分治法，动态规划的学习总结

dskongenius 发表于 2007/10/24 21:24:10

一，贪心法 首先说说贪心法，贪心法是自然的方法，也是最直观的方法，贪心法的当前选择依赖于已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择，但是该方法不能保证最后得出的解是最优的，需要反复选择策略，加以比较，有时候一些选择策略可以很巧妙的解决问题。贪心法主要有两种思想，即贪心算法领先和交换论证，用来证明所得的解是最优的，交换论证的思想为首先假设一个最优解和通过贪心法所得到的解，然后逐步修改最优解，但保持每步的最优性，最后使得最优解跟通过贪心法所得的解相同。

阅读全文(3838) | 回复(0) | 编辑 | 精华 | 删除

 [算法]基本算法

dskongenius 发表于 2007/10/24 21:19:12

贪心算法
一、算法思想
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
　　求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；

回溯法
一、回溯法：
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

阅读全文(1317) | 回复(0) | 编辑 | 精华 | 删除