用栈求解迷宫问题实验报告

TSP问题求解

（一）实验目的

熟悉和掌握遗传算法的原理，流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。 （二）实验原理 巡回旅行商问题

给定一组n个城市和俩俩之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。 TSP问题也称为货郎担问题，是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的典型难题。 TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。 近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法，模拟退火方法以及遗传算法方法等。

TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题，是很自然的想法。

基本遗传算法可定义为一个8元组： （SGA）=（C，E，P0，M，Φ，Г，Ψ，Τ）

C ——个体的编码方法，SGA使用固定长度二进制符号串编码方法；

E ——个体的适应度评价函数； P0

人工智能实验报告 实验三 A*算法实验II

一、实验目的：

熟悉和掌握A*算法实现迷宫寻路功能，要求掌握启发式函数的编写以及各类启发式函数效果的比较。

二、实验原理：

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)小于等于n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

三、实验内容：

1、参考实验系统给出的迷宫求解核心代码，观察求解过程与思路。 2、画出用A*算法求解迷宫最短路径的流程图。 3、尝试改变启发式算法提高迷宫搜索速度。 4、分析不同启发式函数对迷宫寻路速度的提升效果。

四、实验报告要求：

1、画出A*算法求解迷宫最短路径问题的流程图。

2、试分析不同启发式函数对迷宫寻路求解的速度提升效果。 ①: gn =

迷宫问题实验报告

级 班 年 月 日 姓名 学号_

1．实验题目

以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 2．需求分析

本程序使用VC编写，实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路，或得出没有通路的结论。

① 输入的形式和输入值的范围：

A.输入指定的数字，以此选择迷宫的创建方式，分为手动创建迷宫和自动创建迷宫 B. 输入迷宫阵表的行数和列数，行数和列数不超过40行

C. 手动创建迷宫时，需要输入迷宫结点的通畅和障碍情况，0和1分别表示迷宫中的通路和障碍。

② 输出的形式：输出没有通路的结论，或者输出一个长方阵表，其中路径的每个结点都输出→、↓、←、↑之一，表示从当前结点到下一个结点的方向。

③ 程序所能达到的功能：实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路（迷宫的入口指定为坐标为（1,1）的结点，迷宫的出口指定为坐标为（迷宫最大行,迷宫最大列）的结点），或得出没有通路的

人工智能课程项目报告

基于遗传算法求解TSP问题

班级，学号，姓名

摘要：巡回旅行商问题（TSP）是一个组合优化方面的问题，从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以得到最优解。但是，利用穷举法所耗费的时间巨大的，当问题的规模很大时，穷举法的执行效率较低，不能满足及时的需要。

遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。该算法通过模拟生物学交叉、变异等方式，是当前向最优解的方向进化，因此使用于TSP问题的求解。

关键词：人工智能；TSP问题；遗传算法

本组成员：林志青，韩会雯，赵昊罡

本人分工：掌握遗传算法的基本原理，编写遗传算法中部分匹配交叉、循环交叉和循序交叉的具体实现过程。

1 引言

旅行商问题，即TSP问题，是一个最优解的求解问题。假设有n个城市，并且每个城市之间的距离已知，则如何只走一遍并获得最短路径为该问题的具体解释。

对于TSP问题的解决，有穷举法、分支限界法等求解方式，该文章主要介绍遗传算法求解过程。 遗传算法简称GA，在本质上是一种求解问题的高效并行全局搜索方法。遗传算法从任意一个初始化的群体出发，通过随机选择、交叉和变异等遗传操作，使群体一代一代的进化到

#include using namespace std; //坐标位置结构体 struct location { };

//方格信息结构体 struct grid {

bool via; //vir为真表示此通道畅通，否则表示当前位置阻塞 int direction;//从此通道走到下一通道的方向,0-3分别代表东南西int x; int y;

北四个方向。 栈 };

//定义迷宫，即迷宫数组 grid maze[10][10]= {

//0 x y 1 2 3 location seat;//通道在迷宫中的位置

//从每个方向退回来后方向值加1，当方向值为4时从path栈中退

4

{{false,0,0,0},{false,0,0,1},{false,0,0,2},{false,0,0,3},{false,0,0,4},{f

alse,0,0,5},{false,0,0,6},{false,0,0,7},{false,0,0,8},{false,0,0,9}},

{{false,0,

简单的介绍

3.2结合图论的迷宫生成算法

3.2.1图的深度优先遍历简介

例如，要遍历上面这个图

采取深度优先算法(从1开始)

准备一个Stack s，预定义三种状态：A未被访问B正准备访问C 已经访问

一、访问1，把它标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问

此时系统状态：

已经被访问的点：1

还没有被访问的点：3 4 6 7 8 9 10

正准备访问的点：2 5 (存放在Stack之中)

二、从Stack中拿出第一个元素2，标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问，如图：

简单的介绍

此时系统状态：

已经被访问的点：1 2

还没有被访问的点：4 6 7 8 9 10

正准备访问的点：3 5 (存放在Stack之中)

三、从Stack中拿出第一个元素3，标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问，如图：

此时系统状态：

已经被访问的点：1 2 3 4

还没有被访问的点：8 9 10

正准备访问的点：7 6 5 (存放在Stack之中)

依此类推，重复上面的动作，直到Stack为空，即所有的点都被访问

最后可能的遍历情况，如图：

3.2.2深度优先遍历之迷宫生成算法

运筹学实验报告

实验课程:运筹学 实验日期: 6月9日 任课教师: 杨小康 班级：信息与计算科学 姓名：刘静 学号0202110123 一、实验名称: 线性规划模型的编程求解（2） 二、实验目的： 1.掌握Lingo软件中变量定界函数，集合循环函数和@IF(条件，true结果，false结果) 2. 熟悉运输问题的数学模型，掌握简单运输问题数学模型的Lingo软件编程求解的方法，掌握解报告的内容 3. 掌握整数规划、0-1规划和指派问题的计算机求解方法。 三、实验要求: 1.给出所求解问题的数学模型； 2.给出Lingo中的编程程序； 3.能给出最优解和最优值； 四、报告正文（文挡，数据，模型，程序，图形）: 1．利用lingo软件求解下面运输问题的最优解。 单 位 销地 运 B1 B2 价 产地 A1 A2 A3 销量 3 1 7 3 11 9 4 6 B3 B4 产量 3 2 10 5 10 8 5 6 7 4 9 程序： model: sets: AH/A1..A3/:A; BD/B1..B4/:B; link(AH,BD):C,

实验报告

课程名称：数据结构与算法分析 实验名称：后缀表达式的计算

实验日期 3.20 班级： 数媒1401 姓名： 范业嘉 学号 1030514108

一、实验目的

熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的数据结构；

了解表达式的前缀、中缀、后缀等计算机内表示形式。

二、实验内容与要求

按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够： ⑴生成表达式的后缀表示，并输出；

⑵基于表达式的后缀表示，对该表达式求值； ⑶编写一个主程序对表达式求值函数进行测试；

三、数据结构设计

顺序栈

#define MAXSIZE 100 typedef struct {

ElemType elem[MAXSIZE]; int length; }SqStack; SqStack S; 此外还有链栈 Typefef struct{ Float /char data； Float/char *next； }sqstack；

四、算法设计

1.表达式求值基本操作

(1)表达式起始符＃入运算符栈； ⑵读表达式中字符；

实验报告

课程名称：数据结构与算法分析 实验名称：后缀表达式的计算

实验日期 3.20 班级： 数媒1401 姓名： 范业嘉 学号 1030514108

一、实验目的

熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的数据结构；

了解表达式的前缀、中缀、后缀等计算机内表示形式。

二、实验内容与要求

按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够： ⑴生成表达式的后缀表示，并输出；

⑵基于表达式的后缀表示，对该表达式求值； ⑶编写一个主程序对表达式求值函数进行测试；

三、数据结构设计

顺序栈

#define MAXSIZE 100 typedef struct {

ElemType elem[MAXSIZE]; int length; }SqStack; SqStack S; 此外还有链栈 Typefef struct{ Float /char data； Float/char *next； }sqstack；

四、算法设计

1.表达式求值基本操作

(1)表达式起始符＃入运算符栈； ⑵读表达式中字符；

一、 内容：

1、 本游戏主要实现了人控制键盘方向键使小人（*）走出迷宫。 2、 具有的功能：

1）、在游戏菜单里人可以选择不同难度的游戏进行游戏； 2）、在游戏过程中，可以通过键盘方向键使小人移动，走出迷宫； 3）、在游戏过程中，当人碰到墙壁（#）的时候小人过不去； 4）、当人顺利完成游戏之后，输出“========you are win!======”字样，30秒钟

后自动返回到游戏菜单； 5）、在游戏过程中，人可以通过按Esc键返回游戏菜单；也可以可以按0直接退出

游戏； 6）、在游戏菜单里，按0键可以退出游戏。 3、具体应用： 1）、人主要同过键盘的1,2,3数字键来选择游戏难度；

2）、在游戏中通过Esc键来返回菜单； 3）、同过0键退出游戏。

二、 上机环境

操作系统：windows7 开发工具:VC6.0

三、 函数调用关系图

main() 输入1 introduce() system(\roadcake() Enter menu() 输入0 输入2 system(\ 输入3 system(\ roadcake() roadcake() exit(0);

四、 各函数功能说明

main() menu() roadc