3

これは私の初めてのC++プログラミングであり、このクラスが与えられた場合に幅優先探索をコーディングするように求められました

class route {

  friend ostream& operator<<(ostream& os, const route& p);

 public:

  route(const string& startPlayer);
  int getLength() const { return links.size(); };
  void addConnect(const sport& s, const string& player);
  void removeConnect();
  const string& getLastPlayer() const;

 private:

  struct Connect {
    sport s;
    string player;
    Connect() {}
    Connect(const sport& s, const string& player) : s(s), player(player) {}
  };

  string startPlayer;
  vector<Connect> links;
};

sportstring nameとで構成される構造体int playersです。誰かが私にBFSの作成方法を説明してもらえますか？

前もって感謝します！

編集：

私はBFSのアルゴリズムを理解していますが、Cをプログラミングしたことがあるので、オブジェクト指向プログラミングを理解することは非常に混乱します。このBFSをどこから始めればよいのか、BFSを比較する新しい関数を作成するのでしょうか。start stringと_target string

namespace {

string promptForSPlayer(const string& prompt, const spdb& db)
{
  string response;
  while (true) {
    cout << prompt << " [or <enter> to quit]: ";
    getline(cin, response);
    if (response == "") return "";
    vector<sport> splist;
    if (db.getsplist(response, splist)) return response;
    cout << "It's not here: \"" << response << "\" in the sports database. "
     << "Please try again." << endl;
  }
}

}

int main(int argc, char *argv[])
{
  if (argc != 2) {
    cerr << "Usage: sports" << endl;
    return 1;
  }

  spdb db(argv[1]);

  if (!db.good()) {
    cout << "Failed to properly initialize the spdb database." << endl;
    cout << "Please check to make sure the start files exist and that you have permission to read them." << endl;
    exit(1);
  }

  while (true) {
    string start = promptForSplayer("Player", db);
    if (start == "") break;
    string target = promptForSplayer("Another Player", db);
    if (target == "") break;
    if (start == target) {
      cout << "Good one.  This is only interesting if you specify two different people." << endl;
    } else {
      // replace the following line by a call to your generateShortestPath routine... 
      cout << endl << "No path between those two people could be found." << endl << endl;
    }
  }
  return 0;
}
4

2 に答える 2

4

幅優先検索とは、2 つの質問をすることです

  1. 私は今、どのような状態ですか？
  2. ここからどの州に行くことができますか?

アイデアは、初期状態を持ち、これらの 2 つの質問を継続的に自問することです。

  1. もう州は残っていません。
  2. 目的の状態に到達しました。

BFS は通常、見つけた新しい状態を追加するだけの Queue を使用し、新しい状態を処理して新しい状態をキューの最後に追加したいときはいつでも、キューの先頭からポップします。

于 2011-08-09T02:39:04.077 に答える
0

ルート クラスは、BFS を使用して検索したルートを格納するメカニズムにすぎません。少なくとも私はそう解釈しています。BFS アルゴリズムは、適切なタイミングでルート クラスのメソッドを呼び出すスタンドアロン関数になります。BFS は複数のルートに関する情報を維持する必要があるため、ある種のリストまたはキューに複数のルート オブジェクトを作成する必要があります。BFS の各ステップは、キューから 1 つのルート オブジェクトを取得し、それをコピーして addConnect を呼び出して次の場所に移動し、キューに戻します。目的地に到達するまで繰り返し、BFS 関数からの最短パスを表すルート オブジェクトを返します。

とにかくそのような何か。

于 2011-08-09T05:20:03.967 に答える