次のステートメントは私を混乱させます。
最近隣ルールは、ポイント (pi,pj) の各ペアを最大 2 回 (ツアーに pi を追加するときに 1 回、pj を追加するときに 1 回) 調べるため、かなり効率的です。
次のテキスト ブロックからのものです (青色で強調表示)。
点のペアが 2 番目と 3 番目であるとします (2,3) その点のペアはどのように 2 回見られるのでしょうか? 2 番目を追加するときは、2 番目を 1 番目に最も近い未訪問ポイントに設定し、3 番目を追加するときは、3 番目が 2 番目に最も近いと見なします。彼らがその点のペアを見ているのを見ることができる唯一の点です。
誰か説明できますか？
彼らはこれをより数学的に見ています。ポイントのセットがあり、ポイントがツアーに追加されるたびに、セット全体が最適な候補を求めて訪問されます。ポイントがツアーに追加されてもセットは変更されず、ポイントは訪問済みとしてフラグが立てられます。したがって、すべてのペアが 2 回考慮されます。
実際にそのアルゴリズムを実装する場合は、おそらく未訪問のポイントのセットを使用し、各反復後にこのセットを更新します。現在、すべてのペアは 1 回だけ訪問されますが、実装によっては、すべてのペアを 2 回訪問するよりも多かれ少なかれ時間がかかる可能性があるセットを変更するという犠牲を払っています。
説明には「せいぜい2回」と書かれています。
すべてのペアが2回検査されることを期待している場合、「せいぜい」という言葉はありません。「最大2回」の反例は、1回だけ検査されるペアではなく、3回以上検査されるペアです。