浅谈编程解决实际问题的常见思想

标签: 编程 问题 常见 | 发表时间:2013-09-13 16:09 | 作者:
出处:http://kb.cnblogs.com/

  现实生活中有很多问题,人为不好解决,但利用计算机速度快,不出错的特性,可以很方便的解决这些问题,下面简单说说我在程序设计中解决实际问题的一些常见思想,高手可以忽略掉,我也是无聊了随便写写而已。

   1、枚举最优解时的情况

  有很多问题初看很棘手,但经过仔细的分析,可以得出一些显然的结论。

  比如下面这个问题: 平面内有上千个点,用一个半径为R的圆去覆盖,最多能覆盖多少点?

  很多程序员最暴力的思想就是枚举,当然,利用计算机枚举确实是一种很有效的方法,特别是在数据很小的情况下,不过对于上述问题,如何枚举?枚举圆的位置吗?

  确实可以枚举圆的位置,如果不经过思考的话可以在二维正交系内枚举每个点为圆心,然后判断这个圆能覆盖多少圆,最后结果取最大。这个确实是一种方法,不过枚举圆心如何操作?圆心的位置是连续的,不一定是整点这种离散位置。 在数据量小并且精度要求不高的情况下,直接枚举圆心位置不失为一种好方法。 不过稍微分析一下,可以得出这样一个结论,最优解的圆,也就是覆盖点数最多的R半径圆,圆上一定有2个点。

  假设最优解的圆上没有2个点,如上图,那么通过微量的平移操作,可以使圆接触平面上的2个点,并且园内的点数不会减少,它的结果不会比圆上没有2个点的情况差,因为只要求最多覆盖多少点,我们可以枚举任意2个点,这样这个半径为R的圆的位置就确定了(在这2点中垂线上,2种情况),再判断下这个圆能覆盖多少点,两两点枚举后取最大,这是一个O(n^3)的算法,1秒内出结果,已经比较高效了。

  所以很多时候我们可以分析出最优解是满足哪种情况的,然后利用计算机特性枚举最优解,逆向思维解决问题。

   2、动态规划思想

  动态规划是一种非常高效的方法,这个编程里面非常非常常见的,不会搜索和动态规划,基本就不会编程。如果能够把一个大的问题划分成若干同类型的小问题,小问题又可以划分为更小的问题,直到问题程度小到一眼就能看出来,那么可以把小问题先求出保存起来,再求大问题,这样的例子相当多,而且利用递归的写法,记忆化深度搜索,很容易实现这种思想。 经典的动态规划还有很多,最长上升至序列,背包问题等等。

  如果还有同学不明白动态规划,看下面这一段C语言代码,相信能体会到一些。

/******************
Author: lxgsbqylbk
Function : Get the factorial of integer n (n>=0) 求n的阶乘
n!=
1 n==0
n*(n-1)! n>0
****/

//完成动态规划一般2中思路
//1.记忆化深搜
int fac[MAXN];
int F(int n)
{
return n?(fac[n]?fac[n]:fac[n]=n*F(n-1)):1;
}

//2.规划方向后求解
int fac[MAXN];
for(fac[0]=1,i=1;i<=N;i++)
{
fac[i]=fac[i-1]*i;
}

   3、排序思想

  排序是一个很重要的步骤,有很多问题通过排序预处理后可以更加方便的解决,比如有很多张钞票,面值不同,从中选出m张使它们价值最大,一个做法当然是对着些钞票按照面值从大到小排序,然后取钱m张就行了。 很多时候,上述的动态规划需要对变量按照一定规则排序后才能操作,有一定顺序了之后,问题一般更容易解决。

  说到排序,不得不说到贪心算法。 贪心算法就是如果整个大问题要到达一个最优解,在构成大问题的小问题中每次取最优的,大问题就能到达最优情况,当然,这种策略需要经过证明正确性后才能实现。 很多贪心过程前也要有排序的工作,比如著名的Kruscal最小生成树算法,要先对边进行排序,所以排序是个很重要的过程,以至于它被收录到各种语言的库函数中,可以方便的被用户调用。

   4、二分,三分

  前几天听同学说,现在8K已经招不到会写二分的程序员了,当然这句话有夸张的成分啦,^-^ 可见二分在程序设计中的常用性。

  其实这个可以并列到枚举算法那中,只是这种枚举效率很高,很多地方比如SQL数据库里面的查找方式就是二分,二分枚举,三分枚举,时间复杂度都是对数级的,在程序设计中是相当高效的算法。

  二分的条件:数据的单调性。 比如在一组从小到大排序的数中寻找数x,这样就可以二分枚举,每次可以把范围缩小一半,无论数据多大,就算超出int类型,都能很快找出来。

  比如求函数 8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == K 在区间[0,100]的解,由于这个函数在[0,100]是单调递增的,所以二分是个不错的选择。

  三分的条件: 数据的有凸性。

  比如求函数 6*x^7 + 8*x^6 + 7*x^3 + 5*x^2 - K*x 在区间[0,100]的最小值。

  这个函数在[0,100]是一个先减后增(或者完全单调,主要看K)的函数,所以三分求解。

  当然这个问题可以转换为二分,将函数求导,二分其在0的位置即可,这个涉及到高等数学,不赘述了。

  具体过程可以去查资料 二分前一般也需要排序操作的。

   5、随机算法

  很多时候在要解决的问题没有任何思路,枚举数据量又太大的情况下,可以使用一些随机算法。

  常见的随机算法,蚁群算法,模拟退火等等。

  简单说说模拟退火,比如平面内有成千上万个点,要在平面选一个圆,覆盖所有点,问最小的半径是多少?

  第一次接触这个问题的时候我有想到一种做法(不敢保证正确):

  根据1还是可以得出结论,最优情况圆上面一定有2个点,否则的话可以把圆继续缩小平移,使它上面有2个点,结果更优。

  所以枚举任意2个点,圆心一定在这2点中垂线上,这里是对的。 然后假设这个圆心在在中垂线上移动,如果满足要求,包围了所有点。

  那么我猜测这个圆在移动过程中半径先减小后增大。(感觉而已,未证明,也未测试,太麻烦了。) 这里可以使用上述的三分枚举,因为半径函数是下凸性的。

  我上面这个方法正确性先不说,复杂度是有一点的,枚举2点,再三分。O(n^2*logV) 当然,数据很小的情况下,比如只有几千个点的话,结果秒出,数据大了,效率降低了。

  这里说一下模拟退火的思想。 大概依照一个这样的理论,假设现在有1个位置pos,如果最优解圆心位置在pos上面,那么如果往pos下面搜,搜到的圆心一定比在pos的位置时候大。

  依照这个理论,我们就可以现在平面内随机生成一些点,然后贪心的随机移动它们,直到达到一定程度停止。这个算法在时间复杂度上是O(n)的 正确性很高,运行也相当的快。

   6、最后一个问题转化

  有的时候遇到问题,不能立即想出策略,这个时候尝试下将这个问题转化为常见的模型,利用常见模型和经典的算法解决它。

  最常见的还是一些图论上的问题,将实际问题转化为流网络或者二分图。

相关 [编程 问题 常见] 推荐:

浅谈编程解决实际问题的常见思想

- - 博客园_知识库
  现实生活中有很多问题,人为不好解决,但利用计算机速度快,不出错的特性,可以很方便的解决这些问题,下面简单说说我在程序设计中解决实际问题的一些常见思想,高手可以忽略掉,我也是无聊了随便写写而已.    1、枚举最优解时的情况.   有很多问题初看很棘手,但经过仔细的分析,可以得出一些显然的结论.

linux xampp常见问题

- We_Get - 博客园-首页原创精华区
1.安装xampp4linux后,只能本机(http://localhost)访问,局域网内其他机器无法访问. 解答:在/opt/lampp/etc中修改httpd.conf,将Listen 80修改为Listen 本机ip地址:80 本机ip地址使用ifconfig 查看. 2.我按照1修改之后,局域网内的机器还是无法访问.

storm常见问题解答

- - BlogJava-庄周梦蝶
    最近有朋友给我邮件问一些storm的问题,集中解答在这里. 一、我有一个数据文件,或者我有一个系统里面有数据,怎么导入storm做计算. 你需要实现一个Spout,Spout负责将数据emit到storm系统里,交给bolts计算. 怎么实现spout可以参考官方的kestrel spout实现:.

MariaDB常见问题FAQ

- - OurMySQL
MariaDB常见问题,同样适用于MySQL. 老版本MariaDB服务的相关旧信息. via似乎是个关键字,但是至少在MySQL5.1文档中找不到. 在MySQL5.1中执行成功,但是会出现1064错误 (毫无疑问,用avia替代via就可以). 答           elenst. 这个bug(https://bugs.launchpad.net/maria/+bug/1010351)被修复.

hadoop配置常见问题

- - 企业架构 - ITeye博客
收集记录一些Hadoop配置部署过程中遇到的问题. 这种方法解决了运行中的hadoop的safe mode问题,但是下次重启hadoop,还会出现这个问题. 其实这个问题,我猜测可能是由于目录/app/hadoop/tmp/mapred/system被破坏造成. 永久解决,可以删除掉/app/hadoop/tmp/,重新创建,重新format,重启hadoop——如果条件允许的话.

Zookeeper常见问题整理

- - CSDN博客推荐文章
当leader崩溃或者leader失去大多数的follower,这时候zk进入恢复模式,恢复模式需要重新选举出一个新的leader,让所有的Server都恢复到一个正确的状态. Zk的选举算法使用ZAB协议:. 选举线程由当前Server发起选举的线程担任,其主要功能是对投票结果进行统计,并选出推荐的Server;.

[转]常见的CSS兼容性问题。

- - ChaJn To The Dream
总体的来说就是:*_*+识别,IE专用的条件注释,对象的实际宽度不同,消除ul、ol等列表的缩进,透明,圆角,Select控件永远处于最上层,居中问题text-align、margin: auto,浮动后IE6解释外边距为实际边距的双倍加上display:inline,字体大小,空格大小. 1.CSS中几种浏览器对不同关键字的支持,可进行浏览器兼容性重复定义.

关于链接的常见问题

- - Google China Blog
发表者:谷歌中文搜索质量团队. 转载自: 谷歌中文网站管理员博客. 发布时间:2012年9月29日 下午 03:08:00. 在我们的 网站管理员帮助论坛里,站长们问的最多的就是关于链接的问题. 很多站长询问一旦网站因为链接的原因被处理,应该怎样申请重新审核. 也有很多站长询问关于买卖链接方面的问题.

Java String 的十大常见问题

- - ITeye博客
Java字符串经常被问到的排名前十的问题.    1、如何比较字符串. 使用 “==”  还是 “equals()”.   简单来讲,“==”比较的是引用(对象的内存地址),“equals()” 比较值是否相等. 除非你想检测两个字符串是否是同一对象,否则都用equals().   当然了解字符串池的概念更好.

php初学者常见问题

- - SQL - 编程语言 - ITeye博客
最令PHP初学者头痛的十四个问题. 管理提醒: 本帖被 haowubai 执行置顶操作(2009-04-16) 【1】面之间无法传递变量 get,post,session在最新的php 版本中自动全局变量是关闭的,所以要从上一面取得提交过来得变量要使用$_GET[’foo’],$_POST[’foo’],$_SESSION[’foo’]来得到.