构建最优铁路的算法

Question

我在大学接到了以下任务。

任务

有几个数据块：

1. Data：它存储轨道的类型、成本以及给定成本下该类型轨道类型的轨道数量。 轨道类型： { L1, L2, L3, L4 // 直线长度 1-4 T4, T8 // 以 pi/4, pi/8 角度转动 B1 //桥梁，用于在另一条道路上修建一条道路 }
2. Route：它存储了平面上各点的坐标以及这些点的成本。

道路建成后，道路的利润按以下方式计算。 计算道路每个点的成本：

v_i / (1 + d_ij)

，其中

d_ij

是从路径元素的交汇点到

v_i

的最小距离。 最终利润计算为：

F = Points_sum - Road_cost

.

要修最赚钱的路。

输入示例

DATA
L1 42 47
L2 35 41
L3 30 5
L4 19 19
T4 23 45
T8 6 6
B1 2 28
/
ROUTE
0 0 61
10.3 1.0 -17.7
/
ORDER
L1 1
T4 1
T4 1
L1 1
T4 1
T4 1
L1 1
T4 1
T4 1
L1 1
T4 1
T4 1
/

输入描述

数据块：

这定义了铁路类型、成本以及可用于建造的数量。

这里：

L1代表长度为1的直轨，成本为42，可提供47条。 T4代表角度为π/4的转向轨，售价23，有45个。 其他轨道类型（L2、L3 等）遵循相同的逻辑。

路线块：

这定义了平面上具有相应值（或“点的成本”）的点。 示例：0 0 61

这里：

点 (0, 0) 的值为 61。 点 (10.3, 1.0) 的值为 -17.7

订购区块：

这定义了修建道路时使用的铁轨的顺序。 这些铁轨的顺序指定了道路的建造方式。 示例：L1 1 T4 1 T4 1 L1 1 T4 1 T4 1 L1 1 T4 1 T4 1 L1 1 T4 1 T4 1

这里：

L1 1 表示使用长度为1 的直轨。 T4 1 表示使用角度 π/4 的转轨。

我的想法

1. 通常的暴力破解（对于检查解决方案很有用）
2. 我想训练 RL 模型，因为公式与 RL 问题非常相似
3. 我正在考虑使用有序迎风方法（下面的链接）。看起来制作听起来很相似，但我不知道如何使用它。 https://math.berkeley.edu/~sethian/2006/Explanations/ordered_upwind_explain.html

Answer 1

这个问题有很多细节需要实现，但问题的核心是找到一组连接所有点的最佳“道路”。

这是最小生成树（MST）问题。

https://en.wikipedia.org/wiki/Minimum_spanning_tree

您需要构建一个将每个点与其他点连接起来的图表，然后通过构建该链接的成本估计来对每个链接进行加权。您可以首先通过每个点对之间的毕达哥拉斯距离估计权重。使用任何图论库来查找 MST。

按照 MST 建议的路线建设铁路。

将使用的每个链接的成本估算更新为根据所有详细信息计算出的实际成本。

在更新的成本图上重新运行 MST 方法。 如果 MST 发生显着变化，则重复直到变化变得不显着。

希望这能快速收敛到最佳或接近最佳的解决方案。