アルゴリズム設計マニュアルを読んでいます。
別のアイデアは、接続がサイクルの早期終了などの問題を引き起こさない最も近いエンドポイントのペアを繰り返し接続することです。各頂点は、独自の単一の頂点チェーンとして始まります。すべてをマージすると、すべてのポイントを含む 1 つのチェーンになります。最後の 2 つのエンドポイントを接続すると、サイクルが得られます。この最近接ペア ヒューリスティックの実行中の任意のステップで、マージに使用できる一連の単一の頂点と頂点から切り離されたチェーンが得られます。疑似コードでは: ClosestPair(P) n をセット P 内の点の数とします。 i = 1 から n − 1 の場合、d = ∞ を行います。 ) ≤ d の場合、sm = s、tm = t、および d = dist(s, t) Connect (sm,
なぜ d = ∞ なのですか? 最寄りの近隣ツアーについて説明してもらえますか？この本を読む前に、どの本を読むべきですか?