2023-採用-解説
- 考案国：イラン
- 正解
- Yunas は倉庫担当に採用されます。
- 説明
- ある仕事に1人しか応募者がいない場合，その応募者は他の仕事にも応募している場合でも，その仕事に採用される必要があることに注意する必要があります。Omran はただ一人のコールセンター担当応募者なので，Omran をコールセンター担当で雇われなければなりません。 したがって，「Omran は梱包担当に採用されます。」は誤りです。
- すると，コールセンター担当の仕事は Omran に決まり， また， Omran は１つの仕事しか持てないので，Omran とコールセンター担当とそれらに接続している線を図から取り除きます。
- 更新された図の Yunas に対して同じ考えを適用すると， Yunas は倉庫担当として採用され，「Yunas は倉庫担当に採用されます。 」が正しいことが分かります。
- Yunas と倉庫担当を及びそれらに接続している線と取り除くと，他の選択肢が正しくないことが明瞭に分かります。
- 例えば， Mary は梱包担当として，Elif は経理担当として採用されるかもしれません。
- ある仕事に1人しか応募者がいない場合，その応募者は他の仕事にも応募している場合でも，その仕事に採用される必要があることに注意する必要があります。Omran はただ一人のコールセンター担当応募者なので，Omran をコールセンター担当で雇われなければなりません。 したがって，「Omran は梱包担当に採用されます。」は誤りです。
- 実際のコンピュータでは
- この問題は制約充足問題であり，変数に値を割り当てることで他の選択肢を排除し，集合論の記法を用いて表現することができます。例えば，仕事の割り当てを適用する前の倉庫担当 = {Omran, Yunas} などです。制約充足問題は，実世界での資源割当て問題やパズル（数独など）で使われています。
- また，この問題では，仕事と応募者のデータ構造を表現するために二部グラフを使用しています。二部グラフは二つのカテゴリ(部集合）の頂点を使用したグラフ表現です。ノード（頂点）のマッチング問題は，入力を二部グラフに限ると，多項式時間アルゴリズムが存在します。
注があるものを除き, このサイトの内容物は
