3

問題を表すためにPython構文とオブジェクトを使用しますが、実際には、PythonAPIとORMを使用したSQLデータベースのモデルを対象としています。

私はこのような番号のリストを持っています：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

時々、いくつかの数字が削除され、ヌルスペースが残ります：

[0, 1, 2, None, None, 5, 6, None, None, None, 10]

私がする必要があるのは、番号の間にヌルスペースが残らないように、順序付けされた方法と順序付けられていない方法の両方で定期的に行われるメンテナンスステップでこの番号のセットを効率的にパックすることです。

したがって、順序付けられた方法で、次のようになるためにそのリストが必要です。

[0, 1, 2, 5, 6, 10, None, None, None, None, None]

そして、順序付けされていない場合、それらの間にヌルスペースがない限り、各番号がどこに行くかは実際には重要ではありません。

数字は連続したブロックで移動でき、任意の数の場所を左右に移動するのに同じコストがかかりますが、セットアップと分解のコストがかかるため、大きなブロックを移動してできるだけ少ない更新でそれを達成するのがはるかに効率的になります。

現在、私は最も単純なソリューションを使用しており、連続する番号のブロックを見つけて、パックされるまで一度に1ブロックずつ最も近い左に移動します。したがって、この例では、1回の更新で5、6が2ブロック左に移動し、別の更新で10が5ブロック左に移動します。

[0, 1, 2, None, None, 5, 6, None, None, None, 10]

[0, 1, 2, 5, 6, None, None, None, None, None, 10]

[0, 1, 2, 5, 6, 10, None, None, None, None, None]

この些細なアプローチは、順序が重要な場合に最も効率的であるように見えますが、実際には、私の操作のほとんどは順序付けられていないため、より良いアプローチがあるはずです。たとえば、この場合、0、1、2ブロックを6と10の間で移動することにより、リストを1回の更新でパックできます。

[None, None, None, None, None, 5, 6, 0, 1, 2, 10]

実際には何千ものブロックがありますが、各ブロックのサイズと各ギャップを事前に知っています。ブロックの移動は、サイズとギャップの間の組み合わせ論に必要な計算に比べて非常にコストがかかるため、最適なソリューションを見つけることが理想的です。

これは一種のビンパッキング問題のようですが、最善の解決策を見つけるためにどのようにアプローチするかは本当にわかりません。何か案は？

4

3 に答える 3

3

順序付けられていない場合、最終的な連続ブロックが埋める必要があるスペースを誰かが教えてくれたとします。次に、この領域の外側にある最大のブロックを最初に領域内に移動すると、すべてが収まり、ブロックを分割する必要がなくなるというヒューリスティックな方法があります。コメントで示唆されているように、これで A* (またはブランチ アンド バウンド) を実行できます。次に、最初の決定は、最終的な連続ブロックがあるべき場所ですが、これは A*/branch とバインドの別のレベルにすぎません。実際、このヒューリスティックの下では、最も有望な最終連続領域は、現在最大数の塗りつぶされた領域を保持している領域になります。これは、この外側のサブリージョンにのみ移動する必要があると想定しているためです。

これがコストが高すぎるとわかった場合、分枝限定を高速化する 1 つの方法は、質の悪い回答を得るという代償を払って、これまでに見つかった最良の回答を X% だけ改善する可能性のある回答を破棄することです。

実際には、これよりもわずかに優れた下限を取得できると思います-最大(ターゲット領域内の個別の連続したギャップの数、ソース領域から移動する個別の連続した領域の数) は、1 つの移動がせいぜい移動できるため、わずかに優れている必要があります。数字の単一の連続領域で、ターゲット領域の単一のギャップを埋めます。

下限を取得する簡単な方法の 1 つは、問題を簡単にするために十分な制約を無視することです。未知の正解が依然として実行可能な解であると仮定すると、弱められた問題の最良の解は少なくとも未知の正解と同じくらい優れている必要があるため、これは下限を与える必要があります。2 つの更新が互いに衝突しないふりをすることで、ギャップのある更新の問題にこれを適用できます。指定されたターゲット エリアが与えられた場合、このヒューリスティックを計算することは、ソース エリアをチャンクに切り分け、それぞれがターゲット エリアに収まる最適な方法を見つけることになります。これは動的プログラムで解決できます。ソース領域の最後の k 個のセルをコピーするすべての可能な方法を考慮して、ソース領域の最初の n+1 個のセルに対する最良の答えを導き出します。次に、ソース領域の最初の n + 1-k セルをコピーするコストを追加します。これは既に計算済みです。残念ながら、このヒューリスティックが役に立つほど強力かどうかはわかりません。

于 2012-04-22T04:06:25.227 に答える
2

あなたが説明する問題は、圧縮問題と呼ばれます。古典的な圧縮の問題 (順序付きと順序なしの両方のバリアント) では、データ移動のコストはそれほど法外なものとは見なされません。したがって、補助ストレージを使用し、空でないエントリを単一の線形スキャンで補助ストレージにコピーすることで、簡単に解決できます。新しい圧縮されたストレージは、コンテキストに応じて、元のストレージを単純に置き換えるか、元のストレージにコピーすることができます。現在、これらすべてを線形時間で実行でき、線形の追加ストレージのみを使用できます。したがって、ビンパッキングという意味では難しい問題とは見なされません。Bean のパッキングでは、直線的な量の追加ストレージを許可するかどうかにかかわらず、簡単な解決策はまったくありません。したがって、ここで扱っているのは明らかにビンパッキングではありません。

データの移動にコストがかかる場合、非連続データ ブロックの移動回数を最小限に抑えるという追加の制約が追加されました。この問題は、次の 2 つの問題のいずれかのインスタンスと見なすことができます。

  1. バイナリ配列のインプレース ソート。ここでは、0 と 1 の 2 種類のデータのみを含む配列をモデル化します。これは、空のデータ エントリに対して 1 を返し、空でないデータ エントリに対して 0 を返す述語 isNull(a) を使用して、簡単に実現できます。ここで考えられる最も簡単な解決策は 、バイナリ配列の並べ替えにSelection Sortを使用することです。O(n 2 )回の比較を行うことができますが、最悪の場合でもO(n)を超えるデータ移動を行うことはありませんが、データ移動の数を最小限に抑えたいだけなので、気にする必要はありません。 . 移動するデータがない場合は、何もしません! 物事を少し複雑にするいくつかの改善点は次のとおりです。

    • 個々のエントリではなくブロックを交換します。つまり、2 つのブロック (ゼロの 1 つと 1 のもう 1 つ) は、ゼロのブロックの方が大きい場合にのみ交換できます。また、次のスワップが常にこれら 2 つの絶対差を最小化するもの、つまり abs(len(zeroBlock) - len(oneBlock)) であるという貪欲なヒューリスティックを使用することもできます。これは、問題の順序付けられていないインスタンスに対してのみ機能します。
    • 他の 2 つの最適化は、天気を昇順または降順で並べ替える前処理を行うことです。
    • また、リストの連続する末尾を除外することもできます。

  2. ガベージ圧縮。基本的には、空き領域を、ガベージ コレクションが必要なメモリ内の割り当て解除された領域と見なすという考え方です。これについては、この興味深いSO ディスカッション スレッドと、これも参照してください。この研究論文またはこれも役立つ場合があります。

幸運を！

于 2012-04-22T20:00:56.957 に答える
1 
#include <stdio.h>
#include <string.h>

#define IS_EMPTY(c) ((c) <= '@')

unsigned moverup(char buff[], unsigned size)
{
unsigned src,dst,cnt;

for (src=dst=cnt=0; src < size; src++ ) {
        if (!IS_EMPTY(buff[src])) { cnt++; continue; }
        if (!cnt) continue;
ugly:
        memmove(buff+dst, buff+src-cnt, cnt );
        dst += cnt;
        cnt = 0;
        }
if (cnt) goto ugly;
return dst;
}

int main(void)
{
unsigned result;
char array[] = "qwe@rty@ui#op";

printf("Before:%s\n", array );

result = moverup (array, strlen (array) );

printf("result:%u\n", result );
// entries beyond result will contain garbage now.
// array[result] = 0;
printf("After:%s\n", array );

return 0;
}
于 2012-04-22T21:37:31.000 に答える