3

我正在尝试使用动态算法为 3 台服务器获取K-server 问题的最佳解决方案。这个想法是生成所有可能的排列并检查它们以找到最佳值。

我知道这是一个指数时间大 O 的慢排气搜索算法。无论如何，这就是我所拥有的，据我所知它应该可以工作，但它给了我错误的价值。

这里前 3 点是服务器。dist(x,y) 函数计算点 x 和 y 的笛卡尔距离。

void optimalSol()
{

int cost[10][10][10][10];
for(int l=3; l<=totalPoints; l++)
{
    for(int i=0; i<=l; i++)
    {
        for(int j=0; j<=l; j++)
        {
            for(int k=0; k<=l; k++)
            {
                int current_min=99999;
                //cost[i][j][k][l]=0;
                if((i!=l) && (j!=l) && (k!=l))
                    cost[i][j][k][l]=99999;
                else
                {

                    for(int m=0; m<=l; m++)
                    {
                        if(current_min > (cost[m][j][k][l-1] + dist(m, i)))
                        {
                            if(cost[m][j][k][l-1] + dist(m, i)>0)
                            current_min = cost[m][j][k][l-1] + dist(m, i);

                        }

                        else if(current_min > (cost[i][m][k][l-1] + dist(m,j)))
                        {
                            if(cost[i][m][k][l-1] + dist(m,j)>0)
                            current_min = cost[i][m][k][l-1] + dist(m,j);
                        }


                        else if(current_min > (cost[i][j][m][l-1] + dist(m,k)))
                        {
                            if(cost[i][j][m][l-1] + dist(m,k)>0)
                            current_min = cost[i][j][m][l-1] + dist(m,k);
                        }
                    }
                    cost[i][j][k][l] = current_min;
                }
            }
        }
    }
  }
  printCostTable(cost);
}
4

0 回答 0