在 Julia 网格系统性能问题中查找重叠区域

Question

我目前正在尝试计算网格中一组特定类型的位置。手头的问题与二维打包优化问题有关。

打包物品时，我需要在物品的网格中select一个位置(i,j)。由于项目大小，网格中的其他几个位置也可能被覆盖。因此我需要一组 Qijc，这是一组正方形，其中放置一个项目 c 可能覆盖位置 (i,j)。例如，如果项目 c 的尺寸为 2x2，则 Qijc 包含 {(i,j),(i-1,j-1),(i-1,j),(i,j-1)}。如果项目 c 在这些位置中的任何一个.. 位置 (i,j) 也被覆盖。

我有当前的工作代码。然而，它会强制执行计算，并且在达到 150x400 的网格大小时非常慢。我一直在努力优化代码，我相信我遗漏了一些简单的东西。如有任何建议，我们将不胜感激。

目前，我将信息存储在字典中以实现“一对多”关系。该问题的另一个警告是我只存储项目 c 的位置，如果该位置在网络中可用于项目 c，那么它将覆盖位置 (i,j)。

在给定的示例中，如果项目 c = 3，并且我们正在查看位置 (4,3)，那么将覆盖的位置是 (4,2) 和 (4,3)，但是，位置(5,3) 通常也会覆盖 (4,3)，但是不会存储，因为项目 c 无法到达此位置。（我希望这是有道理的）

我相信我有几个冗余循环，并且可以以更快的方式完成，但是，我很难理解它。

function validpositions(UnusuableSpace::Matrix{Int64}, nCargoes::Int64, SquaresL::Vector{Int64}, SquaresW::Vector{Int64})
    # This function should return all position that are valid in the layout for
    # cargo c in C. This should be returned as a tuple e.g. pos = [(1,1),(4,3),..,(18,1)].
    N = []
    for c in 1:nCargoesM
        pos = Vector{Tuple{Int64,Int64}}()

        for i in SquaresL[c]:size(UnusuableSpace)[1] # skip some of the rows. If the cargo has dimensions > 1.
            for j in 1:size(UnusuableSpace)[2]
                # Check if position includes a pillar / object
                if UnusuableSpace[i,j] != 1
                    # Check if these is space for the cargo in the position.
                    if (i-SquaresL[c]) >= 0 && (j+SquaresW[c]-1) <= size(UnusuableSpace)[2]
                        # Check if position i,j covers an are with pillars in due to cargo
                        # dimensions.
                        if sum(UnusuableSpace[i-SquaresL[c]+1:i,j:j+SquaresW[c]-1]) == 0
                            push!(pos,(i,j))
                        end
                    end
                end
            end

        end
        push!(N,pos)
    end
    # return all valid positions of the cargo c.
    return N
end # end valid position function





nCargoesM = 3
SquaresL = [1,2,3]
SquaresW = [1,2,2]


UnusableSpace = [
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 1 0 0 0
0 0 1 1 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0]

N = validpositions(UnusableSpace, nCargoesM, SquaresL, SquaresW)


function coveringSet(UnusableSpace::Matrix{Int64}, nCargoes::Int64, SquaresL::Vector{Int64}, SquaresW::Vector{Int64}, N)
    Qijc = Dict{}()
    for c in 1:nCargoesM
        for i in 1:size(UnusableSpace)[1]
            for j in 1:size(UnusableSpace)[2]
                tmpset = []
                for (k, l) in N[c]
                    # Get the points/nodes of the areas to check
                    vec1 = [i, j]
                    vec2 = [k-SquaresL[c]+1:k, l:l+SquaresW[c]-1]

                    tmp = [[x, y] for x in vec1[1], y in vec1[2]]
                    tpm = [[x, y] for x in vec2[1], y in vec2[2]]

                    # Check for overlapping
                    if sum([tmp in tpm for tmp = tmp]) > 0
                        push!(tmpset, [k, l])
                    end
                end
                push!(Qijc, [i, j, c] => tmpset)
            end
        end
    end
    return Qijc
end



Qijc = coveringSet(UnusableSpace, nCargoesM, SquaresL, SquaresW, N)

Answer 1

我实际上在一段时间后自己解决了这个问题。您可以预先计算字典中的所有键并穿线循环。检查货物的位置，是否是允许的位置。

function coveringSet_new_threaded(UnusableSpace, nCargoesM::Int64, SquaresL::Vector{Int64}, SquaresW::Vector{Int64})
    # Create dictionary
    Qijc4 = Dict{}()

    for c in 1:nCargoesM
        for i in 1:size(UnusableSpace)[1]
            for j in 1:size(UnusableSpace)[2]
                push!(Qijc4, [i, j, c] => [])
            end
        end
    end

    # Finding the combinations of cargo size
    combinationsCargo = Vector{Tuple{Int64,Int64}}()
    for i in 1:length(SquaresL)
        push!(combinationsCargo, (SquaresL[i], SquaresW[i]))
    end

    # The unique combinations available
    CargoTypes = unique(combinationsCargo)


    Threads.@threads for c in 1:length(CargoTypes)
        typeindx = findall(x -> x == CargoTypes[c], combinationsCargo)
        # Index to control where to find information regarding squaresL and squaresW
        sizeidx = typeindx[1]

        #Threads.@threads for c in 1:nCargoesM
        for i in 1:size(UnusableSpace)[1]
            for j in 1:size(UnusableSpace)[2]
                tmpset = []

                # Generate the range of positions to check. (h,m) check if it also covers (i,j)
                # due to cargo size.
                for h in i:i+SquaresW[sizeidx]-1
                    for m in j-SquaresL[sizeidx]+1:j
                        # Check that the position is actually within the layout of the ship
                        if (h > 0 && m > 0 && h <= size(UnusableSpace)[1] && h <= size(UnusableSpace)[2])
                            # Check that the position is not unusable.
                            if UnusableSpace[h, m] != 1
                                # Check that the position given cargo size is withon the layout of the ship.
                                if (h - SquaresW[sizeidx]) >= 0 && (m + SquaresL[sizeidx] - 1) <= size(UnusableSpace)[2]
                                    # Check that the cargo, when in position (h,m) does not collide with any unusable space.
                                    if sum(UnusableSpace[h-SquaresW[sizeidx]+1:h, m:m+SquaresL[sizeidx]-1]) == 0
                                        # Only then is it a position for cargo c that covers (i,j).
                                        push!(tmpset, [h, m])
                                    end
                                end
                            end
                        end
                    end
                end
                # Push in set for that position. It may be empty.
                for k in typeindx
                    Qijc4[[i, j, k]] = tmpset
                end
            end
        end
    end

    return Qijc4
end

在 Julia 网格系统性能问题中查找重叠区域

Finding overlapping areas in Julia grid system performance question

performance

operations-research

julia