OMP-还原为基于另一个值的值

Question

我正在尝试并行化一种简单算法，以找到旅行商问题的正当解决方案。

让path是对应于城市的整数数组。在每次尝试中，选择要切换到path数组的两个随机索引。此开关影响到前一个节点和后一个节点的距离，总共影响4个距离。如果将它们加起来，我们就可以推断出我们执行的转换比旧转换产生的路径更好还是更差。在前一种情况下，保留了开关，我们可以进行下一次尝试。

并行化此算法的想法是同时尝试N个不同的交换机，并执行生成最短路径的交换机。到目前为止，我的代码如下：

float switchCities(){

    int switchCandidates[NUM_THREADS][2];
    float minDist;

    #pragma omp parallel for reduction(*need help here*)
    for(int i=0; i<NUM_THREADS; i++){

        //selecting 2 random candidates excluding the first and last
        switchCandidates[i][0] = rand() % (N-1) + 1;
        switchCandidates[i][1] = rand() % (N-1) + 1;

        float oldDist = localDist(switchCandidates[i][0], switchCandidates[i][1]);
        float newDist = localSwitchedDist(switchCandidates[i][0], switchCandidates[i][1]);

        if(newDist >= oldDist){
            newDist = FLT_MAX;
        }

    }

    //perform the switch
    ....

    return minDist;
}

通过将无效的开关距离设置为一个较大的数字，我可以减小到最小距离，但是，我对路径本身比对距离更感兴趣。是否可以执行减少操作，以便最终得到导致最小距离的索引i？

Answer 1

使用共享向量来保存信息，然后让单个线程使用该向量来找出最佳选择是：

float switchCities(){

    int switchCandidates[NUM_THREADS][2];
    float minDist;

    std::vector<std::pair<float,int> > best(omp_get_max_threads(), std::make_pair<float,int>(9e999999, -1));

    #pragma omp parallel for
    for(int i=0; i<NUM_THREADS; i++){
        //selecting 2 random candidates excluding the first and last
        switchCandidates[i][0] = rand() % (N-1) + 1;
        switchCandidates[i][1] = rand() % (N-1) + 1;

        float oldDist = localDist(switchCandidates[i][0], switchCandidates[i][1]);
        float newDist = localSwitchedDist(switchCandidates[i][0], switchCandidates[i][1]);

        auto &my_best = best.at(omp_get_thread_num());
        if(newDist >= my_best.first){
            my_best.first = newDist;
            my_best.second = i;
        }
    }

    //have one thread look at the `best` vector and find the best value here

    return minDist;
}