模型环境配置

利用yml导入conda虚拟环境

安装cuda与cudnn

cuda和cudnn的安装教程(全网最详细保姆级教程)_cudnn安装-CSDN博客

使用国内源安装

pip install numpy -i https://pypi.tuna.tsinghua.edu.cn/simple

pip install --upgrade tensorflow -i https://pypi.tuna.tsinghua.edu.cn/simple

测试gpu运行

根据提示补全依赖项

datasetProcess.py 将视频文件转换为 NumPy 数组（.npy 文件），并保存到指定目录中

models_rgb_depth.py 模型

evaluate_rgb_depth.py 跑数据集，返回准确度

prediction_test.py 返回true or false

前两者需要输入命令行参数

python evaluate_rgb_depth.py --dataset rwf2000 --vidLen 32 --batchSize 4 --mode all --lstmType sepconv --fusionType C --weightsPath models/rgb_rgbdiff_depth_C_6/rwf2000_best_val_acc_Model

• --dataset rwf2000: 指定数据集为 rwf2000。
• --vidLen 32: 每个视频序列的帧数为 32。
• --batchSize 4: 训练和评估的批量大小为 4。
• --mode all: 模型工作模式为 all，即使用视频帧、帧差和深度图三种输入。
• --lstmType sepconv: 使用 sepconv 类型的 LSTM 层。
• --fusionType C: 使用 C 类型的融合策略（特征拼接和注意力机制）。
• --weightsPath models/rgb_rgbdiff_depth_C_6/rwf2000_best_val_acc_Model: 指定预训练权重文件路径。

查找的概念

查找(Searching) ：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素( 或记录)。

查找表(Search Table) ：是由同一类型的数据元素(或记录)构成的集合。

关键字(Key) ：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。

静态查找表(Static Search Table) ：只作查找操作的查找表。
动态查找表(Dynamic Search Table) ： 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

平均查找长度 ：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度，则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为$\ ASL=\sum_{i=1}^{n}P_iC_i$

式中，n是查找表的长度;P是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即P,= 1/n;C;是找到第i个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

顺序表查找

顺序查找

1
2
3
4
5
6
7
8
9
10
11

/*有哨兵顺序查找*/
int Sequential_Search(int *a, int n, int key){
	int i;
	a[0] = key;	//设置a[0]为关键字，称之为“哨兵”
	i = n;	//循环从数组尾部开始
	while(a[i] != key){
		i--;
	}
	return i;	//返回0则说明查找失败
}

这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。
上述顺序表查找时间复杂度是O (n) 。

折半查找

当查找表是有序表时，可采用折半查找的方法。

算法思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int Binary_Search(SeqList L, ElemType key){
	int low = 0, high = L.length - 1, mid;
	while(low <= high){
		mid = (low + hight)/2;	//取中间位置
		if(L.elem[mid] == key){
			return mid;	//查找成功返回所在位置
		}else if(L.elem[mid] > key){
			high = mid - 1;	//从前半部分继续查找
		}else{
			low = mid + 1;	//从后半部分继续查找
		}
	}
	return -1;	//查找失败，返回-1
}

折半查找的过程可用二叉树来描述，称为判定树。

节点的树高代表该节点的查询次数

因此，长度为13的有序表进行折半查找的平均查找长度ASL=(1×1+2×2+3×4+4×6)/13 =41/13。

折半查找的时间复杂度为$\ O(\log_2n)$，平均情况下比顺序查找的效率高。

分块查找

为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

分块有序，是把数据集的记录分成了若千块，并且这些块需要满足两个条件：

• 块内无序：即每一块内的记录不要求有序。

• 块间有序：例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字…因为只有块间有序，才有可能在查找时带来效率。

对于分块有序的数据集，将每块对应一个索引项， 这种索引方法叫做分块索引。如下图所示，我们定义的分块索引的索引项结构分三个数据项：

• 最大关键码：它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；

• 块长：存储了块中的记录个数，以便于循环时使用；

• 块首指针：用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

在分块索引表中查找，就是分两步进行:
1.在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。例如在上图的数据集中查找62，我们可以很快可以从左上角的索引表中由57<62<96得到62在第三个块中。
2.根据块首指针找到相应的块，并在块中顺序查找关键码。

树表的查找

二叉排序树

二叉排序树(也称二叉查找树)或者是一棵空树，或者是具有下列特性的二叉树:

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
3. 左、右子树也分别是一棵二叉排序树。

根据二叉排序树的定义，左子树结点值<根结点值<右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。例如，下图所示二叉排序树的中序遍历序列为123468。

二叉排序树的插入和建立

在一棵二叉排序树中插入值为系的结点的步骤如下：

①若二叉排序树为空，则生成值为k的新结点s，同时将新结点s作为根结点插入。

②若k小于根结点的值,则在根的左子树中插入值为k的结点。

③若k大于根结点的值,则在根的右子树中插入值为k的结点。

④若k等于根结点的值，表明二叉排序树中已有此关键字，则无需插入。

二叉排序树插入算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 //构造函数
 BiNode(int k) : key(k), lchild(nullptr), rchild(nullptr) {};
// 递归插入函数
    void Insert(BiNode*& ptr, int k) {
        if (ptr == nullptr) { // 如果当前指针为空，插入新节点
            ptr = new BiNode(k);
            return;
        }
        if (k < ptr->key) { 
            Insert(ptr->lchild, k); // 递归插入到左子树
        } else if (k > ptr->key) {
            Insert(ptr->rchild, k); // 递归插入到右子树
        }
        // 如果k等于当前节点值，则不插入（BST通常不允许重复值）
    }
// 插入值到BST
    void Insert(int k) {
        Insert(root, k);
    }

二叉排序树的建立

1
2
3
4
5
6
7

// 构造函数：利用数组 a[] 和大小 n 建立二叉排序树
    BiSortTree(int a[], int n) {
        root = nullptr; // 初始化根节点为空
        for (int i = 0; i < n; ++i) {
            Insert(root, a[i]); // 插入数组中的每个元素
        }
    }

二叉排序树的查找过程

根据二叉排序树的定义，在二叉排序树中查找给定值k的过程如下:

①若二叉排序树为空，则表明查找失败，返回空指针;否则，若给定值k等于根结点的值,则表明查找成功,返回根结点。

②若给定值k小于根结点的值,则继续在根的左子树中查找。

③若给定值k大于根结点的值,则继续在根的右子树中查找。

1
2
3
4
5
6
7
8
9
10
11
12

// 非递归查找函数
   BiNode* Search2(BiNode* ptr, int k) {
       while (ptr) {
           if (k == ptr->key) // 找到目标节点
               return ptr;
           else if (k < ptr->key) // 查找左子树
               ptr = ptr->lchild;
           else                  // 查找右子树
               ptr = ptr->rchild;
       }
       return nullptr; // 未找到
   }

若二叉排序树是平衡的(即形态均匀)，则进行查找的时间复杂度为$\ O(log_2n)$;若退化为一棵单支树（最极端和最差的情况)，则其时间复杂度为$\ O(n)$。对于一般情况，其时间复杂度可以认为是$\ O(log_2n)$。

二叉排序树的删除

二叉排序树的查找和插入都很简单，但是删除操作就要复杂一些，此时要删除的结点有三种情况：

1. 叶子结点；
2. 仅有左或右子树的结点；
3. 左右子树都有的结点；

前两种情况都很简单，第一种只需删除该结点不需要做其他操作；第二种删除后需让被删除结点的直接后继接替它的位置；复杂就复杂在第三种，此时我们需要遍历得到被删除结点的直接前驱或者直接后继来接替它的位置，然后再删除。

第三种情况如下图所示：

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/*
若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，
并返回TRUE;否则返回FALSE
*/
bool DeleteBST(BiTree *T, int key){
	if(!T){
		return FALSE; 
	}else{
		if(key == T->data){
			//找到关键字等于key的数据元素
			return Delete(T);
		}else if(key < T -> data){
			return DeleteBST(T -> lchild, key);
		}else{
			return DeleteBST(T -> rchild, key);
		}
	}
}

下面是Delete()方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/*从二叉排序树中删除结点p，并重接它的左或右子树。*/
bool Delete(BiTree *p){
	BiTree q, s;
	if(p->rchild == NULL){
		//右子树为空则只需重接它的左子树
		q = p;
		p = p->lchild;
		free(q);
	}else if(p->lchild == NULL){
		//左子树为空则只需重接它的右子树
		q = p;
		p = p->rchild;
		free(q);
	}else{
		//左右子树均不空
		q = p;
		s = p->lchild;	//先转左
		while(s->rchild){//然后向右到尽头，找待删结点的前驱
			q = s;
			s = s->rchild;
		}
		//此时s指向被删结点的直接前驱，p指向s的父母节点
		p->data = s->data;	//被删除结点的值替换成它的直接前驱的值
		if(q != p){
			q->rchild = s->lchild;	//重接q的右子树
		}else{
			q->lchild = s->lchild;	//重接q的左子树
		}
		pree(s);
	}
	return TRUE;
}

二叉排序树的查找性能取决于二叉排序树的形状。

例如{ 62 , 88 , 58 , 47 , 35 , 73 , 51 , 99 , 37 , 93 } {62,88,58,47,35,73,51,99,37,93}{62,88,58,47,35,73,51,99,37,93}这样的数组，我们可以构建如下左图的二叉排序树。但如果数组元素的次序是从小到大有序，如{35,37,47,51,58,62,73,88,93,99},则二叉排序树就成了极端的右斜树，如下面右图的二叉排序树：

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，那么查找的时间复杂也就为$\ O(\log_2n)$，近似于折半查找。
不平衡的最坏情况就是像上面右图的斜树，查找时间复杂度为O(n)，这等同于顺序查找。
因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。

平衡二叉树

平衡二叉树：是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF

那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

平衡二叉树的插入

新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列4种情况：

1. LL平衡旋转(右单旋转):由于在结点A的左孩子(L)的左子树(L)上插入了新结点

1. RR平衡旋转(左单旋转):由于在结点A的右孩子(R)的右子树(R)上插入了 新结点

1. LR平衡旋转(先左后右双旋转):由于在A的左孩子(L)的右子树(R)上插入新结点

1. RL平衡旋转(先右后左双旋转):由于在A的右孩子(R)的左子树(L)上插入新结点

举例

B树

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。
B树是所有结点的平衡因子均等于0的多路平衡查找树。

下图所示的B树中所有结点的最大孩子数m = 5，因此它是一棵5阶B树，在m mm阶B树中结点最多可以有m个孩子。可以借助该实例来分析上述性质：

B树(B-树) - 删除_哔哩哔哩_bilibili

参考文献

数据结构：查找(Search)【详解】_index.search返回什么结构-CSDN博客

答辩稿

各位评委老师大家好，我是我们组的主持人张熙浚，我们组的研究方向是基于多模态特征融合的视频暴力行为识别方法的研究

接下来我会从四个方面介绍我们的项目

首先是背景与意义，暴力行为对社会危害极大，即使公共场所存在大量监控摄像头，但这些视频片段通常被用来在暴力犯罪发生后提供线索和证据，而很少被用来实时监控并阻止暴力行为。

由于监控人员不可能实时监控每一个摄像头产生的视频，所以部署暴力行为监测系统，能够节约人力资源，降低监控人员因疲劳而造成的风险，这十分关键

接下来，我将讲述当前暴力行为检测的研究现状。主流的人体动作识别把数据模态分为2类：视觉模态和非视觉模态。不同模态的数据有着各自的独特优势。

目前主流的单模态深度学习方法存在以下缺点。但真实的暴力事件场景往往存在以下特点。因此，我们提出了基于多模态的暴力事件检测，通过结合多种数据来源，从多个角度捕捉行为特征，尤其是在面对复杂环境、多人交互和遮挡等问题时，具有显著的优势。

接下来我会通过几篇论文中的方法介绍行为识别算法的研究现状

这一篇提出了数据集Rwf-2000，同时提出一种的双流网络架构，他们充分利用了RGB数据提供的外观信息和光流提供的运动信息，但缺点在于光流法计算量大、存储成本高，仅仅适用于光照条件良好、不拥挤的情况

这一篇是基于骨架的方法，通过提取人体骨骼关节，构成三维骨架阵列，通过骨架点卷积，实现分类。

优点是骨架可以很好的表示人体运动信息，但问题在于仅使用骨架数据，效果高度依赖于位姿估计的精度，无法有效应对存在遮挡的情况，同时因为仅使用骨架数据，其他信息存在缺失

这一篇是基于 2D CNN + RNN 的方法，2D CNN 提供强大的空间特征提取能力，RNN 提供强大的时间序列建模能力。将两者结合，能够更好地理解视频中的空间和时间信息。这一篇使用简单快速的预处理方法减少了冗余的背景信息，但其仅使用RGB模态，提取的特征不够全面

接下来我将介绍我们的研究内容与方法

我们的研究内容大致包含三个部分：1.提出一种基于多模态特征融合的视频暴力行为识别算法2.提出一种自适应的注意力算法用于多模态融合3.完成人体暴力行为检测系统的设计，接下来我将依次为大家介绍

第一部分，在特征提取阶段，为了区分暴力行为与非暴力行为，我们选择了三个要素进行提取：人体姿态、运动趋势和幅度、人物之间的位置关系，为了获取以上三个要素，研究工作包括下列内容：

a.RGB模态的去除冗余信息
为了避免原生RGB图像冗余信息影响模型判断，我们决定对于原生RGB图像进行冗余信息去除工作，首先计算一个视频中所有帧的均值，记为平均帧，用每一帧减去平均帧：去除不变的背景，保留运动的人体。

b.运动趋势与幅度特征的提取
目前主流反映物体运动趋势的方法是光流法，但我们考虑到光流图像在低像素复杂场景下效果不佳，且易受光照条件改变，并且计算量巨大，于是我们决定采取帧差法，通过对视频图像序列中相邻两帧作差分运算，来获得运动目标轮廓，以很好地适用于存在多个运动目标的情况。

c.深度模态的提取
在原始的RGB模态，复杂场景中难以分辨人物间的相对位置关系。因此，我们选取深度模态，其去除了颜色和纹理信息，并提供三维结构信息和人体轮廓，我们利用该论文提出的深度估计算法，对原始RGB视频进行深度估计，得到深度图，其清晰地反映了三维空间中人物间的相对位置关系。

算法框架方面，我们选择了CNN-LSTM的深度学习网络。LSTM擅长处理时序数据，而CNN能够从视频帧中提取空间特征。通过结合两者的优势，并以此构建了算法框架。

第二部分我们提出了一种自适应的注意力算法用于多模态融合，动态调整每个模态的权重，强调有用的信息特征，抑制不太有用的特征，从而应对不同场景。

池化，全连接层，归一化函数

第三部分，我们完成了人体暴力行为检测系统的设计，刻画了系统的边界及大小，人体暴力行为检测系统是一个自动检测暴力行为的智能视频监控系统。该系统采用了四层架构，即访问层，表示层、业务层以及数据层。 包含暴力检测模块，用户管理模块，视频源管理模块

我们已经初步构建了暴力行为的检测流程，系统包含离线分析和在线监测两种模式

为了提高检测速度和避免资源浪费，根据传入视频的总帧数进行判断，采取提示过短、一次预测或是多轮预测。

离线分析不依赖实时的监控视频，可对任意视频进行分析。它 的优点是它不依赖于视频监控系统，可以直接选择视频开始分析。

在线监测是暴力行为检测系统提供的另一种检测方式。它旨在利用监控视频资源，进行实时的暴力行为检测，达到即时分析并报警提示的功能。

最后是进度安排，我们已经完成算法大部分的编写，后续会继续完成系统的开发

谢谢各位老师观看，请各位老师批评指正

疑问与解惑

为什么暴力行为检测隶属于人体行为识别

人体行为识别（Human Activity Recognition, HAR）是一个广泛的领域，旨在通过传感器或视频数据来识别和分析人的各种动作或行为。暴力行为检测（Violent Behavior Detection, VBD）是这一领域的一个子任务，其核心目标是识别出具有暴力性质的特定行为，如打斗、推搡、殴打等。

暴力行为检测隶属于人体行为识别，主要原因是暴力行为本质上也是一种“人体行为”，通过分析人体的运动模式、姿态变化、动作轨迹等特征，能够有效识别出暴力事件。

对于暴力行为的定义是什么？

暴力行为通常指的是一种以伤害他人或具有威胁性、攻击性目的的行为。

之前的暴力行为检测方向是什么，现在侧重于人体动作本身有什么好处吗？

暴力行为的检测方法传统上主要依赖于视频监控中检测到的图像信息、声音信号以及动作的特征。早期的检测方法侧重于基于背景和环境的变化,声学信号分析

现代的暴力行为检测越来越注重人体动作本身的识别，这有几个显著的好处：

1. 精确度提高：通过分析人体动作的细节，尤其是肢体的动态变化（如运动轨迹、速度、姿势变化），可以更准确地判断是否为暴力行为。
2. 降低误报率：单纯依靠环境变化或者声学分析容易受其他因素干扰（如背景噪音、非暴力事件的运动），而人体动作本身可以提供更加直接、可靠的行为判定依据。
3. 多模态融合：现代的暴力行为检测往往不仅仅依赖于单一的视觉信息，还结合了深度学习、动作识别等技术，可以从多个角度进行判断。通过分析人体动作特征和其他环境数据（如声音、位置等），可以更好地识别暴力事件。
4. 实时监控：实时检测人体动作变化对于暴力行为的早期预警至关重要，尤其是在公共安全或视频监控系统中，动作识别可以即时检测到潜在的暴力行为并进行响应。

综上，侧重人体动作本身不仅可以提升检测的准确性，还能更好地从动态和连续的角度识别暴力行为，提高系统的实时性和鲁棒性。

单模态的人体动作识别的缺点有哪些

单模态人体动作识别（即仅使用一种数据模态，如视觉、声音、加速度等）存在以下主要缺点：

1. 信息局限性：

   单一模态只能捕获动作的部分信息，可能导致对动作的理解不够全面。例如，仅依赖视觉模态可能无法捕获细微的物理接触或动作的力度变化。

2. 环境敏感性：

   单模态方法对环境条件过于依赖。例如，视觉模态在光照不足或存在遮挡的情况下表现不佳，而非视觉模态（如加速度计）在传感器未正确佩戴或被干扰时表现不佳。

3. 无法应对模糊或模态冲突：

   单模态方法难以处理模糊的行为信号或区分相似动作。例如，在视觉模态中，某些动作（如挥手与投掷）可能在外观上十分相似。

4. 鲁棒性差：

   单模态在面对复杂场景（如多人交互、噪音、遮挡等）时，容易出现误判或漏判。例如，在仅依赖声音模态时，背景噪音可能干扰动作识别。

5. 缺乏上下文信息：

   单模态通常难以捕获行为发生的上下文。例如，仅通过视觉识别到一个人弯腰的动作，可能无法判断是捡拾物品还是摔倒

暴力行为场景有哪些特点，使用多模态对这些特点的优势有哪些

暴力行为场景通常具有以下几个显著特点，这些特点对检测系统提出了更高的要求：

1. 动态性强：

   暴力行为往往是迅速发生的，例如打斗、推搡、摔倒等动作可能在短时间内完成，导致动作的变化非常快。

2. 多人交互：

   暴力行为通常涉及两个或更多个体之间的互动，如互相推搡、打斗或攻击等。多个目标的运动和交互增加了识别的复杂度。

3. 复杂的姿态变化：

   暴力行为中的人物姿态变化通常非常剧烈，涉及肢体的快速摆动、抓握、推拉等动作，且可能伴随一定的身体接触。

4. 不规则的空间布局：

   在暴力行为场景中，人物可能会在空间内迅速移动，动作的方向和速度可能会发生剧烈变化。背景也可能因为人物的动态而发生显著变化。

5. 潜在的遮挡：

   在暴力行为中，人物之间的动作可能会出现遮挡（例如，两人打斗时，其中一个人可能被另一个人挡住）。这种情况给基于视觉的检测带来了挑战。

6. 噪声与干扰因素：

   背景中的其他活动、环境变化、背景噪声等都可能干扰暴力行为的识别。例如，打斗声可能被背景音乐、交通噪声等因素掩盖。

多模态（即结合多种数据来源或感知方式，如视觉、声音、传感器数据等）方法能够弥补单模态方法的不足，通过结合视觉、声音和传感器等多模态信息，可以更好地应对这些挑战，提升暴力行为检测的准确性、鲁棒性和实时性。多模态方法能够综合各类信息，从多个角度捕捉行为特征，尤其是在面对复杂环境、多人交互和遮挡等问题时，具有显著的优势。

2D CNN + RNN 的优点

2D CNN（卷积神经网络）与 RNN（递归神经网络）的结合是行为识别中的一种常见方法，尤其适用于视频行为识别任务。其主要优点包括：

1. 空间特征与时间依赖性的有效结合：

• 2D CNN：能够从视频帧中提取空间特征，如人物的姿态、背景和动作细节。通过多层卷积，CNN能够识别局部和全局的空间信息。
• RNN（LSTM/GRU）：RNN特别擅长处理时序数据，可以建模视频帧之间的时间依赖关系，捕捉动作的动态变化和时间长短的依赖，适应动作序列的连续性和长期依赖。
• 优点：2D CNN 提供强大的空间特征提取能力，RNN 提供强大的时间序列建模能力。将两者结合，能够更好地理解视频中的空间和时间信息，提升行为识别的准确性。

1. 自动特征学习：

• 传统方法依赖手工特征提取（如HOG、光流等），需要依赖专家知识且难以适应多样的场景。而 2D CNN 能够自动学习空间特征，减少了人工设计特征的依赖，提高了对复杂场景的适应能力。
• RNN 则可以自动从数据中学习到行为模式的时间序列特征，不需要事先设定固定的时间模型或参数。

1. 鲁棒性强，适应性好：

• 2D CNN 通过卷积层提取多层次的空间特征，具有较好的鲁棒性，能够应对不同背景和复杂场景中的视频数据。
• RNN 具有处理不规则、可变时间长度序列的能力，能够识别动态变化的动作和突发行为，提高了模型的适应性。

1. 可扩展性强：

• 2D CNN 和 RNN 的组合能够很好地扩展到不同的视频数据规模、场景和复杂度上。随着数据集的增大，模型仍然能够通过更深的网络层次和更多的时序数据进行训练，进一步提升识别效果。

答辩稿——初版

各位评委老师大家好，我是我们组的主持人张熙浚，我们组的研究方式是基于多模态特征融合的视频暴力行为识别方法研究

接下来我会从五个方面介绍我们的项目

首先是背景与意义，暴力行为对社会危害极大，即使诸如学校、商场、银行、车站等公共场所存在大量监控摄像头，产生了大量的视频片段，但这些片段通常被用来在暴力犯罪发生后提供线索和证据，而很少被用来实时识别并停止暴力行为。

这便引出了我们项目的目的，我们希望利用计算机视觉技术，赋予机器暴力行为的判别能力，从而及时发现暴力行为并能有效降低其带来的危害，而且大大降低了人力成本，在安防领域有极大的应用价值。

暴力行为的检测方法早期的检测方法主要是依靠设立一些规则，或是依靠背景和环境的变化，这些方法在很多方面存在不足，包括受环境因素影响大，特征提取和分析能力有限，计算效率低等问题

而现代的暴力行为检测越来越注重人体动作本身的识别，其通过分析人体动作的细节，尤其是肢体的动态变化，不仅可以提升检测的准确性，还能更好地从动态和连续的角度识别暴力行为，提高系统的实时性和鲁棒性。

由于监控人员不可能实时监控每一个摄像头产生的视频，所以部署视频暴力行为识别系统，能够节约用于监控的人力资源，降低监控人员因疲劳或走神而造成的漏检风险，一旦识别到暴力行为立即警示相关人员，进一步采取相应措施。由此可以得出我们项目研究的现实意义和应用场景。

接下来，我将讲述当前暴力行为检测的研究背景和挑战，并引出我们的解决方案。多种不同的数据形态都可以用来表示人类的动作和行为。主流的人体动作识别把这些模态分为2类：视觉模态和非视觉模态。这些数据模态是对不同的信息来源进行编码，根据应用场景的不同，不同模态的数据有着不同的独特优势。

目前主流的单模态深度学习方法存在以下缺点：信息单一、对环境敏感、鲁棒性较差，难以应对复杂场景等。但真实的暴力事件场景往往存在以下特点：存在复杂姿态变化，多人交互，大量环境噪声等。因此，我们提出了基于多模态的暴力事件检测，通过结合多种数据来源，从多个角度捕捉行为特征，尤其是在面对复杂环境、多人交互和遮挡等问题时，具有显著的优势。

随着深度学习和计算机视觉技术的发展，深度学习方法已经成为了行为识别算法的主流方向，接下来我会通过几篇论文中的方法介绍研究现状

这一篇是早提出使用深度学习方法解决视频暴力行为识别任务，直接将视频输入三维卷积进行建模

这一篇提出了数据集Rwf-2000，同时提出一种的双流网络架构，他们充分利用了RGB数据提供的外观信息和光流提供的运动信息，但缺点在于光流法计算、存储成本高，适用于光照条件良好、不拥挤的情况

这一篇提出了一种弱监督方法，即通过少量的标签（例如，仅标记视频是否包含暴力，而不是标记具体的暴力事件位置和类型）来训练模型。他选取视频帧最关键的区域，但使用I3D作为骨干网络，参数量巨大（1300万）

这一篇是基于骨架的方法，通过提取人体骨骼关节点构成三维骨架阵列，根据局部区域点的特征和时空位置信息，构建特定的权重分布策略，通过骨架点卷积实现分类。优点是骨架可以很好的表示人体运动信息，但问题在于仅使用骨架数据，效果高度依赖于位姿估计的精度，无法有效遮挡情况，同时因为仅使用骨架数据，其他信息缺失

这一篇是基于 2D CNN + RNN 的方法，2D CNN 提供强大的空间特征提取能力，RNN 提供强大的时间序列建模能力。将两者结合，能够更好地理解视频中的空间和时间信息，提升行为识别的准确性。这一篇使用简单快速的预处理方法突出了人体，减少了冗余的背景信息，但其仅使用RGB模态，提取的特征不够全面

我们的研究内容大致包含三个部分：1.提出一种基于多模态特征融合的视频暴力行为识别算法2.提出一种自适应的注意力算法用于多模态融合3.完成人体暴力行为检测系统的设计，接下来我将依次为大家介绍

第一部分，在特征提取阶段，为了区分暴力行为与非暴力行为，我们选择了三个要素进行提取：人体姿态、运动（趋势、幅度）、人物之间的位置关系，为了获取以上三个要素，并保证模型的通用性和现实性，需要从原始的RGB图像中提取以上特征，研究工作包括下列内容：

a.RGB模态的去除冗余信息
为了避免原生RGB图像冗余信息影响模型判断，减少计算量，我们决定对于原生RGB图像进行冗余信息去除工作，首先计算一个视频中所有帧的均值，记为平均帧（主要包含背景信息，因为背景在所有视频帧中几乎保持不变）用每一帧减去平均帧：去除（不变的）背景，保留（运动的）人体。通过简易的预处理，去除了冗余的背景信息，聚焦于人体的外观、姿态。

b.运动趋势与幅度特征的提取
目前主流反映物体运动趋势的方法是光流法，但我们考虑到光流图像在低像素复杂场景下效果不佳，且易受光照条件改变的影响，于是决定采取帧差法，通过对视频图像序列中相邻两帧作差分运算来获得运动目标轮廓的方法，以很好地适用于存在多个运动目标的情况，算法相对实现简单，程序设计复杂度低，对光线等场景变化不太敏感，能够适应各种动态环境，有着比较强的鲁棒。

c.深度模态的提取
在原始的RGB模态中，复杂场景中，人物多且受光照影响严重，难以分辨人物间的相对位置关系。为了反映人物之间的位置关系，我们选取深度模态，其去除了颜色和纹理信息并提供三维结构信息和人体轮廓，我们利用Depth estimation算法，对原始RGB视频进行深度估计，得到视点到场景中各点之间的距离作为像素点的图片，即深度图，其划分了近景与远景，刻画了人物的轮廓，反映了三维空间中人物间的相对位置关系。

我们选择了CNN-LSTM的深度学习方法。LSTM擅长处理时序数据，可以建模视频帧之间的时间依赖关系，而CNN能够从视频帧中提取空间特征。通过结合两者的优势，我们可以让模型同时考虑到数据的时序信息和空间信息，减少参数降低过拟合风险，从而提供更精确的预测、更出色的性能以及更高的训练效率，并以此构建了算法思路。

第二部分，针对多模态融合中权重数值处理的问题，我们提出了一种自适应的注意力算法用于多模态融合，让模型自适应地学习不同模态特征之间的权重关系，允许模型根据具体任务动态调整每个模态的重要性，强调信息特征，抑制不太有用的特征,从而更灵活地应对不同的场景。

第三部分，我们完成了人体暴力行为检测系统的设计，刻画了系统的边界及大小，人体暴力行为检测系统是一个自动检测暴力行为的智能视频监控系统。该系统采用了三层架构，即表示层、业务层以及数据层。 它被设计成一个Web系统，主要以网页的形式显示在PC 显示器上

我们已经初步构建了暴力行为的检测流程，系统包含离线分析和在线监测两种模式

离线分析不依赖实时的监控视频，可对任意视频进行后处理式的分析。它 的优点是它不依赖于视频监控系统，可以直接选择视频开始分析，在视频来源 和分析时机的选择上更自由。

在线监测是人体暴力行为检测系统提供的另一种检测方式。它旨在利用监 控视频资源，进行实时的暴力行为检测，达到即时分析并报警提示的功能。这 一功能极大地降低了人工分析实时监控视频的成本，便于管理人员进行安全监 管，提高了监管的效率。

为了提高检测速度和避免资源浪费，根据传入视频的总帧数进行判断，采取提示过短、一次预测或是多轮预测。

最后是进度安排，我们已经完成算法大部分的编写，后续会继续完成系统的开发

谢谢各位老师观看，请各位老师批评指正

GraphRAG

最新消息是11.26凌晨，微软宣布将推出 GraphRAG 的全新迭代版本LazyGraphRAG
核心亮点是极低的使用成本，其数据索引成本仅为现有GraphRAG 的 0.1%。此外，LazyGraphRAG 引入了全新的混合数据检索方法，大幅提升了生成结果的准确性和效率。该版本将很快开源，并纳入到 GitHub GraphRAG 库中
原文链接如下:https://www.microsoft.com/en-us/research/blog/lazygraphrag-setting-a-new-standard-for-quality-and-cost/

支持的检索方式

Naive Search
Naive 模式是最简单的检索策略，它直接基于输入查询计算向量相似度，返回最接近的结果，不进行任何额外的优化或复杂处理
Local Search
Local 模式只在本地上下文范围内进行检索。它聚焦于用户当前输入的特定领域或某部分数据，不会考虑全局数据
Global Search
Global 模式会在整个知识库范围内进行检索，试图找到与查询最相关的信息，而不局限于当前上下文或局部区域
Hybrid Search
Hybrid 模式结合了 Local 和 Global 的优势，同时考虑局部上下文和全局信息，综合结果以提高答案的相关性和覆盖范围

Anaconda

Anaconda，中文大蟒蛇，是一个开源的Anaconda是专注于数据分析的Python发行版本，包含了conda、Python等190多个科学包及其依赖项。

Anaconda就是可以便捷获取包且对包能够进行管理，包括了python和很多常见的软件库和一个包管理器conda。常见的科学计算类的库都包含在里面了，使得安装比常规python安装要容易，同时对环境可以统一管理的发行版本

为什么要安装Anaconda？

Anaconda对于python初学者而言及其友好，相比单独安装python主程序，选择Anaconda可以帮助省去很多麻烦，Anaconda里添加了许多常用的功能包，如果单独安装python，这些功能包则需要一条一条自行安装，在Anaconda中则不需要考虑这些，同时Anaconda还附带捆绑了两个非常好用的交互式代码编辑器（Spyder、Jupyter notebook）。

简单来说，Anconda，可以理解成运输车，每当下载Anconda的时候，里面不仅包含了python，还有180多个库（武器)一同被打包下载下来。

下载完Anconda之后，再也不用一个个下载那些库了。

集成开发环境搭建Anaconda+PyCharm

【大模型应用开发基础】集成开发环境搭建Anaconda+PyCharm_哔哩哔哩_bilibili

LightRAG与GraphRAG运行对比

NanGePlus/LightRAGTest: LightRAG与GraphRAG在索引构建、检索测试中的耗时、模型请求次数、Token消耗金额、检索质量等方面进行对比

命令行终端中执行如下命令安装依赖包
cd LightRAG
pip install -e .
cd GraphRAG
pip install graphrag==0.5.0

测试文本 测试文本均为使用西游记白话文前九回内容，文件名为book.txt
模型配置 大模型使用OpenAI(代理方案)，Chat模型均使用gpt-4o-mini,Embedding模型均使用text-embedding-3-small
其他配置 笔记本均为MacBook Pro2017,网速、python环境均相同

LightRAG测试

(1)构建索引

打开命令行终端，执行如下指令
cd LightRAG/nangeAGICode
python test.py
注意 在运行脚本之前，需要调整相关代码将如下代码块打开，检索相关的代码块注释

(2)逐一测试

执行如下指令
cd LightRAG/nangeAGICode
python test.py
注意 在运行脚本之前，需要注释如下构建索引代码，取消检索相关的代码块注释

GraphRAG测试

(1)构建索引

打开命令行终端，执行如下指令
cd GraphRAG
graphrag index —root ./

(2)逐一测试

graphrag query —root ./ —method local —query “这个故事的核心主题是什么?”
graphrag query —root ./ —method global —query “这个故事的核心主题是什么?”
graphrag query —root ./ —method drift —query “这个故事的核心主题是什么?”

利用neo4j可视化

测试文本 测试文本均为使用西游记白话文前九回内容
模型配置 大模型均使用OpenAI(代理方案)，Chat模型均使用gpt-4o,Embedding模型均使用text-embedding-3-small
其他配置 笔记本均为MacBook Pro2017,网速、python环境均相同

1
2
3
4
5

# gpt大模型相关配置根据自己的实际情况进行调整
OPENAI_API_BASE = "https://api.wlai.vip/v1"
OPENAI_CHAT_API_KEY = "sk-Tuza9B8WYo1vkBAAmmLeQjuOl1VTP9Dd0nuKxqnLOaJJMZZd"
OPENAI_CHAT_MODEL = "gpt-4o"
OPENAI_EMBEDDING_MODEL = "text-embedding-3-small"

LightRAG构建索引测试

(1)安装textract依赖包

通过指令 pip install textract 安装时会报错，报错的原因是
其元数据文件中使用了不再被支持的版本约束符号（<=0.29.*），而当前 pip 和 setuptools 不再接受这种格式
解决方案:下载依赖包源码，修改相应参数后本地进行安装
https://pypi.org/project/textract/1.6.5/#description
cd textract-1.6.5
pip install .

(2) 创建neo4j数据库实例

推荐使用云服务进行测试，链接地址如下:
https://console-preview.neo4j.io/tools/query
注册登录成功，直接新建实例即可

也可以用本地neo4j

1
2
3
4
5

# 数据库连接相关参数配置
NEO4J_URI="bolt://localhost:7687"
NEO4J_USERNAME="neo4j"
NEO4J_PASSWORD="zxj03051218"
NEO4J_DATABASE="neo4j"

(3)增量索引构建及知识图谱可视化测试

运行如下指令进行索引构建
cd LightRAG/nangeAGICode1201
python insertTest.py
python queryTest.py
每一次构建完成，先清除数据库中的数据再运行如下指令进行可视化
在运行之前需要根据自己的实际情况进行参数的调整
python graph_visual_with_html.py

python graph_visual_with_neo4j.py
在数据库中进行查询测试
MATCH (n:PERSON)
WHERE n.displayName CONTAINS ‘唐僧’
RETURN n LIMIT 25;

MATCH (n:PERSON)
WHERE n.displayName CONTAINS ‘八戒’
RETURN n LIMIT 25;

MATCH (n:PERSON)
WHERE n.displayName CONTAINS ‘沙和尚’
RETURN n LIMIT 25;

清除数据
MATCH (n)
CALL { WITH n DETACH DELETE n } IN TRANSACTIONS OF 25000 ROWS;

MATCH (n)
OPTIONAL MATCH (n)-[r]-()
DELETE n,r

LightRAG和GraphRAG生成的知识图谱对比

运行如下指令将GraphRAG生成的知识图谱进行可视化展示
cd GraphRAG/utils
python graphvisualwith_neo4j.py
在运行脚本前根据自己的实际情况进行调整,修改文件所在路径为存储增量数据的文件路径
GRAPHRAG_FOLDER=”/Users/janetjiang/Desktop/agi_code/LightRAGTest/GraphRAG/output”
在数据库中进行查询测试
MATCH (n:`__Entity`)
WHERE n.name CONTAINS ‘唐僧’
RETURN n LIMIT 25;

MATCH (n:__Entity__)
WHERE n.name CONTAINS ‘八戒’
RETURN n LIMIT 25;

MATCH (n:__Entity__)
WHERE n.name CONTAINS ‘沙和尚’
RETURN n LIMIT 25;

清除数据
MATCH (n)
CALL { WITH n DETACH DELETE n } IN TRANSACTIONS OF 25000 ROWS;

参考文献

LightRAG与GraphRAG对比评测，从索引构建、本地检索、全局检索、混合检索等维度对请求大模型次数、Token消耗、金额消耗、检索质量等方面进行全面对比_哔哩哔哩_bilibili

还是搞不懂Anaconda是什么?读这一篇文章就够了-CSDN博客

了解Langchain

LangChain是一个强大的框架，旨在帮助开发人员使用语言模型构建端到端的应用程序。它提供了一套工具、组件和接口，可简化创建由大型语言模型 (LLM) 和聊天模型提供支持的应用程序的过程。LangChain 可以轻松管理与语言模型的交互，将多个组件链接在一起，并集成额外的资源，例如 API 和数据库。

一句话概括就是：langchain 完成了对数据一个提炼、查找的完全链路。它并不能提供数据源、查找理由，只是一种方法的凝练。

数据源支持由用户等自行提供，因此它支持本地知识库的搭建，合理想象未来的学生课设系统将会是：金融知识系统（使用 langchain 爬取金融网站提取摘要凝练成知识）、图书简介系统（使用 langchain 对图书提取摘要进行展示）……

安装

Jupyter 就是一个非常好用的 Python 语言编程工具。

或者说是一个 Python 编程语言、以及更多其他编程语言的，交互式集成开发环境。

Jupyter 的一个非常重要的优点，就是 写程序的界面，和运行程序的界面，在一起。

jubyter notebook的安装：pip install jupyterlab

web页面的启动：jupyter-lab

vscode：创建.ipynb格式的文件

langchain的安装：pip install langchain

提供一种LLM集成解决方案，一份代码支持快速同时支持gpt大模型、国产大模型(通义千问、文心一言、百度千帆、讯飞星火等)、本地开源大模型(Ollama)

项目地址：NanGePlus/LLMTest: 为实现代码的高扩展性和兼容性，提出一套综合解决方案，支持多种大模型类型的无缝集成，包括GPT系列大模型、国内主流模型（如通义千问、智谱AI等），以及本地化部署的大模型（如qwen2.5）。

前期准备

openai-api代理：云雾 API

安装One-Api

songquanpeng/one-api: OpenAI 接口管理 & 分发系统，支持 Azure、Anthropic Claude、Google PaLM 2 & Gemini、智谱 ChatGLM、百度文心一言、讯飞星火认知、阿里通义千问、360 智脑以及腾讯混元，可用于二次分发管理 key，仅单可执行文件，已打包好 Docker 镜像，一键部署，开箱即用. OpenAI key management & redistribution system, using a single API for all LLMs, and features an English UI.

利用exe

One API

默认账号密码：root 12345

创建渠道，这里以阿里通义千问为例

获取API-KEY：阿里云百炼

2024年最新免费AI大模型API汇总及国内大模型使用教程（附代码）_免费大模型api-CSDN博客

使用 Ollama 非常简单，只需要按照以下步骤：

1. 安装 Ollama ： 根据你的操作系统，从 Ollama 官网 下载并安装最新版本。
2. 启动 Ollama ： 打开终端或命令行，输入 ollama serve 命令启动 Ollama 服务器。
3. 下载模型： 在模型仓库 找到想要的模型，然后使用 ollama pull 命令下载，例如 ollama pull llama3:70b 。
4. 运行模型 ： 使用 ollama run 命令启动模型，例如 ollama run llama3:70b 。
5. 开始聊天 ： 在终端中输入你的问题或指令，Ollama 会根据模型生成相应的回复。
6. 查看模型列表 ：ollama list

项目

初始化：采用pycharm+anaconda

安装依赖

pip install -r requirements.txt
每个软件包后面都指定了本次视频测试中固定的版本号
注意： 截止2024.10.18，langchain最新版本为0.3.3，langchain-openai最新版本为0.2.2

调整api，调整 utils/myLLM.py 内容

调整 llmTest.py 内容

LLM_TYPE = “oneapi” # openai：调用gpt模型;oneapi：调用oneapi方案支持的模型（这里调用通义千问）

参考文献

langchain-ai/langchain：🦜🔗构建上下文感知推理应用程序

LangChain 入门与避坑指北 - 知乎

LangChain中文网

Jupyter 是什么-CSDN博客

在 Visual Studio Code 中使用 Jupyter Notebook_Vscode中文网

Ollama：从入门到进阶

什么是 Neo4j？

Neo4j 是一个开源的图形数据库，由 Neo4j 公司开发和维护。作为图数据库的代表，Neo4j 使用图理论中的节点和边（关系）来表示和存储数据，相较于传统的关系型数据库（如 MySQL、PostgreSQL）和其他 NoSQL 数据库（如文档型、键值型数据库），Neo4j 在处理复杂关系和连接性强的数据方面具有显著优势。

主要特点：

• 图模型：使用节点、关系和属性来建模数据，直观地反映实体及其之间的关联。
• Cypher 查询语言：专为图数据库设计的声明式查询语言，语法简洁，易于表达复杂的图形查询。
• 高性能：优化的存储和索引机制，能够高效地处理大规模图数据和复杂查询。
• ACID 事务支持：保证数据的一致性和可靠性，适用于需要强事务保障的应用场景。

为什么需要 Neo4j？

在许多应用场景中，数据之间存在复杂的关系和连接性。传统的关系型数据库在处理多层级的关联查询时，往往需要大量的联接操作（JOIN），这会导致查询性能下降，尤其是在数据规模庞大时。而 Neo4j 通过图模型天然适合表示和处理这种高度连接的数据，能够更高效地执行复杂的关系查询。

主要需求原因：

1. 复杂关系处理：需要频繁进行多级关联查询，如社交网络、推荐系统等。
2. 灵活的数据模型：数据结构可能随时间变化，图数据库提供了更大的灵活性。
3. 性能需求：需要在大规模数据集上执行快速的关系查询和遍历操作。
4. 实时性：需要实时分析和处理数据关系，如欺诈检测、网络安全等。

GraphRAG的理解

GraphRAG=Graph(知识图谱)+RAG技术

GraphRAG 是一种结合了图结构和检索增强生成（RAG）的方法，旨在增强语言模型（如大规模预训练的变换器模型）的推理能力和信息检索能力。这个方法通常用于处理复杂的推理任务，尤其是当涉及到大规模知识库或图形数据时，GraphRAG可以通过图的结构来有效地组织信息，从而提高模型在生成和推理时的效率和准确性。

图结构（Graph）：

• 图通常用于表示节点之间的关系和依赖，在处理复杂知识结构时非常有用。在GraphRAG中，图结构帮助捕捉信息之间的关系，能够有效地组织和链接不同的知识点，尤其是在涉及多个实体和关系的任务中。

检索增强生成（RAG）：

• RAG 是一种将信息检索与生成模型结合的框架。它的核心思想是，模型在生成答案时不仅仅依赖于其预训练时获得的知识，还会从一个外部数据库或文档库中检索相关的信息来增强回答的准确性和上下文适应性。

Neo4j的安装

1. 官网下载社区版
2. 安装JDK，java11
3. 配置环境变量
4. 启动Neo4j

1 2 3 4 5 6 7 8 9

常用命令 # 启动服务 neo4j(.bat) start # 重启服务 neo4j(.bat) restart # 停止服务 neo4j(.bat) stop # 控制台模式启动 neo4j(.bat) console

1. 进入到 http://localhost:7474

账号密码 neo4j zxj03051218

第一次进入前安装neo4j 的服务

1

neo4j install-service

查看版本 neo4j —version

apoc用处

数据导入和导出：使用APOC插件可以轻松导入和导出不同格式的数据到Neo4j图数据库。您可以将数据从关系型数据库、CSV文件、JSON等转换为图形数据，并相反地，将图形数据导出到其他格式。
图形算法：APOC提供了许多有用的图形算法，如PageRank、社区发现（例如Louvain算法），路径分析等。这些算法可以帮助您发现数据之间的关联性和模式，并从中提取有价值的信息。
数据清洗和转换：APOC提供了丰富的过程和函数，用于数据清洗和转换。您可以使用它来处理字符串、时间、密码学等方面的数据，并进行必要的清洗和格式化。
可视化：APOC支持将图形数据转换为其他可视化工具所需的格式，例如Gephi、D3.js等。这使得您可以将您的图形数据以更直观的方式呈现，进一步探索和交流。
地理空间分析：APOC提供了与地理空间数据相关的功能，如计算两个地点之间的距离、查找附近的地点等。这对于在地理空间上分析和查询数据特别有用。

我应该是主要用到了数据导入和导出的功能，因为要将构建好的所以传到本地neo4j上

apoc插件安装

知识图谱基本工具Neo4j使用笔记 五 ：APOC插件安装及简单应用_neo4j apoc-CSDN博客

版本 neo4j 4.4.39

APOC插件下载：apoc-4.4.0.9-all.jar（注意apoc要与neo4j版本对应）

Releases · neo4j/apoc

将下载的 apoc-4.4.0.9-all.jar 直接复制到neo4j/plugins文件夹

修改APOC的配置文件

打开配置文件将，这一下内容的注释去掉

1

dbms.security.procedures.unrestricted=apoc.*

参考文献

java - 我的Neo4j探索之旅 - 初识Neo4j（一） - 个人文章 - SegmentFault 思否

《老匠新传》

背景剧情：

在安徽省一个偏远小山村里，住着一位年迈的老匠人程老。他是村里最后一位木雕匠，祖传的技艺如今面临失传的窘境。一天，城市的女孩小林，来到了这个小山村。她被精致的雕刻作品和老人的精湛技艺所吸引，留下来悉心学习这传统技艺。

多年后，女孩学成回到城市。她呼吸着浮躁的空气，下定决心在城市的一隅开设了一家雕刻工作室。门口摆放着一只木雕鸟，和曾经吸引她踏入木雕门扉的那只一般，精致而美丽。但是简约的线条又让它显得轻盈而现代。

“那是一块文化的拼图，串起了过去岁月的技艺，和当代创新的潮流。”

创作理念：

我们的故事从安徽省一个偏远小山村的年迈木雕匠人程老为起点，通过他与来自城市的女孩小林之间的师徒传承，展现传统技艺在现代社会中的困境与重生。

文化传承：我们希望强调了传统技艺的文化价值，如木雕这一几代人相传的技艺，不仅是技艺本身，更是一种文化的延续。程老作为村里最后一位木雕匠，他的技艺和作品承载着丰富的历史和文化信息。

师徒传承：通过小林对程老技艺的学习和传承，我们希望展现师徒之间深厚的情感纽带和技艺的传递。这种传承不仅是对技艺的保存，更是对文化精神的延续。

创新融合：小林学成后，在城市开设雕刻工作室，将传统技艺与现代审美相结合，创作出既具有传统韵味又符合现代审美的作品。其中表达着对传统文化的创新和发展，以及传统技艺在现代社会中焕发出新的生命力。

文化自信：故事中的小林在回到城市后，能够自信地展示和推销自己的作品，体现了对传统文化的自信和自豪感。

艺术表达：

我们采用现代的技术载体讲述传统技艺的传承和新生，希望增添作品的现实意义。

细节描写：故事中对木雕作品的细节描写，如“精致的雕刻作品”和“一只木雕鸟”，不仅展现了程老技艺的精湛，也通过小林对这些作品的喜爱和学习，传递了她对传统文化的热爱和尊重。

情感渲染：通过小林与程老之间的互动，以及小林学成后回到城市的心理变化，渲染师徒之间的深厚情感和传统文化的厚重感。

象征手法：木雕鸟作为故事中的象征物，既代表了程老的技艺传承，也象征着传统技艺在现代社会中的重生和创新。它的“精致而美丽”和“简约的线条”既体现了传统技艺的精髓，又融入了现代审美元素。

语言风格：故事中的语言风格简洁明了，富有诗意。

使用技术：

图像生成：首先训练GPT-4成为Midjourney提示词生成器。然后通过文字描述剧本中的场景，获取提示词。最后使用Midjourney生成场景图片，进行筛选。

视频生成：我们利用可灵AI进行视频的制作，我们使用生成的图片生成初版视频，然后通过提示词进行多次约束，修改，最后剪辑合并。

图的基本概念和术语

定义：一个图可以利用两个集合进行定义。第一个集合是点的集合,这些点在图术语中一般被称(Vertex);第二个集合是连接两个顶点的边(Edge)的集合。图的具体定义如下。 图是由顶点集合及顶点间的关系集合组成的一种数据结构:Graph = (V, E)

基本术语

1. 有向图

2. 无向图

3. 邻接点

4. 顶点的度，入度与出度

5. 权和网：

   • 权 ： 某些图的每条边都可能赋予一个数值，这个数值称为权。
   • 网 ： 带有权的图称为网。

6. 无向完全图： 任意两个顶点之间都有一条边的无向图。

   有向完全图： 任意两个顶点之间都有方向相反的两条边的有向图。

1. 路径与路径长度

2. 简单路径：若路径上经过的各顶点均不重复，则称这样的路径为简单路径。

   回路或环：若路径上的第一个顶点与最后一个顶点相同，则称这样的路径为回路或环。

1. 连通图： 在无向图中，若任意两个顶点之间都存在路径，则称该图为连通图。

   连通分量： 非连通图的极大连通子图称为连通分量。也就是说，一个连通分量是一个连通的子图，且不能再扩大。

2. 强连通图： 在有向图中，若对于任意一对顶点 u 和 v，都存在一条从 u 到 v 和从 v 到 u 的路径，则称该图为强连通图。

   强连通分量： 非强连通图的极大强连通子图称为强连通分量。

3. 生成树： 一个连通图的生成树是包含图中所有顶点的极小连通子图。也就是说，生成树是一棵树，且包含图中的所有顶点。

   生成森林： 非连通图的每个连通分量分别可以得到一棵生成树，这些生成树的集合称为生成森林。

图的储存结构

邻接矩阵

邻接矩阵表示法的基本思想是引入两个数组：

• 一个用于记录图中各个顶点信息的—维数组，称为顶点表；
• 另一个用于表示图中各个顶点之间关系的二维数组，称为邻接矩阵。

设图G=(V, E)是具有n(n>0)个顶点的图，则图G所对应的邻接矩阵A是一个n阶方阵

无向图的邻接矩阵可采用只存储上三角阵或下三角阵的压缩存储方法

对于带权图，需要对邻接矩阵的元素值定义进行修改，让元素值表示相应顶点的权值

其中，∞可用计算机中的一个足够大的数代替，以与权重区分

算法

图类MGraph的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 图的类型定义: 无向图、无向网、有向图、有向网
enum GraphType { undigraph, digraph, undinetwork, dinetwork };

template <class T>
struct EdgeType { // 本类型定义也适用于后面的邻接表结构
    T head, tail;
    int cost;
    EdgeType(T h, T t, int c) {
        head = h;
        tail = t;
        cost = c;
    }
};

template <class T>
class MGraph {
private:
    int vexnum, edgenum;
    GraphType kind;
    vector<vector<int>> edges; // 邻接矩阵
    vector<T> vexs;            // 顶点表
};

无向有权图的邻接矩阵构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void createAdjMatrix(vector<vector<int>>& adjMatrix, const vector<tuple<int, int, int>>& edges, int numVertices) {
    // 初始化邻接矩阵为无穷大
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (i != j) adjMatrix[i][j] = INT_MAX; // 没有边的地方设置为无穷大，当i=j的值为0
        }
    }

    // 填充边的信息
    for (const auto& edge : edges) {
        int u = get<0>(edge);  // 获取第一个元素
        int v = get<1>(edge);  // 获取第二个元素
        int weight = get<2>(edge);  // 获取第三个元素
        adjMatrix[u][v] = weight;
        adjMatrix[v][u] = weight;  // 无向图
    }
}

邻接表

当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，如下图所示：

邻接表中存在两种结点:顶点表结点和边表结点，如下图所示。

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成，边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc) 构成。

算法

基于邻接表存储表示的图类ALGraph定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 边节点
struct EdgeNode {
    int adjvex;  // 邻接点下标
    EdgeNode* next; // 指向下一个邻接点
};

// 顶点节点
template <class T>
struct VexNode {
    T data;
    EdgeNode* firstEdge;
};

// 图的邻接表表示
template <class T>
class ALGraph {
    vector<VexNode<T>> vex;  // 顶点数组
    int vexnum, edgenum;  // 顶点数和边数
	GraphType kind;
};

无向图的构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

template <class T>
ALGraph<T>::ALGraph(GraphType t, T vexs[], int n, int e) {
    // 参数表示图的类型, 参数vexs为存储各顶点值的数组, 参数n和e分别为顶点数和边数
    vexnum = n;
    edgenum = e;
    kind = t;
    adjlist.resize(vexnum);

    // 初始化顶点表
    for (int i = 0; i < vexnum; ++i) {
        adjlist[i].data = vexs[i];
        adjlist[i].firstEdge = 0;
    }

    // 依次输入所有的边的信息
    for (int j = 0; j < edgenum; j++) {
        int va, vb;
        cin >> va >> vb;

        // 产生第一个表结点
        EdgeNode* p = new EdgeNode;
        p->adjvex = vb;
        p->nextedge = adjlist[va].firstEdge;
        adjlist[va].firstEdge = p;

        // 产生第二个表结点
        p = new EdgeNode;
        p->adjvex = va;
        p->nextedge = adjlist[vb].firstEdge;
        adjlist[vb].firstEdge = p;
    }
}

图的遍历

为了防止已经访问过的结点重复访问的问题，提出了辅助数组 visited[]

深度优先遍历

深度优先搜索类似于树的先序遍历。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

bool visited[MAX_VERTEX_NUM];	//访问标记数组
/*从顶点出发，深度优先遍历图G*/
void DFS(Graph G, int v){
	int w;
	visit(v);	//访问顶点
	visited[v] = TRUE;	//设已访问标记
	//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
	//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
	for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
		if(!visited[w]){	//w为u的尚未访问的邻接顶点
			DFS(G, w);
		}
	}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
	int v; 
	for(v=0; v<G.vexnum; ++v){
		visited[v] = FALSE;	//初始化已访问标记数据
	}
	for(v=0; v<G.vexnum; ++v){	//从v=0开始遍历
		if(!visited[v]){
			DFS(G, v);
		}
	}
}

DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为O(V)。

对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要O(V^2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(V＋E)。

广度优先遍历

图的广度优先遍历就类似于树的层序遍历

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G){
	int i, j;
	Queue Q;
	for(i = 0; i<G,numVertexes; i++){
		visited[i] = FALSE;
	}
	InitQueue(&Q);	//初始化一辅助用的队列
	for(i=0; i<G.numVertexes; i++){
		//若是未访问过就处理
		if(!visited[i]){
			vivited[i] = TRUE;	//设置当前访问过
			visit(i);	//访问顶点
			EnQueue(&Q, i);	//将此顶点入队列
			//若当前队列不为空
			while(!QueueEmpty(Q)){
				DeQueue(&Q, &i);	//顶点i出队列
				//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
				//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
				for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
					//检验i的所有邻接点
					if(!visited[j]){
						visit(j);	//访问顶点j
						visited[j] = TRUE;	//访问标记
						EnQueue(Q, j);	//顶点j入队列
					}
				}
			}
		}
	}
}

无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q, n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(V)。
采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)，在搜索任一顶点的邻接点时，每条边至少访问一次，算法总的时间复杂度为O(V＋E)。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(V)，故算法总的时间复杂度为O(V^2)。

注意:图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

应用

简单路径的搜索算法 dfs

二部图的判定算法

最小生成树

生成树变成非连通图;若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图G=(V,E)，生成树不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树)，称为G的最小生成树(Minimum-Spanning-Tree,MST)。

普里姆（Prim）算法

从一个顶点出发，在保证不形成回路的前提下，每找到并添加一条最短的边，就把当前形成的连通分量当做一个整体或者一个点看待，然后重复“找最短的边并添加”的操作。

引入辅助数组miniedges[]，用于存放每个节点到节点v的边的权值，并每次挑选出权值最小的那个边所对应的节点加入生成树，辅助数组miniedges[]的数据类型如下

1
2
3
4

struct Edge {
    int adjvex;  // 与当前生成树连接的节点的编号
    int lowcost; // 到当前生成树的最小边权值
};

若将某个数组元素miniedges[i]的 lowcost成员值设为0，则表示相应的顶点v,已加入到最小生成树中。

为便于算法在执行过程中读取任意两个顶点之间边的权值，对图宜采用邻接矩阵存储结构。

算法思路：

1. 初始化辅助数组，从节点v开始，将v的lowcost设为0，说明已经加入生成树

2. 循环vexnum-1次，利用函数MiniNum找到权值最小的节点并输出

   函数MiniNum循环vexnum次，找到当前所有节点中，未加入生成树的，lowcost最小的节点

3. 更新辅助数组miniedges[]的每个节点的lowcost：循环vexnum次，如果通过当前节点k能找到比原先更小的边，更新该节点的lowcost；如果大，则保留原lowcost的值，更新后代表生成树节点的集合到未加入节点的集合的权值最小的vexnum条边

时间复杂度：O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

void Prim(const vector<vector<int>>& graph, int v, int vexnum) {
    // 初始化 miniedges 数组
    Edge* miniedges = new Edge[vexnum];
    
    // 初始化 miniedges，每个节点到起始点v的边的权值
    for (int i = 0; i < vexnum; i++) {
        miniedges[i].adjvex = GetVexValue(v);        // 初始时节点的连接为起始节点v
        miniedges[i].lowcost = GetEdgeValue(graph, v, i);   // 初始化每个节点到v的边权值
    }

    miniedges[v].lowcost = 0; // 将起始节点v的lowcost设为0，表示已经加入生成树

    // 循环执行，每次选取一个未加入生成树的权值最小的节点
    for (int i = 1; i < vexnum; i++) {
        // 找到最小的lowcost
        int k = MiniNum(miniedges, vexnum);
        
        // 输出当前加入生成树的边
        cout << miniedges[k].adjvex << " --> " << GetVexValue(k) << endl;
        
        // 将选中的节点k加入生成树
        miniedges[k].lowcost = 0; // 表示节点k已加入生成树

        // 更新与当前生成树连接的节点的lowcost（最小边权值）
        for (int j = 0; j < vexnum; j++) {
            // 如果通过当前节点k能找到比原先更小的边，更新该节点的lowcost
            if (GetEdgeValue(graph, k, j) < miniedges[j].lowcost) {
                miniedges[j].adjvex = GetVexValue(k);   // 记录当前节点k
                miniedges[j].lowcost = GetEdgeValue(graph, k, j); // 更新到生成树的最小边权值
            }
        }
    }

    // 释放动态分配的内存
    delete[] miniedges;
}

函数MiniNum用于在数组miniedges中查找集合V-U中的具有最小权值的顶点,可以将它定义为私有成员函数

1
2
3
4
5
6
7
8
9
10
11
12

// 找到当前所有节点中，未加入生成树的，lowcost最小的节点
int MiniNum(Edge miniedges[], int vexnum) {
    int min = INT_MAX;
    int k = -1;
    for (int i = 0; i < vexnum; i++) {
        if (miniedges[i].lowcost != 0 && miniedges[i].lowcost < min) { // 如果该节点未加入生成树
            min = miniedges[i].lowcost;
            k = i;
        }
    }
    return k; // 返回最小权值的节点
}

克鲁斯卡尔（Kruskal）算法

与Prim算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

每次挑选为加入生成树的最小边，若不构成回路，则加入生成树，若构成则挑选下一个

为提高算法执行过程中查找最小权值边的速度，可以采用一种排序算法(如堆排序算法)对边集数组中的边按权值进行排序。

接下来，Kruskal算法的关键问题就是如何判断所选取的边加入T中是否会产生回路，这里通过引入称为并查集的数据结构来解决

在下面描述的Kruskal 算法实现中，首先利用私有成员 GetGraph()函数将图的边按权值排好序后存入边集数组graph中，而边集数组tree则用于保存和返回算法所构造的最小生成树T。

算法思路：

1. 初始话数组graph，用于存放所有的边，并对其排序
2. 并查集的使用利用数组components，先进行初始化，每个节点的祖先都是自己，也可以理解成每个节点都构成一个集合，后续并查集的过程即为集合合并的过程
3. 循环直到找到最小生成树的所有边（vexnum - 1条），对于每条边，查找他的起点和终点节点的祖先，若是一个祖先则说明在同一集合，不能加入到生成树；若不是一个，则可以加入到生成树数组tree，并要修改节点的祖先，使他们集合合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

template <class T>
void MGraph<T>::Kruskal(vector<EdgeType> &tree) {
    // 创建一个图的边集合，用于存放所有的边
    vector<EdgeType> graph;
    // GetGraph函数将图的所有边按权值从小到大存放到graph数组中
    GetGraph(graph);

    // 初始化最小生成树数组，并且初始化并查集组件
    tree.resize(vexnum - 1);  // 最小生成树包含的边数量是vexnum - 1
    int *components = new int[vexnum];  // 记录每个节点所属的集合
    // 初始时，每个节点都属于自己的集合
    for (int i = 0; i < vexnum; i++) {
        components[i] = i;
    }

    int k = 0, j = 0;
    // 循环直到找到最小生成树的所有边（vexnum - 1条）
    while (k < vexnum - 1) {
        // 从排序好的边中选择一条边
        int h1 = graph[j].head;  // 边的起点
        int t1 = graph[j].tail;  // 边的终点
        int h2 = components[h1];  // 获取起点所在的集合
        int t2 = components[t1];  // 获取终点所在的集合

        // 如果起点和终点属于不同的集合，则这条边可以加入最小生成树
        if (h2 != t2) {
            // 将这条边加入最小生成树中
            tree[k].head = h1;
            tree[k].tail = t1;
            tree[k].cost = graph[j].cost;  // 边的权值
            k++;  // 记录已选择的边的数量

            // 合并两个集合，统一编号
            // 将所有属于终点集合t2的顶点，集合编号更新为起点集合h2的编号
            for (int i = 0; i < vexnum; i++) {
                if (components[i] == t2) {
                    components[i] = h2;  // 更新组件编号
                }
            }
        }
        j++;  // 继续检查下一条边
    }

    // 释放动态分配的内存
    delete[] components;
}

显然，Kruskal算法的效率与所选择的排序算法的效率以及并查集数据结构的实现效率有关。若采用第10章介绍的比较高效的堆排序算法排序，并查集采用树结构实现，则Kruskal算法的时间复杂度可达到O($\ elog_{2}{e}$)。相比 Prim 算法而言，Kruskal算法更适用于求解稀疏网(指边数较少的网)的最小生成树。

最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

求图的最短路径问题通常可分为两类。一类是求图中某顶点到其余各顶点的最短路径问题，也称为单源最短路径问题;另一类是求图中每对顶点之间的最短路径问题。

迪杰斯特拉( Dijkstra )算法

Dijkstra算法用于构建单源点的最短路径—，即图中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值。

通俗点说，迪杰斯特拉(Dijkstra)算法，它并不是一下子求出了$\ v_i$到$\ v_j$的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

下面介绍 Dijkstra算法的具体实现。为便于在算法执行过程中快速地求得任意两个顶点之间边的权值，图的存储结构宜采用邻接矩阵方式。

为标识图中各顶点在算法执行过程中是否已求出最短路径，设置一个一维数组s[]

为记录 Dijkstra算法所求出的从源点到各顶点的最短路径，引入数组 path[], path[i]中保存了从源点到终点v,的最短路径上该顶点的前驱顶点的序号。算法结束时，可根据数组path[ ]找到源点到v,的最短路径上每个顶点的前驱顶点，并一直回溯至源点，从而推出从源点到v的最短路径。

为便于每次从V-S中选择当前离源点距离最短的顶点，需要引人一个辅助数组dist[]。它的每一个分量dist[i]表示当前所确定的从源点$\ v0$,到终点$\ v{i}$的最短路径.

算法思路：

1. 初始化，s[]所有值为0，s[0]设置为1，代表从$\ v{0}$节点开始，path[]所有值设为0，path[0]设为-1，dist[]通过查找邻接矩阵，得到$\ v{0}$到各个顶点的值
2. 查找dist中最小的值，从该节点继续完成最小路径，将该节点对应s[]设为1
3. 遍历尚未找到最短路径的节点，即s[]为0，dist[i] = Min{dist[i]，dist[j] +cost(j,i)}，选择是借用上一个最短路径的节点到达还是直接到达，更新dist的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// Dijkstra算法：计算从起点start到其他所有节点的最短路径
void dijkstra(int start, int dist[], int path[]) {
    int n = numVertices;  // 获取图中节点的数量
    bool visited[n];  // 访问标记数组，用于标记节点是否已经被访问

    // 初始化dist数组和path数组
    // dist[i] 表示从起点到节点i的最短距离
    // path[i] 表示从起点到节点i的最短路径的前驱节点
    for (int i = 0; i < n; ++i) {
        visited[i] = false;  // 初始时，所有节点均未被访问
        dist[i] = adjMatrix[start][i];  // dist数组初始化为起点到各节点的初始距离
        if (dist[i] != INT_MAX || i == start) {  // 如果有边（距离不为无穷大），或者是起点本身
            path[i] = start;  // 将路径的前驱节点设置为起点
        } else {
            path[i] = -1;  // 如果节点无法从起点到达，前驱节点为-1
        }
    }

    dist[start] = 0;  // 起点到起点的距离为0
    visited[start] = true;  // 标记起点为已访问

    // 进行n-1轮循环，逐步更新最短路径
    for (int count = 0; count < n - 1; ++count) {
        int min = INT_MAX, min_index;

        // 找到未访问的节点中距离最小的节点
        for (int v = 0; v < n; ++v) {
            // 选择距离最小且未被访问的节点
            if (visited[v] == false && dist[v] <= min) {
                min = dist[v];  // 更新最小距离
                min_index = v;  // 记录最小距离节点的索引
            }
        }

        visited[min_index] = true;  // 标记该节点为已访问

        // 更新与该最小距离节点相邻的节点的距离
        for (int v = 0; v < n; ++v) {
            // 如果v节点未被访问，并且从min_index到v有边，且经过min_index节点的路径更短
            if (!visited[v] &&  
                dist[v] > dist[min_index] + adjMatrix[min_index][v]) {
                dist[v] = dist[min_index] + adjMatrix[min_index][v];  // 更新v的最短距离
                path[v] = min_index;  // 更新v的前驱节点
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 打印从源节点到目标节点v的路径
void PrintPath(const vector<vector<int>>& g, vector<int> path, vector<int> dist, int v) {
    if (dist[v] == INF) {
        cout << "节点 " << v << " 无法到达" << endl;
        return;
    }

    // 递归打印路径
    if (path[v] != -1) {
        PrintPath(g, path, dist, path[v]);
    }

    cout << v << " ";
}

时间复杂度O(n^2)

弗洛伊德( Floyd )算法

算法原理：递归

n阶数组D：用于保留每一步所求得的所有顶点对之间的当前最短路径长度

初始化：$\ D[i][j]=cost(i,j)$用邻接矩阵进行初始化

状态转移方程：$\ D^{k}[i][j]=min{D^{k-1}[i][j],D^{k-1}[i][k]+D^{k-1}[k][j]}$更新$v_i$到$v_j$的最短路径

path数组：用于存储最短路径，初始化若没有直接路径则$\ path[i][j]=-1$，若有则$\ path[i][j] = j$

算法思路：

初始化数组，遍历n*n次，即$v_i$到$v_j$和$v_j$到$v_i$都遍历一遍，通过状态转移方程更新D数组的值，若找到短的路径，则同时也更新path数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// Floyd算法
template <class T>
void MGraph<T>::Floyd(int path[][MAXV], int D[][MAXV]) {
    // 初始化距离矩阵D和路径矩阵path
    for (int i = 0; i < vexnum; ++i) {
        for (int j = 0; j < vexnum; ++j) {
            D[i][j] = edges[i][j];
            //初始化path
            if (D[i][j] < INF && i != j)
                path[i][j] = j;  // 若i到j有直接路径，记录路径
            else
                path[i][j] = -1; // 否则路径不存在
        }
    }

    // 核心Floyd-Warshall算法
    for (int k = 0; k < vexnum; ++k) {
        for (int i = 0; i < vexnum; ++i) {
            for (int j = 0; j < vexnum; ++j) {
                if (D[i][k] != INF && D[k][j] != INF && D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];  // 更新最短路径长度
                    path[i][j] = path[i][k];      // 更新路径
                }
            }
        }
    }
}

函数OutputPath用于输出保存于二维数组path中的所有路径以及保存于二维数组D中的路径长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

template <class T>
void OutputPath(MGraph<T> &G, int path[][MAXV], int D[][MAXV]) {
    // 遍历所有顶点对，输出源点到目标点的最短路径及路径长度
    for (int i = 0; i < G.vexnum; ++i) {      // 遍历所有源点 i
        for (int j = 0; j < G.vexnum; ++j) {  // 遍历所有目标点 j
            if (i != j) { // 排除自身到自身的情况
                if (D[i][j] == INF) {  // 若距离为无穷大，表示无路径
                    std::cout << "Path from " << i << " to " << j << ": No path exists.\n";
                } else {  // 若存在路径
                    std::cout << "Path from " << i << " to " << j << " (Length: " << D[i][j] << "): ";
                    
                    // 输出路径，使用 path 数组逐步跟踪中间节点
                    int temp = i;      // 起始点
                    std::cout << temp; // 输出源点
                    while (temp != j) { // 当未到达目标点时
                        temp = path[temp][j];  // 获取路径中的下一个节点
                        std::cout << " -> " << temp; // 输出中间节点或目标点
                    }
                    std::cout << std::endl; // 换行
                }
            }
        }
    }
}

AOV网与拓扑排序

有向无环图：不含环的有向图

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V, V2 ,..V n，满足若从顶点V到V;有一条路径，则在顶点序列中顶点V必在顶点V;之前。则我们称这样的顶点序列为一个拓扑序列。

拓扑排序：其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤:

①从AOV网中选择一个没有前驱的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。

算法原理：dfs

对于AOV 网宜采用邻接表作为存储结构

数组indegree：用于存放各个顶点的入度

算法思路：

每次遍历数组indegree，查找入度为零的顶点，将其加入队列，再遍历邻接表，将遍历到的顶点的indegree值减一，并判断是否为零，若为零则加入队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// 拓扑排序实现
void Graph::topologicalSort() {
    vector<int> indegree(V, 0); // 入度数组
    queue<int> q;              // 队列

    // 计算所有顶点的入度
    for (int i = 0; i < V; i++) {
        for (int v : adj[i]) {
            indegree[v]++;
        }
    }

    // 将入度为0的顶点加入队列
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0; // 用于检测图是否存在环

    // 输出拓扑排序
    cout << "拓扑排序顺序为: ";
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " "; // 输出顶点
        count++;

        // 遍历该顶点的所有邻接点，并更新它们的入度
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    cout << endl;

    // 如果没有输出所有顶点，说明存在环
    if (count != V) {
        cout << "图中存在环，无法进行拓扑排序！" << endl;
    }
}

参考文献

数据结构：图(Graph)【详解】_图数据结构-CSDN博客

数据结构-图-prim（普里姆）算法最小生成树（过程分析+手写代码）_哔哩哔哩_bilibili

数据结构-图-最小生成树-克鲁斯卡尔（Kruskal)算法-手画+过程分析+代码_哔哩哔哩_bilibili

论文阅读：Jupiter: friend or foe? An answer

奥尔特云：

奥尔特云 - 维基百科，自由的百科全书

长周期彗星：这些天体来自奥尔特云，周期超过200年，具有完整的轨道倾角范围，由 1012-1013 个冰体组成，其中绝大多数的直径小于 10 公里，并占据一个距离太阳约 103-105 天文单位的厚球形壳

短周期彗星：一般认为来自于柯伊伯带或离散盘。周期在200年以下

短周期彗星有两大类：木星族彗星（半长轴小于5天文单位）及哈雷类彗星

短周期彗星 - 维基百科，自由的百科全书

木星族:木星有时会缩短一颗彗星的运动周期，有时会延长一颗彗星的运动周期，有时会改变彗星轨道，从而使得周期彗星变成非周期彗星，反过来也一样。周期3-10年，远日点在木星轨道附近的彗 星称为木星族彗星。

改变木星轨道上巨星的质量Y来 自小行星带的轰击

我们研究了改变“木星”质量对地球从小行星带向内抛出的物体所经历的撞击率的影响。我们在模拟冲击通量时遇到了一些问题。小行星被认为构成了最大的威胁。然而，在创建一群可能进化到撞击地球轨道的测试小行星时，我们面临着巨大的不确定性，特别是与整合开始时小行星的分布有关的不确定性。

因为自木星形成以来，它一直在扰乱目前在小行星带中观察到的物体的轨道。因此，尝试为这颗小行星构建一个受干扰程度要小得多的初始种群是很重要的

我们 2008 年的论文详细介绍了我们如何确定小行星分布，$\ N{0}(a)=k(a-a{min})^\frac{1}{2}$，其中 N（a） 是距离太阳 a 的小行星数量，k 是常数，$\ a{min}$ 是小行星分布的内部边界。$\ a{min}$的值为1.558AU，相当于火星的轨道半长轴，1.52 AU，加上三个 希尔半径

归一化常数 k 的确定
为了使总的小行星数量 $\ N_{total}$, 为一个固定值，我们需要对 N(a)进行归一化。通过对 N(a)在范
围[amin,amax]内积分，可以得到归一化常数 k

$\ k=\frac{3N{total}}{2(a{max}-a_{min})^\frac{2}{3}}$

希尔半径$\ R{H}=a_p(\frac{M{planet}}{3M_{Sun}})^\frac{1}{3}$，ap 是行星轨道的半长轴，M 表示质量。希尔球半径是一个天体对其周围物体产生重力影响的范围

以这种方式创建的物体代表一个碎片圆盘，在行星形成过程中受到了适度但不过度的搅拌（例如 Ward 2002）。

然后，在地球、火星、木星、土星、天星和海王星的影响下，使用 MERCURY 包中包含的混合积分器对测试粒子进行了 1000 万年的跟踪。进行了简单的测试积分，以检查地球横截面积对所经历的冲击通量的影响。正如预期的那样，发现撞击率与地球的横截面积成正比，引力聚焦的影响可以忽略不计。为了提高撞击率以获得合理的撞击统计数据，因此我们将地球膨胀到 $\ 10^6$ 公里的半径。在我们的整合中，小行星与行星和太阳发生引力相互作用，但彼此之间没有相互作用

我们运行中使用的 “Jupiter” 经过修改，因此我们运行了 12 个单独的质量。在木星质量 MJ 的倍数中，这些是：0.01、0.05、0.10、0.15、0.20、0.25、0.33、0.50、0.75、1.00、1.50 和 2.00。每个“木星”的轨道元素与今天的木星相同。同样，模拟中其他行星的元素与今天相同：一次运行和下一次运行之间行星设置的唯一区别是木星质量的变化——所有其他变量都是恒定的。

显示了我们的模拟中 通量与质量关系的形式，其中小行星是 源群体。这些结果令人惊讶。在 1.00 M J 时，对地球的撞击次数约为 0.01 M J 时的撞击次数的 3.5 倍Y几乎没 有屏蔽！在这两个”木星”质量之间， 在 0.2 M J 左右存在一个峰值，其中撞 击次数几乎是 1.00 M J 时的两倍。

我们随机生成了 100 000 个测试群体粒子，近日点位于 0.1– 10 AU 范围内，远日点位于 10 000 和100 000 个AU。人口的结构是为 了模仿观察到的长周期彗星的远日点 分布。近日点距离 q 确定如下$\ q=0.1+[(q{max}-q{min})^\frac{2}{3}*random]^\frac{2}{3}$其中 $\ q{max}$ 和$\ q{min}$分别是 0.1 和 10 AU 的最大和最小可能近日点 距离，而 random 是在克隆程序中 生成的 0 到 1 之间的随机数。这导 致大约 3% 的初始样本具有与地球 轨道交叉的轨道（地球交叉轨 道），大约 38% 位于最初与木星 交叉的轨道（q 小于或等于 5.203 AU 的轨道）。这个分布是一个简 单但有效的尝试，试图拟合新奥尔 特云彗星的已知分布

我们计算了奥尔特云 彗星在（膨胀的）地球上的碰撞次 数。需要采取不同的方法。奥尔特 云彗星的轨道周期是如此之大，以 至于即使在 100 Myr 的模拟中，即 使地球严重膨胀，也很少会与地球 近距离接触。因此，为了直接确定 对地球的撞击率，我们必须模拟大 量的测试粒子，其数量级比所使用 的粒子高出许多数量级

我们模拟中使用的”木 星”的质量被修改了从一个场景到 下一个场景。总共考虑了五种不同 的场景。研究了质量为木星质量 0.25、0.50、1.00 和 2.00 倍 的”木星”系统，以及不存在木星 的系统。和以前一样，场景之间的 唯一区别是木星的质量Y所有其 他参数都是恒定的。

大质量情况下彗星的消失速度 明显快于低质量木星的情况。即使 仅在 1 Myr 后，木星质量较高的喷 射率就很明显，并且一直持续到我 们模拟的最后，到那时，在所有情 况下，仅保留了初始彗星种群的一 小部分。

值得注意的是，即使没有 木星存在，到运行结束时，长周期 彗星的数量仍然会显着减少。由于 木星不存在（”木星”质量为 零）

。当考虑基于喷射率的初始代理 的结果时，重要的是要确保该措施 是实际上是冲击通量的合适代理。 例如，地球上的碰撞率似乎可能并 不简单地与幸存的奥尔特云彗星的 数量成正比。特别是，另外两种可 能性似乎值得进一步研究，以确保 我们最初的假设是正确的：考虑到 所研究的彗星轨道的扩展，重要的 是要检查是否存在穿过地球轨道的 奥尔特云彗星的优先生存（ q < 1 AU)，或那些不存在的 (q > 1 AU)。

换句话说，当考虑到长周期彗星通量（与我们之前 的发现相反），一颗质量更大的木星 肯定会在不存在这样的行星的情况下 为地球提供一些可测量的屏蔽。

事实上，只有在来自奥尔特 云的彗星的情况下，我们的结果表 明木星确实是长期以来所假设的地 球的朋友！

然而，应该指出的 是，在长周期轨道上运动的物体平 均而言通常比在短周期或星状轨道 上运动的物体具有更大的碰撞速度 （这是由于它们较高的倾角[包括逆 行轨道]和更大的轨道）速度为 1 天 文单位），这增加了奥尔特云彗星 作为轰炸机群体的相对重要性。

作 为一个整体，我们的工作表明，而 不是充当作为地球的盾牌，木星反 而增加了我们星球所经历的冲击通 量，超过了如果这颗行星以某种方 式神奇地从我们的太阳系中移走时 所受到的冲击通量。然而，如果木 星的质量减少到土星的质量，地球 的情况会更糟

事实上，只有在来自奥尔特 云的彗星的情况下，我们的结果表 明木星确实是长期以来所假设的地 球的朋友！

我们的结果令人震惊。对于当前时代威胁地球的两个主要种群（近地小行星 和短周期彗星），我们发现木星质量与撞击率之间的关系相当复杂。在”木星”质量 较低的情况下，两颗行星的撞击率都非常低，因为这些小行星很难在地球交叉轨道上 放置物体。同样，在高”木星”质量（类似于或大于我们的木星）时，两个种群的撞 击率都相对较低，尽管略高于质量最小的”木星”。然而，在这两个极端之间，我们 在模拟中发现地球上的撞击通量出现了显着的峰值。对于近地小行星(Horner & Jones, ̚ ̘ ̘ ̠ b)和短周期彗星(Horner & Jones, 2009)，我们发现当模拟中的”木 星”在0.2到0.3倍之间时，撞击通量最大。和我们的木星一样大。换句话说，与质量 小得多的情况相比（例如，当它的质量与海王星相当时），我们的木星仅提供适度的 屏蔽，但如果它围绕土星的质量，那么地球上的撞击通量将是远远大于我们观察到 的。

当我们研究木星质量对第三种潜在危险天体M长周期彗星M的撞击率的影响时 （例如 Wiegert & Tremaine, 1999, Levison, Dones &Duncan, 2001, Horner & Evans, 2002），我们发现”木星”质量越大，对地球的撞击率就越低（Horner，Jones &钱伯斯， 2010）。那么，对于长周期彗星来说，木星似乎确实起到了盾牌的作用。然而，长周期彗星 被认为只对小行星和彗星对地球的影响贡献了一小部分（

这是否也在确定其宿主系统中潜在宜居行星的撞击通量中 发挥作用？在这项工作中，我们通过检查木星轨道偏心率和倾角的影响，建立在早期结果 的基础上。在这项工作中，我们只考虑两个主要的撞击星群M近地小行星和短周期彗星。 由于长周期彗星在轨道倾角基本上各向同性分布的轨道上运行，并且几乎不受太阳系引力 约束，因此可以合理地假设木星轨道的微小变化对彗星通量几乎没有影响或没有影响。

总体而言，很明显，巨行星轨道偏心率的增加会导致近地小行星和短周期彗星对地球的 撞击通量增加。

不要过分苛责自己

​ 数竞的成绩出来，没有看到自己名字，不知道为什么还是有些难受，理性告诉我这是理所应当，因为我根本没有为这个比赛花任何时间，只有前一天晚上临时抱佛脚的两个小时，对于报名，却没有复习的原因，如果别人让我做出解释，我可能会说，那段时间太累了，这不是借口，我记忆中那段时间确实是挺累的，但现在我已经不记得我那段时间忙些了什么，或者为自己留下了什么实际性的收获，似乎什么都没有。

​ 结果上看，我对待这个比赛的态度是放弃的，那既然已经决定放弃的事情，为什么还会有些难受呢，我想，一方面，我还对不劳而获存在不切实际的幻想，幻想着不复习，幻想着靠自己脑子那一点点知识，就想在竞赛中占有一席之地，幻想着运气一次又一次眷顾自己，事实会告诉我这是不可能的；另一方面，每个人的精力确实是有限的，但我总是比较贪心，这也想要，那也想要，结果就是应接不暇，这是好强导致的吗，感觉还是比较幼稚，没有舍弃与选择的魄力，没有舍弃的勇气的人，什么也改变不了，hhh突然想起巨人的台词，有些中二嗷，扯远了扯远了。

​ 其实，就算做不到也没关系，现实已经一次又一次地证明了，人无完人，这件事你做不好不代表其他事你做不好啊，我并不喜欢钻研数学啊物理啊做题做试卷这种，但我决定参加一些项目，学习新的知识很有意思，我也确实在其他一些科研比赛中获得不错的成绩，为什么要为一个小小的数竟，过分地苛责自己呢，况且你一开始就没有好好准备他，失败是理所应当的，你并没有损失什么，看得开一些，向前看，不要为一些小失败而驻足不前，不要为一些小失败过分地苛责自己。

​ 突然发现把一些心里话写下来，心情真的舒畅了很多，继续加油，不要停止奔跑。