“15数码问题求解系统”设计任务书

系统设计目的：设计一个15数码问题求解搜索系统，初步掌握智能搜索算法中的盲目搜索和启发式搜索这两类基本方法，同时通过具体的问题体会搜索算法、数据结构、概率等知识的综合应用。 系统设计基本要求： 问题描述：一个4×4棋盘，有15张牌1，2，…，15及一个空格，空格周围的牌可以向空格移动。求解：给定一个初始状态S、一个目标状态G，求从S到G的走步序列。 编程至少实现一种盲目搜索算法（可自选，如：深度优先，广度优先，有界深度优先等）。 设计一个启发式函数（最好是A*搜索函数）并编程实现，设计报告中必须给出函数的具体形式并说明设计思想（或分析为什么是A*算法）。 问题的初始状态S有程序生成和人工生成2种，数据结构可以采用数组的形式但用户界面尽可能用可视化形式显示。 问题的目标状态G如下图： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 要求系统给出从S到G的走步序列示意图，并计算比较所用算法搜索效率（采用外显率方法）。 编程语言尽可能统一使用VC++，要有良好的系统界面。 系统功能基本要求： 1．搜索算法应尽可能独立于具体问题。亦即搜索算法程序既可用于15数码问题，也可用于迷宫问题、修道士野人问题等。 2．不同搜索算法的搜索路径可实时显示，无解的应说明在搜索的哪一步上终止。 3．尽可能设计一个简单的、可视化的、能反映搜索过程的智能体。 4．对同一问题的初始状态S，能够分析不同搜索算法的效率，如扩展的节点数等。提交文档：课程设计报告（纸质和电子文档，要求见附录）、源程序（电子）和可执行程序。 附录：课程设计报告要求 一、设计任务 二、设计环境及使用说明 三、系统已实现的功能 四、算法思想及分析 包括：采用的算法，设计的思想（启发式函数），主要的实现框架，实现过程中遇到的问题及解决方法，部分关键代码(每行代码附说明) 五、结果图示及分析 包括：界面图示，典型运行结果图示，结果的简单分析，设计简要总结

1878年，美国最伟大的谜题专家"Sam Loyd发明了15数码谜题。这个谜题由一个正方形盒子和15个编号为1，2，...，15的正方形滑块组成，每个滑块的边长是盒子边长的1/4，因此可以把它们拼成如下面左图所示的形式，留下一个空格。每次可以把任何一个与空格相邻的滑块移动到空格中（因此在左图中可以把滑块12和15移动到空格中），而此滑块原来的位置变成新的空格。左图和右图非常接近，那么是否可以从左图的状态出发，在若干步之后变成右图的状态呢？Sam Loyd悬赏"1000美元奖给第一个解决这个问题的人。

游戏规则很容易理解，因此这个问题引起了很多不同职业不同阶层的的人的兴趣，可惜始终没有一个人拿到这1000美元。事实上，这个特殊的15数码问题是无解的，但在很多情况下，是可以从一个布局A转化成另一个布局B的。

15段数码管又称米字管，可以显示所有数字和字母。

数码管有7段数码管、12段数码管、15段数码管等。“段”的个数标明显示字符的笔画数。比如7段数码管就是常见的8字管，显示0~9数字和AbcdEF。

---