动态规划很简单的，就是把大问题分解成一步步的小问题。 <- 中国开发网

CNDEV.ORG

当前在线

论坛

CBD
- 程序员情感CBD
- 程序员见面交流会
CBD开发区
- Java/J2ME
- .NET/C#
- 数据库
- Delphi/BCB
- Visual C
个人
- 袁国术的个人网站
- 翟旭东网!!!
其它
情感
游戏
- CNDEV-CS/WOW
- 浩宇长空
生活
论坛系统

中国开发网: 论坛: 程序员情感CBD: 贴子 760697

半打黑趵：动态规划很简单的，就是把大问题分解成一步步的小问题。

[阅读: 515] 2009-10-15 03:21:41

比如现在这个。
如果已知从第一组出发到第三组每一个点的最短路径，可以直接计算到第四组每一个点的最短路径。
这不就把问题简化成了计算三组坐标的最短路径了吗。以此类推就是了

相关信息:

路径算法 (151字) (leejd [602] 2009-10-15 10:34)
- 问题描述得不清楚。路径是怎么算的？ (空) (空山新雨 [389] 2009-10-15 10:37)
- 红当当，看不下去 (空) (JoJo [371] 2009-10-15 10:38)
  - 让MM修改一下，默认不要UBB显示吧 (空) (leejd [423] 2009-10-15 10:47)
- 【每次从一组里面抓一个坐标】？应该是｛每组里面抓一个坐标｝吧？ (41字) (haitao [379] 2009-10-15 10:40)
- 可能是我表述不清楚 (72字) (leejd [562] 2009-10-15 10:42)
  - 要求每次抓出来的坐标路径最小 - 你有原点？或者起始参考点？还是说，每次从(Xn,Yn)到(Xn+1,Yn+1)的路径长度最短？ (空) (空山新雨 [431] 2009-10-15 10:45)
    - 每次抓取4个坐标，这4个最短距离即可 (10字) (leejd [465] 2009-10-15 10:46)
      - 这4个最短距离是啥意思一共4条线段之和最短，还是6条线段 (41字) (空山新雨 [502] 2009-10-15 10:49)
      - 还是没说清楚。。。。。。。。。。。 (43字) (haitao [356] 2009-10-15 10:49)
        要求每次从每组里面取一个，最后计算出来的距离是其他任何4个的组合的路径的最短 (空) (leejd [422] 2009-10-15 10:53)
        只有四组？也不可能是4个组合，你给的数据，应该可以有3X2X3X1=18个组合 (空) (周星驰 [398] 2009-10-15 10:56)
        前面没问题了（得到了a,b,c,d 4个点），后面：它们怎么组成路径？ (135字) (haitao [452] 2009-10-15 10:57)
        a-b-c-d，所组成的路径最短 (空) (leejd [425] 2009-10-15 11:04)
        你这不就是个图么，从一个点出发到终点，终点只有一个。做遍历吧？ (空) (空山新雨 [399] 2009-10-15 10:58)
        从多个点出发，不是一个点 (39字) (leejd [391] 2009-10-15 11:04)
        终点只有一个，反向遍历不就完了，路径长度无向性的 (空) (空山新雨 [353] 2009-10-15 11:05)
        终点也不是一个啊，而是要根据路径最短来判断哪个终点最好 (空) (leejd [400] 2009-10-15 11:11)
        还是没看懂 (5字) (dingchenye [424] 2009-10-15 13:29)
        根据对鸡蛋业务背景的了解, 就可以知道他的想法了... (54字) (dead_lee [516] 2009-10-15 17:36)
        差不多是这个意思，最短路径只是其中一个因素 (空) (leejd [458] 2009-10-15 17:39)
- 要悬赏就好了 (空) (sealw [373] 2009-10-15 11:02)
  - 出得起赏钱就不用自己去费劲了 (8字) (leejd [460] 2009-10-15 11:02)
    - 能用别人的脑子替自己干活，这样的人了不起 (空) (sealw [375] 2009-10-15 11:12)
      - 能不花钱用别人的脑子替自己干活，这样的人才了不起 (空) (sealw [1] 今天 11:12) (空) (haitao [387] 2009-10-15 11:20)
      - 其实俺缺的就是一个字 (1字) (leejd [430] 2009-10-15 11:22)
        拿钱换时间 or 拿时间换钱 (空) (sealw [421] 2009-10-15 11:27)
        时间、空间、钱 (空) (haitao [346] 2009-10-15 11:29)
- google 动态规划算法 (空) (半打黑趵 [431] 2009-10-15 11:09)
  - 没学好数学，不懂 (空) (leejd [875] 2009-10-15 11:11)
    - 规模不会大的话，完全枚举就行了 (空) (haitao [381] 2009-10-15 11:16)
      - 每组最大也就几百个坐标，一般几十组，最多也就200组 (空) (leejd [347] 2009-10-15 11:16)
        靠！那就只有请出P133才行了。。。。。。。。。。。。 (空) (haitao [367] 2009-10-15 11:19)
        你这个就是典型的 Dynamic Programming 问题 (空) (半打黑趵 [354] 2009-10-15 11:23)
        看来目前只能凑活着，得有钱之后才行 (空) (leejd [399] 2009-10-15 11:33)
        悬赏我吧 (空) (半打黑趵 [336] 2009-10-15 11:48)
        你在上海吧 (5字) (leejd [424] 2009-10-15 12:24)
        能预支赏金吗？ (空) (半打黑趵 [378] 2009-10-15 12:37)
        让俺客户今年先到帐 (6字) (leejd [371] 2009-10-15 12:38)
        无良 (空) (半打黑趵 [303] 2009-10-15 12:56)
      - 7组时的结果。。。。。。。。。。 (371字) (haitao [390] 2009-10-15 17:39)
    - 动态规划很简单的，就是把大问题分解成一步步的小问题。 (86字) (半打黑趵 [514] 2009-10-15 11:21)
      - 得到n*(n-1)/2个最短线段了，还有一个怎么组合它们的问题（在每个点都使用一次的约束下） (空) (haitao [860] 2009-10-15 11:42)
        什么意思？看不懂 (空) (半打黑趵 [345] 2009-10-15 11:47)
  - 正解 (空) (空山新雨 [338] 2009-10-15 11:14)
- A*？ (空) (周星驰 [361] 2009-10-15 11:22)
- Y还在搞这个算法啊 (空) (好望角 [445] 2009-10-15 12:22)
  - 我们一直在努力，每天在进步！ (空) (leejd [401] 2009-10-15 12:24)
    - 反正当初偶学《运筹学》的时候 (63字) (好望角 [385] 2009-10-15 12:27)
      - 靠，总得比小日本的强一点吧 (6字) (leejd [433] 2009-10-15 12:34)
        估计有现成的运筹数学库。。。。。。。。想当初我的运筹学也是学的很好的 (69字) (haitao [357] 2009-10-15 12:49)
        偶这个队好歹还拿了全国三等奖滴 (20字) (好望角 [377] 2009-10-15 12:51)
        我先投降。。。。。。。。。 (空) (haitao [322] 2009-10-15 12:56)
- 我靠,哪到哪的距离啊,你也没说清楚 (空) (Apache [365] 2009-10-15 12:55)
  - Anywhere to Anywhere (空) (好望角 [415] 2009-10-15 12:57)
- 给个DP算法的伪码，不保证对，不一定错 (328字) (半打黑趵 [431] 2009-10-15 12:58)
  - 写错了一点，改过来了 (空) (半打黑趵 [389] 2009-10-15 15:18)
    - 对俺来说是：小狗看花被单 (空) (leejd [450] 2009-10-15 17:38)
      - 什么意思？看不懂 (空) (半打黑趵 [0] 今天 11:47) (空) (半打黑趵 [354] 2009-10-15 19:00)
        看不懂 (空) (半打黑趵 [0] 今天 11:47) (空) (半打黑趵 [0] 昨天 19:00 ) (6字) (leejd [405] 2009-10-16 09:42)

欢迎光临本社区，您还没有登录，不能发贴子。请在这里登录

页面内容处理时间: 0.017 - 558432