贪心算法交换证明（算法设计，第 4 章，6E）
Greedy Algorithm Exchange Proof (Algorithm Design, Chapter 4, 6E)
翻阅这本书，遇到了这个问题：
6. Your friend is working as a camp counselor, and he is in charge of
organizing activities for a set of junior-high-school-age campers. One of
his plans is the following mini-triathalon exercise: each contestant must
swim 20 laps of a pool, then bike 10 miles, then run 3 miles. The plan is
to send the contestants out in a staggered fashion, via the following rule:
the contestants must use the pool one at a time. In other words, first one
contestant swims the 20 laps, gets out, and starts biking. As soon as this
first person is out of the pool, a second contestant begins swimming the
20 laps; as soon as he or she is out and starts biking, a third contestant
begins swimming . . . and so on.)
Each contestant has a projected swimming time (the expected time it
will take him or her to complete the 20 laps), a projected biking time (the
expected time it will take him or her to complete the 10 miles of bicycling),
and a projected running time (the time it will take him or her to complete
the 3 miles of running). Your friend wants to decide on a schedule for the
triathalon: an order in which to sequence the starts of the contestants.
Let’s say that the completion time of a schedule is the earliest time at
which all contestants will be finished with all three legs of the triathalon,
assuming they each spend exactly their projected swimming, biking, and
running times on the three parts. (Again, note that participants can bike
and run simultaneously, but at most one person can be in the pool at
any time.) What’s the best order for sending people out, if one wants the
whole competition to be over as early as possible? More precisely, give
an efficient algorithm that produces a schedule whose completion time
is as small as possible.
只需摆弄数字，答案就很明显了，答案是贪婪算法，按骑行时间 + 运行 时间的降序排序。
我遇到的困难是我的老师提到这是使用交换的良好实践 argument/proof，但我看不出如何使用它（或其他任何东西）来证明这个答案正确。
这个问题在网上其他地方得到了回答（我在好几个地方看到了这个变体），但据我所知答案是错误的
注：bi/ri代表bike/ride选手i
的时间
我们通过交换论证证明了这一点。考虑任何最优解，并假设它不使用这个
命令。那么最优解必须包含两个参赛者i和j，这样j就直接被送出去了
在 i 之后，但 bi + ri < bj + rj 。我们将这样的一对 (i,j) 称为反转。考虑通过交换 i 和 j 的顺序获得的解决方案。在这个交换的时间表中，j 比 he/she 过去更早完成。此外，在交换计划中，i 在 j 先前离开池时离开池；但是因为 bi + ri < bj + rj ，我在交换后的计划中比 j 在之前的计划中完成得更快。
我的问题是粗体，没有理由假设我和 j 有相同的游泳时间，因此当 j 离开便便时我不会离开游泳池；
我错了吗，这个答案在某种程度上是正确的？如果是，为什么？如果不是，正确的 proof/argument 会是什么样子？
我同意你的看法，即这个答案夸大了你用粗体提到的内容。我只能找到发布在 https://www.coursehero.com/file/9692310/HW4S12sol1/ 的这篇文章及其镜像。幸运的是，我们不需要这个假设来证明贪心算法在交换参数下是最优的。
为了证明这一点，我们将计算每个参赛者在每种情况下所花费的时间，并证明交换只会减少 i 或最后一个的时间j完成。
我们可以假设 WLOG i 或 j 中的第一个从时间 0 开始。
在具有反转的最佳时间表中（我先走）：
Contestant
Time Finished
i
toi = si + bi + ri
j
toj = si + sj + bj + rj
因为 bi + ri < bj + rj，很明显toi < toj 即j在这种情况下最后完成。
在交换的时间表中（j 先行）：
Contestant
Time Finished
i
tsi = si + sj + bi + ri
j
tsj = sj + bj + rj
我们不知道两者中哪一个最后完成，但我们可以证明 tsi < toj 和 tsj < toj 这意味着无论哪种方式，最后一位参赛者完成的时间都减少了。
因此，交换这个反转只会提高 i 或 j 的最后一名选手的完成时间，并继续交换贪心解的最优解不会产生次优解。因此贪婪的解决方案是最优的。
翻阅这本书，遇到了这个问题：
6. Your friend is working as a camp counselor, and he is in charge of
organizing activities for a set of junior-high-school-age campers. One of
his plans is the following mini-triathalon exercise: each contestant must
swim 20 laps of a pool, then bike 10 miles, then run 3 miles. The plan is
to send the contestants out in a staggered fashion, via the following rule:
the contestants must use the pool one at a time. In other words, first one
contestant swims the 20 laps, gets out, and starts biking. As soon as this
first person is out of the pool, a second contestant begins swimming the
20 laps; as soon as he or she is out and starts biking, a third contestant
begins swimming . . . and so on.)
Each contestant has a projected swimming time (the expected time it
will take him or her to complete the 20 laps), a projected biking time (the
expected time it will take him or her to complete the 10 miles of bicycling),
and a projected running time (the time it will take him or her to complete
the 3 miles of running). Your friend wants to decide on a schedule for the
triathalon: an order in which to sequence the starts of the contestants.
Let’s say that the completion time of a schedule is the earliest time at
which all contestants will be finished with all three legs of the triathalon,
assuming they each spend exactly their projected swimming, biking, and
running times on the three parts. (Again, note that participants can bike
and run simultaneously, but at most one person can be in the pool at
any time.) What’s the best order for sending people out, if one wants the
whole competition to be over as early as possible? More precisely, give
an efficient algorithm that produces a schedule whose completion time
is as small as possible.
只需摆弄数字，答案就很明显了，答案是贪婪算法，按骑行时间 + 运行 时间的降序排序。
我遇到的困难是我的老师提到这是使用交换的良好实践 argument/proof，但我看不出如何使用它（或其他任何东西）来证明这个答案正确。
这个问题在网上其他地方得到了回答（我在好几个地方看到了这个变体），但据我所知答案是错误的
注：bi/ri代表bike/ride选手i
的时间我们通过交换论证证明了这一点。考虑任何最优解，并假设它不使用这个 命令。那么最优解必须包含两个参赛者i和j，这样j就直接被送出去了 在 i 之后，但 bi + ri < bj + rj 。我们将这样的一对 (i,j) 称为反转。考虑通过交换 i 和 j 的顺序获得的解决方案。在这个交换的时间表中，j 比 he/she 过去更早完成。此外，在交换计划中，i 在 j 先前离开池时离开池；但是因为 bi + ri < bj + rj ，我在交换后的计划中比 j 在之前的计划中完成得更快。
我的问题是粗体，没有理由假设我和 j 有相同的游泳时间，因此当 j 离开便便时我不会离开游泳池；
我错了吗，这个答案在某种程度上是正确的？如果是，为什么？如果不是，正确的 proof/argument 会是什么样子？
我同意你的看法，即这个答案夸大了你用粗体提到的内容。我只能找到发布在 https://www.coursehero.com/file/9692310/HW4S12sol1/ 的这篇文章及其镜像。幸运的是，我们不需要这个假设来证明贪心算法在交换参数下是最优的。
为了证明这一点，我们将计算每个参赛者在每种情况下所花费的时间，并证明交换只会减少 i 或最后一个的时间j完成。
我们可以假设 WLOG i 或 j 中的第一个从时间 0 开始。
在具有反转的最佳时间表中（我先走）：
| Contestant | Time Finished |
|---|---|
| i | toi = si + bi + ri |
| j | toj = si + sj + bj + rj |
因为 bi + ri < bj + rj，很明显toi < toj 即j在这种情况下最后完成。
在交换的时间表中（j 先行）：
| Contestant | Time Finished |
|---|---|
| i | tsi = si + sj + bi + ri |
| j | tsj = sj + bj + rj |
我们不知道两者中哪一个最后完成，但我们可以证明 tsi < toj 和 tsj < toj 这意味着无论哪种方式，最后一位参赛者完成的时间都减少了。
因此，交换这个反转只会提高 i 或 j 的最后一名选手的完成时间，并继续交换贪心解的最优解不会产生次优解。因此贪婪的解决方案是最优的。