如何同时实现n个目标的搜索算法

Question

我需要使用搜索算法（星型，最佳优先）实现以下要求：

n辆车占据n×n网格的正方形（1,1）到（n,1）（即底行）。车辆必须移到第一排，但顺序相反；因此，在（i，1）中启动的车辆i必须在（n）中结束−i+1，n）。在每个时间步长上，n辆车中的每辆车都可以向上、向下、向左或向右移动一个正方形，或保持静止；但如果一辆车停在原地，另一辆相邻的车（但不超过一辆）可以跳过它。两辆车不能占用同一个广场

我确定了hi公式| n-1+I-xi | n-yi| 对于gi公式：

gi = g(i-1), for STAY
gi = g(i-1) + 1, for a simple move 
gi = g(i-1) + 2, for a simple hop

但是我不知道如何为这个问题实现一个合适的代码，我的尝试产生了无限的循环

你能帮我推荐一下哪种搜索算法最合适，以及我如何实现它吗

选择将要移动的下一辆车辆的代码

auto comparator = [](const Vehicle& a, const Vehicle& b) {
        return ((a.g() + a.h()) < (b.g() + b.h())) ||
            ((a.g() + a.h()) == (b.g() + b.h()) && a.getIndex() > b.getIndex() );
    }; 
    std::priority_queue<Vehicle, std::vector<Vehicle>, decltype(comparator)> vehicles(comparator);
    
    while (unparked_vehicles.size()) {
        while (unparked_vehicles.size()) {
            vehicles.push(unparked_vehicles[unparked_vehicles.size() - 1]);
            unparked_vehicles.pop_back();
        }

        while (!vehicles.empty()) {
            unparked_vehicles.push_back(vehicles.top());
            unparked_vehicles[unparked_vehicles.size() - 1].makeBestMove(this->grid);
            vehicles.pop();
        }
        
        this->display();
        for (int i = 0; i < unparked_vehicles.size(); i++) {
            if (unparked_vehicles[i].isParked()) {
                parked_vehicles.push_back(unparked_vehicles[i]);
                unparked_vehicles.erase(std::begin(unparked_vehicles) + i);
                i--;
            }
        }
    }

选择最佳移动的代码：

std::pair<int, int> new_coordonates = {state.first, state.second};
    int h = -1;
    
    auto leftMovements = [&]() {
        if (checkPoints(parking, state.first, state.second - 1)) {
            if (h == -1) {
                h = getPotentialH(state.first, state.second - 1);
                new_coordonates = std::make_pair(state.first, state.second - 1);
            }
            else if (h > getPotentialH(state.first, state.second - 1)) {
                h = getPotentialH(state.first, state.second - 1);
                new_coordonates = std::make_pair(state.first, state.second - 1);
            }
        }
        else if (checkPoints(parking, state.first, state.second - 2)) {
            if (h == -1) {
                h = getPotentialH(state.first, state.second - 2);
                new_coordonates = std::make_pair(state.first, state.second - 2);
            }
            else if (h > getPotentialH(state.first, state.second - 2)) {
                h = getPotentialH(state.first, state.second - 2);
                new_coordonates = std::make_pair(state.first, state.second - 2);
            }
        }
    };
    auto rightMovements = [&]() {
        if (checkPoints(parking, state.first, state.second + 1)) {
            if (h == -1) {
                h = getPotentialH(state.first, state.second + 1);
                new_coordonates = std::make_pair(state.first, state.second + 1);
            }
            else if (h > getPotentialH(state.first, state.second + 1)) {
                h = getPotentialH(state.first, state.second + 1);
                new_coordonates = std::make_pair(state.first, state.second + 1);
            }
        }
        else if (checkPoints(parking, state.first, state.second + 2)) {
            if (h == -1) {
                h = getPotentialH(state.first, state.second + 2);
                new_coordonates = std::make_pair(state.first, state.second + 2);
            }
            else if (h > getPotentialH(state.first, state.second + 2)) {
                h = getPotentialH(state.first, state.second + 2);
                new_coordonates = std::make_pair(state.first, state.second + 2);
            }
        }
    };
    auto upMovements = [&]() {
        if (checkPoints(parking, state.first - 1, state.second)) {
            if (h == -1) {
                h = getPotentialH(state.first - 1, state.second);
                new_coordonates = std::make_pair(state.first - 1, state.second);
            }
            else if (h > getPotentialH(state.first - 1, state.second)) {
                h = getPotentialH(state.first - 1, state.second);
                new_coordonates = std::make_pair(state.first - 1, state.second);
            }
        }
        else if (checkPoints(parking, state.first - 2, state.second)) {
            if (h == -1) {
                h = getPotentialH(state.first - 2, state.second);
                new_coordonates = std::make_pair(state.first - 2, state.second);
            }
            else if (h > getPotentialH(state.first - 2, state.second)) {
                h = getPotentialH(state.first - 2, state.second);
                new_coordonates = std::make_pair(state.first - 2, state.second);
            }
        }
    };
    auto downMovements = [&]() {
        if (checkPoints(parking, state.first + 1, state.second)) {
            if (h == -1) {
                h = getPotentialH(state.first + 1, state.second);
                new_coordonates = std::make_pair(state.first + 1, state.second);
            }
            else if (h > getPotentialH(state.first + 1, state.second)) {
                h = getPotentialH(state.first + 1, state.second);
                new_coordonates = std::make_pair(state.first + 1, state.second);
            }
        }
        else if (checkPoints(parking, state.first + 2, state.second)) {
            if (h == -1) {
                h = getPotentialH(state.first + 2, state.second);
                new_coordonates = std::make_pair(state.first + 2, state.second);
            }
            else if (h > getPotentialH(state.first + 2, state.second)) {
                h = getPotentialH(state.first + 2, state.second);
                new_coordonates = std::make_pair(state.first + 2, state.second);
            }
        }
    };
    
    upMovements();
    downMovements();
    leftMovements();
    rightMovements();
        
    if (h != -1) {
        move(parking, new_coordonates.first, new_coordonates.second);
    }