4

苦労している組み合わせ最適化問題があります。問題の技術的な詳細は扱いにくいので、架空の甘い 16 の誕生日パーティーの観点から物事を翻訳しました。明らかに、ティーンエイジャーは NP 困難ですが、それは私が解決しようとしている実際の問題とは別のものです。

もうすぐ 16 歳になる息子がいるとしましょう。息子は友達全員を誕生日パーティーに招待しますが、すべての友達がお互いを好きというわけではありません。実際、私の息子の友人には、少なくとも 1 人は嫌いな人がいて、中にはそれ以上の人もいます。これらの「フレネミー」は、1 人以上の宣誓した「フレネミー」が同じテーブルに座っている場合、同じテーブルに座ることを拒否します。私の息子は、招待されたすべての友達のリストと、誰が誰を嫌いなのかを教えてくれました。この情報は対称的ですが (友人 A が友人 B を好きではない場合、友人 B は友人 A を好きではありません)、推移的ではありません (友人 A が友人 B を好きではなく、友人 C が好きなら、友人 C は依然として友人 B を好き嫌いは自由）。私の質問は次のとおりです。2 つの「フレネミー」が存在しないという条件を満たすテーブルの最小数を決定するにはどうすればよいですか?

4

2 に答える 2

1

これは組み合わせ最適化の問題であり、機械学習の問題ではありません。

実際、これは塗り絵の問題です:G各頂点が人に対応するグラフを作成します。(u, v)2人がお互いを好きuではない場合、エッジが存在します。vあなたは今、色付け可能kな最小のものGを求めていkます。c(v)どのテーブルvに座っているかは色でわかります。

あとはアルゴリズムを選択するだけです。

于 2013-04-11T20:15:19.017 に答える
0

これは、機械学習の問題というよりも、制約付き最適化の問題のように思えます。以下のようにモデル化します。

  • フレンドごとに 1 つの変数、値はテーブル、
  • friendX !- friendYこれら2つが同じテーブルに座ることができないことを示すフォームの追加の制約（リストに従って） 。

これは、選択した制約ソルバーを使用して解決できる基本モデルです (私はMinionをお勧めします)。テーブルの最大数を最小化するか (いくつかの追加の制約が必要になります)、解が存在しないテーブルに到達するまで、指定された数のテーブル (つまり、変数のドメイン内の値) を使用して解を見つけようとすることができます。 .

問題の規模 (つまり、友人やテーブルの数) によって、これが機能する場合と機能しない場合があります。考慮しなければならないのは、問題の対称性 (つまり、テーブル A にいる人がテーブル B に移動でき、その逆も可能であり、それは依然として解決策である) であり、追加の制約によって壊れる可能性があります。

于 2013-04-11T19:23:52.843 に答える