根据矩阵对矩阵中的元素进行排序

这可以通过ILP（整数线性规划）来完成。粗略的切割如下所示。您似乎没有声明权重来考虑一个结果优于另一个结果，因此您也可能很幸运地使用 CP（约束规划）方法。下面的 ILP 使用成功元素填充的数量作为目标。可能有很多解决方案（或没有解决方案），它只会抓住第一个发现的解决方案。

值得注意的是，您提供的示例没有针对 3x3 目标矩阵的解决方案。我使用下面的部分从单位矩阵（翻转 1/0）中制作元素，通过检查，这是最适合拟合元素列表的方法。

我稍微调整了你的函数，因为你有一个混合模式，你接受（x，y）并返回一个编号的位置。我刚刚做到了这一切（x，y）adj()

如果有解，对于中等大小的 ，这往往会很快找到它，尤其是在解集很大的情况下。matrix_a

我在这里使用了求解器，这是不错的免费软件，但还有其他 MIP 求解器可以正常工作（glpk、highs......cbc

这里仍然有一些“骨头上的肉”来优化这一点，主要是通过域将元组修剪为基于值的合法赋值，这意味着任何具有非零属性的元素都是不合法的，应该从 的域中删除。然后，您可以考虑预先计算任何给定元素的可能邻居，以稍微减小约束的大小。[e, p, a]aplace[e, p, a]eaplaceadjacency

法典：

"""
fit elements into matrix based on adjacency rules
"""

import numpy as np
import pyomo.environ as pyo


class Element:
    """a convenience to hold the rows of attribute values"""
    def __init__(self, row):
        self.attributes = tuple(row)

    def attribute(self, idx):
        return self.attributes[idx]

    def __repr__(self):
        return str(self.attributes)


class Position:
    """a convenience for (x, y) positions that must have equality & hash defined for consistency"""
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f'({self.x}, {self.y})'

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        if isinstance(other, Position):
            return (self.x, self.y) == (other.x, other.y)
        return False

# each 'row' corresponds to an element
# each 'column' corresponds to an attribute of the various elements
# here, each element has 5 attributes, which are always 0 or 1
element_map = np.array([[0, 0, 1, 0, 1],  # element 1
                        [1, 1, 1, 0, 1],  # element 2
                        [1, 0, 0, 1, 0],  # element 3
                        [1, 0, 1, 0, 0],  # etc.
                        [1, 1, 1, 0, 0],
                        [1, 1, 0, 1, 0],
                        [1, 0, 1, 0, 1],
                        [1, 1, 0, 0, 0],
                        [1, 1, 0, 0, 0]])  # element 9

# Alternate element map...
d = 5
element_map = np.ones((d, d), dtype=int) - np.eye(d, dtype=int)
print(element_map)

matrix_a_rows = 3
matrix_a_cols = 3
matrix_a = np.zeros((matrix_a_rows, matrix_a_cols))


def adj_xy(mat, p: Position):
    x, y = p.x, p.y
    res = []
    rows = len(mat) - 1
    cols = len(mat[0]) - 1
    for i in range(x - 1, x + 2):
        for j in range(y - 1, y + 2):
            if all((0 <= i <= rows, 0 <= j <= cols, (i, j) != (x, y))):
                res.append(Position(i, j))
    return res


# SET UP ILP
m = pyo.ConcreteModel('matrix_fitter')

# SETS

m.E = pyo.Set(initialize=[Element(row) for row in element_map], doc='elements')
m.P = pyo.Set(initialize=[Position(x, y) for x in range(len(matrix_a)) for y in range(len(matrix_a[0]))],
              doc='positions')
m.A = pyo.Set(initialize=list(range(len(element_map[0]))), doc='attribute')

# VARS
# place element e in position p based on attribute a being 0...
m.place = pyo.Var(m.E, m.P, m.A, domain=pyo.Binary, doc='place')

# OBJ:  Place as many as possible....  ideally --> len(matrix_a)
m.obj = pyo.Objective(expr=pyo.sum_product(m.place), sense=pyo.maximize)


# CONSTRAINTS
@m.Constraint(m.E, m.P, m.A)
def zero_attribute(m, e: Element, p, a):
    # can only place if attribute a is zero
    return m.place[e, p, a] * e.attribute(a) == 0


@m.Constraint(m.P)
def only_one(m, p):
    # can only place at most one element at each location
    return sum(m.place[e, p, a] for e in m.E for a in m.A) <= 1


@m.Constraint(m.E, m.P, m.A)
def adjacency(m, e: Element, p: Position, a):
    # neighbors must "add up" in the selected attribute (a), if placed in neighbor positions
    # we can "add up" the values of the selected attribute (a) for all adjacent positions that were selected
    neighbor_positions = adj_xy(matrix_a, p)
    return (sum(m.place[ee, pp, aa] * ee.attribute(a) for ee in m.E for pp in neighbor_positions for aa in m.A) >=
            len(neighbor_positions) * m.place[e, p, a])


solver = pyo.SolverFactory('cbc')
results = solver.solve(m, tee=True)
print(results)
if results.solver.termination_condition == pyo.TerminationCondition.optimal:
    for idx in m.place.index_set():
        if m.place[idx].value == 1:
            print(idx)
    if pyo.value(m.obj) == matrix_a_rows * matrix_a_cols:
        # all positions were filled
        print('success!')
    else:
        print(f'the max number of elements that can be placed is {pyo.value(m.obj)} / {matrix_a_rows * matrix_a_cols}')

else:
    print('Problem with model...see results')

输出（截断）：

((0, 1, 1, 1, 1), (0, 1), 0)
((0, 1, 1, 1, 1), (2, 1), 0)
((1, 1, 0, 1, 1), (1, 0), 2)
((1, 1, 0, 1, 1), (1, 2), 2)
((1, 1, 1, 0, 1), (1, 1), 3)
((1, 1, 1, 1, 0), (0, 0), 4)
((1, 1, 1, 1, 0), (0, 2), 4)
((1, 1, 1, 1, 0), (2, 0), 4)
((1, 1, 1, 1, 0), (2, 2), 4)
success!