有向图表的算法帮助

Question

我有一个作业给我的班级，在那里我们试图找到最好的(最便宜的)道路到目的地。说明如下：

每个技术都有一个名称，一个购买该技术的成本，一个表示播放器是否已经拥有该技术的布尔值，以及当玩家购买该技术时可供购买的0到N技术的列表。触觉技术有三类:社会技术、军事技术和科学技术。这三种技术中的每一种都是从玩家在购买更先进的技术之前必须购买的基本技术开始的。这些基本的技术是特别的，因为它们总是可以买到。查看图表，您将注意到有几个技术人员被多个技术人员解锁。记住，一旦技术人员打开锁，他们就会被解锁。换句话说，为了购买“攻击动物训练”，你需要“善待动物”或“对人们来说是个混蛋”。你不需要两者都需要，只有一个。你的任务是找到最便宜的方法来获得任何给定的技术。玩家可能已经拥有了任何一套技术，所以你必须说明这一点。例如，如果玩家已经拥有“对人好”，并且希望找到最便宜的方法来获得“交友”，那么返回的路径应该是“交友”。他们不需要再买任何东西了。

图如下：

​

​

我最初的想法是，在计算每条路径的成本的同时，对这三个类别中的每一个进行深度优先搜索。我对此功能的代码如下：

    //---------------------------------------------------------------------------------------------------------------------
// This function finds the best path to the tech we want.
//      * goalTech: The index of the tech we're looking for.  Call GetTechByIndex() to get the actual Tech instance.
//      * bestPath: The best path to the goal tech.  This is an array sorted in the order of the best path from the 
//                  start to the goal.  This is an output variable; it's what you need to populate with this function.
//---------------------------------------------------------------------------------------------------------------------
void TechTree::FindBestPath(int goalTech, Path& bestPath)
{
    //First ensure that best path is cleared out
    bestPath.clear();

    //Get Tech Instance for this Goal Tech
    const Tech* pGoalTech = GetTechByIndex(goalTech);

    //make sure we get a valid tech
    assert(pGoalTech != nullptr);

    //Check first if user already has this unlocked. 
    if (pGoalTech->HasTech())
    {
        //just return
        return;
    }

    //Check if the goal tech is one of the three starting techs.
    if (pGoalTech == GetBasicSocialTech()|| pGoalTech == GetBasicScienceTech() || pGoalTech == GetBasicMilitaryTech())
    {

        //now we know that one of the basic techs are the goal, so we just add one of those to the path
        if (pGoalTech == GetBasicSocialTech())
            bestPath.push_back(GetBasicSocialTech());
        else if (pGoalTech == GetBasicMilitaryTech())
            bestPath.push_back(GetBasicMilitaryTech());
        else
            bestPath.push_back(GetBasicScienceTech());


        return; //now return
    }


    //my process will be as follows. 
    //1. Since all the edges are directed we need to traverse down three different graphs: Social (starting at index 0), Military (starting at index 4) and Science (starting at index 8)
    //2. I am going to perform a depth-first search starting at Social and then moving down to Military and then Science.
    //3. As I am performing a depth-first I am going to keep track of a path and its respective cost, if a search gets to the goal I will make sure to register that and then move onto the next graph.
    //4. When there are no more paths to search I send the lowest cost one back. 

    ///start with social at index 0
    const Tech* pStartSocialTech = GetBasicSocialTech();
    std::pair<int, std::vector<const Tech*>> bestCurrentPath;


    //get starting cost for this category before we move into neighbors,
    // if player already has this tech we set this to zero if not we get the cost of buying into this category
    int startingCost = pStartSocialTech->HasTech() ? 0 : pStartSocialTech->GetCost();


    

    /*pStartSocialNeighbors = get all neighbors for starting point at social

    while (destination is not found AND there are more neighbors to pStartSocialNeighbors)
    {
        DFS(neighbor, dest) //if this finds the destination we store a path and its cost, otherwise it doesnt do anything and we move on to next basic tree
    }

    //do the same thing for military and science...
    */
}

我对此有很多评论，但我只是想知道这是否是最好的选择。其他选项是Dijkstras或A*，但我不知道您将如何遍历这个有向图的路径。我不是在找一个直接的答案，因为这是一个家庭作业，但我正在寻找一些指导。

谢谢!

Answer 1

使用Dijkstras从目标到源，如果要在搜索所有路径之前停止，则需要修改停止条件。在这种情况下，我看不出对A*有任何启发。

• 向所有已知的技术

添加具有路径的节点。

您现在可以使用Dijkstras /Bellman。

使用A*有问题，您需要找到一个有效的启发式。你可以使用深度时间最小成本的所有边缘。这要求您已经遍历了图表以指定深度。