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

账号

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

半打黑趵 · 2009-10-15 03:21:41 · 阅读: 540

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

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

相关信息:

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

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

页面内容处理时间: 0.018 - 568616