我试图弄清楚如何解决这个问题。它取自为 12 年级学生举办的编程竞赛。任务是让学生“Karli”参加足够的课程以获得 214 个学分。学生在进入考场前不得超过或少于 214 个学分。门在图中表示。用户可以重复一堂课，但他们必须离开那个教室..去另一个教室..然后回来。
我尝试手动执行此操作，并且能够找到一个带有路径的解决方案：
数学-代数-哲学-代数-数学-建模-微积分-建模-考试
我正在尝试开发一种算法，该算法将在给定所需信用数的情况下找到一条路径（即本例为 214）
这是我尝试过并陷入困境的：
将地图表示为一个图，门是两个节点之间的一条双边。但是我不知道什么图遍历算法可以让我解决这个问题？
将图形转换为邻接矩阵会使事情变得更容易吗？
谢谢
Breadth First Search将解决这个问题。
(room, credit)将Karli 到达房间编号的状态记录为room中记录的信用值credit。
使用 aqueue来维护数据。开始时，只有 (outside, 0) 在队列中。每次弹出头部，从 描述的状态移动head到 的每个相邻房间head，然后计算新的状态并将它们推到末尾queue（记住使用哈希，以避免重复添加相同的状态） .
当您达到 status(exam, 214)时，展开过程完成。剩下的工作就是从 status 往回遍历(exam, 214)。在 BFS 中获取新状态时，您还可以记录指向前驱状态的指针。
这是我的代码。
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要从代码中去掉，在生成新状态时计算路径，信用为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;
}
}
这是 Haskell 中的一个版本，从考场向后生成路径并丢弃学分总和大于要求的路径：
import Data.Maybe (fromJust)
import Control.Monad (guard)
classes = [("exam",["modeling"])
,("modeling",["exam","stochastic","calculus","math","modern arts"])
,("stochastic",["calculus","modeling"])
,("calculus",["stochastic","modeling","math"])
,("math",["calculus","modeling","algebra"])
,("algebra",["math","philosophy"])
,("philosophy",["algebra","modern arts"])
,("modern arts",["philosophy","modeling"])]
credits = [("exam",0)
,("modeling",29)
,("stochastic",23)
,("calculus",20)
,("math",17)
,("algebra",35)
,("philosophy",32)
,("modern arts",17)]
solve requirement = solve' ["exam"] 0 where
solve' path creditsSoFar =
if creditsSoFar == requirement && head path == "math"
then [path]
else do
next <- fromJust (lookup (head path) classes)
guard (next /= "exam"
&& creditsSoFar + fromJust (lookup next credits) <= requirement)
solve' (next:path) (creditsSoFar + fromJust (lookup next credits))
输出：
*Main> solve 214
[["math","algebra","philosophy","algebra","math","modeling","calculus","modeling","exam"]
,["math","calculus","math","calculus","math","calculus","math","calculus","math","calculus","modeling","exam"]
,["math","algebra","philosophy","modern arts","philosophy","algebra","math","modeling","exam"]]
(0.19 secs, 9106396 bytes)