logo标签列表

如何解决这个线性规划问题？

algorithmcachingtreematrix
17

我不太擅长线性规划，所以在这里发布了这个问题。希望有人能指导我正确的方向。这不是作业问题，不要误解。

我有一个5x5的矩阵（25个节点）。每个节点与其相邻节点（或邻居节点）之间的距离为1单位。一个节点可以处于2种状态之一：缓存或访问。如果一个节点'i'是缓存节点，则访问节点'j'可以使用成本为Dij x Aij（访问成本）访问它。 Dij是节点i和j之间的曼哈顿距离。Aij是从节点i到j的访问频率。

为了成为缓存节点i，它需要使用成本为Dik x C从现有缓存节点k进行缓存，其中C为整数常量（缓存成本）。C称为缓存频率。

A是一个25x25的矩阵，包含所有整数，显示任何一对节点i和j之间的访问频率。D是一个25x25的矩阵，包含任何一对节点i和j之间的所有曼哈顿距离。

假设矩阵中有1个缓存节点，请找出其他缓存节点和访问节点的集合，使得总成本最小。总成本=总缓存成本+总访问成本。

我希望有机会解决这个问题，我很想复习一下线性规划。可惜，我已经生疏了而且没有机会。:( - Brent Arias
我实际上已经解决了这个问题，但那是一种费时的穷举方法。因此，我想知道是否有比我更聪明的人可以更快地解决它，我敢打赌肯定有 :) - user188276
你尝试过查看最小割算法吗？你确定只能通过LP来解决吗？从外观上看，它似乎在“呼喊”最小割（我可能听力不好 :)。从我的经验来看：你有节点之间的边缘成本，并希望将集合分成两个部分（缓存节点和访问节点），以最小化成本...我会花一些时间将其减少到最小割（或更具体地说是图像分割），看看是否可行。 - PhD
这似乎是子集问题的变体，而子集问题是NP-完全问题。我不确定它是否完全等同于NP-完全问题，但很可能是NP-完全问题。这意味着您需要指数级运行时间来完全搜索解空间。NP-完全问题非常难以/耗时地精确解决，但可以快速找到近似解。最近我读到“蜂巢”算法可以成功地解决NP-完全问题并得出合理的解决方案。 - Stephen Chung
3个回答
7

我已经解决了一些类似的问题。

首先，如果你不需要一个精确的答案，我通常建议你考虑使用遗传算法或贪婪算法。虽然它不会是正确的答案，但通常也不会太差。而且它比精确算法要快得多。例如，您可以将所有点作为缓存点开始，然后找到使成为非缓存点最大程度降低成本的点。继续这样做，直到删除下一个点会使成本上升，并将其用作您的解决方案。这不会是最好的，但通常会相当不错。

如果您需要一个精确的答案，您将需要对大量数据进行暴力搜索。假设初始缓存点已指定，则您将有224 = 16,777,216个可能的缓存点集合要搜索。这很昂贵。

更便宜的方法（请注意，不是便宜，只是更便宜）是找到剪枝搜索的方法。牢记这样一个事实，即如果在每个集合上进行100倍的工作可以让您平均删除10个点作为缓存点的考虑，那么您的整体算法将访问0.1％的集合，并且您的代码将运行10倍快。因此，即使剪枝步骤相当昂贵，也值得花费惊人的精力来频繁地剪枝。

通常你需要多种剪枝策略。其中一个通常是“从这里开始能做到的最好的比我们先前发现的最好的还要差。”如果您已经找到了相当不错的最佳解决方案，则此方法效果更好。因此，在寻找解决方案的搜索中进行一些本地优化通常是值得的。

通常，这些优化不会改变您正在进行大量工作的事实。但是它们确实让您做的工作量减少了几个数量级。

我对此的初步尝试将利用以下观察结果。

  1. 假设x是一个缓存点，y是其最近的缓存邻居。如果您只沿着该路径从x到y路由缓存更新流量，则可以使某些路径从x到y免费缓存。因此，不失一般性，缓存点集在网格上是连通的。
  2. 如果最小成本可能超过我们找到的当前最佳成本，则我们不会朝着全局解决方案的方向前进。
  3. 只要所有距离缓存点大于1的点的访问率之和加上您仍然可以使用的缓存点邻居的最高访问频率小于缓存频率，添加更多缓存点总是会造成损失。（这将是一个“昂贵的条件，让我们提前10分钟停止。”）
  4. 当前缓存点集的最高访问邻居是下一个要尝试的缓存点的合理候选人。（还有几种其他启发式方法可供尝试，但这个方法是合理的。）
  5. 任何总访问频率超过缓存频率的点绝对必须是缓存点。

这可能不是最好的观察结果。但它很有可能是相当合理的。要利用这一点，您将需要至少一个您可能不熟悉的数据结构。如果您不知道优先队列是什么，请查找您选择的语言中的有效队列。如果找不到，则堆相当容易实现，并且作为优先队列效果非常好。

考虑到这一点，假设您已经获得了所描述的信息和初始缓存节点P，下面是用于查找最佳解的伪代码。

# Data structures to be dynamically maintained:
#  AT[x, n] - how many accesses x needs that currently need to go distance n.
#  D[x] - The distance from x to the nearest cache node.
#  CA[x] - Boolean yes/no for whether x is a cache node.
#  B[x] - Boolean yes/no for whether x is blocked from being a cache node.
#  cost - Current cost
#  distant_accesses - The sum of the total number of accesses made from more than
#      distance 1 from the cache nodes.
#  best_possible_cost - C * nodes_in_cache + sum(min(total accesses, C) for non-cache nodes)
#  *** Sufficient data structures to be able to unwind changes to all of the above before
#      returning from recursive calls (I won't specify accesses to them, but they need to
#      be there)
#  best_cost - The best cost found.
#  best_solution - The best solution found.

initialize all of those data structures (including best)
create neighbors priority queue of neighbors of root cache node (ordered by accesses)
call extend_current_solution(neighbors)
do what we want with the best solution

function extend_current_solution (available_neighbors):
    if cost < best_cost:
        best_cost = cost
        best_solution = CA # current set of cache nodes.
    if best_cost < best_possible_cost
        return # pruning time
    neighbors = clone(available_neighbors)
    while neighbors:
        node = remove best from neighbors
        if distant_accesses + accesses(node) < C:
            return # this is condition 3 above
        make node in cache set
            - add it to CA
            - update costs
            - add its immediate neighbors to neighbors
        call extend_current_solution
        unwind changes just made
        make node in blocked set
        call extend_current_solution
    unwind changes to blocked set
    return

这需要大量的工作来完成，并且您需要小心地维护所有数据结构。但是我敢打赌，尽管它看起来很重，但您会发现它能够减少搜索空间，从而比现有解决方案更快地运行。（仍然不会非常迅速。）
祝好运！
更新
当我思考这个问题时，我意识到更好的观察方法是注意到如果您可以将“不是缓存节点，不是阻塞节点”的集合分成两部分，那么您可以独立地解决这些问题。每个子问题比整个问题快几个数量级，因此请尽快解决。
一个很好的启发式方法是遵循以下规则：
1. 在没有到达边缘时： - 向最近的边缘驾驶。距离是通过沿着非缓存、非阻塞集的最短路径来测量的。 - 如果两个边缘距离相等，则按照以下优先顺序进行排序：(1, x)，(x, 1)，(5, x)，(x, 5)。 - 按照朝向边缘中心的方向打破任何剩余的关系。 - 随机打破任何剩余的联系。
2. 当到达边缘并且您的组件仍然有可能成为缓存块时： - 如果您可以立即进入边缘并将边缘块分成两个组件，请这样做。对于“边缘在缓存集中”和“边缘不在缓存集中”，您将获得2个独立的子问题，这些问题更容易处理。 - 否则，朝着您的边缘片段中间的部分移动到最短路径。 - 如果存在关系，则优先选择使从添加的块到添加的缓存元素的线路尽可能接近对角线的任何内容。 - 随机打破任何剩余的联系。
3. 如果您通过这里，请随机选择。（此时您应该有一个非常小的子问题。没有必要聪明。）
如果您尝试以(3, 3)作为缓存点开始，您会发现在前几个决策中，您有7/16的时间成功将其分成两个相等的问题，1/16的时间阻塞在缓存点并完成，1/4的时间成功将一个2x2块切出一个单独的问题（使整体解决方案运行16倍快），1/4的时间您会很快地陷入困境，或者是候选解决方案，它具有许多需要被修剪的缓存点，因为它正朝着成为一个糟糕解决方案的轨迹前进。

我不会为这种变体提供伪代码。它将与上面所述的内容有很多相似之处，需要处理许多重要细节。但我敢打赌，在实践中，它比您原来的解决方案运行速度快几个数量级。

实现剪枝步骤的更好方法是将问题放松为线性规划，并使用Simplex（Simplex在复杂度上近似于线性）来解决它。这给出了成本的下限，告诉我们哪个分支更有可能包含最优解（因此深度优先搜索应该首先跟随它）。当找到任何解决方案时，所有较差边界的子树都可以完全剪枝。 - Ben Voigt
@ben-voigt：我不确定如何将这个问题放宽到线性规划。如果你能在答案中写出一个合理的描述，我会投票支持它。 - btilly
3
事实上，这是一个编程中的问题。通常很难解决。 - Martijn
1
实际上，这是一个二进制编程问题。通过使用Simplex解决线性规划作为上界，并修剪候选空间，可以高效地解决整数和二进制程序。 - Ben Voigt
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接