5

我正在寻找类似于piccsy.com的 3 列布局。给定许多宽度相同但高度不同的图像,有什么算法可以对它们进行排序以使列长的差异最小?理想情况下在 Python 或 JavaScript 中......

非常感谢您提前提供的帮助!

马丁

4

4 回答 4

12

几张图?

如果您限制了最大页面大小,并且具有最小图片高度的值,则可以计算每页的最大图像数量。在评估任何解决方案时,您都需要这个。

我认为您提供的链接上有 27 张图片。

下面使用了 Robin Green 之前提到的 first_fit 算法,但随后通过贪婪交换对此进行了改进。

交换例程找到离平均列高最远的列,然后系统地在它的一个图片和另一列中的第一张图片之间寻找一个交换,以最小化与平均值的最大偏差。

我使用了 30 张图片的随机样本,高度在 5 到 50 个“单位”之间。就我而言,收敛速度很快,并且在 first_fit 算法上得到了显着改进。

代码(Python 3.2:

def first_fit(items, bincount=3):
    items = sorted(items, reverse=1) # New - improves first fit.
    bins     = [[] for c in range(bincount)]
    binsizes = [0] * bincount
    for item in items:
        minbinindex = binsizes.index(min(binsizes))
        bins[minbinindex].append(item)
        binsizes[minbinindex] += item
    average = sum(binsizes) / float(bincount)
    maxdeviation = max(abs(average - bs) for bs in binsizes)

    return bins, binsizes, average, maxdeviation

def swap1(columns, colsize, average, margin=0):
    'See if you can do a swap to smooth the heights'
    colcount = len(columns)
    maxdeviation, i_a = max((abs(average - cs), i)
                              for i,cs in enumerate(colsize))
    col_a = columns[i_a]
    for pic_a in set(col_a): # use set as if same height then only do once
        for i_b, col_b in enumerate(columns):
            if i_a != i_b: # Not same column
                for pic_b in set(col_b):
                    if (abs(pic_a - pic_b) > margin): # Not same heights
                        # new heights if swapped
                        new_a = colsize[i_a] - pic_a + pic_b
                        new_b = colsize[i_b] - pic_b + pic_a
                        if all(abs(average - new) < maxdeviation
                               for new in (new_a, new_b)):
                            # Better to swap (in-place)
                            colsize[i_a] = new_a
                            colsize[i_b] = new_b
                            columns[i_a].remove(pic_a)
                            columns[i_a].append(pic_b)
                            columns[i_b].remove(pic_b)
                            columns[i_b].append(pic_a)
                            maxdeviation = max(abs(average - cs)
                                               for cs in colsize)
                            return True, maxdeviation
    return False, maxdeviation

def printit(columns, colsize, average, maxdeviation):
    print('columns')
    pp(columns)
    print('colsize:', colsize)
    print('average, maxdeviation:', average, maxdeviation)
    print('deviations:', [abs(average - cs) for cs in colsize])
    print()


if __name__ == '__main__':
    ## Some data
    #import random
    #heights = [random.randint(5, 50) for i in range(30)]
    ## Here's some from the above, but 'fixed'.
    from pprint import pprint as pp

    heights = [45, 7, 46, 34, 12, 12, 34, 19, 17, 41,
               28, 9, 37, 32, 30, 44, 17, 16, 44, 7,
               23, 30, 36, 5, 40, 20, 28, 42, 8, 38]

    columns, colsize, average, maxdeviation = first_fit(heights)
    printit(columns, colsize, average, maxdeviation)
    while 1:
        swapped, maxdeviation = swap1(columns, colsize, average, maxdeviation)
        printit(columns, colsize, average, maxdeviation)
        if not swapped:
            break
        #input('Paused: ')

输出:

columns
[[45, 12, 17, 28, 32, 17, 44, 5, 40, 8, 38],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 34, 9, 37, 44, 30, 20, 28]]
colsize: [286, 267, 248]
average, maxdeviation: 267.0 19.0
deviations: [19.0, 0.0, 19.0]

columns
[[45, 12, 17, 28, 17, 44, 5, 40, 8, 38, 9],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 34, 37, 44, 30, 20, 28, 32]]
colsize: [263, 267, 271]
average, maxdeviation: 267.0 4.0
deviations: [4.0, 0.0, 4.0]

columns
[[45, 12, 17, 17, 44, 5, 40, 8, 38, 9, 34],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 37, 44, 30, 20, 28, 32, 28]]
colsize: [269, 267, 265]
average, maxdeviation: 267.0 2.0
deviations: [2.0, 0.0, 2.0]

columns
[[45, 12, 17, 17, 44, 5, 8, 38, 9, 34, 37],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 44, 30, 20, 28, 32, 28, 40]]
colsize: [266, 267, 268]
average, maxdeviation: 267.0 1.0
deviations: [1.0, 0.0, 1.0]

columns
[[45, 12, 17, 17, 44, 5, 8, 38, 9, 34, 37],
 [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42],
 [46, 44, 30, 20, 28, 32, 28, 40]]
colsize: [266, 267, 268]
average, maxdeviation: 267.0 1.0
deviations: [1.0, 0.0, 1.0]

好问题。


这是我在下面的单独评论中提到的反向排序信息。

>>> h = sorted(heights, reverse=1)
>>> h
[46, 45, 44, 44, 42, 41, 40, 38, 37, 36, 34, 34, 32, 30, 30, 28, 28, 23, 20, 19, 17, 17, 16, 12, 12, 9, 8, 7, 7, 5]
>>> columns, colsize, average, maxdeviation = first_fit(h)
>>> printit(columns, colsize, average, maxdeviation)
columns
[[46, 41, 40, 34, 30, 28, 19, 12, 12, 5],
 [45, 42, 38, 36, 30, 28, 17, 16, 8, 7],
 [44, 44, 37, 34, 32, 23, 20, 17, 9, 7]]
colsize: [267, 267, 267]
average, maxdeviation: 267.0 0.0
deviations: [0.0, 0.0, 0.0]

如果您有反向排序,附加到上述代码底部的这个额外代码(在 'if name == ... 中)将对随机数据进行额外试验:

for trial in range(2,11):
    print('\n## Trial %i' % trial)
    heights = [random.randint(5, 50) for i in range(random.randint(5, 50))]
    print('Pictures:',len(heights))
    columns, colsize, average, maxdeviation = first_fit(heights)
    print('average %7.3f' % average, '\nmaxdeviation:')
    print('%5.2f%% = %6.3f' % ((maxdeviation * 100. / average), maxdeviation))
    swapcount = 0
    while maxdeviation:
        swapped, maxdeviation = swap1(columns, colsize, average, maxdeviation)
        if not swapped:
            break
        print('%5.2f%% = %6.3f' % ((maxdeviation * 100. / average), maxdeviation))
        swapcount += 1
    print('swaps:', swapcount)

额外的输出显示了交换的效果:

## Trial 2
Pictures: 11
average  72.000 
maxdeviation:
 9.72% =  7.000
swaps: 0

## Trial 3
Pictures: 14
average 118.667 
maxdeviation:
 6.46% =  7.667
 4.78% =  5.667
 3.09% =  3.667
 0.56% =  0.667
swaps: 3

## Trial 4
Pictures: 46
average 470.333 
maxdeviation:
 0.57% =  2.667
 0.35% =  1.667
 0.14% =  0.667
swaps: 2

## Trial 5
Pictures: 40
average 388.667 
maxdeviation:
 0.43% =  1.667
 0.17% =  0.667
swaps: 1

## Trial 6
Pictures: 5
average  44.000 
maxdeviation:
 4.55% =  2.000
swaps: 0

## Trial 7
Pictures: 30
average 295.000 
maxdeviation:
 0.34% =  1.000
swaps: 0

## Trial 8
Pictures: 43
average 413.000 
maxdeviation:
 0.97% =  4.000
 0.73% =  3.000
 0.48% =  2.000
swaps: 2

## Trial 9
Pictures: 33
average 342.000 
maxdeviation:
 0.29% =  1.000
swaps: 0

## Trial 10
Pictures: 26
average 233.333 
maxdeviation:
 2.29% =  5.333
 1.86% =  4.333
 1.43% =  3.333
 1.00% =  2.333
 0.57% =  1.333
swaps: 4
于 2011-04-16T21:03:40.600 回答
5

这就是离线 makepan 最小化问题,我认为它相当于多处理器调度问题。你有图像而不是工作,而不是工作持续时间你有图像高度,但这是完全相同的问题。(它涉及空间而不是时间的事实并不重要。)因此(大约)解决其中任何一个的任何算法都可以。

于 2011-04-11T20:03:52.213 回答
3

这是一种算法(称为First Fit Decreasing),可以在合理的时间内为您提供非常紧凑的排列。可能有更好的算法,但这非常简单。

  1. 按从高到低的顺序对图像进行排序。
  2. 拍摄第一张图像,并将其放在最短的列中。(如果多列高度相同(并且最短),则选择任何一列。)
  3. 重复步骤 2,直到没有图像。

完成后,您可以重新排列每列中的元素,但如果您不喜欢从最高到最短的外观,您可以选择。

于 2011-04-11T21:34:08.783 回答
0

这是一个:

 // Create initial solution
 <run First Fit Decreasing algorithm first>
 // Calculate "error", i.e. maximum height difference
 // after running FFD
 err = (maximum_height - minimum_height)
 minerr = err

 // Run simple greedy optimization and random search
 repeat for a number of steps: // e.g. 1000 steps
    <find any two random images a and b from two different columns such that
     swapping a and b decreases the error>
    if <found>:
         swap a and b
         err = (maximum_height - minimum_height)
         if (err < minerr):
              <store as best solution so far> // X
    else:
         swap two random images from two columns
         err = (maximum_height - minimum_height)

 <output the best solution stored on line marked with X>
于 2011-04-14T03:31:09.923 回答