有哪些已知算法（或查找算法的资源）可以在约束满足问题中找到最大化分配变量数量的分配（如果不存在令人满意的分配）？
问问题
351 次
2 回答
0
对于线性方程，线性代数可用于计算自由度的数量，从而确定可分配自变量的数量。
编辑：
在仔细考虑您的问题后，我认为Simplex 算法可能会对您有所帮助。它是一种优化算法，用于寻找线性优化问题的最佳整数解。
编辑2：
设可行区域为提供的仓库。
例子：
假设您有 2 个仓库类型，X 和 Y。
X 需要提供 5 种油和 7 种钢材。
Y 需要提供 8 种油和 2 种钢材。
您想最大化提供的仓库数量：
最大化函数 = X + Y
条件：
X <= X 型油库总数 Y <= Y 型油库总数 5X + 8Y < 石油供应总量 7X + 2Y < 钢材供应总量
应用 Simplex 算法，瞧！
于 2013-02-21T09:08:26.417 回答
0
您是否想最大化满足约束的数量，而不是分配变量？我考虑过最大化分配变量的数量可能会获得什么（直到您微不足道地看到至少违反了一个约束），在我看来，您想要一些符合可满足的最大约束子集的东西。否则我可能不明白你的优化标准。
如果您想要这个可满足约束的最大子集，一个想法是将您的问题转换为约束优化问题，找到最小化违反约束数量的分配，然后选择该分配满足的所有约束来构建最大可满足约束的子集。
下面我将使用加权约束满足问题（WCSP）的框架。
鉴于您将约束表示为允许或不允许的部分分配表，您可以通过简单地分配允许的分配成本 0 和不允许的分配成本 1 来转换约束。也就是说，只要约束不允许变量分配，它就会产生一个成本。因此，最小化成本的分配会最小化它违反的约束的数量，这相当于最大化满足的约束的数量。一旦你有了这样的分配，通过迭代所有约束并检查分配是否满足它们应该很容易构造可满足约束的最大子集。WCSP 的一个很好的求解器是toulbar2，它计算给定 WCSP 的最小成本分配。
如果您确实将约束表示为表，则从约束满足问题 (CSP) 构造 WCSP 很简单。加权约束只是表格的表格
X_1 X_2 … X_n c
1 1 … 1 0
1 2 … 1 0
...
2 2 … 3 1
2 2 … 4 1
这里我们对 n 个变量 X_1, ..., X_n 有一个约束，其中变量可以接受来自有限域 {1,2} 和 {1,2,3,4} 的值。假设您将允许的元组标记为“T”，而将不允许的元组标记为“F”，则转换金额为将“T”替换为成本 0，将“F”替换为成本 1。
请注意，这不是实际的 WCSP 格式。格式在上面链接的 toulbar2 包中有详细描述。
当然，更紧凑的约束表示将需要更精细的转换，这可能会根据您的表示变得任意复杂。那就是你可能想要研究其他东西的地方。
于 2013-03-01T16:48:36.340 回答