随笔 - 303  文章 - 883  trackbacks - 0
<2007年9月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

欢迎光临! 
闲聊 QQ:1074961813

随笔分类(357)

我管理的群

公共blog

  • n维空间
  • Email : java3d@126.com 群 : 12999758

参与管理的论坛

好友的blog

我的其他blog

朋友的网站

搜索

  •  

最新评论

很久只前我有个朋友提出一道某大公司应聘的题目,今晚突然回想起来,觉得很有趣
如下
有一个 m * n  的矩阵,m n 是提供的确定的数,但算法必须适应任意情况
里面的数是不确定(任意的)的,要求按一定的方向(如图),
从左上角第一个元素走到右下角最后一个元素,只能向右和向下走,每走一步,加上那
个数,要求得到的数最小。




要求如下:
第一:算法要简单
第二:效率要高(因为数据可能很多)

比如:

1 8   0
7 8   8
7 15 1

那么最优路径就是

1 8  0 
       8 
       1

下面我提出自己的想法:

首先:遍历整个矩阵(二维数组),得到最大的那个数,用一个标记替换他如 '#' ,重复这一,
大概 n 次(n为可能路径 (还在计算中,会补上的) 的1/3);

然后:用循环,判断(排除前面的标记)得到剩下路径,取出最优值;(如果剩下的个数
还很大,可以重复上一步操作)

这个我的自己的想法,不知道您有没有其他的想法?请多多指教!

如果您知道,可能的路径数目的计算公式,也希望你能提供我参考;谢谢!!!




地震让大伙知道:居安思危,才是生存之道。
posted on 2007-09-03 22:35 小寻 阅读(1959) 评论(11)  编辑  收藏 所属分类: 算法

FeedBack:
# re: 关于一个矩阵最优路径算法 2007-09-03 22:50 幻想~@@~
提示下:穷举看起来不太可能,我算过了,太多了 呵呵  回复  更多评论
  
# re: 关于一个矩阵最优路径算法 2007-09-03 22:54 幻想~@@~
再提示一下:贪婪法,每次寻找与当前节点邻接的最小值
1 8 0
7 8 8
7 15 1
得到的是
1
7
7 15 1
明显不可以  回复  更多评论
  
# re: 关于一个矩阵最优路径算法 2007-09-03 22:55 星空丨丶情缘
.可不可以把矩阵分成多个一维数组.
用线程同时算出每维最小的数.再放在一个一维的数.再穷举一次.

仅仅思路.怎么实现..那就..  回复  更多评论
  
# re: 关于一个矩阵最优路径算法 2007-09-03 23:02 幻想~@@~
可以但是路径有可能断掉了,这个想法和我的很类似  回复  更多评论
  
# re: 关于一个矩阵最优路径算法 2007-09-25 16:40 beginner
从深的优先和广度优先搜索法入手,
拿着大学时候c++教材可以解决的.
现在忘了具体算法了  回复  更多评论
  
# re: 关于一个矩阵最优路径算法[未登录] 2007-09-26 07:45 寻觅
呵呵 谢谢 还有人说用图论 解决 认为怎么样?  回复  更多评论
  
# re: 关于一个矩阵最优路径算法 2008-05-03 21:51 ygh
能不能实现这样的一个算法,我把所有的数字看成是网格各边的长度,所有的数字就可以构成一个网络,我只要在对角上一拉,直到不能拉的时候为止,此时的路径就是最短的路径,就不晓得这样的算法能不能实现呢!  回复  更多评论
  
# re: 关于一个矩阵最优路径算法[未登录] 2008-05-11 16:48 寻觅
呵呵 感觉你的想法不错!有个地方不是很清楚:
"对角上一拉,直到不能拉的时候为止"这句话什么意思呢?
是否解释下? 谢谢  回复  更多评论
  
# re: 关于一个矩阵最优路径算法[未登录] 2008-07-27 01:44 test
因为只能向右,向下走,从最左上角开始,这其实就是一个二叉树,但是倒了边界又不是二叉树(不过可以当作二叉树来处理),这就是看哪种算法最优了!个人觉得先一支走到底,然后再用分支定界法!  回复  更多评论
  
# re: 关于一个矩阵最优路径算法 2009-09-23 12:01 
没看懂?
  回复  更多评论
  
# re: 关于一个矩阵最优路径算法 2011-05-10 09:36 Ghost
复杂度太大!用动态规划吧~@beginner
  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: