作者chrisdar (克里斯)
看板Prob_Solve
标题Re: [问题] 如何解 池塘边的木头 问题
时间Fri Nov 7 12:36:56 2008
※ 引述《Fenikso (我是蜜蜂~)》之铭言：
: ※ 引述《ledia (下班後才下棋)》之铭言：
: : ◆ From: 140.112.30.54
: : 推 chrisdar:忘记说 全都是整数 11/06 07:29
: : 推 Fenikso:为什麽可以保证第i根要摆在第i+1根前面? 11/06 21:25
: : 推 Fenikso:这样不一定会最好 11/06 21:27
: : 推 yoco315:其实我觉得这提用 simplex 最好.. 11/07 04:33
: : → yoco315:数字范围还可以是实数... @@" 11/07 04:33
: : 推 chrisdar:Fenikso 我试过把顺序洗乱下去解线性规画 值都比1500大 11/07 08:08
: 可能是你洗的太乱了
: 把Yi相同的那些重排试试看
: : 推 chrisdar:to yoco315 您的意思是我把45顶点的简单型压成一维? 11/07 08:17
: : 推 chrisdar:to Fenikso 或许是限制式的问题导致 11/07 08:25
: 那我举个例子好了
: 宽度100
: Yi = {3, 4}, H = {80, 2}
: 你觉得该怎麽移?
: 最佳解应该是把短的那根(Yi[1])搬到头才对喔
我把资料又重新排序了 用木头的中点来排序
Yi[45] = { 60, 78,130,151,155,224,236,238,246,260,352,356,394,409,419,
429,432,430,440,446,453,452,464,464,480,517,523,547,634,709,
712,712,712,712,712,712,713,713,713,713,713,718,724,725,725 }
H[45] = { 13, 4, 10, 4, 4, 7, 7, 5, 3, 4, 3, 5, 2, 4, 3,
5, 6, 23, 3, 3, 2, 5, 2, 4, 7, 3, 23, 7, 2, 19,
16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 10, 4, 2, 2 }
Solution: 1492
Yo[45] = { 60, 78,130,151,155,224,234,241,246,260,352,356,394,409,413,
416,421,427,450,453,456,458,464,466,480,487,490,513,520,522,
541,557,573,589,605,621,637,652,667,682,697,712,722,726,728 }
确实没考虑到您所提到的问题 目前的值 1492 有变小了 不过这真的是最小了吗?
目前还是没想到有效的演算法，如果有就可以花时间把全部的排列都列出来去解，
目前都还是套用之前线性规画的模型(不更换次序的原则下)去解的。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.195.68.196
1F：推 Fenikso:这题除了A*之外我没什麽好想法.. 11/07 14:33