首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何知道k服务器动态解决方案的最佳路径位于数组成本[i ][ j ][ k ][ t ]中?

问如何知道k服务器动态解决方案的最佳路径位于数组成本[i ][ j ][ k ][ t ]中?
EN

Stack Overflow用户
提问于 2016-11-30 18:20:23
回答 1查看 88关注 0票数 1

您可以通过动态编程类型参数来优化策略:如果输入序列是n个请求点长(p1,.,pn),则创建一个n×n数组;条目costik是从给定的起始位置开始并为请求服务的最便宜的移动序列的成本,并以pi处的黄色服务器、pj处的红色服务器和pk上的蓝色服务器结束。一个ijk必须是t,因为在pt上的最后一个请求是服务的,所有其他表条目都要花费∞。任何可能的表条目都必须通过将三台服务器中的一台从步骤t−1的位置移动而达到。

现在假设我有一个名为positions的数组,它包含点(x,y)坐标值,位置0、1和2的数组分别是服务器1、2、3的初始位置,从3到数组末尾索引的数组元素是请求点。

如果我使用这个算法并计算所有三个服务器所能采取的所有可能路径,我如何才能知道k服务器问题的最佳路径位于哪里?

如果职位的大小是10,为什么cost99不是解决方案,我在哪里可以找到解决方案?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-11-30 18:34:05

若要在计算成本后找到最优解决方案,您可以如下所示:

  1. 为i、j和k的最终值找到最佳组合(只需尝试所有三胞胎)。
  2. 使用(i, j, k, t)初始化当前状态。
  3. 继续查找父状态并进入父状态,直到达到初始状态。
  4. 要找到父状态,可以迭代可能导致当前状态的所有状态,并确保从前一个状态到当前状态的转换确实会产生当前状态的成本(如果有多个选项,则可以选择其中的任何选项)。
  5. 您还可以存储父数组并在计算cost函数时填充它。

一旦您知道了导致最终最优解决方案的状态序列,就可以通过检查每个转换的服务器移动情况来轻松地获得路径本身。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/40895487

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档