小学生赶牛过河问题

yigo

有\(n\)头牛过河，每头牛过河时间为\(0<t_1<t_2<...<t_n\)，牧童需要骑一头牛，赶一头牛过河，骑快牛赶慢牛，
过河时间为慢牛过河的时间，过河后还要选择骑一头牛回来赶其他牛过河，直到所有牛过完河，求过完河需要的时间\(T\)的最小值。
我们知道牧童需要过河\(n-1\)次，返回\(n-2\)次，每次需要的时间都对应某一头牛过河的时间，
所以\(T\)的表达式为\(T=t_1x_1+t_2x_2+...+t_nx_n\),且\(x_1+x_2+...+x_n=2n-3\)。
要求\(T\)最小值，首先需要知道\((x_1,x_2,...,x_n)\)的所有解。
现在想知道\((x_1,x_2,...,x_n)\)解的数量\(X_n\)的通项公式，以及解\((x_1,x_2,...,x_n)\)的数值有什么规律。
然后分析总时间取最小值时，哪些方案是必然摒弃的，哪些是需要根据\(t_1,t_2,...,t_n\)的具体值比对的，如果去除需要摈弃的解，仅剩下需要比对的解数\(Y_n\)，\(Y_n\)的通项公式是什么。
返程肯定是选择已过河的牛里的速度最快的牛，这个比较容易证明，我觉得\(X_n\)可能并时不是太必要，\(Y_n\)的通项公式更有意义。

===================
一个求最短时间的递归算法：
\(T_{min}(t_1,t_2,...,t_n)=min(t_i+t_j+T_{min}(t_1,...,t_{j-1},t_{j+1},...,t_n))_{1≤i<j≤n}\)
这个递推是错的，因为第二次过河，河对面已经有一头牛了，不等价于少了一头牛的情况。
看看大家有什么思路，我脑袋都乱了。
===================

小学原本题目是\(n=4,t_1=1,t_2=2,t_3=5,t_4=6\)，
方案一：骑\(1\)牛赶其他所有牛，\(T=2t_1+t_2+t_3+t_4=15\),
方案二：骑\(1\)牛赶\(2\)牛过河，骑\(1\)牛返回，骑\(3\)牛赶\(4\)牛过河，骑\(2\)牛返回，骑\(1\)牛赶\(2\)牛过河，\(T=1t_1+3t_2+0t_3+1t_4=13\)，方案二较快。

做题人生

$n=1$ 时, 总时间 $= t_1$;
$n=2$ 时, 总时间 $= t_2$;
$n=3$ 时, 总时间 $= t_2+t_1+t_3=t_1+t_2+t_3$;
以上无有意义的不同方案
$n=4$ 时, 有意义的方案
方案1: 总时间 $= t_2+t_1+t_3+t_1+t_4=2t_1+t_2+t_3+t_4$;
方案2: 总时间 $= t_2+t_1+t_4+t_2+t_2=t_1+3t_2+t_4$;
$t_{方案1}-t_{方案2} = t_1+t_3-2t_2$, 此值的符号决定了优胜路径的选择.

对于 $n\ge5$ 的情形，我们总是骑 $t_1$， 或有利的时候 $t_2$ 作返程。这里我们用时间来指称对应的牛。 我们认为最优策略如下：

$t_1, t_2$ 均已在彼岸，
1. 若始案发仅剩1头牛$t_k$，那么 $t_1$, $t_k$, 任务完成；
2. 若始发案仅剩2头及以上，令其中最慢的两头为$t_m$ 与 $t_n, (t_m<t_n)$, 如果 $t_1+t_m-2t_2 > 0$, 则骑 $t_1$ 返，$t_m, t_n$ 一起渡河，骑 $t_2$ 返，$t_1, t_2$ 渡河；反之则骑 $t_1$ 返，$t_n, t_1$ 渡河。

重复此操作至所有牛完成渡河。虽然未经证明，不过感觉此贪心选择的策略应该会获得全局最优解。