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

これを行う 1 つの方法は、接続のグラフを作成することです。ここで見ているのは、かなり基本的なグラフ作成です。最も明白な方法は、通常、他のノードへの接続のベクトルを持つノード タイプを使用することです。

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が「単純」であることを前提としています。つまり、目的地に直接向かう 1 本の道を通るということです (これで十分なように思えます)。ほとんどの場合、これらも対称にする必要があるため、X から Y への接続を追加する場合は、Y から X への同様の接続も追加する必要があります。

実際には、接続には途中で道路を切り替える必要がある場合があるため、(たとえば) 高速道路 X と高速道路 Y のジャンクションを表す名前のないノードがいくつかある場合があります (ただし、名前のないノードではない可能性もあります)。 X と Y" という名前がぴったりかもしれません)、ある地点 A からある地点 B に到達するには、いくつかのノードを経由する必要があります。

これを演習として行っている場合を除き、Boost Graph Libraryを確認することをお勧めします。このような基本的なグラフを作成するだけでなく、2 つの町が直接接続されていなくても、ある町から別の町へのルートを見つけるなどの作業にも役立ちます。

車の位置に関する限り、特定の距離を計算するだけを見ているのか、それとも (たとえば) 地点 A からポイント B で、特定の道路の交通量が一定のしきい値を超えていることを確認する、交通量が多すぎる場合は別のルートを見つけるなど。あなたがその距離を移動するまで、彼らのルート。car後者の場合は、各車が独自の現在位置と目的地を認識しているクラスを追加することになるでしょう。次に、一定間隔で車のリストを調べて、それぞれが現在の位置を更新するようにします (たとえば、シミュレートされた 1 分ごとに 1 回)。

少し調べてみると、グラフ内のルートを見つける (たとえば、グラフ X が与えられた場合、A から B への最短ルートを見つける)、すべてのノードが接続など

于 2013-01-26T14:49:00.633 に答える