1. 项目概述从经典谜题到桌面应用“农夫过河”这个题目但凡学过数据结构或者算法导论的朋友应该都不陌生。它本质上是一个经典的“状态空间搜索”问题通常被用来讲解图的广度优先搜索BFS或者深度优先搜索DFS算法。我第一次接触它还是在大学的数据结构课本上当时用控制台打印一堆字符来表示状态变化虽然逻辑通了但总觉得少了点“产品”的感觉像个半成品。这次课程设计的要求是把这道经典题目从一个简单的算法演示升级为一个完整的、带图形界面的桌面应用程序。核心就是用C实现算法逻辑再用微软的MFCMicrosoft Foundation Classes框架给它套上一个Windows风格的“外壳”。这就不再是单纯的编程作业了它更像是一个微型软件项目的雏形要求你同时考虑后台算法的正确性与效率以及前台用户交互的友好与直观。对于计算机相关专业的学生来说这是一个绝佳的练手机会能让你把数据结构、算法设计、面向对象编程和基本的UI开发知识串起来体验一次小型软件的生命周期。为什么选择C和MFC这个组合C自不必说它是理解内存管理、数据结构和算法效率的“不二法门”很多底层逻辑用C实现起来非常直接。而MFC虽然如今看来有些“复古”不再是市场主流但在教学和特定遗留系统维护中它依然有其一席之地。学习MFC能让你深刻理解Windows消息驱动机制、文档/视图架构这些GUI编程的核心思想其设计模式对理解其他框架如Qt的Signal/Slot也大有裨益。通过这个项目你收获的将不仅仅是一个“过河程序”更是一套解决同类状态搜索问题的通用方法以及一次完整的桌面应用开发实战经验。2. 核心问题解析与算法设计思路在动手敲代码之前我们必须把“农夫过河”这个问题本身以及解决它的核心算法思路彻底吃透。这是整个项目的基石如果这里想错了后面的界面做得再花哨也是徒劳。2.1 “农夫过河”问题的状态建模我们先明确一下游戏规则农夫需要把一只狼、一只羊和一筐白菜从河的左岸安全运到右岸。他的小船一次只能载他自己和另外一样东西狼、羊或白菜。如果农夫不在场狼会吃羊羊会吃白菜。我们的目标就是找到一系列安全的渡河步骤。解决这类问题的第一步也是最重要的一步就是状态抽象。我们不能在程序里真的去模拟一条河、一条船而是要把所有可能的安全局面抽象成计算机能处理的数据。一个典型的状态可以用一个四元组来表示(Farmer, Wolf, Sheep, Cabbage)每个元素取值为L左岸或R右岸。例如初始状态是(L, L, L, L)目标状态是(R, R, R, R)。但是并非所有2^416种组合都是合法的。我们需要根据规则定义非法状态即被吃掉的状态农夫不在左岸且狼和羊同在左岸(R, L, L, *)农夫不在左岸且羊和白菜同在左岸(R, *, L, L)农夫不在右岸且狼和羊同在右岸(L, R, R, *)农夫不在右岸且羊和白菜同在右岸(L, *, R, R)*表示任意即狼或白菜的位置不影响该非法条件的成立。我们的算法就是要从初始状态出发避开所有这些非法状态找到一条通往目标状态的路径。2.2 搜索算法选型BFS vs DFS这本质上是一个在图状态空间中寻找路径的问题。每个合法状态是一个节点一次安全的渡河操作就是连接两个节点的边。最常用的两种搜索策略是广度优先搜索BFS和深度优先搜索DFS。广度优先搜索BFS像水波扩散一样从起点开始先探索所有一步能到达的状态再探索所有两步能到达的状态以此类推。BFS保证找到的路径一定是步数最少的。对于本题状态空间很小BFS是首选因为它能直接给出最优解最少渡河次数。实现上我们需要一个队列Queue来存放待探索的状态。深度优先搜索DFS沿着一条路径一直深入直到无法继续或找到目标然后回溯尝试其他分支。DFS不保证找到的路径最短而且如果不对搜索深度加以限制在状态图有环的情况下可能会陷入无限循环。对于本题虽然也可以用但需要记录已访问状态以防止重复探索其代码逻辑比BFS稍复杂且结果不一定最优。在这个课程设计中强烈建议使用BFS算法。理由很充分问题规模小BFS实现简单且能天然求得最优解这能让你的项目报告更有亮点。在向用户展示时你可以明确说明“本程序找到的是步数最少的解决方案”。2.3 路径的记录与回溯BFS帮我们找到了目标状态但我们还需要把“怎么走过来的”这条路径还原出来。这就需要我们在搜索过程中不仅记录每个状态还要记录该状态是从哪个前驱状态通过何种操作转换而来的。一个经典的实现方法是使用一个map或unordered_map哈希表。键Key是当前状态可以用一个整数编码表示如二进制位值Value是一个结构体包含两个信息parentState: 前一个状态。action: 从父状态到当前状态所执行的操作例如“农夫独自过河”、“农夫带羊过河”。当我们从队列中取出一个状态并扩展出它的所有合法后继状态时如果某个后继状态未被访问过我们就将其加入队列并在这个map中记录它的父状态和对应的操作。一旦搜索到目标状态我们就可以从这个map出发沿着parentState一路回溯到起始状态同时将action反向收集起来就得到了一条从起点到终点的操作序列。注意状态编码要注意唯一性。一个简单的方法是用4个比特位分别表示农夫、狼、羊、白菜的位置0为左岸1为右岸。这样一个状态可以用一个0-15之间的整数唯一表示非常便于作为容器的键值。3. 核心数据结构与C算法实现详解理论清晰之后我们进入具体的代码实现环节。这一部分我们将用C构建整个问题的求解引擎。我建议将核心算法部分封装成一个独立的类比如叫做RiverCrossingSolver这样逻辑清晰也便于与后续的MFC界面进行对接。3.1 状态与操作的表示首先我们需要定义如何表示状态和操作。// 定义位置左岸或右岸 enum class Position { LEFT, RIGHT }; // 状态结构体表示某一时刻所有角色在岸上的位置 struct State { Position farmer; Position wolf; Position sheep; Position cabbage; // 为了方便比较和作为map的key我们需要重载运算符 bool operator(const State other) const { return farmer other.farmer wolf other.wolf sheep other.sheep cabbage other.cabbage; } // 也可以将其编码为一个整数 int encode() const { int code 0; if (farmer Position::RIGHT) code | 1 3; if (wolf Position::RIGHT) code | 1 2; if (sheep Position::RIGHT) code | 1 1; if (cabbage Position::RIGHT) code | 1 0; return code; } }; // 操作动作枚举表示农夫可以执行的动作 enum class Action { FARMER_ALONE, // 农夫独自过河 FARMER_WITH_WOLF, // 农夫带狼过河 FARMER_WITH_SHEEP, // 农夫带羊过河 FARMER_WITH_CABBAGE // 农夫带白菜过河 };3.2 非法状态判断与状态转移这是算法的核心函数。给定一个状态和一个动作我们需要判断执行这个动作后得到的新状态是否合法。class RiverCrossingSolver { private: // 判断一个状态是否安全不被吃 bool isStateValid(const State s) { // 农夫在左岸时检查右岸是否安全实际上检查对岸更直观 // 更通用的判断如果农夫和羊不在同一边那么狼和羊不能单独在一起羊和白菜也不能单独在一起。 if (s.sheep s.wolf s.farmer ! s.sheep) { return false; // 狼吃羊 } if (s.sheep s.cabbage s.farmer ! s.sheep) { return false; // 羊吃白菜 } return true; } // 尝试应用一个动作返回新状态。如果动作非法如农夫想带一个不在他身边的东西返回false。 bool applyAction(const State current, Action action, State next) { next current; // 农夫总是移动 next.farmer (current.farmer Position::LEFT) ? Position::RIGHT : Position::LEFT; switch (action) { case Action::FARMER_ALONE: // 只移动农夫其他不变 break; case Action::FARMER_WITH_WOLF: if (current.wolf ! current.farmer) return false; // 狼不和农夫在同一边不能带 next.wolf next.farmer; // 狼跟随农夫移动 break; case Action::FARMER_WITH_SHEEP: if (current.sheep ! current.farmer) return false; next.sheep next.farmer; break; case Action::FARMER_WITH_CABBAGE: if (current.cabbage ! current.farmer) return false; next.cabbage next.farmer; break; default: return false; } // 移动后检查新状态是否安全 return isStateValid(next); } };3.3 BFS搜索与路径回溯的实现现在我们实现BFS的主函数。我们将使用queue进行广度优先搜索使用unordered_mapint, pairint, Action来记录路径键是编码后的状态值是一个对包含父状态的编码和导致此状态的动作。std::vectorstd::pairState, Action RiverCrossingSolver::solveBFS() { State startState {Position::LEFT, Position::LEFT, Position::LEFT, Position::LEFT}; State goalState {Position::RIGHT, Position::RIGHT, Position::RIGHT, Position::RIGHT}; std::queueState q; std::unordered_mapint, std::pairint, Action cameFrom; // 路径记录器 std::unordered_setint visited; // 已访问集合防止重复访问 int startCode startState.encode(); int goalCode goalState.encode(); q.push(startState); visited.insert(startCode); cameFrom[startCode] {-1, Action::FARMER_ALONE}; // 起始状态没有父状态 while (!q.empty()) { State current q.front(); q.pop(); int currentCode current.encode(); if (currentCode goalCode) { // 找到目标回溯路径 return reconstructPath(cameFrom, startCode, goalCode); } // 尝试所有可能的动作 std::vectorAction allActions {Action::FARMER_ALONE, Action::FARMER_WITH_WOLF, Action::FARMER_WITH_SHEEP, Action::FARMER_WITH_CABBAGE}; for (Action act : allActions) { State nextState; if (applyAction(current, act, nextState)) { int nextCode nextState.encode(); if (visited.find(nextCode) visited.end()) { visited.insert(nextCode); q.push(nextState); cameFrom[nextCode] {currentCode, act}; // 记录父状态和动作 } } } } // 如果队列为空还没找到返回空路径理论上本题必有解 return std::vectorstd::pairState, Action(); } // 回溯函数根据cameFrom映射重建步骤序列 std::vectorstd::pairState, Action RiverCrossingSolver::reconstructPath( const std::unordered_mapint, std::pairint, Action cameFrom, int startCode, int goalCode) { std::vectorstd::pairState, Action path; int currentCode goalCode; // 从目标倒推到起点 while (currentCode ! startCode) { auto it cameFrom.find(currentCode); if (it cameFrom.end()) break; // 理论上不会发生 int parentCode it-second.first; Action action it-second.second; // 我们需要解码状态这里简化为一个解码函数根据编码还原State State currentState decodeState(currentCode); // decodeState函数需要实现 // 将状态导致该状态的动作加入路径。注意顺序是反的。 path.push_back({currentState, action}); currentCode parentCode; } // 加入起始状态其动作无意义 path.push_back({decodeState(startCode), Action::FARMER_ALONE}); std::reverse(path.begin(), path.end()); // 反转得到从起点到终点的顺序 return path; }实操心得在实现BFS时visited集合至关重要它可以防止程序陷入状态循环例如农夫带着羊过去又独自回来无限重复。使用unordered_set基于状态编码进行查找效率很高。另外cameFrom这个映射是回溯路径的关键务必在将新状态加入队列时同步更新它。4. MFC图形界面设计与实现算法引擎准备好了现在我们要给它做一个Windows桌面应用的“外壳”。MFC是一个基于文档/视图架构的框架但对于我们这种小型工具使用基于对话框的应用程序Dialog-based更加简单快捷。4.1 创建MFC对话框项目与界面布局打开Visual Studio新建一个“MFC应用”项目在应用程序类型中选择“基于对话框”取消“使用Unicode库”如果你的项目不需要国际化可以简化字符串处理。项目创建好后你会看到一个资源视图里面有一个主对话框模板。我们的界面需要包含以下几个核心区域状态显示区用图片或文字形象地展示左岸和右岸分别有哪些角色。可以使用Picture Control控件放置静态图片或者用List Box、Static Text动态更新文字。操作记录区用一个List Box或Edit Control设置为只读、多行来显示已执行的步骤或完整的解决方案步骤。控制按钮如“开始求解”Button、“下一步”Button、“上一步”Button、“重置”Button。信息提示区用Static Text显示当前状态、步数等信息。布局时可以利用MFC的对话框编辑器拖拽控件并调整位置。为了美观和清晰可以使用Group Box控件将状态显示区和控制区分开。4.2 连接界面与算法数据绑定与消息响应这是MFC开发的核心——消息映射机制。我们需要将按钮的点击事件BN_CLICKED与我们的处理函数关联起来。首先在对话框类的头文件如CMyDlg.h中声明我们的算法求解器对象以及用于存储解决方案的变量。// CMyDlg.h class CMyDlg : public CDialogEx { // ... private: RiverCrossingSolver m_solver; std::vectorstd::pairState, Action m_solutionPath; size_t m_currentStepIndex; // 当前演示到第几步 // 控件变量 CListBox m_wndStepList; // 步骤列表控件变量 CStatic m_wndLeftBankPic; // 左岸图片控件 CStatic m_wndRightBankPic; // 右岸图片控件 // ... };然后在对话框的OnInitDialog()函数中进行初始化比如设置列表的样式初始化状态显示等。最关键的是为按钮添加事件处理程序。在资源编辑器中右键点击“开始求解”按钮选择“添加事件处理程序”向导会自动在头文件和源文件中生成代码框架。// CMyDlg.cpp BEGIN_MESSAGE_MAP(CMyDlg, CDialogEx) ON_BN_CLICKED(IDC_BUTTON_SOLVE, CMyDlg::OnBnClickedButtonSolve) ON_BN_CLICKED(IDC_BUTTON_NEXT, CMyDlg::OnBnClickedButtonNext) ON_BN_CLICKED(IDC_BUTTON_PREV, CMyDlg::OnBnClickedButtonPrev) ON_BN_CLICKED(IDC_BUTTON_RESET, CMyDlg::OnBnClickedButtonReset) END_MESSAGE_MAP() void CMyDlg::OnBnClickedButtonSolve() { // 调用求解器 m_solutionPath m_solver.solveBFS(); m_currentStepIndex 0; // 清空步骤列表 m_wndStepList.ResetContent(); // 将解决方案的每一步描述性文字加入列表 CString strStep; for (size_t i 0; i m_solutionPath.size(); i) { const auto step m_solutionPath[i]; strStep.Format(_T(步骤%2d: %s), i1, actionToString(step.second).c_str()); m_wndStepList.AddString(strStep); } // 更新界面显示当前状态初始状态 updateUIWithState(m_solutionPath.empty() ? State{} : m_solutionPath[0].first); } void CMyDlg::OnBnClickedButtonNext() { if (m_currentStepIndex 1 m_solutionPath.size()) { m_currentStepIndex; updateUIWithState(m_solutionPath[m_currentStepIndex].first); // 高亮显示当前步骤在列表中 m_wndStepList.SetCurSel(m_currentStepIndex); } else { AfxMessageBox(_T(已经是最后一步了)); } } void CMyDlg::OnBnClickedButtonPrev() { if (m_currentStepIndex 0) { m_currentStepIndex--; updateUIWithState(m_solutionPath[m_currentStepIndex].first); m_wndStepList.SetCurSel(m_currentStepIndex); } else { AfxMessageBox(_T(已经是第一步了)); } }updateUIWithState函数负责根据传入的State对象更新界面上的图片或文字直观地展示谁在左岸、谁在右岸。actionToString函数将Action枚举转换为易于理解的文字描述如“农夫带羊过河”。4.3 状态可视化与交互反馈为了让界面更生动我们可以用图片来表示各个角色。准备四张小图片农夫、狼、羊、白菜根据State中的位置将它们分别加载并显示在对话框左岸或右岸的Picture Control中。可以使用MFC的CImage类或更老的CBitmap来加载和显示位图。在updateUIWithState函数中void CMyDlg::updateUIWithState(const State state) { // 假设我们有成员变量 CStatic m_picFarmerLeft, m_picFarmerRight 等... // 根据state.farmer的值显示/隐藏左岸或右岸的农夫图片 m_picFarmerLeft.ShowWindow(state.farmer Position::LEFT ? SW_SHOW : SW_HIDE); m_picFarmerRight.ShowWindow(state.farmer Position::RIGHT ? SW_SHOW : SW_HIDE); // 同理更新狼、羊、白菜的图片显示... // 更新状态文字提示 CString strStatus; strStatus.Format(_T(当前步数: %d/%d), m_currentStepIndex1, m_solutionPath.size()); SetDlgItemText(IDC_STATIC_STATUS, strStatus); }交互反馈也很重要。例如当用户点击“下一步”但已是最后一步时用AfxMessageBox给出提示当求解完成时可以在列表框中自动选中第一步甚至可以为每一步添加短暂的延时用Sleep()函数或定时器实现自动播放动画效果。踩坑提醒MFC的控件操作如SetWindowText,ShowWindow必须在主UI线程中执行。如果你在某个耗时计算线程中直接调用这些函数更新界面可能会导致程序崩溃或界面卡死。标准的做法是在计算线程中通过PostMessage或SendMessage向主窗口发送自定义消息在主窗口的消息处理函数中更新UI。对于我们这个项目由于BFS计算瞬间完成直接在按钮响应函数中更新UI是安全的。5. 项目集成、调试与功能扩展将算法核心和MFC界面整合成一个流畅可用的应用程序还需要处理一些细节并思考如何让这个课程设计更加出彩。5.1 工程配置与模块整合在Visual Studio中你需要确保项目的配置正确。通常使用“Debug”模式进行开发调试使用“Release”模式生成最终可执行文件。将之前写好的RiverCrossingSolver类的.h和.cpp文件添加到项目中。一个常见的整合问题是字符编码。MFC默认使用TCHAR和CString它们可能是多字节字符集MBCS或宽字符Unicode这取决于项目设置。而我们的算法核心使用的是标准C的std::string。为了避免混乱我建议在项目属性中将“字符集”设置为“使用多字节字符集”这样TCHAR就是charCString可以方便地与std::string转换。在核心算法模块中坚持使用标准C库std::vector,std::string等。在界面交互层MFC对话框类使用CString。当需要将算法结果std::string显示到界面时进行转换std::string stdStr Result; CString cstr(stdStr.c_str()); // 简单转换 m_wndSomeStatic.SetWindowText(cstr);反之从控件获取文本时CString cstr; m_wndSomeEdit.GetWindowText(cstr); std::string stdStr CT2A(cstr.GetString()); // 使用ATL转换宏5.2 典型问题排查与调试技巧在开发过程中你可能会遇到以下问题程序运行后点击按钮无反应检查首先在按钮响应函数OnBnClickedButtonXXX的开始处设置一个断点看函数是否被调用。如果没有检查消息映射BEGIN_MESSAGE_MAP和ON_BN_CLICKED的ID是否正确以及控件ID是否与头文件中定义的IDC_BUTTON_XXX常量一致。检查对话框编辑器中的按钮ID是否与代码中的ID匹配。界面显示错乱或图片不更新检查updateUIWithState函数逻辑确保ShowWindow(SW_SHOW)和SW_HIDE用对了。检查图片资源的ID是否正确加载。确保在OnInitDialog()中为CStatic图片控件调用了ModifyStyle(0, SS_BITMAP)并正确设置了位图句柄。尝试在状态更新后调用Invalidate()和UpdateWindow()强制重绘对话框区域。BFS求解结果为空或错误检查isStateValid函数的逻辑。这是最容易出错的地方。仔细对照2.1节中的非法状态条件用几个典型状态如(R, L, L, L)测试你的函数。调试在BFS循环中打印或输出到调试窗口每一步扩展出的状态和动作观察搜索过程是否合理。检查applyAction函数确保它正确地改变了状态并且进行了“携带物是否在身边”的校验。路径回溯时程序崩溃检查cameFrom映射表。确保在找到目标状态开始回溯时cameFrom中包含了从起点到目标的所有状态链接。崩溃很可能是因为在cameFrom中找不到某个状态的父节点it cameFrom.end()这通常是因为起始状态没有被正确加入cameFrom或者在记录父状态时键值对弄错了。调试利器熟练使用Visual Studio的调试器。设置断点、逐行执行F10、进入函数F11、查看变量值悬停或监视窗口、查看调用堆栈这些是定位问题的基本技能。对于MFC程序特别要留意消息处理函数的调用栈。5.3 功能扩展与课程设计亮点挖掘完成基本功能后你可以考虑添加一些扩展功能这能让你的课程设计报告更加丰满也更能体现你的思考和能力算法对比除了BFS再实现一个DFS算法可以设置最大深度防止无限递归。在界面上增加一个选项让用户可以选择使用BFS还是DFS求解并对比两者找到的解决方案步数、搜索过的状态数。这能直接体现你对不同搜索策略的理解。动画演示让过河过程动起来。使用MFC的定时器SetTimer/KillTimer在“自动演示”模式下每隔一秒或由滑块控件控制的速度自动触发“下一步”并让角色图片在两岸间有一个简单的移动动画可以通过改变图片控件的位置实现。这大大提升了用户体验。问题泛化当前的代码是针对“农夫、狼、羊、白菜”这个特定问题的。你可以尝试设计一个更通用的“状态空间搜索求解器”。定义一个抽象的“状态”接口和“动作”接口让“农夫过河”只是它的一个具体实现。这样你的程序框架就可以轻松扩展到解决“传教士与野人”、“八数码”等问题。这体现了优秀的软件设计思想。步骤详解与撤销在列表框中点击某一步界面立即跳转到该步骤的状态。实现完整的“撤销”Undo和“重做”Redo功能允许用户手动操作拖动角色并检查操作是否合法这相当于实现了一个交互式游戏。图形美化使用更精美的图片或者用GDI绘制更生动的河岸、小船、波浪等元素。良好的视觉效果永远是加分项。实现这些扩展功能时最重要的是保持代码的模块化。将算法、界面控制、图形渲染分离到不同的类或模块中这样在添加新功能时才不会让代码变得一团糟。例如将动画控制逻辑单独放在一个CAnimationManager类中。最后在撰写课程设计报告时不要只贴代码。重点阐述你的设计思路为什么用BFS状态如何编码、关键实现细节路径记录、非法状态判断、遇到的问题及解决方案调试过程以及对扩展功能的思考和实现。画出程序模块结构图、类图、状态转换图这些都能让你的报告更具专业性。记住这个项目最大的价值在于它完整地展示了你将理论算法转化为实际应用的能力而MFC正是连接这两者的那座“桥”。
1. 项目概述从经典谜题到桌面应用“农夫过河”这个题目但凡学过数据结构或者算法导论的朋友应该都不陌生。它本质上是一个经典的“状态空间搜索”问题通常被用来讲解图的广度优先搜索BFS或者深度优先搜索DFS算法。我第一次接触它还是在大学的数据结构课本上当时用控制台打印一堆字符来表示状态变化虽然逻辑通了但总觉得少了点“产品”的感觉像个半成品。这次课程设计的要求是把这道经典题目从一个简单的算法演示升级为一个完整的、带图形界面的桌面应用程序。核心就是用C实现算法逻辑再用微软的MFCMicrosoft Foundation Classes框架给它套上一个Windows风格的“外壳”。这就不再是单纯的编程作业了它更像是一个微型软件项目的雏形要求你同时考虑后台算法的正确性与效率以及前台用户交互的友好与直观。对于计算机相关专业的学生来说这是一个绝佳的练手机会能让你把数据结构、算法设计、面向对象编程和基本的UI开发知识串起来体验一次小型软件的生命周期。为什么选择C和MFC这个组合C自不必说它是理解内存管理、数据结构和算法效率的“不二法门”很多底层逻辑用C实现起来非常直接。而MFC虽然如今看来有些“复古”不再是市场主流但在教学和特定遗留系统维护中它依然有其一席之地。学习MFC能让你深刻理解Windows消息驱动机制、文档/视图架构这些GUI编程的核心思想其设计模式对理解其他框架如Qt的Signal/Slot也大有裨益。通过这个项目你收获的将不仅仅是一个“过河程序”更是一套解决同类状态搜索问题的通用方法以及一次完整的桌面应用开发实战经验。2. 核心问题解析与算法设计思路在动手敲代码之前我们必须把“农夫过河”这个问题本身以及解决它的核心算法思路彻底吃透。这是整个项目的基石如果这里想错了后面的界面做得再花哨也是徒劳。2.1 “农夫过河”问题的状态建模我们先明确一下游戏规则农夫需要把一只狼、一只羊和一筐白菜从河的左岸安全运到右岸。他的小船一次只能载他自己和另外一样东西狼、羊或白菜。如果农夫不在场狼会吃羊羊会吃白菜。我们的目标就是找到一系列安全的渡河步骤。解决这类问题的第一步也是最重要的一步就是状态抽象。我们不能在程序里真的去模拟一条河、一条船而是要把所有可能的安全局面抽象成计算机能处理的数据。一个典型的状态可以用一个四元组来表示(Farmer, Wolf, Sheep, Cabbage)每个元素取值为L左岸或R右岸。例如初始状态是(L, L, L, L)目标状态是(R, R, R, R)。但是并非所有2^416种组合都是合法的。我们需要根据规则定义非法状态即被吃掉的状态农夫不在左岸且狼和羊同在左岸(R, L, L, *)农夫不在左岸且羊和白菜同在左岸(R, *, L, L)农夫不在右岸且狼和羊同在右岸(L, R, R, *)农夫不在右岸且羊和白菜同在右岸(L, *, R, R)*表示任意即狼或白菜的位置不影响该非法条件的成立。我们的算法就是要从初始状态出发避开所有这些非法状态找到一条通往目标状态的路径。2.2 搜索算法选型BFS vs DFS这本质上是一个在图状态空间中寻找路径的问题。每个合法状态是一个节点一次安全的渡河操作就是连接两个节点的边。最常用的两种搜索策略是广度优先搜索BFS和深度优先搜索DFS。广度优先搜索BFS像水波扩散一样从起点开始先探索所有一步能到达的状态再探索所有两步能到达的状态以此类推。BFS保证找到的路径一定是步数最少的。对于本题状态空间很小BFS是首选因为它能直接给出最优解最少渡河次数。实现上我们需要一个队列Queue来存放待探索的状态。深度优先搜索DFS沿着一条路径一直深入直到无法继续或找到目标然后回溯尝试其他分支。DFS不保证找到的路径最短而且如果不对搜索深度加以限制在状态图有环的情况下可能会陷入无限循环。对于本题虽然也可以用但需要记录已访问状态以防止重复探索其代码逻辑比BFS稍复杂且结果不一定最优。在这个课程设计中强烈建议使用BFS算法。理由很充分问题规模小BFS实现简单且能天然求得最优解这能让你的项目报告更有亮点。在向用户展示时你可以明确说明“本程序找到的是步数最少的解决方案”。2.3 路径的记录与回溯BFS帮我们找到了目标状态但我们还需要把“怎么走过来的”这条路径还原出来。这就需要我们在搜索过程中不仅记录每个状态还要记录该状态是从哪个前驱状态通过何种操作转换而来的。一个经典的实现方法是使用一个map或unordered_map哈希表。键Key是当前状态可以用一个整数编码表示如二进制位值Value是一个结构体包含两个信息parentState: 前一个状态。action: 从父状态到当前状态所执行的操作例如“农夫独自过河”、“农夫带羊过河”。当我们从队列中取出一个状态并扩展出它的所有合法后继状态时如果某个后继状态未被访问过我们就将其加入队列并在这个map中记录它的父状态和对应的操作。一旦搜索到目标状态我们就可以从这个map出发沿着parentState一路回溯到起始状态同时将action反向收集起来就得到了一条从起点到终点的操作序列。注意状态编码要注意唯一性。一个简单的方法是用4个比特位分别表示农夫、狼、羊、白菜的位置0为左岸1为右岸。这样一个状态可以用一个0-15之间的整数唯一表示非常便于作为容器的键值。3. 核心数据结构与C算法实现详解理论清晰之后我们进入具体的代码实现环节。这一部分我们将用C构建整个问题的求解引擎。我建议将核心算法部分封装成一个独立的类比如叫做RiverCrossingSolver这样逻辑清晰也便于与后续的MFC界面进行对接。3.1 状态与操作的表示首先我们需要定义如何表示状态和操作。// 定义位置左岸或右岸 enum class Position { LEFT, RIGHT }; // 状态结构体表示某一时刻所有角色在岸上的位置 struct State { Position farmer; Position wolf; Position sheep; Position cabbage; // 为了方便比较和作为map的key我们需要重载运算符 bool operator(const State other) const { return farmer other.farmer wolf other.wolf sheep other.sheep cabbage other.cabbage; } // 也可以将其编码为一个整数 int encode() const { int code 0; if (farmer Position::RIGHT) code | 1 3; if (wolf Position::RIGHT) code | 1 2; if (sheep Position::RIGHT) code | 1 1; if (cabbage Position::RIGHT) code | 1 0; return code; } }; // 操作动作枚举表示农夫可以执行的动作 enum class Action { FARMER_ALONE, // 农夫独自过河 FARMER_WITH_WOLF, // 农夫带狼过河 FARMER_WITH_SHEEP, // 农夫带羊过河 FARMER_WITH_CABBAGE // 农夫带白菜过河 };3.2 非法状态判断与状态转移这是算法的核心函数。给定一个状态和一个动作我们需要判断执行这个动作后得到的新状态是否合法。class RiverCrossingSolver { private: // 判断一个状态是否安全不被吃 bool isStateValid(const State s) { // 农夫在左岸时检查右岸是否安全实际上检查对岸更直观 // 更通用的判断如果农夫和羊不在同一边那么狼和羊不能单独在一起羊和白菜也不能单独在一起。 if (s.sheep s.wolf s.farmer ! s.sheep) { return false; // 狼吃羊 } if (s.sheep s.cabbage s.farmer ! s.sheep) { return false; // 羊吃白菜 } return true; } // 尝试应用一个动作返回新状态。如果动作非法如农夫想带一个不在他身边的东西返回false。 bool applyAction(const State current, Action action, State next) { next current; // 农夫总是移动 next.farmer (current.farmer Position::LEFT) ? Position::RIGHT : Position::LEFT; switch (action) { case Action::FARMER_ALONE: // 只移动农夫其他不变 break; case Action::FARMER_WITH_WOLF: if (current.wolf ! current.farmer) return false; // 狼不和农夫在同一边不能带 next.wolf next.farmer; // 狼跟随农夫移动 break; case Action::FARMER_WITH_SHEEP: if (current.sheep ! current.farmer) return false; next.sheep next.farmer; break; case Action::FARMER_WITH_CABBAGE: if (current.cabbage ! current.farmer) return false; next.cabbage next.farmer; break; default: return false; } // 移动后检查新状态是否安全 return isStateValid(next); } };3.3 BFS搜索与路径回溯的实现现在我们实现BFS的主函数。我们将使用queue进行广度优先搜索使用unordered_mapint, pairint, Action来记录路径键是编码后的状态值是一个对包含父状态的编码和导致此状态的动作。std::vectorstd::pairState, Action RiverCrossingSolver::solveBFS() { State startState {Position::LEFT, Position::LEFT, Position::LEFT, Position::LEFT}; State goalState {Position::RIGHT, Position::RIGHT, Position::RIGHT, Position::RIGHT}; std::queueState q; std::unordered_mapint, std::pairint, Action cameFrom; // 路径记录器 std::unordered_setint visited; // 已访问集合防止重复访问 int startCode startState.encode(); int goalCode goalState.encode(); q.push(startState); visited.insert(startCode); cameFrom[startCode] {-1, Action::FARMER_ALONE}; // 起始状态没有父状态 while (!q.empty()) { State current q.front(); q.pop(); int currentCode current.encode(); if (currentCode goalCode) { // 找到目标回溯路径 return reconstructPath(cameFrom, startCode, goalCode); } // 尝试所有可能的动作 std::vectorAction allActions {Action::FARMER_ALONE, Action::FARMER_WITH_WOLF, Action::FARMER_WITH_SHEEP, Action::FARMER_WITH_CABBAGE}; for (Action act : allActions) { State nextState; if (applyAction(current, act, nextState)) { int nextCode nextState.encode(); if (visited.find(nextCode) visited.end()) { visited.insert(nextCode); q.push(nextState); cameFrom[nextCode] {currentCode, act}; // 记录父状态和动作 } } } } // 如果队列为空还没找到返回空路径理论上本题必有解 return std::vectorstd::pairState, Action(); } // 回溯函数根据cameFrom映射重建步骤序列 std::vectorstd::pairState, Action RiverCrossingSolver::reconstructPath( const std::unordered_mapint, std::pairint, Action cameFrom, int startCode, int goalCode) { std::vectorstd::pairState, Action path; int currentCode goalCode; // 从目标倒推到起点 while (currentCode ! startCode) { auto it cameFrom.find(currentCode); if (it cameFrom.end()) break; // 理论上不会发生 int parentCode it-second.first; Action action it-second.second; // 我们需要解码状态这里简化为一个解码函数根据编码还原State State currentState decodeState(currentCode); // decodeState函数需要实现 // 将状态导致该状态的动作加入路径。注意顺序是反的。 path.push_back({currentState, action}); currentCode parentCode; } // 加入起始状态其动作无意义 path.push_back({decodeState(startCode), Action::FARMER_ALONE}); std::reverse(path.begin(), path.end()); // 反转得到从起点到终点的顺序 return path; }实操心得在实现BFS时visited集合至关重要它可以防止程序陷入状态循环例如农夫带着羊过去又独自回来无限重复。使用unordered_set基于状态编码进行查找效率很高。另外cameFrom这个映射是回溯路径的关键务必在将新状态加入队列时同步更新它。4. MFC图形界面设计与实现算法引擎准备好了现在我们要给它做一个Windows桌面应用的“外壳”。MFC是一个基于文档/视图架构的框架但对于我们这种小型工具使用基于对话框的应用程序Dialog-based更加简单快捷。4.1 创建MFC对话框项目与界面布局打开Visual Studio新建一个“MFC应用”项目在应用程序类型中选择“基于对话框”取消“使用Unicode库”如果你的项目不需要国际化可以简化字符串处理。项目创建好后你会看到一个资源视图里面有一个主对话框模板。我们的界面需要包含以下几个核心区域状态显示区用图片或文字形象地展示左岸和右岸分别有哪些角色。可以使用Picture Control控件放置静态图片或者用List Box、Static Text动态更新文字。操作记录区用一个List Box或Edit Control设置为只读、多行来显示已执行的步骤或完整的解决方案步骤。控制按钮如“开始求解”Button、“下一步”Button、“上一步”Button、“重置”Button。信息提示区用Static Text显示当前状态、步数等信息。布局时可以利用MFC的对话框编辑器拖拽控件并调整位置。为了美观和清晰可以使用Group Box控件将状态显示区和控制区分开。4.2 连接界面与算法数据绑定与消息响应这是MFC开发的核心——消息映射机制。我们需要将按钮的点击事件BN_CLICKED与我们的处理函数关联起来。首先在对话框类的头文件如CMyDlg.h中声明我们的算法求解器对象以及用于存储解决方案的变量。// CMyDlg.h class CMyDlg : public CDialogEx { // ... private: RiverCrossingSolver m_solver; std::vectorstd::pairState, Action m_solutionPath; size_t m_currentStepIndex; // 当前演示到第几步 // 控件变量 CListBox m_wndStepList; // 步骤列表控件变量 CStatic m_wndLeftBankPic; // 左岸图片控件 CStatic m_wndRightBankPic; // 右岸图片控件 // ... };然后在对话框的OnInitDialog()函数中进行初始化比如设置列表的样式初始化状态显示等。最关键的是为按钮添加事件处理程序。在资源编辑器中右键点击“开始求解”按钮选择“添加事件处理程序”向导会自动在头文件和源文件中生成代码框架。// CMyDlg.cpp BEGIN_MESSAGE_MAP(CMyDlg, CDialogEx) ON_BN_CLICKED(IDC_BUTTON_SOLVE, CMyDlg::OnBnClickedButtonSolve) ON_BN_CLICKED(IDC_BUTTON_NEXT, CMyDlg::OnBnClickedButtonNext) ON_BN_CLICKED(IDC_BUTTON_PREV, CMyDlg::OnBnClickedButtonPrev) ON_BN_CLICKED(IDC_BUTTON_RESET, CMyDlg::OnBnClickedButtonReset) END_MESSAGE_MAP() void CMyDlg::OnBnClickedButtonSolve() { // 调用求解器 m_solutionPath m_solver.solveBFS(); m_currentStepIndex 0; // 清空步骤列表 m_wndStepList.ResetContent(); // 将解决方案的每一步描述性文字加入列表 CString strStep; for (size_t i 0; i m_solutionPath.size(); i) { const auto step m_solutionPath[i]; strStep.Format(_T(步骤%2d: %s), i1, actionToString(step.second).c_str()); m_wndStepList.AddString(strStep); } // 更新界面显示当前状态初始状态 updateUIWithState(m_solutionPath.empty() ? State{} : m_solutionPath[0].first); } void CMyDlg::OnBnClickedButtonNext() { if (m_currentStepIndex 1 m_solutionPath.size()) { m_currentStepIndex; updateUIWithState(m_solutionPath[m_currentStepIndex].first); // 高亮显示当前步骤在列表中 m_wndStepList.SetCurSel(m_currentStepIndex); } else { AfxMessageBox(_T(已经是最后一步了)); } } void CMyDlg::OnBnClickedButtonPrev() { if (m_currentStepIndex 0) { m_currentStepIndex--; updateUIWithState(m_solutionPath[m_currentStepIndex].first); m_wndStepList.SetCurSel(m_currentStepIndex); } else { AfxMessageBox(_T(已经是第一步了)); } }updateUIWithState函数负责根据传入的State对象更新界面上的图片或文字直观地展示谁在左岸、谁在右岸。actionToString函数将Action枚举转换为易于理解的文字描述如“农夫带羊过河”。4.3 状态可视化与交互反馈为了让界面更生动我们可以用图片来表示各个角色。准备四张小图片农夫、狼、羊、白菜根据State中的位置将它们分别加载并显示在对话框左岸或右岸的Picture Control中。可以使用MFC的CImage类或更老的CBitmap来加载和显示位图。在updateUIWithState函数中void CMyDlg::updateUIWithState(const State state) { // 假设我们有成员变量 CStatic m_picFarmerLeft, m_picFarmerRight 等... // 根据state.farmer的值显示/隐藏左岸或右岸的农夫图片 m_picFarmerLeft.ShowWindow(state.farmer Position::LEFT ? SW_SHOW : SW_HIDE); m_picFarmerRight.ShowWindow(state.farmer Position::RIGHT ? SW_SHOW : SW_HIDE); // 同理更新狼、羊、白菜的图片显示... // 更新状态文字提示 CString strStatus; strStatus.Format(_T(当前步数: %d/%d), m_currentStepIndex1, m_solutionPath.size()); SetDlgItemText(IDC_STATIC_STATUS, strStatus); }交互反馈也很重要。例如当用户点击“下一步”但已是最后一步时用AfxMessageBox给出提示当求解完成时可以在列表框中自动选中第一步甚至可以为每一步添加短暂的延时用Sleep()函数或定时器实现自动播放动画效果。踩坑提醒MFC的控件操作如SetWindowText,ShowWindow必须在主UI线程中执行。如果你在某个耗时计算线程中直接调用这些函数更新界面可能会导致程序崩溃或界面卡死。标准的做法是在计算线程中通过PostMessage或SendMessage向主窗口发送自定义消息在主窗口的消息处理函数中更新UI。对于我们这个项目由于BFS计算瞬间完成直接在按钮响应函数中更新UI是安全的。5. 项目集成、调试与功能扩展将算法核心和MFC界面整合成一个流畅可用的应用程序还需要处理一些细节并思考如何让这个课程设计更加出彩。5.1 工程配置与模块整合在Visual Studio中你需要确保项目的配置正确。通常使用“Debug”模式进行开发调试使用“Release”模式生成最终可执行文件。将之前写好的RiverCrossingSolver类的.h和.cpp文件添加到项目中。一个常见的整合问题是字符编码。MFC默认使用TCHAR和CString它们可能是多字节字符集MBCS或宽字符Unicode这取决于项目设置。而我们的算法核心使用的是标准C的std::string。为了避免混乱我建议在项目属性中将“字符集”设置为“使用多字节字符集”这样TCHAR就是charCString可以方便地与std::string转换。在核心算法模块中坚持使用标准C库std::vector,std::string等。在界面交互层MFC对话框类使用CString。当需要将算法结果std::string显示到界面时进行转换std::string stdStr Result; CString cstr(stdStr.c_str()); // 简单转换 m_wndSomeStatic.SetWindowText(cstr);反之从控件获取文本时CString cstr; m_wndSomeEdit.GetWindowText(cstr); std::string stdStr CT2A(cstr.GetString()); // 使用ATL转换宏5.2 典型问题排查与调试技巧在开发过程中你可能会遇到以下问题程序运行后点击按钮无反应检查首先在按钮响应函数OnBnClickedButtonXXX的开始处设置一个断点看函数是否被调用。如果没有检查消息映射BEGIN_MESSAGE_MAP和ON_BN_CLICKED的ID是否正确以及控件ID是否与头文件中定义的IDC_BUTTON_XXX常量一致。检查对话框编辑器中的按钮ID是否与代码中的ID匹配。界面显示错乱或图片不更新检查updateUIWithState函数逻辑确保ShowWindow(SW_SHOW)和SW_HIDE用对了。检查图片资源的ID是否正确加载。确保在OnInitDialog()中为CStatic图片控件调用了ModifyStyle(0, SS_BITMAP)并正确设置了位图句柄。尝试在状态更新后调用Invalidate()和UpdateWindow()强制重绘对话框区域。BFS求解结果为空或错误检查isStateValid函数的逻辑。这是最容易出错的地方。仔细对照2.1节中的非法状态条件用几个典型状态如(R, L, L, L)测试你的函数。调试在BFS循环中打印或输出到调试窗口每一步扩展出的状态和动作观察搜索过程是否合理。检查applyAction函数确保它正确地改变了状态并且进行了“携带物是否在身边”的校验。路径回溯时程序崩溃检查cameFrom映射表。确保在找到目标状态开始回溯时cameFrom中包含了从起点到目标的所有状态链接。崩溃很可能是因为在cameFrom中找不到某个状态的父节点it cameFrom.end()这通常是因为起始状态没有被正确加入cameFrom或者在记录父状态时键值对弄错了。调试利器熟练使用Visual Studio的调试器。设置断点、逐行执行F10、进入函数F11、查看变量值悬停或监视窗口、查看调用堆栈这些是定位问题的基本技能。对于MFC程序特别要留意消息处理函数的调用栈。5.3 功能扩展与课程设计亮点挖掘完成基本功能后你可以考虑添加一些扩展功能这能让你的课程设计报告更加丰满也更能体现你的思考和能力算法对比除了BFS再实现一个DFS算法可以设置最大深度防止无限递归。在界面上增加一个选项让用户可以选择使用BFS还是DFS求解并对比两者找到的解决方案步数、搜索过的状态数。这能直接体现你对不同搜索策略的理解。动画演示让过河过程动起来。使用MFC的定时器SetTimer/KillTimer在“自动演示”模式下每隔一秒或由滑块控件控制的速度自动触发“下一步”并让角色图片在两岸间有一个简单的移动动画可以通过改变图片控件的位置实现。这大大提升了用户体验。问题泛化当前的代码是针对“农夫、狼、羊、白菜”这个特定问题的。你可以尝试设计一个更通用的“状态空间搜索求解器”。定义一个抽象的“状态”接口和“动作”接口让“农夫过河”只是它的一个具体实现。这样你的程序框架就可以轻松扩展到解决“传教士与野人”、“八数码”等问题。这体现了优秀的软件设计思想。步骤详解与撤销在列表框中点击某一步界面立即跳转到该步骤的状态。实现完整的“撤销”Undo和“重做”Redo功能允许用户手动操作拖动角色并检查操作是否合法这相当于实现了一个交互式游戏。图形美化使用更精美的图片或者用GDI绘制更生动的河岸、小船、波浪等元素。良好的视觉效果永远是加分项。实现这些扩展功能时最重要的是保持代码的模块化。将算法、界面控制、图形渲染分离到不同的类或模块中这样在添加新功能时才不会让代码变得一团糟。例如将动画控制逻辑单独放在一个CAnimationManager类中。最后在撰写课程设计报告时不要只贴代码。重点阐述你的设计思路为什么用BFS状态如何编码、关键实现细节路径记录、非法状态判断、遇到的问题及解决方案调试过程以及对扩展功能的思考和实现。画出程序模块结构图、类图、状态转换图这些都能让你的报告更具专业性。记住这个项目最大的价值在于它完整地展示了你将理论算法转化为实际应用的能力而MFC正是连接这两者的那座“桥”。
双梁正问题 【 torch 实战】（Python代码实现）)
