algorithm - このパズルで予想される手数は?

Question

nサイズxのバイナリ行列nが与えられます。

各ステップで、関数は、指定された行列の各行と各列に少なくとも 1 つの があるかどうかをチェックします1。そうでない場合は、純粋にランダムな座標が選択されます。たとえばi, j、 where 1 <= i、 、が保持されているかのようにj <= nマークされます。101

このプロセスは、行列の各行と列に少なくとも 1 つの が含まれるまで繰り返されます1。

このアルゴリズムの「予想される手数」を教えてください。

Answer 1

ヒューリスティックを使用し、ランダム フィールドでシミュレートして、おおよその出力を得ることができます。
これに対して出力ファイルを作成できます。これにより、大量のデータをシミュレートして、おおよその答えが最適化されたものに近いことを確認できます。