优化旅行和从工厂收集单位的成本
optimised cost to travel and collect units form factories
问题陈述
有 'n' 家工厂，位于 arr[i]。入口位于“0”，出口 ID 位于 'exit-pos'。从一个地方到另一个地方的移动时间就是两者之间的距离。
每个工厂需要 'processing' 时间（所有工厂都一样）来处理。您必须从 '0' 开始，从 'exit-pos' 退出。
另外你必须生产'n'个单位，每个工厂只能生产1个单位。沿途您需要参观每个工厂并下达生产订单。那么需要‘加工’时间才能生产出来。您可以等待那个时间让单位生产并继续前进。或者你可以访问其他工厂给他们订单。后面需要再去工厂取货。
行进时间是两地之间的距离。
问题：你需要说出生产'n'个单位并收集它们的最短时间。您的旅程从“0”开始，到 'end-pos' 结束。
输入：
number of units required to produce = number of factories = n
the location of factories in a array = arr
the exit position = ext-pos
the processing time at each unit (it is same for each factory) = processing-time.
我的做法
我在测试时遇到了这个问题。测试已提交，但不幸的是没有给出答案。在测试过程中，我尝试使用递归的方法。它考虑了 'items-collected'、'time'、'factory - position'。它失败了。进入了时间循环
任何关于问题清晰度的建议/问题都可以随时发表评论。
谢谢
更新：0 < arrr[i]（出厂时间）< exiPos
使用带有 A* 搜索的策略来解决它
我已将解决方案上传到 GitHub repo。
可以看到一个live demo here.
以下是 README 的内容和截图：
解决方案总结
自 0 < arr[i] < exit-pos 以来，我们总是从第一个 工厂开始，在最后一个 工厂结束。添加剩余时间是微不足道的。
该解决方案包括三种不同的算法，可通过下拉菜单进行选择：
1。 Dijkstra 算法（最差）
探索所有状态并找出到达最终状态的最短时间：
- 一个状态由当前的位置和所有工厂的状态组成 ？).
- 从每个状态 等待 直到生产完成，向左（向开始）移动或向右（走向出口）。
- 显然使用 Dijkstra's algorithm.
2。 A*搜索算法
A* algorithm 与 Dijkstra 的算法基本相同，但使用启发式算法来支持更有希望的节点。
使用的启发式无需等待即可计算出最小行驶距离。它计算到最左边未完成的工厂和从那里到出口的时间。
改进显着（即使是小输入）。
3。专业 A*（最佳）
此版本使用与之前相同的搜索，但限制正在探索的新状态：
一旦您从右转转向左转，它遵循的策略是完成您剩下的一切。并且只允许在最左边未完成的工厂等待。
- 你可以向左移动，只有当你还剩下一个未完成的工厂时。
- 你可以等，只要你在最左边的未完成工厂。
- 您可以向右移动，前提是您要移动到未触及的区域或您不正确的所有内容都已完成。
- 如果您在上一回合向左移动，请尽可能继续向左移动。
- 如果你上个回合向左移动，不能再向左移动，你只能等待。
为什么这行得通（上面列出的参考文献）？
- 否则向左移动没有任何意义。只是不要。
- 无论如何你都得回到最左边的未完工工厂。在向右返回的路上，您将向右穿过所有工厂。所以我们选择只在最左边等待，因为在别处等待可以转化为在这里等待。
- 向右移回到接触区域不会更快，因为您必须回到最左边（参见 2.）。要么一开始向右走得更远，但只有当你在左边走完后才向右转回去。
- 你在转身的时候选择了回去。在转弯之前向右移动更远的距离来探索其他选项。
- 同 4.
性能
这些是此输入的粗略时间：
n = 14
arr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
processingTime = 15
Algorithm
Time
Dijkstra
~ 3000 ms
A*
~ 100 ms
Strategy
~ 10 ms
如何找到这个解决方案
首先我选择了可视化解决方案并使用 Dijkstra 算法求解。
检查各种输入的路径后，我注意到“策略”解决方案中描述的模式：向右走，转身然后完成这块工厂。
可能的改进
可以采取策略并将工厂数组分块。
每个区块 [a1, a2, ..., an] 需要 travelTime + waitTime = [3 * (an-a1)] + [min(0, processingTime - 2 * (an-a1))] 时间才能完成。
在区块 [a1, ..., an] 和 [b1, ..., bm] 之间移动需要 b1 - an 时间。
现在必须确定块，使总时间最小化。
解决这个问题我玩得很开心。
而且我只能推荐 可视化 事物。
请注意：编码前请三思。拿一张纸，画出没有电脑你会做什么。
问题陈述 有 'n' 家工厂，位于 arr[i]。入口位于“0”，出口 ID 位于 'exit-pos'。从一个地方到另一个地方的移动时间就是两者之间的距离。
每个工厂需要 'processing' 时间（所有工厂都一样）来处理。您必须从 '0' 开始，从 'exit-pos' 退出。
另外你必须生产'n'个单位，每个工厂只能生产1个单位。沿途您需要参观每个工厂并下达生产订单。那么需要‘加工’时间才能生产出来。您可以等待那个时间让单位生产并继续前进。或者你可以访问其他工厂给他们订单。后面需要再去工厂取货。
行进时间是两地之间的距离。
问题：你需要说出生产'n'个单位并收集它们的最短时间。您的旅程从“0”开始，到 'end-pos' 结束。
输入：
number of units required to produce = number of factories = n
the location of factories in a array = arr
the exit position = ext-pos
the processing time at each unit (it is same for each factory) = processing-time.
我的做法 我在测试时遇到了这个问题。测试已提交，但不幸的是没有给出答案。在测试过程中，我尝试使用递归的方法。它考虑了 'items-collected'、'time'、'factory - position'。它失败了。进入了时间循环
任何关于问题清晰度的建议/问题都可以随时发表评论。 谢谢
更新：0 < arrr[i]（出厂时间）< exiPos
使用带有 A* 搜索的策略来解决它
我已将解决方案上传到 GitHub repo。
可以看到一个live demo here.
以下是 README 的内容和截图：
解决方案总结
自 0 < arr[i] < exit-pos 以来，我们总是从第一个 工厂开始，在最后一个 工厂结束。添加剩余时间是微不足道的。
该解决方案包括三种不同的算法，可通过下拉菜单进行选择：
1。 Dijkstra 算法（最差）
探索所有状态并找出到达最终状态的最短时间：
- 一个状态由当前的位置和所有工厂的状态组成 ？).
- 从每个状态 等待 直到生产完成，向左（向开始）移动或向右（走向出口）。
- 显然使用 Dijkstra's algorithm.
2。 A*搜索算法
A* algorithm 与 Dijkstra 的算法基本相同，但使用启发式算法来支持更有希望的节点。
使用的启发式无需等待即可计算出最小行驶距离。它计算到最左边未完成的工厂和从那里到出口的时间。
改进显着（即使是小输入）。
3。专业 A*（最佳）
此版本使用与之前相同的搜索，但限制正在探索的新状态：
一旦您从右转转向左转，它遵循的策略是完成您剩下的一切。并且只允许在最左边未完成的工厂等待。
- 你可以向左移动，只有当你还剩下一个未完成的工厂时。
- 你可以等，只要你在最左边的未完成工厂。
- 您可以向右移动，前提是您要移动到未触及的区域或您不正确的所有内容都已完成。
- 如果您在上一回合向左移动，请尽可能继续向左移动。
- 如果你上个回合向左移动，不能再向左移动，你只能等待。
为什么这行得通（上面列出的参考文献）？
- 否则向左移动没有任何意义。只是不要。
- 无论如何你都得回到最左边的未完工工厂。在向右返回的路上，您将向右穿过所有工厂。所以我们选择只在最左边等待，因为在别处等待可以转化为在这里等待。
- 向右移回到接触区域不会更快，因为您必须回到最左边（参见 2.）。要么一开始向右走得更远，但只有当你在左边走完后才向右转回去。
- 你在转身的时候选择了回去。在转弯之前向右移动更远的距离来探索其他选项。
- 同 4.
性能
这些是此输入的粗略时间：
n = 14
arr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
processingTime = 15
| Algorithm | Time |
|---|---|
| Dijkstra | ~ 3000 ms |
| A* | ~ 100 ms |
| Strategy | ~ 10 ms |
如何找到这个解决方案
首先我选择了可视化解决方案并使用 Dijkstra 算法求解。
检查各种输入的路径后，我注意到“策略”解决方案中描述的模式：向右走，转身然后完成这块工厂。
可能的改进
可以采取策略并将工厂数组分块。
每个区块 [a1, a2, ..., an] 需要 travelTime + waitTime = [3 * (an-a1)] + [min(0, processingTime - 2 * (an-a1))] 时间才能完成。
在区块 [a1, ..., an] 和 [b1, ..., bm] 之间移动需要 b1 - an 时间。
现在必须确定块，使总时间最小化。
解决这个问题我玩得很开心。
而且我只能推荐 可视化 事物。
请注意：编码前请三思。拿一张纸，画出没有电脑你会做什么。