オブジェクトの 2 次元配列があります。各オブジェクトは、常に何らかの (可変) スコアを持っています (つまり、時間 t でのオブジェクトのスコアは、時間 t+1 でのオブジェクトのスコアであるとは限りません)。隣のオブジェクトよりもスコアが高いオブジェクトを複製し、その複製を隣の場所に配置する最も効率的なアルゴリズムを見つけたいと考えています。1
私の最初の衝動は単純な解決策でした：
- 配列のコピーを作成する
- 「changeWasMade」フラグを false に設定します
- すべての位置を循環 p
- スコアをすべての近隣 n と比較する
- スコア (p) > スコア (n) の場合、コピーしたグリッドの n を p のコピーに置き換え、「changeWasMade」を true に設定します。
- 「changeWasMade」の場合、元のグリッドを破棄し、コピーを新しいオリジナルとして使用して繰り返します。それ以外の場合は、コピーを返します
ただし、nxn 配列の場合、これは O(n 4 ) (n 2チェックの n 2回の反復) のように見えますが、これはかなり遅いように思えます。私のアルゴリズムの知識はかなり貧弱なので、これを行うためのより迅速な方法があるかどうか尋ねるのが賢明だと思いました.
アップデート
置換の「パス」を作成してから、新しく作成された (つまり、クローン化された) すべてのオブジェクトが隣接オブジェクトの最高スコア (つまり、極大値) を持っていることを確認する方が速いかもしれないと思いました。もしそうなら、正しいことが起こった - そうでないなら、それらを最高スコアの隣人のコピーに置き換えます。これにより、おそらく必要な反復が削減されます (ただし、すべてを正しく維持するには、適切な簿記が必要になります!) - もっと迅速な方法はありますか?
**脚注**
- (文脈上、「The Quantum Thief」を読んだ人のために、これは冒頭のページで説明されている監獄の設定です)