c++ - 创建节点并计算汽车的初始位置

Question

在这种情况下，如何使用 C++ 创建代码和算法？

1. 可以从文件中读取的城市(节点)数量有限(最多 6 个)。
2. 城市之间的连接和距离可以手动分配或从文件中读取。
3. 有车可以手动分配路线，起点是城市(节点)。

问题，

1. 如何创建节点并分配节点之间的距离？
2. 如何在节点之间建立连接？
3. 如何在汽车开始移动一段时间后计算汽车的初始点？

我试过城市之间的连接，例如:

    A   B   C   D   
A   0  20   0  20  
B  20   0  20  20  
C  20  20   0  15
D  0    8   9  0

如果两个城市之间有联系，它就有一个值。如果不是，则值为“0”。谢谢，

Answer 1

实现此目的的一种方法是构建连接图。您在这里看到的是相当基本的图形构建。最明显的方法通常是让节点类型带有与其他节点的连接 vector :

struct node;

// "name" may be optional here -- just the name of the road like "A5" or "US 101"
struct connection { 
    std::string name;
    unsigned distance;
    node *destination;
};

struct node { 
    std::string name;
    std::vector<connection> connections;
};

有了这个，建立从一个城镇到另一个城镇的连接就是创建一个包含距离、目的地城市和(可能)道路名称的 connection 对象，然后推送该连接到起始城市的 connections vector 上。目前，这假设每个 connection 都是“简单的”——您走上一条直接通往目的地的道路(这听起来足以满足您的需求)。在大多数情况下，您还希望它们是对称的，因此当/如果您添加从 X 到 Y 的连接，您还需要添加从 Y 到 X 的类似连接。

在现实生活中，连接可能需要沿途切换道路，因此您可能有一些无名节点，它们仅表示(例如)高速公路 X 与高速公路 Y 的交汇处，(尽管它可能也不是无名的 - “X 和 Y 的交界处”可能是一个非常好的名字)所以你必须穿过几个节点才能从某个点 A 到达某个点 B。

除非您将此作为练习，否则您可能需要查看 Boost Graph Library .它不仅有助于构建像这样的基本图表，而且还有助于找到从一个城镇到另一个城镇的路线，即使这两个城镇没有直接连接。

就汽车的位置而言，很大程度上取决于您是否只想计算特定距离，或者(例如)您是否想要一个完整的模拟，您可以在其中做一些事情，比如从从 A 点到 B 点，发现特定道路上的交通量超过某个阈值，如果交通量太大，可能会找到替代路线等。首先，这是根据时间和速度计算距离的简单问题，然后步行通过他们路线上的节点，直到你走过那段距离。对于后者，您可能会添加一个 car 类，其中每辆车都知道自己的当前位置和目的地。然后，您会每隔一段时间遍历汽车列表，并让每辆汽车更新其当前位置(例如，每模拟分钟一次)。

如果您做一些研究，您很快就会发现有很多算法可以用于在图中查找路线(例如，给定图 X，找到从 A 到 B 的最短路线)，查找是否所有节点连接等