2

在这种情况下，如何在 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

如果 2 个城市之间存在连接，则它具有值。如果不是，则值为“0”。谢谢，

4

1 回答 1

0

一种方法是构建连接图。您在这里看到的是相当基本的图形构建。最明显的方法通常是让节点类型具有与其他节点的连接向量：

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起始城市的向量上。目前，这假设每一个connection都是“简单的”——你走上一条直接通往目的地的道路（这听起来足以满足你的需求）。在大多数情况下，您还希望它们是对称的，因此当/如果您添加从 X 到 Y 的连接时，您还需要添加从 Y 到 X 的类似连接。

在现实生活中，连接可能需要沿途切换道路，因此您可能有一些无名节点，它们仅代表（例如）高速公路 X 与高速公路 Y 的交汇点，（尽管它也可能不是无名的——“ X 和 Y" 可能是一个非常好的名称），因此您必须经过多个节点才能从某个点 A 到达某个点 B。

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

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

如果你做一些研究，你会很快发现有很多算法可以解决诸如在图中查找路线（例如，给定图 X，找到从 A 到 B 的最短路线），查找是否所有节点都连接等

于 2013-01-26T14:49:00.633 回答