M種類の部品からN種類の部品を抽出する効率的なアルゴリズム

問題：
ある製品に必要な部品はN種類あり、倉庫にはM種類の部品がある。
部品を投入して、製品ができるか出来ないかを判断するにはT時間かかる。
できるだけ短期間にN種類の部品を抽出したい。
抽出手順とその作業時間を求めよ
ただし、N<M/10である。

考えたこと
M種類から1つ取り除いた部品を投入してチェックする方法
成功すれば、取り除いた部品は不要な部品、失敗すれば必要な部品と判断できる
従って、MT時間があれば、確実にN種類の部品が抽出できる。

2つずつ取り除いてチェックする方法（改良版）
成功すれば、取り除いた２つの部品は両方とも不要な部品、失敗すれば2つのうち少なくともひとつは必要な部品と判断できる
M/2回のチェックのうち、M/2-N回は成功する。
N<M/10　より、5回に4回はチェックに成功することになり、1つずつ取り除いてチェックするよりも不要部品を効率良く選別できるアルゴリズムといえる。

もっと良いアルゴリズムありますか？

N種類の部品を抽出するのが困難なら、
　N種類を確実に含むM/10種類の部品を抽出するアルゴリズム
でもうれしいです。

質問者からの補足コメント

• 条件、不足してました。
  Nについて：　条件　N<M/10　しか情報がなく、Nの実際の値は未知です。
  
  余裕があれば、「N種類を確実に含む部品の部分集合」のサイズがM/10でなく、
  　３０回程度のチェックでどの程度まで、「N種類を確実に含む部品の部分集合」のサイズを小さくできるか
  も知りたいです。

    補足日時：2022/04/22 19:01

No.2 回答者： masa2211 回答日時： 2022/04/24 08:40

＞Mは2^18程度を想定

質問文補足で
＞３０回程度のチェックで
とあるので、
・O(n)であっても定数項の値が小さいアルゴリズム
ということを想定するなんて無理です。
・Mはかなり小さい　または　O(n)より速い
と解釈するしかないのですけど。
お察しくださいと言われても、そんなこと想定したら質問文と矛盾するので、想定できない。　　としか言えません。

でもそういった条件なら、

ランダムにM/N個取り除いてチェックする　　を繰り返す。
（M:残りの倉庫にある種類数。）
Mが減ってきて、N≧M/Neになったら、取り除く個数を1個に切り変える。

では？

部品1個を使う確率はN/M。
N個取り除いたときに、この中に使用部品が混じっている確率は
（1-N/M)^M/N であるので、約36%。(=1/e。）
よって、テスト1回で、平均　M/eN　個を除外できる。
※取除く個数を1個に切り変えるタイミングは要精査。（1-N/M)^M/N＝1/eという近似からずれていく。）

Nが不明、という条件があるから、しばらくの間はNを当初想定値とし、
実際の除外確率を使って、Nの想定値（（1-N/M)^M/Nが実値と一致するようなN） を計算しなおし、更新する。

この回答へのお礼

応答ありがとうございます

＞お察しくださいと言われても、そんなこと想定したら質問文と矛盾するの
＞で、想定できない。　　としか言えません。
おっしゃる通りですね、すいません。カテゴリー違ってたかなと思っています（汗）

N個取り除いたときに、この中に使用部品が混じっている確率は
（1-N/M)^M/N であるので、約36%。(=1/e。）

なるほど、除外確率が高い個数を求めて、テストする方法ですね。

手作業で何回かやって、多少なりとも濃度を上げたいと思ったのですが、無理そうですね。

今回の質問の内容からは外れますが、
　必要な部品をいくつか見つけて、
　「必要な部品らしさ」を何とか無理やり定義して、
　その値が小さい部品を優先的に取り除いてチェックする
のが現実的な気がしてきました。
お付き合いいただき、ありがとうございました。

お礼日時：2022/04/25 17:39

No.1 回答者： masa2211 回答日時： 2022/04/23 10:23

そういうアルゴリズム、無いのでは？

N=1とかN=2なら、その手のアルゴリズムは存在して、
最初にM/2個を取り除く。
以下、あなたが示した改良版の方法でチェックする。
その結果、ごっそり不要部品を排除できる（場合がある）。
以下、M/4、M/8......1　に対し、同様に行う。
　※1,2.4,8,16.....の逆順でグループ化しても理屈の上では同じ。
　※※このアルゴリズム(N=1)は、「M個の数値のうちX番目の値を求める」
　　　ためのアルゴリズムの流用。

これは、Ｎ＜log(M) かつ、Ｍは相当大きい
　(logの底は2。以後も同じ。あと、うまくいくかどうかの範囲は曖昧だが概ねこれくらいという意味。)
という条件なら、まあまあうまくいくのですが、
それ外れるとあまりうまくいかない......
　※N<M/10という条件なら、うまくいく範囲（Ｎ＜log(M)） を外れてしまう場合が多発。

ちなみに、計算量は、オーダーで判断しています。
オーダーとは、Ｍがとてつもなく大きくなった時、Ｍに比例するか、log(Ｍ)に比例するか、Ｍ＾２に比例するか、2＾Ｍに比例するか、そういうことを指してオーダーと言います。
ですから、質問者さんの示した改良版とは、おおむね、回数が半分強になるだけだから、それ、Mに比例だよね？オーダー変わるほど効率化してないよね？
となります。
ですので、Ｍ比例から、log(M) 比例とか√M比例とかになるなら、アルゴリズム改良と言えるけど、そうでないなら、アルゴリズム改良と言えるかどうかが微妙な話です。

なお、私の質問文の解釈だけど、
＞N<M/10。Nの実際の値は未知
とは、1≦N<M/10であるので、N=1で成立する(N=0は、問題の性質上ありえない。)ことまでがっちりチェックが必要。アルゴリズム的にはN＝Mでも動作する（計算時間は問わない）。という条件を付加。
　※まあ、N≧M/2なら必要/不必要を反転すればよいので、実質N≧M/2。

この回答へのお礼

応答ありがとうございます

＞そういうアルゴリズム、無いのでは？
＞ちなみに、計算量は、オーダーで判断しています。
>Mに比例だよね？オーダー変わるほど効率化してないよね？
本問題、
　MT時間での解放があるのでO(n)は明らか
なので、ここでの「良いアルゴリズム」はO(n)であっても定数項の値が小さいアルゴリズムを求めていることは、お察しください。

＞なお、私の質問文の解釈だけど、
Mは2^18程度を想定しています。　Nも十分大きく、2^14程度で、N<M/10しかわかっていません。後出しになってしまいますが、問題としては、M/20<N<M/10でもOKです。

必要部品の濃度が１０％以下ならば、５つずつ取り出してチェックすれば、チェックした半分は確実に成功するので、M/5回のチェックで濃度を2倍の２０％以下にすることができる。というところまでは、改良できるとはおもいますがその先が思いつきません。

引き続き回答お待ちしています。

お礼日時：2022/04/23 13:17