形状内に線を分配するための最適化アルゴリズムの選択

Question

補強バーと穴を備えたコンクリートスラブ要素の次の表現を考えてみましょう。

Iは自動的に別の穴を有する任意の形状の上に線を分配アルゴリズムを必要とします。

主な制約は、次のとおり

1. 線が
2. 二つのサイド・バイ・サイドラインとの間の距離が可変D
3. 線はに持って超えることができない領域の外側又は穴の内側にすることができません固定の間隔I、すなわちy mod I = 0に配置することができます。yは、ラインのY座標です。
4. 形状内の各利用可能な点はD/2

より線から遠いことができない私は、行Nの総数を最小化することによって溶液を最適化します。どのような最適化アルゴリズムがこの問題に適していますか？

ほとんどのアプローチでは、シェイプをラスター（ピクセルの高さがI）に簡素化し、各ピクセルを無効または有効にすることが必要です。私はこれが明らかなLPの問題だと思ってGLPKでセットアップしようとしましたが、任意の数のラインに対してこの単純なラスタを使って問題を記述することは非常に難しいと感じました。私はまた、ソリューションのスペースが大きすぎるかもしれないと思う。

私はすでにC＃でアルゴリズムを実装していますが、あまり最適化されていません。

1. は、アカウントに他のロッドや障害物に可能な行の長さと距離をとり、複雑な数式を使用して、各セルのスコアを計算し、ジオメトリ
2. の簡略化されたラスタを作成します。これは、それがどのように動作するかです。
3. （Y方向における遊離細胞の数>D場合）
4. 補強を必要と最高のスコアを有する細胞を選び、そして-xに可能な限りそれを補強し、+ X方向の補強を必要とする決定
5. 繰り返し

は、複雑な式に応じて、これはかなりうまく動作しますが、最後の数行を入れたときに、それはすでに置くラインを動かすことはできませんので、不要な結果を与えて起動します。 他の最適化手法がありますか？

Answer 1

私は、あなたが欲しいものが何であるかはわかりません - 私はそれがあなたが心に留めていたものではないと確信していますが、合理的であれば試してみることができます。

距離は単にで最もdあり、そしてそれより少ない何もすることができますので貪欲アルゴリズムは、ここで動作するはずのように、それは一見思えます。（1）可能な限り少なく、（2）既存の線から可能な限り離れているように、常に次の線を配置します。

この問題の最適なアルゴリズムがあり、最後の行から距離a <= dに次の行を配置するとします。それがb行を置くと言う。私たちの欲張りアルゴリズムは、b行以上を配置することはできません（最初の基準はできるだけ配置しないためです）。b行を配置すると、距離cとa <= c <= dに配置されます。可能。

貪欲アルゴリズムは、最適なアルゴリズムが何をしたかしなかった場合は、次のいずれかの方法で異なっていた：

1. それは遠く離れて、同じまたは少ないラインを配置。最適アルゴリズムが、b'行を次のステップで距離a'に配置したとします。次に、これらの線は、距離a+a'にあり、合計でb+b'行があります。しかし、欲張りアルゴリズムは、この場合、b'の線を変位a+a'に置き、c' = (a+a') - cを選択することによって、最適なアルゴリズムを模倣することができます。 c > aとa' < d以降、c' < dとこれは正式な配置です。

2. これは、より近いラインをより近くに配置しました。この場合は実際に問題があります。これは、少なくともk行を必要とし、最も遠いものはより多くを要求し、（例えば）それがまたがる距離がdの倍数となるように、穴の配置が選択される場合には、kが不必要な線を配置する可能性がある。

したがって、貪欲アルゴリズムは、ケース2で機能しないことが判明します。ただし、それ以外の場合はそうです。特に、最初のケースでの観察は非常に便利です.2つのプレースメント(distance, lines)と(distance', lines')の場合、distance >= distance'とlines <= lines'の場合、最初のプレースメントが常に優先されます。これは、次のアルゴリズムを提案している：

PlaceLines(start, stop) 

    // if we are close enough to the other edge, 
    // don't place any more lines. 
    if start + d >= stop then return ([], 0) 

    // see how many lines we can place at distance 
    // d from the last placed lines. no need to 
    // ever place more lines than this 
    nmax = min_lines_at_distance(start + d) 

    // see how that selection pans out by recursively 
    // seeing how line placement works after choosing 
    // nmax lines at distance d from the last lines. 
    optimal = PlaceLines(start + d, stop) 
    optimal[0] = [d] . optimal[0] 
    optimal[1] = nmax + optimal[1] 

    // we only need to try fewer lines, never more 
    for n = 1 to nmax do 

     // find the max displacement a from the last placed 
     // lines where we can place n lines. 
     a = max_distance_for_lines(start, stop, n) 

     if a is undefined then continue 

     // see how that choice pans out by placing 
     // the rest of the lines 
     candidate = PlaceLines(start + a, stop) 
     candidate[0] = [a] . candidate[0] 
     candidate[1] = n + candidate[1] 

     // replace the last best placement with the 
     // one we just tried, if it turned out to be 
     // better than the last 
     if candidate[1] < optimal[1] then 
      optimal = candidate 

    // return the best placement we found 
    return optimal 

これは(start, stop)でインデックスされるキャッシュに結果(seq, lines)を置くことによってメモ化によって改善することができます。そうすれば、すでに評価されている課題をいつ計算しようとしているのかを認識することができます。私は、問題インスタンスに対して粗いか細かい離散化を使用するかどうかにかかわらず、このケースを多くすることが期待されます。

max_lines_at_distanceとmax_distance_for_linesの機能については詳しくは言及していませんが、これらについての言葉は多々あります。

最初は、ジオメトリをスパニングするために必要な線の数が表示されます。ジオメトリと色のついた穴を黒に塗りつぶした場合、これは、表示された変位でセルの行を見て、連続する黒い線分を考慮してそこからいくつの線があるかを判断することを意味します。

秒は、与えられた候補行数に対して、その行数を配置できる現在の位置からの最大距離を示します。あなたはその行数がまたはそれ以下のの最大距離を置くことができるようにすることで、これをより良くすることができます。あなたはこの改善を使用する場合は、あなたがnを反復している方向と逆のことができます：f(start, stop, x) = aとy < x場合

1. を、あなただけで、その後から、stop、aまで検索する必要はありません。
2. f(start, stop, x)が未定義で、y < xの場合、それ以上検索する必要はありません。

どこでもstartとstop間nまたは少ないラインを配置することは不可能である場合、この関数は未定義できることに注意してください。

これらの関数を別々に覚えておけば、繰り返し検索を節約できます。それぞれの行に対してmax_lines_at_distanceをあらかじめ計算し、後で使用するためにキャッシュに格納することができます。次に、max_distance_for_linesは、2つの境界内の先頭に戻るキャッシュをチェックするループになる可能性があります。