Name名無し20/02/25(火)21:48:14No.113490+
9月27日頃消えます 区間スケジューリング問題
N 個の仕事 w_i(i=1,2,…N)がある。
各仕事 w_i の開始時刻は s_i 、終了時刻は t_i である。
あなたは各仕事について参加するか参加しないかを選ばなければならない。ある仕事に参加するならば、その仕事に始めから終わりまで参加しなくてはならない。すなわち、他に参加する仕事と時間か重なってはならない。開始・終了の瞬間だけが重なるのも許されない。
参加できる仕事の数の最大値を求めよ。

数学的な証明が上手く理解できない……このスレは古いので、もうすぐ消えます。
削除された記事が7件あります.見る

…No.113491+前の仕事の終了時刻以降に開始する仕事のなかから 終了時刻がなるべく早いものを選ぶ というのを繰り返せばいいような

…No.113492+区間グラフでの最大独立集合問題だから、基本被らないような仕事（次数の少ない頂点）を優先的にやっていけばいい気もするがNP困難だから仕事の規模が多くなると多項式時間では解けんかなぁ

…No.113493+>No.113491 それを数学的に書くのが上手くできなくて…… 一番早く終わるのより早いのがあればそれを選ぶのが最適ってのは 理解できるんだけど例えばテストで紙に書いて説明しろって言われると案外難しい

…No.113540+間引けば良いんじゃない？ w_iを閉区間[s_i,t_i]と同一視するとして， まず，一般のN個の区間で部分集合の関係になっている２つを探す． つまり，w_i⊆w_jとなっていたら，w_jを消して間引く．これを繰り返してどの２つの区間も部分集合の関係にない状態まで間引く． この時点でどの区間も共通部分がないなら，残った区間を数えれば答え． 共通部分がある場合は，開始時刻が遅い方の区間を消して間引く． 最後に残った共通部分がない区間の数が答え． どうだろう？

…No.113541+>共通部分がある場合は，開始時刻が遅い方の区間を消して間引く． これだけじゃ上手くいかないな． 正確にはタイムライン上で早い時刻から重なりのある２区間を検索していって，見つかったら開始時刻が遅い方を消す． でないと，ランダムに検索して消していくと余計に消してしまうこともあるね． これでどうだろう？

…No.113542+>それを数学的に書くのが上手くできなくて…… 帰納法で解けばいいんじゃないの? 1,3つの区間で最適なことを証明する 2,4つの区間が3つの区間と同等なことを証明する そんな流れで

…No.113544+私がNo.113540とその次で書いた内容はアルゴリズム的（計算可能）な表現だから，そのまま数学的証明になってるよ． あとは，テストなり論文なりの書きぶりに書き直せばいい．

…No.113546+書き込みをした人によって削除されました

…No.113547+書き込みをした人によって削除されました

…No.113548+書き込みをした人によって削除されました

…No.113549+ｽﾚには >開始・終了の瞬間だけが重なるのも許されない。 と言う条件が有るが、これは所与の仕事が離散時間区間[a, b]のとき代わりに[a, b+1]を考えたら >他に参加する仕事と時間か重なってはならない。 に帰着できるから無きものにできうる、 で、重なりはあれども互いに包含関係に無い[a,c][b,d]という2つのお仕事のどっちを 請け負うべきかというのは - 早く始まるけど長い仕事 - 遅く始まるけど短い仕事 の比較になった場合、どっちを請け負ったほうが全体最適になるか、 時刻c, d以降の仕事の配置を弄ることにより出題者が任意に設定できる。 任意の出題が可能ということは、解くほうは出題者の自由意志の自由度成分に対して 探索で対応せねば正解がわからんちん

…No.113559+>どっちを請け負ったほうが全体最適になるか、 仕事の量（総時間）ではなく仕事の数（区間の数）だから．

…No.113562+書き込みをした人によって削除されました

…No.113563+書き込みをした人によって削除されました

…No.113564+書き込みをした人によって削除されました

…No.113565+区間の数の話をしてるやがな； いま時刻a,b,c,d, ..., w,x,y,zの順を考えて、 仕事[w,y][x,z]があり、y〜z内にスタートする仕事が何も無いケースを考えると、 出題者が時刻wで終わる（重なりの有る）別の仕事[*,w]を設定すれば [*,w]と[x,z]を請け負うべきというのが暫定的な答え --- (*1) そうでなければ（wより前に終わる仕事しかなければ）[w,y][x,z]のど っちを請け負っても変わらないというのが暫定的な答え -- (*2) この比較がベースとなる しかし上記比較内で平均的に不利と考えられる[w,y]も、 別の時刻系列w',x',y',z'の中の[x',z']ポジかもしれない *'〜w'〜x'〜z'が*〜w〜x〜zより短かったりすると(*1), (*2)の答えは再考を求められる というわけで出題者の意図を全部読みきらないと答えが定まらない系列があり得る、 ｷﾓｽ

…No.113578+>どっちを請け負っても変わらないというのが暫定的な答え -- (*2) 区間の数の最大値を求めればいいだけだから，その最大値となる区間の組み合わせが一意的でなくても良い． (*1)も(*2)も区間の数が変わらないのなら解釈に変わりはない．答えは同じ． 結局私が先に書いているように，タイムライン順に二組づつ検索していって，共通部分があれば開始時刻が遅い区間を消せばいい．

…No.113584+>(*1)も(*2)も区間の数が変わらない ちょっ(*1)は仕事2件、(*2)は仕事1件やん？ 変わらなくないやん？？ >タイムライン順に二組づつ検索していって，共通部分があれば開始時刻が遅い区間を消せ このアルゴリズムを(*1)と(*2)のケースに適用すると、 [x,z]（(*1)に属する）と[w,y]（(*2)に属する）において [x,z]の方が消されるから(*1)の可能性が無くなるやん？ 仕事損するやん？？

…No.113592+>ちょっ(*1)は仕事2件、(*2)は仕事1件やん？ 変わらなくないやん？？ (*1)と(*2)の違いはごちゃごちゃ書いてるけどwという点が重なる2つの区間があるかないかだから． あったとしても，なかったとしても「正しい最大値」をそれぞれの場合で返すなら答えるべきアルゴリズムは同じだよ． そもそも，異なる初期状態にアルゴリズムを施すのだから，出力結果が異なるとしても何も問題ない． 解釈問題はそこにはないよ．

…No.113594+>このアルゴリズムを(*1)と(*2)のケースに適用すると、 その2つはそもそも初期状態が違うんだから，出力結果が違って当然なんだよ．

…No.113596+ごちゃごちゃ書いてるけど，まとめたらこういうこったろ？ (*1) …，[v,w],[w,y][x,z] (*2) …，[u,v],[w,y][x,z] だから，そもそも初期状態が異なる別の系列だ． …の前は同型だとして無視して論じるとして， (*1)は[v,w]と[x,z]の2つの区間が残る． (*2)は[u,v]と[w,y]の2つの区間が残る． どっちも残るのは2つの区間だから最大値は同じだ． どっちの区間が長いとか得するとか関係なくて，区間の数が問われてるんだよ．

…No.113754+書き込みをした人によって削除されました