17 algorithm tree caching matrix
我不太擅长线性编程,所以我在这里发布这个问题.希望有人可以指出我正确的方向.这不是作业问题,所以不要误解.
我有一个矩阵5x5 (25个节点).每个节点与其相邻节点(或相邻节点)之间的距离为1个单位.节点可以处于以下两种情况之一:缓存或访问.如果节点"i"是缓存节点,则访问节点"j"能够以Dij x Aij (访问成本)的成本访问它.Dij是节点i和j之间的曼哈顿距离.Aij是从节点i到j的访问频率.
为了成为缓存节点i,它需要从现有缓存节点k缓存成本为Dik×C,其中C是整数常量.(缓存成本).C称为缓存频率.
A被提供为包含所有整数的25×25矩阵,其显示任何节点i和j之间的访问频率.D被提供为25×25矩阵,其包含任何节点i和j之间的所有曼哈顿距离.
假设矩阵中有1个缓存节点,找出其他缓存节点和访问节点的集合,以便最小化总成本. 总成本=总缓存成本+总访问成本.
我已经解决了一些像这样的问题.
首先,如果你不需要一个确切的答案,我通常建议你研究类似遗传算法,或做一个贪婪的算法.这不对,但一般也不会坏.它将比精确的算法快得多.例如,您可以将所有点作为缓存点开始,然后找到最大限度降低成本的点,使其成为非缓存点.继续,直到删除下一个使成本上升,并将其用作您的解决方案.这不是最好的.它通常会相当不错.
如果确实需要确切的答案,则需要强力搜索大量数据.假设指定了初始缓存点,您将有2 24 = 16,777,216个可能的缓存点集进行搜索.那很贵.
更便宜地做这件事(注意,不便宜,只是更便宜)的方法是找到修剪你的搜索的方法.请注意这样一个事实:如果你在每组上做100倍的工作,你可以将平均10个点从考虑中移除作为缓存点,那么你的整体算法将访问0.1%的集合,并且你的代码将会运行快了10倍.因此,即使修剪步骤相当昂贵,也值得花费大量精力尽早修剪.
通常你需要多种修剪策略.其中一个通常是"我们能从这里做的最好的事情比我们之前发现的最好." 如果您已经找到了一个非常好的最佳解决方案,那么效果会更好.因此,在搜索解决方案时进行局部优化通常值得花一些时间.
通常,这些优化不会改变您正在进行大量工作的事实.但他们确实让你的工作量减少了一半.
我最初的尝试将利用以下观察.
x是一个缓存点,并且y是最近的缓存邻居.然后你就可以随时做出一些路径从x到y缓存中"免费"如果你只是从路由缓存更新流量x,以y沿该路径.因此,不失一般性,该组高速缓存点连接在网格上.这可能不是最好的观察集.但这可能是非常合理的.要利用这一点,您至少需要一个您可能不熟悉的数据结构.如果您不知道优先级队列是什么,那么请用您选择的语言环顾四周.如果找不到堆,那么堆很容易实现,并且作为优先级队列工作得很好.
考虑到这一点,假设您已经获得了您所描述的信息和初始缓存节点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, x), (x, 1), (5, x), (x, 5).如果你(3, 3)以缓存点开始尝试这个,你会发现在最初的几个决定中你会发现7/16的时间你设法切成两个甚至是问题,你阻止了1/16的时间在缓存点和完成时,1/4的时间你设法将一个2x2块切割成一个单独的问题(使整个解决方案运行速度快16倍)和1/4的时间你很好地结束你正朝着一个解决方案的方向前进(或者快速耗尽),或者是一个具有大量缓存点的解决方案的候选者,这些缓存点会因为成为一个糟糕的解决方案而被修剪.
我不会为这种变化提供伪代码.它将与我上面的内容有很多相似之处,需要处理许多重要细节.但我愿意赌钱,实际上它会比原来的解决方案快几个数量级.
小智 3
解是一个集合，所以这不是一个线性规划问题。它是连接设施位置的特例。Bardossy 和 Raghavan 有一个看起来很有希望的启发式方法：http://terpconnect.umd.edu/~raghavan/preprints/confl.pdf