关于建模的一道题,请求大神指点一下方向~~~? 400 报错-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

关于建模的一道题,请求大神指点一下方向~~~? 400 报错

爱吃鱼的程序员 2020-06-04 11:51:50 35

关于建模的一道题,请求大神指点一下方向~~~? 400 报错

@中山野鬼 你好,想跟你请教个问题:下面这道题我想应该不是最短路径问题,但是有没有头绪下手,请前辈帮帮忙指点一二,谢谢

某区政府计划在下列区域(见图1)修建一条从A(0,9)到B(9,0)的直线型公路,由于涉及路面拆迁等因素,各地段建设费用有所不同,图1中的数字代表该区域公路单位建设费用(单位:百万元)。未标数字的任何地方单位建设费用均为1。图1的每个网格长与宽都是1个单位。每个网格的边界上建设费用按该地区最小单位费用计算。

    请按建设部门的如下具体要求,从建设费用最省的角度,给出最优的方案。

(1)公路至多只能有1个转弯点,且转弯点只能建在图1所示的网格点上。

(2)公路至多可以有2个转弯点,且转弯点只能建在图1所示的网格点上。

(3)公路至多只能有2个转弯点,且转弯点只能建在图1所示的网格线上。

(4)公路至多只能有2个转弯点,转弯点可以建在图1所示区域的任何位置。

(5)如果各区域的单位建设费用为1.5-0.1*[(x-4)^2+(y-4)^2]^0.5 (百万元),公路至多只能有1个转弯点,转弯点可以建在图1所示区域的任何位置。

 

分享到
取消 提交回答
全部回答(1)
  • 爱吃鱼的程序员
    2020-06-04 16:40:26

    你这个题目还是最优策略的问题。只不过有些约束未必是唯一解。对于最多一个转折点,这类问题,你可以等同于看作,在A,B中间取一点C。分别求AC,CB的最优路径总和的最优。

    这里暂时我不讨论优化策略。你主要不清楚的在什么地方?

     

    ###### @中山野鬼 我不明白的是求AC+CB费用最少是要用什么模型求出来,我现在能想出来去解的方法只是,先求出AC,CB直线方程,接着解出直线与网格的每一交点, 再算每一网格内线段长度*单位造价,这样累积和最小,我不知道这种方法行不行的通,因为首先我发现计算量很大.....前辈有什么好的方法吗?######

    引用来自“iamwilling”的答案

    @中山野鬼 我不明白的是求AC+CB费用最少是要用什么模型求出来,我现在能想出来去解的方法只是,先求出AC,CB直线方程,接着解出直线与网格的每一交点, 再算每一网格内线段长度*单位造价,这样累积和最小,我不知道这种方法行不行的通,因为首先我发现计算量很大.....前辈有什么好的方法吗?
    求AC的计算,和求AB(没有拐弯,就是任意直线)的计算是等同的。
    0 0
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

推荐文章