我已经解决了一些类似的问题。
首先,如果你不需要一个精确的答案,我通常建议你考虑使用遗传算法或贪婪算法。虽然它不会是正确的答案,但通常也不会太差。而且它比精确算法要快得多。例如,您可以将所有点作为缓存点开始,然后找到使成为非缓存点最大程度降低成本的点。继续这样做,直到删除下一个点会使成本上升,并将其用作您的解决方案。这不会是最好的,但通常会相当不错。
如果您需要一个精确的答案,您将需要对大量数据进行暴力搜索。假设初始缓存点已指定,则您将有224 = 16,777,216个可能的缓存点集合要搜索。这很昂贵。
更便宜的方法(请注意,不是便宜,只是更便宜)是找到剪枝搜索的方法。牢记这样一个事实,即如果在每个集合上进行100倍的工作可以让您平均删除10个点作为缓存点的考虑,那么您的整体算法将访问0.1%的集合,并且您的代码将运行10倍快。因此,即使剪枝步骤相当昂贵,也值得花费惊人的精力来频繁地剪枝。
通常你需要多种剪枝策略。其中一个通常是“从这里开始能做到的最好的比我们先前发现的最好的还要差。”如果您已经找到了相当不错的最佳解决方案,则此方法效果更好。因此,在寻找解决方案的搜索中进行一些本地优化通常是值得的。
通常,这些优化不会改变您正在进行大量工作的事实。但是它们确实让您做的工作量减少了几个数量级。
我对此的初步尝试将利用以下观察结果。
- 假设
x
是一个缓存点,y
是其最近的缓存邻居。如果您只沿着该路径从x
到y
路由缓存更新流量,则可以使某些路径从x
到y
免费缓存。因此,不失一般性,缓存点集在网格上是连通的。
- 如果最小成本可能超过我们找到的当前最佳成本,则我们不会朝着全局解决方案的方向前进。
- 只要所有距离缓存点大于1的点的访问率之和加上您仍然可以使用的缓存点邻居的最高访问频率小于缓存频率,添加更多缓存点总是会造成损失。(这将是一个“昂贵的条件,让我们提前10分钟停止。”)
- 当前缓存点集的最高访问邻居是下一个要尝试的缓存点的合理候选人。(还有几种其他启发式方法可供尝试,但这个方法是合理的。)
- 任何总访问频率超过缓存频率的点绝对必须是缓存点。
这可能不是最好的观察结果。但它很有可能是相当合理的。要利用这一点,您将需要至少一个您可能不熟悉的数据结构。如果您不知道优先队列是什么,请查找您选择的语言中的有效队列。如果找不到,则堆相当容易实现,并且作为优先队列效果非常好。
考虑到这一点,假设您已经获得了所描述的信息和初始缓存节点P
,下面是用于查找最佳解的伪代码。
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
if best_cost < best_possible_cost
return
neighbors = clone(available_neighbors)
while neighbors:
node = remove best from neighbors
if distant_accesses + accesses(node) < C:
return
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的时间您会很快地陷入困境,或者是候选解决方案,它具有许多需要被修剪的缓存点,因为它正朝着成为一个糟糕解决方案的轨迹前进。
我不会为这种变体提供伪代码。它将与上面所述的内容有很多相似之处,需要处理许多重要细节。但我敢打赌,在实践中,它比您原来的解决方案运行速度快几个数量级。