1

実際、私はすでにこの質問に対する部分的な答えを持っていますが、この貪欲なコードの小さな断片を一般化して、最適な解決策に近づけることができるかどうか疑問に思っています.

この問題にどのように遭遇したか（問題自体には関係ありませんが、興味深いかもしれません）：

オブジェクトの大規模なコレクション (堤防のプロファイルのセットであり、各堤防はその長さに沿って多かれ少なかれ同じ形状を維持します) を受け取り、プロパティ (堤防の名前) に従ってそれらをグループ化できます。私のプログラムの出力は、手動で呼び出す必要がある外部プログラムに送られ (理由は聞かないでください)、失敗から回復することはできません (1 つの間違いでバッチ全体が停止します)。

私がこれを使用しているアプリケーションでは、ビンの量やビンの最大サイズに厳しい要件はありません。私がやろうとしていることは

  • グループの数を少なく保ちます (プログラムを数回呼び出します)。
  • セットを小さく保つ (バッチが失敗した場合のダメージを減らす)
  • 似たようなものをまとめる (グループの失敗は、おそらくグループ全体の失敗です)。

あまり時間がなかったので、セットをグループ化する小さな貪欲な関数を書きました。

同僚は、データにノイズを追加して、見つけた近似解の近傍を探索することができると提案しました。

真の最適解を必要としない元のタスクに関連しているわけではありませんが、この質問をコミュニティと共有して、そこからどのようなコメントが出てくるか見てみようと思いました。

def group_to_similar_sizes(orig, max_size=None, max_factor=None):
    """group orig list in sections that to not overflow max(orig) (or given max_size).

    return list of grouped indices, plus max effective length.

    >>> group_to_similar_sizes([1, 3, 7, 13])
    ([[2, 1, 0], [3]], 13)
    >>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ])
    ([[3, 1], [4, 2], [5], [6, 0], [7], [8]], 22)

    result is independent of original ordering
    >>> group_to_similar_sizes([9, 19, 22, 12, 19, 9, 2, 22, 11, ])
    ([[3, 1], [4, 2], [5], [6, 0], [7], [8]], 22)

    you can specify a desired max size
    >>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ], 50)
    ([[3, 2, 1], [6, 5, 4], [8, 7, 0]], 50)

    if the desired max size is too small, it still influences the way we make groups.
    >>> group_to_similar_sizes([1, 3, 7, 13], 8)
    ([[1], [2, 0], [3]], 13)
    >>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ], 20)
    ([[1], [3, 2], [4, 0], [5], [6], [7], [8]], 22)

    max size can be adjusted by a multiplication factor
    >>> group_to_similar_sizes([9, 19, 22, 12, 5, 9, 2, 22, 11, ], max_factor=0.75)
    ([[2], [3], [4, 1], [5, 0], [6], [7], [8]], 22)
    >>> group_to_similar_sizes([9, 19, 22, 12, 5, 9, 2, 22, 11, ], max_factor=1.5)
    ([[2, 1], [6, 5], [7, 3, 0], [8, 4]], 33)
    """

    ordered = sorted(orig)
    max_size = max_size or ordered[-1]
    if max_factor is not None:
        max_size = int(max_size * max_factor)

    orig_ordered = list(ordered)
    todo = set(range(len(orig)))
    effective_max = 0

    result = []
    ## while we still have unassigned items
    while ordered:
        ## choose the largest item
        ## make it member of a group
        ## check which we can still put in its bin

        candidate_i = len(ordered) - 1
        candidate = ordered.pop()
        if candidate_i not in todo:
            continue
        todo.remove(candidate_i)

        group = [candidate_i]
        group_size = candidate

        for j in sorted(todo, reverse=True):
            if orig_ordered[j] + group_size <= max_size:
                group.append(j)
                group_size += orig_ordered[j]
                todo.remove(j)

        result.insert(0, group)
        effective_max = max(group_size, effective_max)

    return result, effective_max
4

1 に答える 1

0

あなたの同僚がノイズ データを追加するというアイデアは気に入っていorderedますordered = sorted(orig)。

于 2011-05-18T13:48:26.760 に答える