如何在二维数组中找到 N 个最小值 (c++)

Question

您好，我目前正在编写一个程序来计算溶剂中氢键构型的稳定性。问题是目前我选择用两个分子 i 和 j 之间的距离制作二维数组。如何在给定 i 的数组中找到 N 个（给定的）最小值，而不会在排序时丢失索引。标准库中有这样的东西吗，我首先想到使用std::min但是没有成功。

编辑：其中 MAXBONDS 是上面提到的 N。 class 是

class item{ // ITEM the molecule itself
private:
            //part for molecule charazerization

    std::vector<double> coordinates;
    std::vector<int> bondings;
public:
double calculateSolvents(double dist[][], std::vector<item> items);
}



double item::calculateSolvents(double dist[][], std::vector<item> items){  
for(int i=0; i <= items.size()-1;i++){
  if(items[i].bondings.size()<MAXBONDS){
  for(int j=0;j<= items.size()-1 ;j++){
      if(items[j].bondings.size()< MAXBONDS && 
        (find(items[i].bondings.begin(),items[i].bondings.end(),j)==items[i].bondings.end()) &&
        (find(items[j].bondings.begin(),items[j].bondings.end(),i)==items[j].bondings.end())){


  }}
  }}

class 的实例存储在向量中

 std::vector<item> items

是的，我的意思是对于给定的 i，我想要所有可能的 j 的 N (MAXBONDS) 个最小值。

编辑2：这实际上是一个图形算法问题 dist[][] 表示分子 i 和 j 之间的距离。我需要（就像在 TSP 问题中一样）所有分子之间的整体最短路径（我需要知道哪个分子连接到哪个分子）。每个分子都应该与其他分子有 MAXBONDS 连接（它们实际上也位于最大距离内，但我已经在 dist 数组中考虑到了这一点）所以我贪婪的方法是对所有可能的 j 采取 N(MAXBONDS) 最短距离给定我形成数组 dist.

Answer 1

我给你一个算法，在给定距离矩阵的情况下找出 N 个最近的邻居。我不会进一步猜测你对分子化合物的建模，所以我使用了一种非常简化的方法。

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <limits>

struct Point3D {
    double x;
    double y;
    double z;
};

double squareDistance(const Point3D &a, const Point3D &b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    double dz = a.z - b.z;
    return dx*dx + dy*dy + dz*dz;
}

struct Molecule {
    // more meaningfull stuff omitted 
    // ...
    Point3D _pos;
};

我正在使用地图存储分子 j 的索引以及与分子 i 的距离。

#define MAX_NEIGHBOUR 4 

struct Neighbours {
    std::map<double,size_t> _n;
    double _limit;

    Neighbours() : _limit(std::numeric_limits<double>::infinity()) {}

    double add(double dd, size_t index) {
        if (dd <= _limit) {     // update neighbours only when necessary
            _n[dd] = index;
            if ( _n.size() > MAX_NEIGHBOUR ) {
                auto itn = _n.end();
                _n.erase(--itn);
                if ( dd < _limit ) _limit = dd;
            }
        }
    }

    friend std::ostream & operator<<( std::ostream & out, const Neighbours & nn) {
        for ( auto i : nn._n) {
            out << i.second << " at " << std::sqrt(i.first) << ", ";
        }
        return out << std::endl;
    }
};

我假设距离矩阵是对称的（除非你使用相同的奇怪拓扑）并且我将它存储在一个向量中。

struct DistMol {
    DistMol(const std::vector<Molecule> & mols) :   _rows(mols.size()),
                                                    _d(_rows*(_rows-1)/2+1),
                                                    _near(_rows),
                                                    _mol(mols){}

    void evaluate() {       // The "matrix" of distances is simmetric
        auto id = _d.begin();
        for (size_t i=0; i<_rows; i++) {
            for (size_t j=i+1; j<_rows; j++) {
                *id = squareDistance(_mol[i]._pos,_mol[j]._pos);
                _near[i].add(*id,j);
                _near[j].add(*id,i);
                ++id;
            }
        }
    }

    double distance(size_t i, size_t j) { // remember that I have only half the matrix
        long int dij = i - j;

        if ( dij > 0 && i < _rows ) 
            return std::sqrt(_d[j*_rows - j*(j+1)/2 + dij - 1]);
        else if ( dij < 0 && j < _rows)
            return std::sqrt(_d[i*_rows - i*(i+1)/2 - dij - 1]);
        else return 0.0;
    }
    void showDistances() {
        std::cout << std::fixed;
        for ( size_t i=0; i<_rows; i++) {
            for (size_t j=0; j<_rows; j++) {
                std::cout << distance(i,j) << ' ';
            }
            std::cout << std::endl;
        }
    }
    void showNearest() {
        size_t i = 0;
        for ( auto n : _near) {
            std::cout << i++ << ": " << n;
        }
    }

    size_t _rows;
    std::vector<double> _d;
    std::vector<Neighbours> _near;
    const std::vector<Molecule> & _mol;
};

这是一个使用示例及其输出：

int main() {
    std::vector<Molecule> mo   {{1.0,0.0,0.5}, {2.0,0.5,1.2}, {4.8,2.3,1.9},
                                {3.7,3.9,8.7}, {2.1,0.5,1.3}, {5.8,2.5,4.4},
                                {5.7,4.1,2.3}, {1.7,0.8,6.2}, {0.8,0.3,1.0}};
    DistMol dm {mo};

    dm.evaluate();
    dm.showDistances();
    dm.showNearest();

    return 0;
}

输出：

0.000000 1.319091 4.657252 9.473120 1.449138 6.670832 6.491533 5.798276 0.616441 
1.319091 0.000000 3.401470 8.408329 0.141421 5.355371 5.278257 5.017968 1.232883 
4.657252 3.401470 0.000000 7.071775 3.300000 2.700000 2.051828 5.509083 4.561798 
9.473120 8.408329 7.071775 0.000000 8.299398 4.985980 6.708204 4.456456 8.981091 
1.449138 0.141421 3.300000 8.299398 0.000000 5.224940 5.188449 4.925444 1.349074 
6.670832 5.355371 2.700000 4.985980 5.224940 0.000000 2.641969 4.789572 6.434283 
6.491533 5.278257 2.051828 6.708204 5.188449 2.641969 0.000000 6.488451 6.335614 
5.798276 5.017968 5.509083 4.456456 4.925444 4.789572 6.488451 0.000000 5.300943 
0.616441 1.232883 4.561798 8.981091 1.349074 6.434283 6.335614 5.300943 0.000000 
0: 8 at 0.616441, 1 at 1.319091, 4 at 1.449138, 2 at 4.657252, 
1: 4 at 0.141421, 8 at 1.232883, 0 at 1.319091, 2 at 3.401470, 
2: 6 at 2.051828, 5 at 2.700000, 4 at 3.300000, 1 at 3.401470, 
3: 7 at 4.456456, 5 at 4.985980, 2 at 7.071775, 4 at 8.299398, 
4: 1 at 0.141421, 8 at 1.349074, 0 at 1.449138, 2 at 3.300000, 
5: 6 at 2.641969, 2 at 2.700000, 3 at 4.985980, 4 at 5.224940, 
6: 2 at 2.051828, 5 at 2.641969, 4 at 5.188449, 1 at 5.278257, 
7: 3 at 4.456456, 5 at 4.789572, 4 at 4.925444, 1 at 5.017968, 
8: 0 at 0.616441, 1 at 1.232883, 4 at 1.349074, 2 at 4.561798,

如何在二维数组中找到 N 个最小值 (c++)

How to find the N smallest values in a 2 dimensional array (c++)

c++

arrays

algorithm

graph-algorithm