0と1で構成される長さ10のシーケンスがたくさんあります。例えば：
1010100000
1011000001
1011100010
1100000100
0011111011
電気ショック療法
各列に0が集合的に含まれるシーケンスを見つけたいと思います。たとえば、アルゴリズムは次の2つを返す必要があります。
1100000100
0011111011
そしてこれらの3つ：
1100110000
0011111111
1111001111
等
このためのアルゴリズムはありますか？
あなたが説明している問題は、すべての解を見つけたい正確なカバー問題の制限されたケースです。この問題の一般的なバージョンは NP 困難であるため、このより大きな問題に対する既知の効率的な一般的なアルゴリズムはありません。
考えられるすべての解を見つけるには、ビットベクトルのすべてのサブセットを一覧表示して、各列に 0 が 1 つだけ含まれているかどうかをテストします。バックトラッキング検索アルゴリズムを実装してすべてのサブセットを選択することを検討することもできますが、これは機能しない可能性のあるパス (たとえば、同じ列に 0 を持つ 2 つのビットベクトルを含むパス) の検索を停止します。必要に応じて、この一般的な問題に対するすべてのソリューションを一覧表示するように特別に設計された、ダンシング リンク アルゴリズムを実装してみてください。
お役に立てれば！