具有多个依赖性的任务杂耍者，其中任务长度取决于先前的任务
我有一个任务 Z，只能完成一次任务 X 或 任务Y已完成。另外：
% 任务 Z 的长度取决于 X 或 Y 中的哪一个完成：
% 如果任务 X 完成，任务 Z 需要 4 小时
% 如果任务 Y 完成，任务 Z 需要 7 小时
% 任务 X 需要 5 小时完成
% 任务 Y 需要 3 小时才能完成
% 任务 X 和任务 Y 是互斥的：你不能同时做这两个任务（但那是 可能无关紧要，因为这永远不会是最佳的）
问题：我能最快完成任务 Z 是多少？
在这种情况下，答案显然是 9 小时（X 然后 Z），但我真正的 问题有很多这样的情况。
任务杂耍者可以帮助我吗？可以用别的工具吗？附加说明：
% 这是“旅行商问题”的延伸，因此 NP-困难。我很高兴有一个好的但非最佳的解决方案。
% 在实际问题中，有些任务是具有里程碑意义的“里程碑” 非负值。我的目标是最大化这些的总和 价值观。不过，我很乐意在最短的时间内解决问题 问题先。此外，这些值对于所有 里程碑，简化问题。
注意：由于 Mathematica 有一个功能可以快速（但不是最佳）解决 TravelingSalesman 问题，因此将其添加为标签。
I have a task Z that can only be completed once either task X or
task Y is completed. Also:
% The length of task Z depends on which of X or Y is completed:
% If task X is completed, task Z takes 4 hours
% If task Y is completed, task Z takes 7 hours
% Task X takes 5 hours to complete
% Task Y takes 3 hours to complete
% Task X and task Y are exclusive: you can't do both (but that's
probably irrelevant, since that would never be optimal)
The question: what's the quickest I can complete task Z?
In this case, the answer is obviously 9 hours (X then Z), but my real
problem has many cases like this.
Can taskjuggler help me? Can another tool? Additional notes:
% This is an extension of the "traveling salesman problem", and thus
NP-hard. I'd be happy with a good-but-non-optimal solution.
% In the actual problem, some tasks are "milestones" which have a
non-negative value. My goal is to maximize the sum of these
values. However, I'm more than happy to solve the minimum time
problem first. Additionally, the values may be equal for all
milestones, simplifying the problem.
NB: since Mathematica has a function to quickly (but non-optimally) solve the TravelingSalesman problem, adding it as a tag.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您应该研究一下动态规划。基本上，您将重用子问题的解决方案来构建整个问题的解决方案。您可以使用 Mathematica 或大多数编程语言来完成此操作。
You should look into dynamic programming. Basically, you'll reuse the solutions to subproblems to build a solution for your whole problem. You can do this in Mathematica or most any programming language.