5。
G. 右图是一个算法的流程图，最后输出的k=______
首先给循环变量k和累加变量S赋值1和0，
判断0＜20，执行S=0+1=1，k=1+2=3；
判断1＜20，执行S=1+3=4，k=3+2=5；
判断4＜20，执行S=4+5=9，k=5+2=7；
判断9＜20，执行S=9+7=16，K=7+2=9；
判断16＜20，执行S=16+9=25，k=9+2=11；
判断25＞20，输出k的值为11，算法结束．
故答案为11． |
H. K近邻算法的理论基础
从理论基础、手写数字识别算法、手写数字识别实例等角度介绍K近邻算法。
K近邻算法的本质是将指定对象根据已知特征值分类。
例如，看到一对父子，一般情况下，通过判断他们的年龄，能够马上分辨出哪位是父亲，哪位是儿子。这是通过年龄属性的特征值来划分的。
上述例子是最简单的根据单个特征维度做的分类，在实际场景中，情况可能更复杂，有多个特征维度。
例如，为一段运动视频分类，判断这段视频是乒乓球比赛还是足球比赛。
为了确定分类，需要定义特征。这里定义两个特征，一个是运动员“挥手”的动作，另一个是运动员“踢脚”的动作。当然，我们不能一看到“挥手”动作就将视频归类为“乒乓球比赛”，因为我们知道某些足球运动员习惯在运动场上通过挥手来跟队友进行交流。同样，我们也不能一看到“踢脚”动作就将视频归类为“足球比赛”，因为有些乒乓球运动员会通过“踢脚”动作来表达自己的感情。
我们分别统计在某段特定时间内，视频中“挥手”和“踢脚”动作的次数，发现如下规律：
● 在乒乓球比赛的视频中，“挥手”的次数远多于“踢脚”的次数。
● 在足球比赛的视频中，“踢脚”的次数远多于“挥手”的次数。
根据对一组视频的分析，得到如表20-1所示的数据。
为了方便观察，将上述数据绘制为散点图，如图20-1所示。
从图20-1中可以看到，数据点呈现聚集特征：
● 乒乓球比赛视频中的数据点聚集在x轴坐标为[3000, 5000], y轴坐标为[1,500]的区域。
● 足球比赛视频中的数据点聚集在y轴坐标为[3000, 5000], x轴坐标为[1,500]的区域。
此时，有一个视频Test，经过统计得知其中出现2000次“挥手”动作，100次“踢脚”动作。如果在图20-1中标注其位置，可以发现视频Test的位置最近的邻居是乒乓球比赛视频，因此可判断该视频是乒乓球比赛视频。
上面的例子是一个比较极端的例子，非黑即白，而实际的分类数据中往往参数非常多，判断起来也不会如此简单。因此，为了提高算法的可靠性，在实施时会取k个近邻点，这k个点中属于哪一类的较多，然后将当前待识别点划分为哪一类。为了方便判断，k值通常取奇数，这和为了能得到明确的投票结果通常将董事会成员安排为奇数的道理是一样的。
例如，已知某知名双胞胎艺人A和B长得很像，如果要判断一张图像T上的人物到底是艺人A还是艺人B，则采用K近邻算法实现的具体步骤如下：
以上所述就是K近邻算法的基本思想。
I. 农夫过河的图算法
#include<iostream>
using namespace std;
#define VertexNum 16 //最大顶点数
typedef struct // 图的顶点
{
int farmer; // 农夫
int wolf; // 狼
int sheep; // 羊
int veget; // 白菜
}Vertex;
typedef struct
{
int vertexNum; // 图的当前顶点数
Vertex vertex[VertexNum]; // 顶点向量（代表顶点）
bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关
}AdjGraph; // 定义图的邻接矩阵存储结构
bool visited[VertexNum] = {false}; // 对已访问的顶点进行标记（图的遍历）
int retPath[VertexNum] = {-1}; // 保存DFS搜索到的路径，即与某顶点到下一顶点的路径
// 查找顶点（F，W，S，V）在顶点向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)
{
// 从0开始查找
for (int i = 0; i < graph->vertexNum; i++)
{
if ( graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf
&& graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget )
{
return i; //返回当前位置
}
}
return -1; //没有找到此顶点
}
// 判断目前的（F，W，S，V）是否安全
bool isSafe(int farmer, int wolf, int sheep, int veget)
{
//当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的
if ( farmer != sheep && (wolf == sheep || sheep == veget) )
{
return false;
}
else
{
return true; // 安全返回true
}
}
// 判断状态i与状态j之间是否可转换
bool isConnect(AdjGraph *graph, int i, int j)
{
int k = 0;
if (graph->vertex[i].wolf != graph->vertex[j].wolf)
{
k++;
}
if (graph->vertex[i].sheep != graph->vertex[j].sheep)
{
k++;
}
if (graph->vertex[i].veget != graph->vertex[j].veget)
{
k++;
}
// 以上三个条件不同时满足两个且农夫状态改变时，返回真, 也即农夫每次只能带一件东西过桥
if (graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1)
{
return true;
}
else
{
return false;
}
}
// 创建连接图
void CreateG(AdjGraph *graph)
{
int i = 0;
int j = 0;
// 生成所有安全的图的顶点
for (int farmer = 0; farmer <= 1; farmer++)
{
for (int wolf = 0; wolf <= 1; wolf++)
{
for (int sheep = 0; sheep <= 1; sheep++)
{
for (int veget = 0; veget <= 1; veget++)
{
if (isSafe(farmer, wolf, sheep, veget))
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
graph->vertex[i].veget = veget;
i++;
}
}
}
}
}
// 邻接矩阵初始化即建立邻接矩阵
graph->vertexNum = i;
for (i = 0; i < graph->vertexNum; i++)
{
for (j = 0; j < graph->vertexNum; j++)
{
// 状态i与状态j之间可转化，初始化为1，否则为0
if (isConnect(graph, i, j))
{
graph->Edge[i][j] = graph->Edge[j][i] = true;
}
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 判断在河的那一边
char* judgement(int state)
{
return ( (0 == state) ? "左岸" : "右岸" );
}
// 输出从u到v的简单路径，即顶点序列中不重复出现的路径
void printPath(AdjGraph *graph, int start, int end)
{
int i = start;
cout << "farmer" << ", wolf" << ", sheep" << ", veget" << endl;
while (i != end)
{
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
i = retPath[i];
}
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
}
// 深度优先搜索从u到v的简单路径 //DFS--Depth First Search
void dfsPath(AdjGraph *graph, int start, int end)
{
int i = 0;
visited[start] = true; //标记已访问过的顶点
if (start == end)
{
return ;
}
for (i = 0; i < graph->vertexNum; i++)
{
if (graph->Edge[start][i] && !visited[i])
{
retPath[start] = i;
dfsPath(graph, i, end);
}
}
}
int main()
{
AdjGraph graph;
CreateG(&graph);
int start = locate(&graph, 0, 0, 0, 0);
int end = locate(&graph, 1, 1, 1, 1);
dfsPath(&graph, start, end);
if (visited[end]) // 有结果
{
printPath(&graph, start, end);
return 0;
}
return -1;
}
