论坛 › 难题征解 › PuzzleUp 20090812

到处瞎逛 发表于 2009-8-12 20:04:51

PuzzleUp 20090812

A,B,C,D,E五人用一条船过河。
船最多一次乘坐两人。
单独乘坐过河所需要的时间：A ：11分钟，B：7分钟，C：4分钟，D：2分钟，E：1分钟。
两个人乘坐时所需要为两个单独过河所需时间之差。
例如：
按如下秩序过河：AB,A,AC,B,BD,C,CE ，则他们所需的时间为41分钟：
(4+11+7+7+5+4+3=41)

问最短多少时间能过使得所有的人都过河。

282842712474 发表于 2009-8-12 20:16:45

假设是同一个人依次把船开回来，那么最少的时间为：
11-2+7-2+4-2+2-1+2*3=23分钟
以及11-1+7-1+4-1+2-1+1*3=23

nlrte13 发表于 2009-8-12 21:08:15

2 + 2 + 4 + 3 + 7 + 4 = 22

nlrte13 发表于 2009-8-12 21:19:42

{ 1, 2, 4, 7, 11 } { }
1
{ 4, 7, 11 } { 1, 2 }
1
{ 1, 4, 7, 11 } { 2 }
4
{ 1, 4 } { 2, 7, 11 }
2
{ 1, 2, 4 } { 7, 11 }
2
{ 1 } { 2, 4, 7, 11 }
2
{ 1, 2 } { 4, 7, 11 }
1
{ } { 1, 2, 4, 7, 11 }
1 + 1 + 4 + 2 + 2 + 2 + 1 = 13

mathe 发表于 2009-8-12 21:46:49

这个计算机求解很简单.是一个图论问题.
其中状态数目(图的顶点数目)为$2^6=64$(5个人以及船的分布).
而每个顶点最多发出$C_5^2=10$条边.
于是问题就是一个最短路径问题.

mathe 发表于 2009-8-13 08:12:29

Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,2,B}{1}
{11,7}{4,2,1,B}
{11,7,2,B}{4,1}
{2}{11,7,4,1,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,2,B}{1}
{11,7}{4,2,1,B}
{11,7,1,B}{4,2}
{1}{11,7,4,2,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,2,B}{1}
{4,2}{11,7,1,B}
{4,2,1,B}{11,7}
{4}{11,7,2,1,B}
{4,2,B}{11,7,1}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,2,B}{1}
{4,2}{11,7,1,B}
{4,2,1,B}{11,7}
{4}{11,7,2,1,B}
{4,1,B}{11,7,2}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,2,B}{1}
{4,2}{11,7,1,B}
{4,2,1,B}{11,7}
{2}{11,7,4,1,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,2,B}{1}
{4,2}{11,7,1,B}
{4,2,1,B}{11,7}
{1}{11,7,4,2,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,1,B}{2}
{11,7}{4,2,1,B}
{11,7,2,B}{4,1}
{2}{11,7,4,1,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,1,B}{2}
{11,7}{4,2,1,B}
{11,7,1,B}{4,2}
{1}{11,7,4,2,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,1,B}{2}
{4,1}{11,7,2,B}
{4,2,1,B}{11,7}
{4}{11,7,2,1,B}
{4,2,B}{11,7,1}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,1,B}{2}
{4,1}{11,7,2,B}
{4,2,1,B}{11,7}
{4}{11,7,2,1,B}
{4,1,B}{11,7,2}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,1,B}{2}
{4,1}{11,7,2,B}
{4,2,1,B}{11,7}
{2}{11,7,4,1,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,4}{2,1,B}
{11,7,4,1,B}{2}
{4,1}{11,7,2,B}
{4,2,1,B}{11,7}
{1}{11,7,4,2,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,2}{4,1,B}
{11,7,2,1,B}{4}
{11,7}{4,2,1,B}
{11,7,2,B}{4,1}
{2}{11,7,4,1,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,2}{4,1,B}
{11,7,2,1,B}{4}
{11,7}{4,2,1,B}
{11,7,1,B}{4,2}
{1}{11,7,4,2,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,1}{4,2,B}
{11,7,2,1,B}{4}
{11,7}{4,2,1,B}
{11,7,2,B}{4,1}
{2}{11,7,4,1,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Start:
{11,7,4,2,1,B}{}
{11,7,1}{4,2,B}
{11,7,2,1,B}{4}
{11,7}{4,2,1,B}
{11,7,1,B}{4,2}
{1}{11,7,4,2,B}
{2,1,B}{11,7,4}
{}{11,7,4,2,1,B}
Total 16 solutions, distance 13

nlrte13 发表于 2009-8-13 09:03:14

^^ 总借助计算机的话，脑子都不会思考咯~~~

到处瞎逛 发表于 2009-8-13 10:17:35

最短路径问题只能借助计算机啊。

否则你有什么办法能证明你的走法就是最短时间的？

数学是一个严谨的科学，最短路径问题作为一个P/NP现在都没有定论，你就敢说不用借助计算机？光靠推理？现在的问题是怎么用计算机找到最好的算法。而不是你所说的要不要借助计算机的问题。

shshsh_0510 发表于 2009-8-13 11:00:18

数学是一个严谨的科学，最短路径问题作为一个P/NP现在都没有定论，你就敢说不用借助计算机？
楼上的结论是哪里来的？
这个题状态数那么少，理应手推就行的。

数学星空 发表于 2009-8-13 13:56:42

"两个人乘坐时所需要为两个单独过河所需时间之差"应该至少为两人单独所需时间和的平均比较合理哟,时间之差好像不符合现实...不过这样题目难度加大了!

查看完整版本: PuzzleUp 20090812