Bài toán sắp xếp hình chữ nhật

Bài toán

Có n hình chữ nhật với kích thước (w_i, h_i). Cho trước khung bao hình chữ nhật với kích thước (W, H). Hãy tìm cách xếp n đó vào khung bao với điều kiện:

Các hình chữ nhật không được xếp chồng lấp lên nhau

Các hình chữ nhật phải được giữ nguyên dạng, không cắt, xoay, ...

Ví dụ:

Khung bao 10x13

Các hình chữ nhật: 2x6 4x4 3x3 4x2 1x3 3x2 2x1

Giải pháp

Giải pháp 1: Tìm kiếm đệ qui thử-sai

Lần lượt đặt từ hcn vào khung sao cho không overlap với các khung đã đặt

global found = false

function main()

    Try(1)

end

function Try(index)

    if index == n then

        found = true

    else

        for col = 1 --> W

            for row = 1 --> H

               if  có thể đặt khung index ở (row, col) //không overlap với các khung từ 1 .. index - 1

                   Đặt hcn index tại (row, col)

                   Try(index + 1)

                   if found then

                       break

end

               endif

            endfor

        endfor

    endif

end

Ưu điểm: Cho kết quả chính xác
Nhược điểm: chi phí tính toán cao, không phù hợp với n lớn hoặc WxH lớn

Giải pháp 2: Xếp theo chiến lượt phân tầng

Ta giả sử khung bao như một kệ sách gồm nhiều tầng, và bài toán trở thành xếp các vật thể lên kệ. Có một số chiến lượt để xếp với điểm chung là sắp xếp các vật thể giảm dần theo chiều cao (chính), và chiều rộng (phụ)

Sau khi sắp xếp, ta có danh sách: 2x6 4x4 3x3 1x3 4x2 3x2 2x1

Cách 1: sắp xếp liên tiếp các vật thể trên từng tầng, khi không thể xếp thì chuyển tầng

Chọn hcn đầu tiên trong danh sách xếp vào khung, khung lúc này được chia thành 2 tầng
Chọn các hcn còn lại, xếp liên tiếp trong tầng cho đến khi không còn tìm được hcn nào vừa vặn
Chuyển lên tầng tiếp theo, tiếp tục quay lại bước đầu

Với vị dụ trên:

Ưu điểm của cách này là khá dễ cài đặt, tuy nhiên xuất hiện khá nhiều vùng trống giữa 2 tầng không được sử dụng

Cách 2: Sắp xếp 2 chiều trên từng tầng, khi không thể xếp thì chuyển tầng

Các này giúp cải tiến cách một, sau khi xếp trong 1 chiều trên 1 tầng như cách một, tiến hành xếp theo chiều ngược lại nếu có thể

Trong cách này, ô màu đỏ (tầng 1 - bảng 2) được xếp theo chiều ngược lại sau khi đã xếp xong tầng 1 như cách 1.

Cách 3: Phương thức này tận dụng tối đa các vùng trống để lại từ phương pháp trên. Ý tưởng cơ bản của giải thuật này là tiếp tục chia "tầng con" sau khi phân tầng

Giải thuật

B1: Gọi regions là danh sách các vùng cần xét, lưu trữ dạng queue. Gọi list_rect la danh sách các hình chữ nhật (hcn) cần sắp xếp

B2: Thực hiện vòng lặp đến khi không còn vùng nào trong danh sách hoặc tất cả các hcn đã được chọn

B2.1:    Chọn ra một reg trong regions (dequeue)

B2.2:    Tìm hcn sao cho kích thước gần khớp với reg nhất (không vượt qua reg)

B2.3:    Nếu tồn tại hcn thỏa yêu cầu trên:

B2.3.1:        Loại hcn ra khỏi danh sách list_rect

B2.3.2:        Thêm 2 vùng mới vào queue (enqueue)

{x = reg.x, y = reg.y + hcn .h, w = reg.w, h = reg.h - hcn.h}

{x = reg.x + hcn.w, y = reg.y, w = reg.w - hcn.w, h = reg.h}

B3: Nếu không còn hcn nào trong danh sách list_rect thì xem như bài toán được giải quyết

Kết quả:

Như vậy, với cách sắp xếp này, khoảng trống hữu dụng còn lại nhiều hơn 2 cách trước (chỉ mang tính tương đối)

Source code (python)

import sys

from sys import argv

def Rearrange(list, width, height):

    x = 0

    y = 0

    liney = 0

    isAdd = False

    isNewLine = False

    items = []

    for obj in list:

        items.append(obj)

    items = sorted(items, key=lambda k: (-k['h'], -k['w']))

    for obj in items:

        print(obj['w'], obj['h'])

    if items[0]['w'] > width or items[0]['h'] > height:

        return [-1, -1]

    regions = []

    reg = {'x':0, 'y':0, 'w':width, 'h':height, 'size':width*height}

    regions.append(reg)

    max_height = -1

    max_width = -1

    while len(items) > 0 and len(regions) > 0:

        reg = regions.pop()

        mix_dif = 99999999

        select_item = -1

        for obj in items:

            if obj['w'] <= reg['w'] and obj['h'] <= reg['h']:

                dif = (reg['w'] - obj['w']) + (reg['h'] - obj['h'])

                if dif < mix_dif:

                    mix_dif = dif

                    select_item = obj

        if not select_item == -1:

            obj = select_item

            obj['x'] = reg['x']

            obj['y'] = reg['y']

            if max_height < obj['y'] + obj['h']:

                max_height = obj['y'] + obj['h']

            if max_width < obj['x'] + obj['w']:

                max_width = obj['x'] + obj['w']

            items.remove(obj)

            reg1 = {'x':reg['x'], 'y':reg['y'] + obj['h'], 'w':reg['w'], 'h':reg['h'] - obj['h']}

            reg2 = {'x':reg['x'] + obj['w'], 'y':reg['y'], 'w':reg['w'] - obj['w'], 'h':obj['h']}

            regions.append(reg1)

            regions.append(reg2)

    if (len(items) == 0):

        # print (max_width, max_height, max_width*max_height)

        return [max_width, max_height]

    else:

        return [-1, -1]

def PadText(txt):

    txt = "%s"%(txt)

    while len(txt) < 8:

        txt = txt + " "

    return txt

def main(argv):

    listRect = []

    listRect.append({'name':"Rect-1", 'x': 0, 'y': 0, 'w': 2, 'h': 6})

    listRect.append({'name':"Rect-2", 'x': 0, 'y': 0, 'w': 4, 'h': 4})

    listRect.append({'name':"Rect-3", 'x': 0, 'y': 0, 'w': 3, 'h': 3})

    listRect.append({'name':"Rect-5", 'x': 0, 'y': 0, 'w': 4, 'h': 2})

    listRect.append({'name':"Rect-6", 'x': 0, 'y': 0, 'w': 1, 'h': 3})

    listRect.append({'name':"Rect-7", 'x': 0, 'y': 0, 'w': 3, 'h': 2})

    listRect.append({'name':"Rect-7", 'x': 0, 'y': 0, 'w': 2, 'h': 1})

    re = Rearrange(listRect, 10, 13)

    for item in listRect:

        print("%s: x = %s y = %s w = %s h = %s"%(PadText(item['name']), PadText(item['x']), PadText(item['y']), PadText(item['w']), PadText(item['h'])))

    print(re[0], re[1])

#=================================================================================

if __name__ == '__main__':

    main(sys.argv)

Cải tiến

Trước khi xếp, sắp xếp các object giảm dần về kích thước
Trong khi xếp, ở bước chia vùng, có 2 cách chia vùng:

Chọn cách cho ra kết quả có vùng trống được tạo ra là lớn nhất.
Sắp xếp các vùng trống giảm dần theo kích thước

# list item format : {'name':reg_name, 'x': x, 'y': y, 'w': w, 'h': h, 'rearrangeX': x, 'rearrangeY': y}

def Rearrange(list, width, height):

    # print("======width x height = %s %s======="%(width, height))

    x = 0

    y = 0

    liney = 0

    isAdd = False

    isNewLine = False

    items = []

    for obj in list:

        items.append(obj)

    if items[0]['w'] > width or items[0]['h'] > height:

        return [-1, -1]

    regions = []

    reg = {'x':0, 'y':0, 'w':width, 'h':height, 'size':width*height}

    regions.append(reg)

    max_height = -1

    max_width = -1

    items = sorted(items, key=lambda k: -k['w']*k['h'])  # sort items descending order by size

    while len(items) > 0 and len(regions) > 0:

        reg = regions.pop()

        mix_dif = 99999999

        select_item = -1

        for obj in items:

            if obj['w'] <= reg['w'] and obj['h'] <= reg['h']:

                dif = (reg['w'] - obj['w']) + (reg['h'] - obj['h'])

                if dif < mix_dif:

                    mix_dif = dif

                    select_item = obj

                    break

        if not select_item == -1:

            obj['rearrangeX'] = reg['x']

            obj['rearrangeY'] = reg['y']

            if max_height < obj['rearrangeY'] + obj['h']:

                max_height = obj['rearrangeY'] + obj['h']

            if max_width < obj['rearrangeX'] + obj['w']:

                max_width = obj['rearrangeX'] + obj['w']

            items.remove(obj)

            #there're two way to split free region into up/right. Choose the best way (given bigger free region)

            regUp1  = {'x':reg['x'], 'y':reg['y'] + obj['h'], 'w':reg['w'], 'h':reg['h'] - obj['h'], 'size':reg['w']*(reg['h'] - obj['h'])}

            regRight1 = {'x':reg['x'] + obj['w'], 'y':reg['y'], 'w':reg['w'] - obj['w'], 'h':obj['h'], 'size':(reg['w'] - obj['w'])*obj['h']}

            candidateSize1 = max(regUp1['size'], regRight1['size'])

            regUp2 = {'x':reg['x'], 'y':reg['y'] + obj['h'], 'w':obj['w'], 'h':reg['h'] - obj['h'], 'size':obj['w']*(reg['h'] - obj['h'])}

            regRight2 = {'x':reg['x'] + obj['w'], 'y':reg['y'], 'w':reg['w'] - obj['w'], 'h':reg['h'], 'size':(reg['w'] - obj['w'])*reg['h']}

            candidateSize2 = max(regUp2['size'], regRight2['size'])

            if candidateSize1 > candidateSize2:

                regions.append(regUp1)

                regions.append(regRight1)

            else:

                regions.append(regUp2)

                regions.append(regRight2)

            # break

        regions = sorted(regions, key=lambda k: -k['size'])  # sort regions descending order by size

    if (len(items) == 0):

        return [max_width, max_height]

    else:

        return [-1, -1]

Kết luận phương pháp xếp tầng

Ưu điểm: cài đặt đơn giản, cho tốc độ xử lý tốt
Nhược điểm: cho kết quả chỉ mang tính tương đối, không hoàn hảo như trường hợp thử-sai

Các giải thuật khác và tài liệu

http://users.cs.cf.ac.uk/C.L.Mumford/heidi/Algorithms.html

http://homepage3.nifty.com/ono-t/GA/GA-papers/TO-099.pdf

Ứng dụng

Bài toán này thường được ứng dụng trong việc sắp xếp các module hình ảnh trong game, đảm bảo tối ưu về kích thước resource, loại bỏ dư thừa.

Bài toán liên quan với bài toán này là tìm vùng bao nhỏ nhất của tập hình cho trước. Đây là bài toán rất khó, tuy nhiên có thể áp dụng phương pháp phân tầng để cho kết quả khả dĩ.

Page updated

Google Sites

Report abuse