算法分析与设计实验报告书评分。
题目：（例如）基于矩阵变换算法的图同构识别。
设计人：李文森。
班级：网络工程2班学号：1214080613213
一、 实验环境：
1、硬件环境：个人机，cpu主频：2.3ghz内存：4gb
2、软件环境：操作系统：windows
编程语言：c++
二、 实验任务解决方案：
实验思路：设两个无向图g=(v,e),g’=(v’,e’),g,g’同构当且仅当两图的邻接矩阵、行间同或矩阵、行间异或矩阵具有相同的行行置换。
1. 矩阵算法步骤。
a. 根据定义，求出同型矩阵aag、aag’.
b. 计算出行间同或矩阵rag、rag’，行间异或矩阵rxg、rxg’.
c. 以图g=(v,e)的行间异或矩阵为参照，对rxg的每一行，从rxg’搜索所有行，找到一个匹配。若不存在相应匹配，则两图不同构；若匹配，转步骤（4）.
d. 判断邻接矩阵ag、ag’,行间同或矩阵中是否存在同样的匹配，若匹配存在，调整邻接矩阵ag’、行间异或矩阵rxg’、行间同或矩阵rag’对应的行和列；若不匹配，则不同构。
2、基于矩阵变换算法的流程图。
3、基于矩阵变换算法实现的关键**。
冒泡排序。void wensen_mp(int mp,int n)
int t;
for(int i=0;i
核心**。/异或矩阵行转换。
void wensen_hx(int **p1,int **p13,int **p14,int **p2,int **p23,int **p24,int n)
int *p77=new int[n];/用于替换的临时一维数组，存放p13
int *p88=new int[n];/用于替换的临时一维数组，存放p23
int *p33=new int[n];/用于替换的临时一维数组，存放p1
int *p44=new int[n];/用于替换的临时一维数组，存放p14
int *p55=new int[n];/用于替换的临时一维数组，存放p2
int *p66=new int[n];/用于替换的临时一维数组，存放p24
int *p99=new int[n];/用于行行替换的临时数组。
int t;
int tt;//进行跳转判断。
int ttt=0;//进行跳转判断。
//行行替换。
for( int i=0;i
首先进行行赋值给另外一个数组p1
for(int i33=0;i33
首先进行行赋值给另外一个数组。
for(int i44=0;i44
p77,p33,p44冒泡排序。
wensen_mp(p77,n);
wensen_mp(p33,n);
wensen_mp(p44,n);
开始进行比较，p12的每一行与p23的每一行进行比较。
for(int y=i;y
三、 基于矩阵变换算法的计算复杂度分析（最好、最差、平均情况复杂度）：
1.同构最好情况是：每一行都互相对应，所以复杂度为：3n^2+3n^3+8n^2
时间复杂度为o(n^3)。
2.同构最坏情况是：每一行都与最后一行对应，所以复杂度为：3n^2+3n^3+8n*n!
时间复杂度为o(n*n!)
3.所以平均时间复杂度为o(n*n!)
四、 总结综合实验心得体会：
1.实例演示。
邻接矩阵：2. 实验体会。
本课程设计是为了判断无向图是否同构，采用了较为容易实现的邻接矩阵，同时用到了同型矩阵、行间异或矩阵、行间同或矩阵等知识。知道了同构当且仅当两图的邻接矩阵、行间同或矩阵、行间异或矩阵具有相同的行行置换。通过他们之间对应的关系，我写出了这个算法，并已经初步测试过，能正确判断图是否同构。
通过本次的课程设计，让我更好的了解了算法的重要性，一个优异的算法能极大的减少运行时间。在本课程设计上，在异或矩阵的比对上，为了更好的实现元素比对，我采用了了冒泡排序法，可以让它实现有序的比对，这样就减少了比对的次数，减少运算时间。本算法还有挺多改进的地方，例如，算法复杂度太大，所以算法还有待进一步改善，以达到更优。
/完全**。
#include
using namespace std;
/定义函数。
/22222222222222222222222同型矩阵。
void wensen_tx(int **p1,int **p2,int n)
for(int i=0;i
/3333333333333333333333异或矩阵。
void wensen_yh(int **p1,int **p2,int **p3,int n)
for( int i=0;i
///44444444444444444同或矩阵。
void wensen_th(int **p1,int **p2,int **p4,int n)
for(int i=0;i
输出函数。void wensen_out(int **p,char *s,int n)
cout< cout<<"n";
for(int i=0;i {
for(int j=0;j 姓名挑战游戏。学习算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对算法课程中基本概念 理论和方法的理解 训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念 使同学的程序设计... 一 课程题目。零钱问题贪心算法实现。二 课程摘要。1 题目描述。使用贪心算法设计思想设计算法实现找零钱问题。例题13 4一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分 10美分 5美分 及1美分的硬币。售货员分步骤组成... 一 课程题目。零钱问题贪心算法实现。二 课程摘要。1 题目描述。使用贪心算法设计思想设计算法实现找零钱问题。例题13 4 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分 1 0美分 5美分 及1美分的硬币。售货员分步...算法分析课程设计
算法设计与分析课程设计
算法设计与分析课程设计