老师参与

Python求解动态规划（工序问题）把自己绕进去了

澄碧钓徒 发表于2019年10月12日
<p><code class="brush:python;toolbar:false" >p&nbsp;=&nbsp;[[0]&nbsp;*&nbsp;3&nbsp;for&nbsp;i&nbsp;in&nbsp;range(9)]&nbsp;&nbsp;#3台机器，问题分9步 t&nbsp;=&nbsp;[[9,&nbsp;8,&nbsp;15],&nbsp;[8,&nbsp;10,&nbsp;11],&nbsp;[6,&nbsp;4,&nbsp;9]]&nbsp;#对应本道工序与下道工序的间隔时间 for&nbsp;i&nbsp;in&nbsp;range(3): &nbsp;&nbsp;&nbsp;&nbsp;p[0][i]&nbsp;=&nbsp;t[0][i] temp&nbsp;=&nbsp;[[]&nbsp;for&nbsp;i&nbsp;in&nbsp;range(9)] for&nbsp;i&nbsp;in&nbsp;range(1,&nbsp;9): &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;j&nbsp;in&nbsp;range(3): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;k&nbsp;in&nbsp;range(3): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp[i].append(p[i-1][j]&nbsp;+&nbsp;t[j][k])&nbsp;&nbsp;&nbsp;#应该就是这一步出了问题？ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[i][j]&nbsp;=&nbsp;min(temp[i]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#print(temp[i]) print(min(p[9]))&nbsp;&nbsp;#最后一行的最小值对应最短时间 #print(p)</code></p><p>说实在的之前的一年多每次我看到MATLAB第一期还有新帖出现我让他们去最新的一期提问的时候我自己也是不好意思再提问的，现在我还是想通了来第五期发帖吧，实际上这个问题是夏伟怀老师的《运筹学》专题五作业第一题（透露其他课的题目本来就不太好，我实在是不好意思把题干截图了），我的思路是通过迭代求每步的最优决策，p矩阵最后一行的最小值对应最短时间，t对应的是本道工序与下道工序的间隔时间，三台机器三行三列，但是第11行输出中间结果明显不对头啊（手算结果应该是68），比如temp[1][0]正常的值是16应该等于min(t[0][0]+p[0][0],t[1][0]+p[0][1],t[2][0]+p[0][2])吧（感觉这里思路有点混乱……），那边肯定只有手算提交了，但是这段代码刘老师能不能帮我看下问题出在哪里？</p>
举报
1 回复
    LiuWG

    1楼

  • LiuWG 发表于2019年10月12日
    1 | 4 | 举报
    <p>print(min(p[9]))&nbsp;&nbsp;下标会越界。</p><p>建议根据问题按以下步骤检查程序：</p><p>1）检查1-5行的原始数据对不对，即p、t、temp的值、大小（size）对不对。</p><p>2）6-10行对不对？循环次数并不多，可以每循环一次和手算结果对比一次，应该能发现问题。<br ></p><p>请先试试吧！</p>
    LiuWG 发表于2019年10月12日
    1 | 评论(4) | 举报
    • 澄碧钓徒 2019年10月12日
      0 | 举报
      <p>老师，对比手算递推修改现在最优解倒是对上了，找最短路径或许思路就是找每一步最小值对应的列号，但是13行如果这样输出的话又不对了，那么要怎么改呢？<br ></p><p><code class="brush:python;toolbar:false" >p&nbsp;=&nbsp;[[0]&nbsp;*&nbsp;3&nbsp;for&nbsp;i&nbsp;in&nbsp;range(9)] t&nbsp;=&nbsp;[[9,&nbsp;8,&nbsp;15],&nbsp;[8,&nbsp;10,&nbsp;11],&nbsp;[6,&nbsp;4,&nbsp;9]] for&nbsp;i&nbsp;in&nbsp;range(3): &nbsp;&nbsp;&nbsp;&nbsp;p[0][i]&nbsp;=&nbsp;t[0][i] for&nbsp;i&nbsp;in&nbsp;range(1,&nbsp;9): &nbsp;&nbsp;&nbsp;&nbsp;temp&nbsp;=&nbsp;[[0]&nbsp;*&nbsp;3&nbsp;for&nbsp;i&nbsp;in&nbsp;range(3)] &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;j&nbsp;in&nbsp;range(3): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;k&nbsp;in&nbsp;range(3): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp[j][k]=p[i-1][k]&nbsp;+&nbsp;t[k][j] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#print(p[i-1][k],t[k][j],temp[j]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[i][j]&nbsp;=&nbsp;min(temp[j]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#print(p[i][j]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print(temp[j].index(min(temp[j]))) print(min(p[8])) #print(p)</code></p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>0</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>0</p><p>1</p><p>2</p><p>2</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>2</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>0</p><p>1</p><p>2</p><p>2</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>2</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>0</p><p>1</p><p>2</p><p>2</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>2</p><p>1</p><p>2</p><p>1</p><p>1</p><p>2</p><p>0</p><p>1</p><p>2</p><p>2</p><p>1</p><p>2</p><p>1</p><p>68</p>
      澄碧钓徒 发表于2019年10月12日
      0 | 举报
    • LiuWG 2019年10月12日
      0 | 举报
      <p>&gt;&gt;&gt; p=[2,3,4,-21,4]</p><p>&gt;&gt;&gt; p.index(min(p))</p><p>3</p><p>找最小值序号还是可以的</p>
      LiuWG 发表于2019年10月12日
      0 | 举报
    • 澄碧钓徒 2019年10月13日
      0 | 举报
      <p>老师，这里找最短路径似乎通过找最小值的索引还是行不通啊？如果用三维列表的话也实现不了，感觉这跟一般的最短路径问题还不太一样。。。<br ></p>
      澄碧钓徒 发表于2019年10月13日
      0 | 举报
    • LiuWG 2019年10月13日
      0 | 举报
      <p>按老师要求做吧！</p>
      LiuWG 发表于2019年10月13日
      0 | 举报
    添加评论
发表回复