組み合わせのユニークな解とは？
- ６０作品に対して３０人の審査員が１０分間の合議で評価し採点します。
- 重複のない審査員の配置を考えるアルゴリズムを提案してください。
- 解がない場合は空白の時間帯を入れて全体の審査時間を延長する必要があります。
- ベストアンサー
組み合わせのユニークな解？
組み合わせのユニークな解？ ６０の作品に対して、審査員が３０人います。 それぞれの作品について、３つの会場で、数名の審査員が１０分間の合議で評価し採点します。 例えば、 作品Aの審査委員はa氏、ｂ氏、ｃ氏、ｄ氏の4名。 作品Bの審査委員はa、ｂ、eの3名。 作品Cの審査委員はc、d、e、f、gの5名。 などなど、、、一つの作品に対して審査員は概ね4名です。 多くを審査する売れっ子審査員は15作品も審査しますが、 不人気の審査員は３作品を審査するだけです。 適当にばらけていれば、６０作品×１０分÷３会場＝２００分で審査は終わります。 これまでは、売れっ子上位３名の審査員を同じ時間に2つ以上の会場に当らないように配置し、 次いで、その他の上位の審査員を重複しないように配置し、 中位、下位の審査員を配置し、重複したら適当に入れ替えて 丸く納めるという方針で何とかこなして来ました。 しかし、今回はいろいろ頭で考えても重複が消えません。 さらに今後、作品も審査員も規模が大きくなりそうで、人力では無理があります。 そこで、どの審査員が何時どの会場へ出向いてどの作品を審査するかという タイムテーブルを作成する場合のアルゴリズムを提案して下さい。 解が多数存在する場合、審査員の会場移動を少なくするには どのようなアルゴリズムを考えればよいでしょう？ 解がなければ、空白の時間帯を入れて、全体の審査時間を10分延長しなければ 全作品を審査できません。「解なし」はどのように導けばよいでしょう？ そのようなソフトウェアがあればご紹介下さい。
- pop_eye
- お礼率60% (3/5)
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
問題の詳細がいまいちはっきりしませんが。（ある作品を何人で審査するかがあらかじめ決まっているのかどうか等） いずれにせよ、そのものずばりなアルゴリズムやソフトウェアはないでしょう。 もし、自分でプログラムを作るなら、バックトラック（というアルゴリズム）で作るのがいいでしょう。 さらに、ものすごく大規模（作品数１万とか）になる可能性があるのであれば、「０－１整数計画問題」を解く専用のソルバをどっかから探してきて用いるのがいいでしょう。
関連するQ&A
- 16チームの試合の組み合わせ
16チームで試合をします。 1日目は4チームごとに会場を分けて、リーグ戦をします。 2日目は4チームごとに会場を分けて、1日目とは違うチームと試合ができるようにリーグ戦をします。 3日目は4チームごとに会場を分けて、1日目、2日目とは違うチームと試合ができるようにリーグ戦をします。 4日目は4チームごとに会場を分けて、1日目、2日目、3日目とは違うチームと試合ができるようにリーグ戦をします。 5日目は4チームごとに会場を分けて、1日目、2日目、3日目、4日目とは違うチームと試合ができるようにリーグ戦をします。 5日間で各チーム15試合、全120試合の総当たりができると思うのですが、それそれの会場に分ける作業がうまくできません。3日目くらいにどうしても試合が重複してしまいます。どなたかいい知恵をかしてください。 3日目まではなんとかできるのですが4日目で同じチーム同士の試合ができてしまいました。 チームを１～１６、会場をＡＢＣＤとしました。 1日目 会場Ａ（１・２・３・４） 会場Ｂ（５・６・７・８） 会場Ｃ（９・１０・１１・１２） 会場Ｄ（１３・１４・１５・１６） 2日目 会場Ａ（１・５・９・１３） 会場Ｂ（２・６・１０・１４） 会場Ｃ（３・７・１１・１５） 会場Ｄ（４・８・１２・１６） 3日目 会場Ａ（１・６・１１・１５） 会場Ｂ（２・７・１２・１３） 会場Ｃ（３・８・９・１４） 会場Ｄ（４・５・１０・１５） 4日目 会場Ａ（１・８・１１・１４） 会場Ｂ（２・５・１２・１５） 会場Ｃ（３・６・９・１６） 会場Ｄ（４・７・１０・１３） と分けてしまうと、4日目で、会場Ａの１・１１、会場Ｂの２・１２、会場Ｃの３・９、会場Ｄの４・１０のように１～３日目までの試合と重複してしまいます。
- ベストアンサー
- 数学・算数
- 順列と組み合わせについて
１、リンゴ５つを三人で分けたとき何通りの分け方があるか、ただし一つももらわない 人がいてもよいとする。 ２、５人のをＡ，Ｂ，Ｃの三部屋に分けるとき何通りの分け方があるか、ただし空き部屋があってもよいとする １と２の違いについて教えてください、後不定方程式の解の個数と重複順列と重複組み合わせの関係について教えてください。 よろしくお願いします
- ベストアンサー
- 数学・算数
- ２分法で方程式の複数の解を自動的に求めるには？
２分法を授業で習い、アルゴリズムは理解できました。 そして、２分法で方程式の解を求めるプログラムも完成したのですが、 ３次方程式などの全ての解を２分法で求める場合、本来ならば、 グラフなどを描き、適切な初期値を自分で変更していく必要があると思います。 しかし、方程式の複数の解を自動的に求めたいのです。 もし、２分法で方程式の複数の解を自動的に求めるアルゴリズムがあれば教えていただけないでしょうか。 よろしくお願いします。 ※ 私が作成したプログラム（C言語）も載せておきます。 #include <stdio.h> #include <math.h> double f(double x) { return ((x-1.0)*(x-2.0)*(x-3.0)); } int main () { int i; double a,b,x; double gosa = 1.0e-14; printf("aの値を入力してください。\n"); scanf("%lf",&a); printf("bの値を入力してください。\n"); scanf("%lf",&b); if(f(a)*f(b) >0) printf("aとbの範囲の中に適切な解が存在しません。\n"); while(1){ x = (a+b)/2.0; printf("%.14f\n",x); if(fabs(b-a)<gosa) break; if(f(a)*f(x)<=0){ b = x; } else{ a = x; } } return(0); }
- ベストアンサー
- C・C++・C#
- 数学 解の配置の問題について
数学 解の配置の問題について よく解の配置の問題では、 y=f(x)(=x^2+ax+bだとします。)が p< x <qの範囲に少なくとも1つの解をもつような(a,b)の存在範囲を図示せよ。という問題があります。どの解答も解が1つのとき、2つのとき、重解の時…など、場合分けをしています。 少なくとも1つの解をもつ条件を求める際に、1つも解がないときの存在範囲でないほうを描けばいいのでは?と思ったのですが、答が一致しない場合のほうが多いです。 どうして、1つも解がないときの存在範囲から少なくとも1つの解をもつ条件を導き出すことができないのでしょうか？（どこで必要条件・十分条件が崩れるのでしょうか。）
- ベストアンサー
- 数学・算数
- ３元連立１次方程式の解を持つ条件とその解
３元連立１次方程式の解を持つ条件とその解 次の３元連立１次方程式(1)x+2y+3z=a (2)2x+3y+4z=b (3)3x+4y+5z=c の解を持つ条件とその解を求めます。-2x-y=8a-3b,2y+4z=3a-c,x-z=-3a+2bなどの関係式を求めたのですが、そこからの展開がわかりません。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 解と係数の関係
xの３次方程式 ax^3＋bx^2＋cx＋d＝0 の３つの解α、β、γとするとき解と係数の関係を書き、それを証明せよ。 というもんだいがあるのですが 解答をみると まず解と係数の関係を記す。 つぎに証明に入り 因数定理でa(x-α)(x-β)(x-γ)としてこれを展開して 恒等式として係数比較して。。。。。というながれがかいてあるのですが 私は解答の方法を思いつけず、 まず解と係数の関係を記す。 α＋β＋γ＝－b/a αβ＋βγ＋γα＝c/a αβγ＝－d/a これを変形して b=－a(α＋β＋γ) c=a(αβ＋βγ＋γα) d=－aαβγ としてはじめの３次方程式へ代入 ax^3-a(α＋β＋γ)+a(αβ＋βγ＋γα)-aαβγ=0 ここでx=α、β、γ を代入すると左辺＝０＝右辺となりこの方程式の解は x=α、β、γとわかる またこの方程式は３次方程式なので解の個数は高々３つ よってこの方程式の解はα、β、γのみ というふうに書いたのですがどうなんでしょうか？ この問題は解がα、β、γならば α＋β＋γ＝－b/a αβ＋βγ＋γα＝c/a αβγ＝－d/a が成立 をしめすべきなのですが わたしの解答では α＋β＋γ＝－b/a αβ＋βγ＋γα＝c/a αβγ＝－d/a ならば 解はα、β、γ を示してしまっていると思います しかし「解がα、β、γのみ」と書いたので 解がα、β、γのならば α＋β＋γ＝－b/a αβ＋βγ＋γα＝c/a αβγ＝－d/a という逆も示せているのではないかとも思います 自分ではよくわかりませんのでどなたか教えていただきませんか？
- 締切済み
- 数学・算数
お礼
ヒントをご回答頂きありがとうございます。 審査員は3人以上というキマリしかありませんが、通常、多くて5人です。 「ソルバ」で検索したところ、「MS-excel」にそんなソルバ機能がついているようですので、使えるかどうか試してみます。