7

編集：これはスイープラインの問題だと思います。(下部の update2 を参照)

この問題では、NオブジェクトとM制約が与えられます。（Nできる200k、Mできる100k）。各オブジェクトは、黒または白のいずれかです。各制約は の形式(x, y)であり、オブジェクトの範囲内に 1 つの白いオブジェクトx..yがあることを意味します。残りは黒です。存在できる白いオブジェクトの最大数、または制約を満たすことができないかどうかを判断したいと考えています。

制約が別の制約に完全に含まれている場合、内部の制約によって白いオブジェクトを配置できる場所が決まります。また、複数の交差しない制約が別の制約に含まれている場合、制約ごとに1 つの白いオブジェクトしか存在できないという事実に違反するため、これは不可能です。アルゴリズムは、2 ～ 3 秒未満で実行できるほど高速である必要があります。

更新: 回答の 1 つは、正確なカバーの問題に言及しています。これは NP 完全ではない特殊なインスタンスですか?

Update2: 各制約を開始イベントと終了イベントに変更し、これらのイベントを並べ替えると、これらのイベントを体系的にスイープして白いオブジェクトを割り当てることができますか?

4

2 に答える 2

2

You problem can be expressed as an exact cover problem: the constraint intervals form the set to be covered, and each white object covers those constraint intervals which it falls inside of. Your problem, then, is to find a subset of the white objects which covers each constraint interval exactly once.

Exact cover problems in general are NP-complete, although that obviously doesn't necessarily mean that any specific subset of them are. However, there nonetheless exist algorithms, such as Knuth's Algorithm X (as implemented by dancing links) that can solve most such problems quite efficiently.

It's possible that the one-dimensional structure of your problem might also allow more straightforward specialized solution methods. However, Algorithm X is a very good general tool for attacking such problems. (For example, the fastest sudoku solvers typically use something like it.)

于 2013-04-06T18:33:59.367 に答える