基于分支定界算法的C++初始-终位最优匹配优化求助

我正在开发一款游戏原型，需要将N个起始位置与N个终位关联，以最小化总距离之和。当前是2D项目，但问题同样适用于3D（或更高维度）。我用大学学过的分支定界算法能得到正确结果，但C++实现无法满足实时需求：当N=10时，算法执行耗时约8-10秒。测试发现do while循环是性能瓶颈，希望优化这段代码。

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
#include <tuple>
#include <cmath>

const float Epsilon = 0.0005f;

class HashMap {
private:
    size_t* map;
    size_t size;

public:
    explicit HashMap(size_t size) {
        this->size = size;
        map = new size_t[size];
        for (auto i = 0; i < size; ++i) {
            map[i] = -1;
        }
    }

    ~HashMap() {
        delete map;
    }

    void clear() {
        for (auto i = 0; i < size; ++i) {
            map[i] = -1;
        }
    }

    void insert(size_t key, size_t value) {
        map[key] = value;
    }

    size_t get(size_t key) {
        return map[key];
    }

    void remove(size_t key) {
        map[key] = -1;
    }
};

struct Vector2 {
    float x, y; // Assuming a 2D vector
};

float distance(const Vector2& v1, const Vector2& v2) {
    float dx = v1.x - v2.x;
    float dy = v1.y - v2.y;
    return std::sqrt(dx * dx + dy * dy);
}

float getBestLineSolution(HashMap& usedValues, size_t size, const float* distances, size_t line) {
    auto best = std::numeric_limits<float>::max();
    for (auto i = 0; i < size; i++) {
        if (usedValues.get(i) == -1 && distances[line * size + i] < best) {
            best = distances[line * size + i];
        }
    }
    return best;
}

float getRemainingScore(HashMap& usedValues, size_t size, const float* distances, size_t line) {
    auto remainingScore = 0.0f;
    for (auto i = line; i < size; i++) {
        remainingScore += getBestLineSolution(usedValues, size, distances, i);
    }
    return remainingScore;
}

float getTotalHeuristic(std::tuple<float, float, std::vector<size_t>> a) {
    // 0 is the true weight up until now and 1 is the heuristics
    return std::get<0>(a) + std::get<1>(a);
}

struct CustomCompare {
    bool operator()(std::tuple<float, float, std::vector<size_t>> a, std::tuple<float, float, std::vector<size_t>> b) {
        // Sort by cost
        return getTotalHeuristic(std::move(a)) > getTotalHeuristic(std::move(b));
    }
};

std::vector<size_t> branchAndBoundIterative(const std::vector<Vector2>& currentPosition, std::vector<Vector2>& finalPositions) {
    auto size = currentPosition.size();
    auto usedPosition = HashMap(size);
    float distances[size * size];
    auto minHeap = std::priority_queue<std::tuple<float, float, std::vector<size_t>>,
                                        std::vector<std::tuple<float, float, std::vector<size_t>>>, CustomCompare>();

    // Initialize the matrix with the distances
    for (auto i = 0; i < size; i++) {
        for (auto j = 0; j < size; j++) {
            distances[i * size + j] = distance(currentPosition[i], finalPositions[j]);
        }
    }

    // Getting the threshold
    auto threshold = 0.0f;
    for (auto i = 0; i < size; i++) {
        threshold += distances[i * size + i];
    }

    // Getting all first node whose cost is under the threshold
    for (size_t i = 0; i < size; i++) {
        auto dist = distances[i];
        auto heuristic = getRemainingScore(usedPosition, size, distances, 1);

        if (dist + heuristic <= (threshold + Epsilon)) {
            auto v = std::vector<size_t>();
            v.push_back(i);
            minHeap.emplace(dist, heuristic, v);
        }
    }

    // Doing the algorithm
    // This is part is really slow
    auto bestTuple = minHeap.top();
    do {
        // Lower cost path (called current path in the rest of the algorithm)
        auto currentTuple = minHeap.top();
        minHeap.pop();
        usedPosition.clear();
        auto positions = std::get<2>(currentTuple);
        auto posSize = positions.size();

        if (posSize == size) {
            // If the current path (in the matrix) contains all elements
            auto totalDistance = std::get<0>(currentTuple);
            if (totalDistance <= (threshold + Epsilon)) {
                threshold = totalDistance;
                bestTuple = currentTuple;
            }
        } else {
            // If the current path (in the matrix) doesn't contain all elements
            for (auto i = 0; i < posSize; i++) {
                usedPosition.insert(positions[i], i);
            }

            auto currentDist = std::get<0>(currentTuple);

            // Getting the next best result for the next line in the current path
            for (auto i = 0; i < size; i++) {
                if (usedPosition.get(i) == -1) {
                    auto newDist = currentDist + distances[posSize * size + i];
                    auto heuristic = getRemainingScore(usedPosition, size, distances, posSize + 1);
                    if (newDist + heuristic <= (threshold + Epsilon)) {
                        auto positionCopy = std::vector<size_t>(positions);
                        positionCopy.push_back(i);
                        minHeap.emplace(newDist, heuristic, positionCopy);
                    }
                }
            }
        }
    } while (!minHeap.empty() && getTotalHeuristic(minHeap.top()) <= (threshold + Epsilon));

    return std::get<2>(bestTuple);
}

int main() {
    std::vector<Vector2> currentPosition = { {0, 0},
                                             {1, 0},
                                             {2, 0},
                                             {3, 0},
                                             {4, 0},
                                             {5, 0},
                                             {6, 0},
                                             {7, 0},
                                             {8, 0},
                                             {9, 0}
    };

    std::vector<Vector2> finalPosition = { {-4, 5},
                                           {-3, 5},
                                           {-2, 5},
                                           {-1, 5},
                                           {0, 5},
                                           {1, 5},
                                           {2, 5},
                                           {3, 5},
                                           {4, 5},
                                           {5, 5}
    };
    std::vector<size_t> bestFinalPosition = branchAndBoundIterative(currentPosition, finalPosition);

    // Output the result
    std::cout << "Optimal final positions:" << std::endl;
    for (auto i = 0; i < currentPosition.size(); i++) {
        auto pos = finalPosition[bestFinalPosition[i]];
        std::cout << "(" << pos.x << ", " << pos.y << ") ";
    }

    return 0;
}

1. 替换自定义HashMap为位集或布尔数组 #

自定义HashMap的实现冗余，完全可以用std::vector<bool>或std::bitset替代，这类结构访问和修改速度更快，内存占用极小：

// 替换HashMap为std::vector<bool>
std::vector<bool> usedPosition(size, false);
// 检查是否使用：if (!usedPosition[i])
// 标记使用：usedPosition[i] = true;
// 清空：std::fill(usedPosition.begin(), usedPosition.end(), false);

避免了不必要的内存操作和类型转换，大幅提升get和insert的效率。

2. 预计算启发式数据，减少重复计算 #

当前每次调用getRemainingScore都会遍历剩余行查找最小未使用距离，属于重复计算重灾区。可以：

• 预计算每行的最小距离数组row_mins，初始时row_mins[i]是第i行的最小距离。
• 用行最小和列最小的和作为下界，这个启发式更紧，能更早剪枝：

std::vector<float> row_mins(size, std::numeric_limits<float>::max());
std::vector<float> col_mins(size, std::numeric_limits<float>::max());
for (int i = 0; i < size; ++i) {
    for (int j = 0; j < size; ++j) {
        row_mins[i] = std::min(row_mins[i], distances[i*size + j]);
        col_mins[j] = std::min(col_mins[j], distances[i*size + j]);
    }
}
float initial_lower_bound = std::accumulate(row_mins.begin(), row_mins.end(), 0.0f);

计算剩余启发式时，基于已使用的行和列快速得到剩余行的最小可用距离之和，无需每次遍历所有列。

3. 减少优先级队列的数据拷贝 #

当前每次插入队列都会拷贝整个std::vector<size_t>，开销极大。可以用位掩码替代vector存储已选列：

// 把tuple中的vector替换为uint16_t（N<=16时足够）
using Node = std::tuple<float, float, uint16_t, int>; // 当前距离，启发式，位掩码，已选数量
// 检查第j列是否被使用：(mask & (1 << j)) == 0
// 标记第j列使用：mask | (1 << j)

每个节点内存占用从O(N)降到O(1)，拷贝速度大幅提升。

4. 优化初始阈值 #

当前初始阈值用对角线距离之和，远大于实际最优值，导致队列堆积大量无用节点。用贪心算法快速生成接近最优的初始阈值：

float greedy_threshold = 0.0f;
std::vector<bool> used(size, false);
for (int i = 0; i < size; ++i) {
    float min_dist = std::numeric_limits<float>::max();
    int best_j = -1;
    for (int j = 0; j < size; ++j) {
        if (!used[j] && distances[i*size + j] < min_dist) {
            min_dist = distances[i*size + j];
            best_j = j;
        }
    }
    greedy_threshold += min_dist;
    used[best_j] = true;
}
threshold = greedy_threshold;

初始阈值更接近最优值，能大幅减少队列中的节点数量。

5. 去掉不必要的浮点运算 #

最小化总距离和与最小化总距离平方和的结果一致（平方根是单调递增函数），可以去掉std::sqrt，用平方距离计算：

float distance_sq(const Vector2& v1, const Vector2& v2) {
    float dx = v1.x - v2.x;
    float dy = v1.y - v2.y;
    return dx*dx + dy*dy;
}

所有距离计算用平方值，仅在最终输出时按需计算平方根。

6. 调整优先级队列比较逻辑 #

当前CustomCompare中的std::move是多余的，直接传引用即可：

struct CustomCompare {
    bool operator()(const Node& a, const Node& b) {
        return (std::get<0>(a) + std::get<1>(a)) > (std::get<0>(b) + std::get<1>(b));
    }
};

避免不必要的移动操作。

7. 内存安全优化 #

栈数组float distances[size * size];在N较大时可能溢出，换成std::vector<float>更安全，性能几乎无差别：

std::vector<float> distances(size * size);

替代方案：匈牙利算法 #

如果N超过20，分支定界可能仍不够快，此时可以用匈牙利算法，它专门解决这类分配问题，时间复杂度为O(N³)，效率远高于分支定界。

Optimal final positions:
(-4, 5) (-3, 5) (-2, 5) (-1, 5) (0, 5) (1, 5) (2, 5) (3, 5) (4, 5) (5, 5)

内容的提问来源于stack exchange，提问作者Jersey591