algorithm - 查找路径的算法(计划类)

我正在想办法解决这个问题。它取自为12年级学生举办的一个节目比赛。
任务是让学生“karli”参加足够的课程，获得214个学分。学生进入考场前不能修满214学分门在图中有表示。用户可以重复一节课来上其他的课，但他们必须离开那个教室…去另一个教室…然后回来。
我尝试手动执行此操作，并找到一个路径为的解决方案：
数学代数哲学代数数学建模微积分建模考试
我正在尝试开发一个算法，该算法将在给定所需学分数的情况下找到一条路径（即214）。
以下是我尝试过并坚持的：
将地图表示为图形，门是两个节点之间的双边但是我不知道什么样的图遍历算法能让我解决这个问题？
把图转换成邻接矩阵会让事情变得更容易吗？
谢谢

最佳答案

Breadth First Search将解决此问题。
当Karli到达编号为(room, credit)的房间时，记录状态room，并在credit中记录信用值。
使用queue来维护数据开始时，队列中只有（外部，0）每次，弹出头部，从head所描述的状态移动到head的每个相邻房间，然后计算新状态并将其推到queue的末尾（记住使用散列以避免重复添加同一状态）。
当您达到(exam, 214)状态时，展开过程结束。剩下的工作是从(exam, 214)状态返回。在BFS中获取新状态时，还可以记录指向predier status的指针。
这是我的密码。

char name[][15] = {
        "exam",
        "stochastic",
        "modeling",
        "calculus",
        "math",
        "modern arts",
        "algebra",
        "philosophy",
        "outside"
};

int credits[]={0, 23, 29, 20, 17, 17, 35, 32, 0};

int neighbour[][7]={
        { 1, 2, -1},
        { 2, 3, -1},
        { 0, 1, 3, 4, 5, -1},
        { 1, 2, 4,-1},
        { 2, 3, 6, -1},
        { 2, 6, 7, -1},
        { 4, 5, 7, -1},
        { 5, 6, -1},
        { 4, -1}
};


class Node{
public:
        int pos;
        int credit;
        bool operator <( const Node a) const{
                return pos < a.pos || pos == a.pos && credit < a.credit;
        }
};

vector<Node> Q;
vector<int> pred;
set<Node> hash;
void bfs(){
        int n = 9;
        bool found = false;
        hash.clear();
    Node start;
        start.pos = 8, start.credit = 0;
        Q.push_back(start);
        pred.push_back(-1);
        hash.insert(start);
        for(int f=0; f<Q.size(); ++f){
                Node head = Q[f];
                int pos = head.pos;
                //printf("%d %d -> \n", head.pos, head.credit);
                for(int i=0; neighbour[pos][i]!=-1; ++i){
                        Node tmp;
                        tmp.pos = neighbour[pos][i];
                        tmp.credit = head.credit + credits[tmp.pos];
                        if(tmp.credit > 214) continue;
                        if(hash.count(tmp)) continue;
                        if(tmp.credit !=214 && tmp.pos==0)continue;   // if the credit is not 214, then it is not allowed to enter exame room(numbered as 0)
                        Q.push_back(tmp);
                        pred.push_back(f);
                        //printf("    -> %d, %d\n", tmp.pos, tmp.credit);
                        if(tmp.credit==214 && tmp.pos==0){
                                found = true;
                                break;
                        }
                }
                if(found)break;
        }
        stack<int> ss;
        int idx = Q.size()-1;
        while(true){
                ss.push(Q[idx].pos);
                if(pred[idx]!=-1) idx=pred[idx];
                else break;
        }
        for(int credit=0; ss.size() > 0; ){
                int pos = ss.top();
                credit += credits[pos];
                printf("%s(%d) ", name[pos], credit);
                ss.pop();
        }
        printf("\n");
}

UPD1:很抱歉，我在给neighbour[]赋值时犯了一些错误。我已经改正了。
UPD1：对不起，我进入考场时忘记检查学分是否为214。我已经改正了。
UPD3:@Nuclearman说它没有给出所有的解决方案我们只需要从代码中删除hash，并在用credit 214生成新状态时计算路径我把新密码给你。

char name[][15] = {
        "exam",
        "stochastic",
        "modeling",
        "calculus",
        "math",
        "modern arts",
        "algebra",
        "philosophy",
        "outside"
};

int credits[]={0, 23, 29, 20, 17, 17, 35, 32, 0};

int neighbour[][7]={
        { 1, 2, -1},
        { 2, 3, -1},
        { 0, 1, 3, 4, 5, -1},
        { 1, 2, 4,-1},
        { 2, 3, 6, -1},
        { 2, 6, 7, -1},
        { 4, 5, 7, -1},
        { 5, 6, -1},
        { 4, -1}
};


class Node{
public:
        int pos;
        int credit;
        bool operator <( const Node a) const{
                return pos < a.pos || pos == a.pos && credit < a.credit;
        }
};

vector<Node> Q;
vector<int> pred;
set<Node> hash;

void outputpath(){
        stack<int> ss;
        int idx = Q.size()-1;
        while(true){
                ss.push(Q[idx].pos);
                if(pred[idx]!=-1) idx=pred[idx];
                else break;
        }
        for(int credit=0; ss.size() > 0; ){
                int pos = ss.top();
                credit += credits[pos];
                printf("%s(%d) ", name[pos], credit);
                ss.pop();
        }
        printf("\n");
}

void bfs(){
        int n = 9;
        bool found = false;
        hash.clear();
        Node start;
        start.pos = 8, start.credit = 0;
        Q.push_back(start);
        pred.push_back(-1);
        hash.insert(start);
        for(int f=0; f<Q.size(); ++f){
                Node head = Q[f];
                int pos = head.pos;
                for(int i=0; neighbour[pos][i]!=-1; ++i){
                        Node tmp;
                        tmp.pos = neighbour[pos][i];
                        tmp.credit = head.credit + credits[tmp.pos];
                        if(tmp.credit > 214) continue;
                        if(hash.count(tmp)) continue;
                        if(tmp.credit !=214 && tmp.pos==0)continue;
                        Q.push_back(tmp);
                        pred.push_back(f);
                        if(tmp.credit==214 && tmp.pos==0){
                                outputpath();
                                /* uncomment the next line to get only one solution*/
                                //found = true;
                                break;
                        }
                }
                if(found)break;
        }
}

关于algorithm - 查找路径的算法(计划类)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16755269/