-
在计算机视觉领域，卷积神经网络（Convolutional Neural Network，CNN）是一项具有革命性意义的深度学习算法。通过模拟人类视觉系统的工作原理，CNN在图像识别任务中取得了令人瞩目的成就，成为图像处理和计算机视觉领域的里程碑之一。 卷积层的特色 CNN的核心在于卷积层，其中包含了多个卷积核，它们类似于生物学中的神经元。这些卷积核通过滑动窗口的方式在输入图像上进行局部特征检测。通过卷积操作，CNN能够捕捉图像中的边缘、纹理和形状等重要特征，从而实现对图像的有效表示和抽象。 池化层的有效降维 CNN中的池化层对特征图进行降维处理，它通过选择局部区域内的最大值（最大池化）来减少特征图的尺寸和复杂性。这种降维有助于减少计算负担，防止过拟合，并提高模型的泛化能力。 全连接层的分类能力 在经过卷积层和池化层处理之后，CNN通过全连接层将提取到的高级特征映射到具体的类别。全连接层的非线性映射能力，使得CNN能够准确地对图像进行分类。 梯度下降优化 在训练CNN模型时，采用梯度下降优化算法，通过最小化损失函数来不断调整模型参数，使得预测结果与真实标签尽可能接近。这样的优化过程使得CNN逐步学习到图像的特征和模式，从而提高了识别准确率。 迁移学习的巧妙运用 鉴于CNN的庞大参数量，对于某些特定任务或数据较少的情况，单独训练一个大型CNN模型可能导致过拟合。在这种情况下，迁移学习成为一种有效的技术。通过利用在大规模图像数据集上预训练的CNN模型作为初始模型，在特定任务上进行微调，能够在较小数据集上取得优秀的识别性能。 总结：卷积神经网络（CNN）的出现在图像识别领域引起了一场革命。它通过卷积、池化和全连接层等核心技术，实现了对图像特征的高效提取和表示。其在图像分类、物体检测、人脸识别等任务上取得的卓越成就，彰显了其在计算机视觉领域的重要地位和广泛应用前景。通过持续的技术优化和迁移学习策略，CNN必将在未来继续推动图像识别技术的发展，为人们带来更多便捷和智能的应用体验。 -
经过我今年对深度学习 机器学习的研究发现 其算法是错误的 计算机是一台以指令为单位的机器 它是不会学习的 所以没有学习算法一说 那是没有认清计算机的本质 学习是人才有的行为 机器怎么会学习吗 它只有指令啊 经过研究发现我们常说的人工智能 主要是如下四个函数构成的 下面我以常见的游戏AI为例讲解其实现 由于已有多年未碰编程 这里只给出大致算法 在游戏中 当角色或者NPC看/听到什么的时候 就开始学习过程 如何学习呢 其实所有的学习都是从理解开始的 下面给出Understand()函数 int Understand(string type, string action, string p1, string p2) { string memory; switch(type) { case 'walk' memory=Walk(action,p1,p2); // Walk()函数根据词典定义及参数p1, p2解释action并将相应的字符串写入memory break; case 'run' memory=Run(action,p1,p2); break; case 'fight' memory=Fight(action,p1,p2); break; case 'look' memory=Look(action,p1,p2); // 比如看这个行为 Understand()函数会把它解释成使视线接触人或事物 并把记忆记在数据库里 // 实际上人在想看东西的时候 检索记忆也是找到上面的解释并做出相应的行为的 break; ...... 各种人的行为的函数 // 这里要注意的是行为的归类一定要仔细不要冗余 比如躺和侧躺是一类不能归为2类 我个人估算25个行为左右已经有很好 // 的人工智能70个基本上完美 这个时候Understand才两三百行 对游戏来说是个微不足道的小函数 // 要特别指出的是像跳绳 踢毽子等应该归属于一类Playing()玩游戏 break; } Remember(action, memory); // 记忆理解所得的结果即把原始记忆和理解得出的记忆写入数据库 如表hero/NPC} 第二个函数是Study() 人要认识世界就要各种学习 理解了就学习了 所以 bool Study(string action) { action=Look()/action=Listen(); // 通过看或者听学习 string type=IsAction(action); // 判断是某种行为 比如走 跑 说话 看等 string p1,p2; p1=IsParam1(action); p2=IsParam2(action); // 对行为的一些描述p1 p2 Understand(type, action, p1, p2); // 对行为进行理解并记忆 } 然后 NPC在空闲的时候还会想事情(就是普通的漫无目的想 假定其函数名为Thinking) 想了之后就做某种事情 第三个函数如下 int Thinking() { int n=0; // n是随机数 NPC在空闲的时候想什么事情是个随机事件 它随机性的发生 int type=rand()/2; // 2可用其它值 处于某种想之中 switch(type) { case 1: n=OnIdle(); // 在空想 函数给n赋予随机值 break; case 2: n=Memory(); // 在回忆 函数给n赋予随机值 break; ...... } switch(n) { case 1: Walk(); // 某种形式某种目的的行走 与Understand()中那个不同这个是实际的行为 那个是把行走理解成某种行动的字符串数据 break; case 2: Talk(); // 某种目的某种内容的谈话 break; ...... default break; } } 最后一个函数 也是最难的一个函数 就是思考(Thought) 对某个问题经过思考得出结果 int Thought(string question) { if(LookupMemory(question)) // 在记忆中查找看是否找到 实际上是一个查找数据库的表并在表中的数据项查找的函数 { string law; law=Haslaw(question); // 函数中可用IsNum() IsMathChar() IsLaw()等函数判断question里面是否有数字 数学符号 数学/物理法则等 if(law.IsNotNull()) // 看是否包含有法则 { RunLogic(law); // 运行相应的逻辑法则 } else { // 做其它的事 比如和某个NPC对话 } return 1; } else { if(Research(question)) // 研究问题 { ...... // 成功相应的行为 return 1; } else { ...... // 失败相应的行为 return 0; } } } 通过以上四个函数就可以把理解 学习 想事情 思考问题完整的实现出来 完成人工智能的全部功能 这里根本不需要什么深度学习 机器学习 这就是全部的人工智能函数 下面再写两个跟游戏有关及常用的人工智能函数 第一个自动寻路/自动驾驶 自动寻路要注意的一点就是不能把HitTest()当成"轻重缓急"算法写在判断避让那里 因为自动寻路避让障碍的时候是个轻重缓急行为 不是进行碰撞检测 bool AutoDriving(int Character) { bool obstacle=Look(); // 看道路上有无障碍 if(obstacle) { int distance=OrderofPriority(Character); // 判断轻重缓急 int direction=GetInput(keyboard); ChangeDirection(direction, distance); // 在距离distance处转向 } } 一个可能的轻重缓急算法是 int OrderofPriority(int Character) { int type=rand()/2; // 轻和重 缓和急是个随机产生情况 这是客观世界的真实反应 游戏世界也是一样的 switch(type) { int min=GetMinimum(); // 测出物体中心到前端的距离的最大值即碰撞距离 不碰撞只要大于它就行了 比如可以略大于它 也可以+1 +2 +5厘米或者加个随机数 int senmin,senmax; GetDistanceSensitivity(Character,senmin,senmax); // 得到角色的最小最大距离敏感度 一个查询数据库的函数 case 1: // 轻/缓 return min+(rand()/0.1~1)+senmax; // 大于碰撞距离小于等于角色最大距离敏感度并略有出入的随机数 或者其它可自定 break; case 2: // 重/急 return min+(rand()/0.1~1)+senmin; // 大于碰撞距离小于等于角色最小距离敏感度并略有出入的随机数 或者其它可自定 break; } } 第二个真实打斗 这个函数主要是随机数加上一些三十六计计谋即可 如 int RealFighting() { int type=rand()/50; // 计谋中的一种 包括连环计 计中计 switch(type) { case 1: 声东击西(); break; case 2: 围魏救赵(); break; case 3: 四面楚歌(); 火上浇油(); break; ...... } } 甚至还可以写出复合体及变体 提到游戏中人工智能 很多时候都是个随机数问题 因为自然界中的事都是随机发生的 当然到了虚拟世界里面 各种事情也是个随机性的 恰好有rand()函数能很好的解决这一问题 欢迎转载 -
经过我今年对深度学习 机器学习的研究发现 其算法是错误的 计算机是一台以指令为单位的机器 它是不会学习的 所以没有学习算法一说 那是没有认清计算机的本质 学习是人才有的行为 机器怎么会学习吗 它只有指令啊 经过研究发现我们常说的人工智能 主要是如下四个函数构成的 下面我以常见的游戏AI为例讲解其实现 由于已有多年未碰编程 这里只给出大致算法 在游戏中 当角色或者NPC看/听到什么的时候 就开始学习过程 如何学习呢 其实所有的学习都是从理解开始的 下面给出Understand()函数 int Understand(string type, string action, string p1, string p2) { string memory; switch(type) { case 'walk' memory=Walk(action,p1,p2); // Walk()函数根据词典定义及参数p1, p2解释action并将相应的字符串写入memory break; case 'run' memory=Run(action,p1,p2); break; case 'fight' memory=Fight(action,p1,p2); break; case 'look' memory=Look(action,p1,p2); // 比如看这个行为 Understand()函数会把它解释成使视线接触人或事物 并把记忆记在数据库里 // 实际上人在想看东西的时候 检索记忆也是找到上面的解释并做出相应的行为的 break; ...... 各种人的行为的函数 // 这里要注意的是行为的归类一定要仔细不要冗余 比如躺和侧躺是一类不能归为2类 我个人估算25个行为左右已经有很好 // 的人工智能70个基本上完美 这个时候Understand才两三百行 对游戏来说是个微不足道的小函数 // 要特别指出的是像跳绳 踢毽子等应该归属于一类Playing()玩游戏 break; } Remember(action, memory); // 记忆理解所得的结果即把原始记忆和理解得出的记忆写入数据库 如表hero/NPC} 第二个函数是Study() 人要认识世界就要各种学习 理解了就学习了 所以 bool Study(string action) { action=Look()/action=Listen(); // 通过看或者听学习 string type=IsAction(action); // 判断是某种行为 比如走 跑 说话 看等 string p1,p2; p1=IsParam1(action); p2=IsParam2(action); // 对行为的一些描述p1 p2 Understand(type, action, p1, p2); // 对行为进行理解并记忆 } 然后 NPC在空闲的时候还会想事情(就是普通的漫无目的想 假定其函数名为Thinking) 想了之后就做某种事情 第三个函数如下 int Thinking() { int n=0; // n是随机数 NPC在空闲的时候想什么事情是个随机事件 它随机性的发生 int type=rand()/2; // 2可用其它值 处于某种想之中 switch(type) { case 1: n=OnIdle(); // 在空想 函数给n赋予随机值 break; case 2: n=Memory(); // 在回忆 函数给n赋予随机值 break; ...... } switch(n) { case 1: Walk(); // 某种形式某种目的的行走 与Understand()中那个不同这个是实际的行为 那个是把行走理解成某种行动的字符串数据 break; case 2: Talk(); // 某种目的某种内容的谈话 break; ...... default break; } } 最后一个函数 也是最难的一个函数 就是思考(Thought) 对某个问题经过思考得出结果 int Thought(string question) { if(LookupMemory(question)) // 在记忆中查找看是否找到 实际上是一个查找数据库的表并在表中的数据项查找的函数 { string law; law=Haslaw(question); // 函数中可用IsNum() IsMathChar() IsLaw()等函数判断question里面是否有数字 数学符号 数学/物理法则等 if(law.IsNotNull()) // 看是否包含有法则 { RunLogic(law); // 运行相应的逻辑法则 } else { // 做其它的事 比如和某个NPC对话 } return 1; } else { if(Research(question)) // 研究问题 { ...... // 成功相应的行为 return 1; } else { ...... // 失败相应的行为 return 0; } } } 通过以上四个函数就可以把理解 学习 想事情 思考问题完整的实现出来 完成人工智能的全部功能 这里根本不需要什么深度学习 机器学习 这就是全部的人工智能函数 下面再写两个跟游戏有关及常用的人工智能函数 第一个自动寻路/自动驾驶 自动寻路要注意的一点就是不能把HitTest()当成"轻重缓急"算法写在判断避让那里 因为自动寻路避让障碍的时候是个轻重缓急行为 不是进行碰撞检测 bool AutoDriving(int Character) { bool obstacle=Look(); // 看道路上有无障碍 if(obstacle) { int distance=OrderofPriority(Character); // 判断轻重缓急 int direction=GetInput(keyboard); ChangeDirection(direction, distance); // 在距离distance处转向 } } 一个可能的轻重缓急算法是 int OrderofPriority(int Character) { int type=rand()/2; // 轻和重 缓和急是个随机产生情况 这是客观世界的真实反应 游戏世界也是一样的 switch(type) { int min=GetMinimum(); // 测出物体中心到前端的距离的最大值即碰撞距离 不碰撞只要大于它就行了 比如可以略大于它 也可以+1 +2 +5厘米或者加个随机数 int senmin,senmax; GetDistanceSensitivity(Character,senmin,senmax); // 得到角色的最小最大距离敏感度 一个查询数据库的函数 case 1: // 轻/缓 return min+(rand()/0.1~1)+senmax; // 大于碰撞距离小于等于角色最大距离敏感度并略有出入的随机数 或者其它可自定 break; case 2: // 重/急 return min+(rand()/0.1~1)+senmin; // 大于碰撞距离小于等于角色最小距离敏感度并略有出入的随机数 或者其它可自定 break; } } 第二个真实打斗 这个函数主要是随机数加上一些三十六计计谋即可 如 int RealFighting() { int type=rand()/50; // 计谋中的一种 包括连环计 计中计 switch(type) { case 1: 声东击西(); break; case 2: 围魏救赵(); break; case 3: 四面楚歌(); 火上浇油(); break; ...... } } 甚至还可以写出复合体及变体 提到游戏中人工智能 很多时候都是个随机数问题 因为自然界中的事都是随机发生的 当然到了虚拟世界里面 各种事情也是个随机性的 恰好有rand()函数能很好的解决这一问题 欢迎转载
-
在SDC APP开发指南文档里有看到这个接口的描述，可参考样例是空，算法资料地图帖子里也好像没有相关的代码例子。
-
0x01 编码发展史0x20以下的编码用作控制码，接下来一直到127号的的字节用来表示大小写字母，标点符号，空格，数字，这就是ascii码，只能满足美国人的需要。中国人民通过对 ASCII 编码的中文扩充改造，产生了 GB2312 编码，可以表示6000多个常用汉字。汉字实在是太多了，包括繁体和各种字符，于是产生了 GBK 编码，它包括了 GB2312 中的编码，同时扩充了很多。中国是个多民族国家，各个民族几乎都有自己独立的语言系统，为了表示那些字符，继续把 GBK 编码扩充为 GB18030 编码。每个国家都像中国一样，把自己的语言编码，于是出现了各种各样的编码，如果你不安装相应的编码，就无法解释相应编码想表达的内容。终于，有个叫 ISO 的组织看不下去了。他们一起创造了一种编码 UNICODE ，这种编码非常大，大到可以容纳世界上任何一个文字和标志。所以只要电脑上有 UNICODE 这种编码系统，无论是全球哪种文字，只需要保存文件的时候，保存成 UNICODE 编码就可以被其他电脑正常解释。UNICODE 在网络传输中，出现了两个标准 UTF-8 和 UTF-16，分别每次传输 8个位和 16个位。于是就会有人产生疑问，UTF-8 既然能保存那么多文字、符号，为什么国内还有这么多使用 GBK 等编码的人？因为 UTF-8 等编码体积比较大，占电脑空间比较多，如果面向的使用人群绝大部分都是中国人，用 GBK 等编码也可以。但是目前的电脑来看，硬盘都是白菜价，电脑性能也已经足够无视这点性能的消耗了。所以推荐所有的网页使用统一编码：UTF-8。0x02 各种编码URL编码一个百分号和该字符的ASCII编码所对应的2位十六进制数字，例如“/”的URL编码为%2F(一般大写，但不强求)具体情况：网址路径的编码，用的是utf-8编码查询字符串的编码，用的是操作系统的默认编码GET和POST方法的编码，用的是网页的编码在Ajax调用中，IE采用GB2312编码（操作系统的默认编码），而Firefox采用utf-8编码。escape()不能直接用于URL编码，它的真正作用是返回一个字符的Unicode编码值。比如"春节"的返回结果是%u6625%u8282，也就是说在Unicode字符集中，"春"是第6625个（十六进制）字符，"节"是第8282个（十六进制）字符。它的具体规则是，除了ASCII字母、数字、标点符号"@ * _ + - . /"以外，对其他所有字符进行编码。在\u0000到\u00ff之间的符号被转成%xx的形式，其余符号被转成%uxxxx的形式。对应的解码函数是unescape()。所以，"Hello World"的escape()编码就是"Hello%20World"。因为空格的Unicode值是20（十六进制）。HTML实体编码命名实体：以&开头，分号结尾的，例如“<”的编码是“<”字符编码：十进制、十六进制ASCII码或unicode字符编码，样式为“&#数值;”,例如“<”可以编码为“<”和“<”JS编码js提供了四种字符编码的策略，三个八进制数字，如果不够个数，前面补0，例如“e”编码为“\145”两个十六进制数字，如果不够个数，前面补0，例如“e”编码为“\x65”四个十六进制数字，如果不够个数，前面补0，例如“e”编码为“\u0065”对于一些控制字符，使用特殊的C类型的转义风格（例如\n和\r）CSS编码用一个反斜线()后面跟1~6位的十六进制数字，例如e可以编码为“\65”或“65”或“00065”复合编码所谓复合编码，也就是说输出的内容输出在多个环境中，例如<td onclick=”openUrl(add.do?userName=’<%=value%>’);”>11</td>value的内容首先出现在一个URL中，这个URL在一段javascript中，而javascript代码又是html的一部分。所以解码的顺序就是HTML解码–>js解码–>url解码，那么正确的编码顺序就应该是url编码–>js编码–>html编码。0x03 浏览器解析浏览器解析HTML的步骤浏览器收到从服务器发送来的HTML内容，会从头解析，当遇到<script></script>时，会调用javascript脚本解析器解析javascript，并执行脚本，然后继续解析其他的HTML内容，对于一些需要触发才能执行的事件，当触发事件发送时，脚本解析器才会解析其中的脚本，在事件触发之前，它是HTML的一部分。编码问题实例解析分析1、URL编码"javascript:alert(1)" <a href="%6a%61%76%61%73%63%72%69%70%74:%61%6c%65%72%74%28%31%29"></a>Answer: The javascript will NOT execute.url不能对协议以及协议后的冒号进行编码，否则url解析器会认为其是无类型的。这里JavaScript是个伪协议，而且对javascript进行了url编码，会导致url解析器认为其是无类型，无法进行url解码。最终也就不会弹窗。2、HTML字符实体编码 "javascript" 和 URL 编码 "alert(2)"<a href="javascript:%61%6c%65%72%74%28%32%29">Answer: The javascript will execute.这里javascript属于html解析中的”属性值中的字符引用“，所以可以先被html解码，然后被url解析器识别出来，后面的alert(2)由于不是协议，url解析器可以正常解析，最后会弹窗。3、URL 编码 ":" <a href="javascript%3aalert(3)"></a>Answer: The javascript will NOT execute.url不能对协议以及协议后的冒号进行编码，否则url解析器会认为其是无类型的。这里JavaScript是个伪协议，而且对javascript后的冒号进行了url编码，会导致url解析器认为其是无类型，无法进行url解码。最终也就不会弹窗。4、HTML字符实体编码 < 和 > <div><img src=x onerror=alert(4)></div>Answer: The javascript will NOT execute.“<”和“>”字符被编码为“<”和“>”。当解析器解析完“<div>”并处于“数据状态”时，这两个字符将会被解析。当解析器遇到“&”字符，它会知道这是“数据状态的字符引用”，因此会消耗一个字符引用（例如“<”）并释放出对应字符的token。在这个例子中，对应字符指的是“<”和“>”。读者可能会想：这是不是意味着“<”和“>”的token将会被理解为标签的开始和结束，然后其中的脚本会被执行？答案是脚本并不会被执行。原因是解析器在解析这个字符引用后不会转换到“标签开始状态”。正因为如此，就不会建立新标签。因此，我们能够利用字符实体编码这个行为来转义用户输入的数据从而确保用户输入的数据只能被解析成“数据”。5、HTML字符实体编码 < 和 > <textarea><script>alert(5)</script></textarea>Answer: The javascript will NOT execute AND the character entities will NOT be decoded either在<textarea>和<title>标签中的字符引用会被HTML解析器解码，在解析这些字符引用的过程中不会进入“标签开始状态”，甚至在<textarea>和<title>的内容中都无法创建标签，更不会有javascript执行了。6、<textarea>和<title><textarea><script>alert(6)</script></textarea>Answer: The javascript will NOT execute.在浏览器解析RCDATA元素的过程中，解析器会进入“RCDATA状态”。在这个状态中，如果遇到“<”字符，它会转换到“RCDATA小于号状态”。如果“<”字符后没有紧跟着“/”和对应的标签名，解析器会转换回“RCDATA状态”。这意味着在RCDATA元素标签的内容中（例如<textarea>或<title>的内容中），唯一能够被解析器认做是标签的就是“</textarea>”或者“</title>”。当然，这要看开始标签是哪一个。因此，在“<textarea>”和“<title>”的内容中不会创建标签，就不会有脚本能够执行。7、HTML字符实体编码 " ' " （单引号）<button onclick="confirm('7');">Button</button>Answer: The javascript will execute.html先将'解码为一个控制字符'，闭合成功，然后javascript进行解析，最终执行。8、Unicode编码 " ' " （单引号）<button onclick="confirm('8\u0027);">Button</button>Answer: The javascript will NOT execute.javascript把uniocde\u0027解析为一个常量'，而不是控制字符'，所以无法闭合。//像圆括号、双引号、单引号等等这些控制字符的unicode编码，在进行JavaScript解析的时候仅会被解码为字符串文本或者标识符名称9、HTML字符实体编码 alert(9);<script>alert(9);</script>Answer: The javascript will NOT execute.在script块中的字符引用并不会被解析和解码，对于unicode字符视情况而定。10、Unicode 编码 alert<script>\u0061\u006c\u0065\u0072\u0074(10);</script>Answer: The javascript will execute.Unicode转义序列只有在标识符名称里不被当作字符串，也只有在标识符名称里的编码字符能够被正常的解析。当Unicode转义序列出现在标识符名称中时，它会被解码并解释为标识符名称的一部分，比如标识符alert,所以可以弹框。11、Unicode 编码 alert(11)<script>\u0061\u006c\u0065\u0072\u0074\u0028\u0031\u0031\u0029</script>Answer: The javascript will NOT execute.这里的unicode转义序列 (11) 不是标识符，所以无法正常解析，即无法弹窗。12、Unicode 编码 alert 和 12 <script>\u0061\u006c\u0065\u0072\u0074(\u0031\u0032)</script>Answer: The javascript will NOT execute.\u0031\u0032不会被解释为字符串常量（因为它们没有用引号闭合）13、Unicode 编码 " ' " （单引号） <script>alert('13\u0027)</script>Answer: The javascript will NOT execute.这里\u0027没有被解析为控制字符，无法闭合，所以无法弹窗。（当用Unicode转义序列来表示一个控制字符时，例如单引号、双引号、圆括号等等，它们将不会被解释成控制字符，而仅仅被解码并解析为标识符名称或者字符串常量。）14、Unicode 编码换行符（0x0A） <script>alert('14\u000a')</script>Answer: The javascript will execute.这里会执行程序并弹窗，因为\u000a被解析成了换行字符文本，避免了因为换行符的出现而导致的javascript语法错误。15、混合加密解析<a href="javascript:%5c%75%30%30%36%31%5c%75%30%30%36%63%5c%75%30%30%36%35%5c%75%30%30%37%32%5c%75%30%30%37%34(15)"></a>Answer: The javascript will execute.(1)先经过html解析(题目2，属性值中的字符引用，正常解析)<a href="javascript:%5c%75%30%30%36%31%5c%75%30%30%36%63%5c%75%30%30%36%35%5c%75%30%30%37%32%5c%75%30%30%37%34(15)"></a>(2)然后url解析(依旧题目2，url解析的内容为非协议内容，正常解析)<a href="javascript:\u0061\u006c\u0065\u0072\u0074(15)"></a>(3)unicode解析(题目10，unicode转义字符出现在标识符名称中，正常解析)<a href="javascript:alert(15)"></a>(4)最后语法正确，javascript正常解析并弹窗。（当然，这里需要在</a>前面随便加点字符，不然无法显示并弹窗）资料索引：对于xss等有关的html，url，unicode编码做的一个小结深入理解浏览器解析机制和XSS向量编码浏览器编码流程從XSS理解編碼解析原理 网页编码就是那点事作者：Hf1dw链接：https://www.jianshu.com/p/19d8172d730b来源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 -
0x01 二分法原理：二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。一般步驟：（1）确定该区间的中间位置K；（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。0x02 递归原理：一种通过重复将问题分解为同类的子问题而解决问题的方法典型例子：斐波那契数列描述：斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368.....自然中的斐波那契数列") 自然中的斐波那契数列，这个数列从第3项开始，每一项都等于前两项之和。解决方式：def f(n, mermory={}): if n == 1 or n == 2: return 1 else: try: return mermory[n] except KeyError: result = f(n-1)+f(n-2) mermory[n] = result return resultprint(f(9))0x03 回溯法原理：在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。解决问题一般步骤：1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。典型例子：八皇后问题描述：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。解决方式：https://blog.csdn.net/weixin_41865447/article/details/800344330x04 排序算法概念：将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。分类：非稳定排序算法：快速排序、希尔排序、堆排序、直接选择排序稳定的排序算法：基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序十个常用排序算法0x05 搜索算法利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。分类：枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。0x06 哈希算法将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。很难找到逆向规律只要符合散列思想的算法都可以被称为是Hash算法对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称为碰撞。0x07 贪心算法原理在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。一种近似算法一般步骤：1、建立数学模型来描述问题；2、把求解的问题分成若干个子问题；3、对每一子问题求解，得到子问题的局部最优解；4、把子问题的解局部最优解合成原来解问题的一个解。典型例子：0/1背包问题马踏棋盘均分纸牌例题：https://www.cnblogs.com/hust-chen/p/8646009.html0x08 分治算法概念：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。典型例子：排序中：归并排序、堆排序、快速排序；实例：找伪币、求最值、棋盘覆盖https://baike.baidu.com/item/%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95/32632970x09 动态规划概念：用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。举例：线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济）等；应用实例：最短路径问题 ，项目管理，网络流优化等；https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fromtitle=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&fromid=15742703&fr=aladdin0x10 字符串匹配算法概念：在一个给定的字符文本内搜寻出自己想要找的一个字符串，平常所用的各种文本编辑器里的ctrl+F大多就是使用的这些字符匹配算法。分类：KMP、BM、Sunday、Horspool、RK参考：https://cloud.tencent.com/developer/news/282694https://blog.csdn.net/paincupid/article/details/81159320作者：Hf1dw链接：https://www.jianshu.com/p/4b29805f9fa7来源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
-
[技术干货] 2023-05-21：给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个， 并把它加到字符串的末尾。 返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串。 输入：s = "baaca", k = 3。 输2023-05-21：给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个， 并把它加到字符串的末尾。 返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串。 输入：s = "baaca", k = 3。 输出："aaabc"。 -
[问题求助] 2023-05-17：一个正整数如果能被 a 或 b 整除，那么它是神奇的。 给定三个整数 n , a , b ，返回第 n 个神奇的数字。 因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。 输入：n = 4, a =2023-05-17：一个正整数如果能被 a 或 b 整除，那么它是神奇的。给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。输入：n = 4, a = 2, b = 3。输出：6。
-
工程概论 - 电梯调度模拟软件设计思路问题建模及基本假设查阅18层大楼的层高和电梯速度，再结合便于软件开发的目的，不妨设电梯的速度为0.5层/秒，且为匀速运动，没有加减速过程。考虑到实际电梯容量和便于图形化的原因，不妨设电梯容量为12人。考虑到进出电梯的人越多，电梯停留时间越长，不妨设为每秒钟电梯可以出一人或者进一人。考虑到出现人群的分布不是均匀的，尤其在 1楼有非常大的吞吐量，所以设置人群生成规则如下: 25%的人群 : 1楼出发,到达 random(0,20) 25%的人群 : random(0,20)出发,到达1楼 50%的人群 : random(0,20)出发 到达 random(0,20)设人群的人数为 random(1,5)技术选型首先，在所有同学都已经有 C 和 Java学习经验的基础上，最关键的技术瓶颈在于GUI层。经过交流，团队中只有一名同学掌握有GUI 开发的经验，技术栈是 .NET 的 C# + WPF。但是会 C#的只有一人，如果承担了所有的开发工作就会导致效率低下，所以要将程序解耦为算法层和GUI层。后来算法同学决定使用Python。因为程序的数据规模非常低，使用 Python不会造成性能瓶颈，而且可以降低语言层面的复杂度。算法层和GUI层之间的通信，一开始使用了命令行调用、标准输入输出的方式。算法层和GUI层定义了一致的数据结构，并且使用JSON 进行数据传递。但这种方式需要使用者也拥有 Python环境，且该方式在非GUI开发者的电脑上出现异常，难以调试。所以决定转用 HTTP协议，使用 Flask 对算法进行服务端的封装，再使用 Docker部署在服务器上，对外提供API。这样使用者的电脑只需要 .NET Framework环境就可以运行程序。此外，以后还可以使用 Web 端 / QT / Android / IOS等不同前端技术及平台开发运行在不同操作系统上的前端程序。核心算法简介该电梯调度算法主要基于 LOOK调度算法。该算法按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求，当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，从而实现对电梯的有效调度。此外由于电梯1只停在单数层,电梯2只停在双数层,只有电梯3可以停在任意层。这个约束条件看似引入了新的复杂度，其实恰恰让三个电梯失去了联系，大大降低了复杂度。显然，只存在唯一一种调度分配情况，就是单数层到单数层的人由电梯1负责，双数层到双数层的人由电梯2负责，剩下由电梯3负责。3个电梯之间互不干扰，实现非常简便。在后续实践中，也验证了此调度分配情况可以基本完成负载均衡分配，效率高。基本数据类型定义person：搭乘电梯的乘客。其属性包括：come_time（出现的时间）、from_floor（起始楼层）to_floor（目标楼层）、current_floor（当前楼层）、in_which_elevator（所在电梯,可取0，1，2，3，分别指不在电梯中、在第一个电梯中、在第二个电梯中、在第三个电梯中）、is_out（是否完成电梯乘坐）elevator：电梯。其属性包括：current_floor（当前楼层）、move_direction（运行方向）floor：楼层。其属性包括：floor_up_people =[]（上行人群）、self.floor_down_people =[]（下行人群）、up_button（上升按钮）、down_button（下降按钮）算法伪代码//已知第t秒时的状态,进行调度,给出t+1时的状态时间循环（每循环一轮为一秒）//处理person到达事件遍历person数组，如果p.come_time==t（该乘客首次出现）将该乘客分配给对应的楼层 更新对应楼层电梯按钮更新楼层people数组（分为上行人群和下行人群）//处理电梯//对每个电梯，根据电梯的move_direction分类处理（move_direction取0，1，2，分别代表电梯静止、上行、下行）//（这一秒结束）代表continue，不再执行循环体剩下的部分 如果电梯静止遍历所有楼层，检测楼层电梯按钮 如果楼上有人按电梯电梯设置为上行（这一秒结束） 如果楼下有人按电梯电梯设置为下行（这一秒结束） 如果本层楼有人 如果此人上行电梯设置为上行（这一秒结束） 如果此人下行 电梯设置为下行（这一秒结束）如果电梯上行 如果电梯没有对齐某一楼层（如在3.5层） 电梯向上运行半层更新乘客状态（这一秒结束） 如果电梯对齐了某一楼层如果电梯中有乘客抵达目标楼层 更新该乘客的状态（这一秒结束）如果电梯人数已满 电梯向上运行半层 更新乘客状态（这一秒结束）如果楼层有人要进电梯 更新人的状态 更新楼层的状态如果楼层上行person数组为空 楼层上行按钮置False （这一秒结束）如果电梯内人数不为零 向上半层，并且更新乘客状态（这一秒结束）如果电梯内人数为零 如果电梯以上的楼层还有人向上半层，并且更新乘客状态（这一秒结束） 如果电梯以上的楼层没有人电梯状态改为静止（这一秒结束） //下行同理 //其余两个电梯同理软件功能不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是。不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。每天早上，那些差5分钟就迟到的人，在等电梯时，一般会做两件事： 第一，在心里骂电梯慢 第二，在心里暗算着电梯调度如何优化前者可能是写字楼里上班族惯有的精神类疾病，但后者肯定是程序员的职业病。为了上班不扣工资不迟到，我们决定通过调整电梯调度算法来实现对电梯运行载客的优化，以达到节约时间的目的。本程序基于我们的电梯调度算法，计划使用三个电梯同时模拟各层楼随机出现人前往不同楼层来验证本算法的可靠性。并且为了使运行结果明显，本程序还增添了可视化界面，使测试人能够清晰明了的观察本程序的运行情况。运行结果通过分析最终采用3个电梯，1号电梯只停奇数楼层和1楼，2号电梯只停偶数电梯和1楼，三号电梯所有楼层都停。经过多次测试，每次测试时长均超过10分钟，程序运行稳定，能够满足预想的最优化调度电梯，尽可能的缩短人员的等待时间，来实现效率最大化。in.json 运行顺利，没有故障，对实际的电梯调度具有参考意义。结构框图在这里插入图片描述软件流程图在这里插入图片描述在这里插入图片描述运行界面截图在这里插入图片描述在这里插入图片描述在这里插入图片描述软件测试及截图测试文件为algorithm_test.py文件。该文件为测试算法的一个测试文件，读取test_json文件夹中的测试文件，调用算法运行，与正确结果进行对比，相同returntestsuccess。交互选择初始人为设定乘楼梯人的属性（come_time,from_floor,to_floor,current_floor,in_which-elevator,is_out）,把设定的属性写在test_json文件夹中的in1.json和in2.json文件中，把正确的结果写在该文件夹下的out1.json和out2.json文件中。在这里插入图片描述在这里插入图片描述♻️ 资源在这里插入图片描述大小： 1.33MB➡️ 资源下载：https://download.csdn.net/download/s1t16/87390787————————————————版权声明：本文为CSDN博主「神仙别闹」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/s1t16/article/details/129314916 -
安排电影院座位如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[i]=[3,8] ，它表示第 3 行第 8 个座位被预约了。请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。示例 1：输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]输出：4解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，橙色的连续座位表示一个 4 人家庭。 1 2 3解法：位运算判断解题思路： 其实思路很简单，每行最多能容纳两个四人家庭，而第一个位置跟最后一个位置并不会对结果造成影响所以我们用一个8位的数字来进行判断，当第i个位置被预定之后，我们就将i-2位的数字变成1，没被预定即为0，然后将该数字跟当前行用一个哈希表联系起来当预定数字全部遍历完之后，我们只要取出哈希表中的值进行以下操作即可判断是否能容纳四人家庭 跟11110000按位或计算，如果结果仍是11110000,说明四个0的位置可以容纳一个四人家庭 跟11000011按位或计算，同理 跟00001111按位或计算，同理完整代码：class Solution { public int maxNumberOfFamilies(int n, int[][] reservedSeats) { int left = 0b11110000; int middle = 0b11000011; int right = 0b00001111; Map <Integer, Integer> occupied = new HashMap <Integer, Integer> (); for (int[] seat: reservedSeats) { if (seat[1] >= 2 && seat[1] <= 9) { int origin = occupied.containsKey(seat[0]) ? occupied.get(seat[0]) : 0; int value = origin | (1 << (seat[1] - 2)); occupied.put(seat[0], value); } } int ans = (n - occupied.size()) * 2; //seat[1] = 1 || seat[1] = 10的就是坐两组家庭的，他们不会出现在哈希表中 for (Map.Entry <Integer, Integer> entry : occupied.entrySet()) { int row = entry.getKey(), bitmask = entry.getValue(); if (((bitmask | left) == left) || ((bitmask | middle) == middle) || ((bitmask | right) == right)) { ++ans; // 每一排座位只能坐一组家庭，因为出现在哈希表表示在[2,9]至少有一个座位被预约了 } } return ans; }} 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心得体会其实看到这道题我就觉得挺简单的，但是没想到用哈希表和按位或计算来简化代码，用了一大堆if语句，后面受不了了就看了题解————————————————版权声明：本文为CSDN博主「jump_into_zehe」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/jump_into_zehe/article/details/107544321
-
写在前面GitHubTensorFlow原文档TensorFlow版本：2.3引言Keras的Tokenizer是一个分词器，用于文本预处理，序列化，向量化等。在我们的日常开发中，我们经常会遇到相关的概念，即token-标记、tokenize–标记化以及tokenizer–标记解析器。Tokenizer类允许通过将每个文本转换为整数序列（每个整数是字典中标记的索引）或转换成矢量（其中每个标记的系数可以是二进制的）的矢量化语料库，基于单词数 ，基于TF-IDF等等。形如如下使用创建方式：tf.keras.preprocessing.text.Tokenizer( num_words=None, filters='!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~\t\n', lower=True, split=' ', char_level=False, oov_token=None, document_count=0, **kwargs) 1 2 3 4 5 6 7 8 9 10参数 num_words：根据单词频率排序，保留前num_words个单词，即仅保留最常见的num_words-1个单词 filters: 一个用于过滤的正则表达式的字符串，这个过滤器作用在每个元素上，默认过滤除‘`’字符外的所有标点符号，制表符和换行符 lower：boolean值， 标记是否将文本转换为小写 split：字符串值， 分词分隔符 char_level：如果为True，则进行字符级别的分词 oov_token：如果给出的话，它将被添加到word_index中，并用于在text_to_sequence调用期间替换词汇外的单词，即用来补充原文本中没有的词。默认情况下，将删除所有标点符号，从而将文本转换为以空格分隔的单词序列（单词可能包含’字符，如I’am）， 然后将这些序列分为标记列表，并将它们编入索引或向量化。注意力， 0是保留索引，不会分配给任何单词。所以科学使用Tokenizer的方法是，首先用Tokenizer的 fit_on_texts 方法学习出文本的字典，然后word_index 就是对应的单词和数字的映射关系dict，通过这个dict可以将每个string的每个词转成数字，可以用texts_to_sequences，这是我们需要的，然后通过padding的方法补成同样长度，在用keras中自带的embedding层进行一个向量化，并输入到LSTM中。方法 fit_on_texts(texts) ： 参数 texts：要用以训练的文本列表。 返回值：无。 texts_to_sequences(texts) ： 参数 texts：待转为序列的文本列表。 返回值：序列的列表，列表中每个序列对应于一段输入文本。 texts_to_sequences_generator(texts) ： 本函数是texts_to_sequences的生成器函数版。 参数 texts：待转为序列的文本列表。 返回值：每次调用返回对应于一段输入文本的序列。 texts_to_matrix(texts, mode) ： 参数 texts：待向量化的文本列表。 参数 mode：‘binary’，‘count’，‘tfidf’，‘freq’ 之一，默认为 ‘binary’。 返回值：形如(len(texts), num_words) 的numpy array。 fit_on_sequences(sequences) ： 参数 sequences：要用以训练的序列列表。 返回值：无 sequences_to_matrix(sequences) ： 参数 sequences：待向量化的序列列表。 参数 mode：‘binary’，‘count’，‘tfidf’，‘freq’ 之一，默认为 ‘binary’。 返回值：形如(len(sequences), num_words) 的 numpy array。 get_config: 将标记器的配置返回为Python字典，标记器使用的字数字典被序列化为纯JSON，以便其他项目可以读取配置 返回值：带有tokenizer配置的Python字典 to_json： 返回包含标记器配置的JSON字符串，要从JSON字符串加载标记器，请使用keras.preprocessing.text.tokenizer_from_json(json_string)。 返回值：包含标记器配置的JSON字符串属性 word_counts: 字典，将单词（字符串）映射为它们在训练期间出现的次数。仅在调用fit_on_texts之后设置。 word_docs: 字典，将单词（字符串）映射为它们在训练期间所出现的文档或文本的数量。仅在调用fit_on_texts之后设置。 word_index: 字典，将单词（字符串）映射为它们的排名或者索引。仅在调用fit_on_texts之后设置。 document_count: 整数。分词器被训练的文档（文本或者序列）数量。仅在调用fit_on_texts或fit_on_sequences之后设置示例from tf.keras.preprocessing.text import Tokenizer# Using TensorFlow backend.# 创建分词器 Tokenizer 对象tokenizer = Tokenizer()# texttext = ["今天 北京 下 雨 了", "我 今天 加班"]# fit_on_texts 方法tokenizer.fit_on_texts(text)# word_counts属性tokenizer.word_counts# OrderedDict([('今天', 2),# ('北京', 1),# ('下', 1),# ('雨', 1),# ('了', 2),# ('我', 1),# ('加班', 1)])# word_docs属性tokenizer.word_docs# defaultdict(int, {'下': 1, '北京': 1, '今天': 2, '雨': 1, '了': 2, '我': 1, '加班': 1})# word_index属性tokenizer.word_index# {'今天': 1, '了': 2, '北京': 3, '下': 4, '雨': 5, '我': 6, '加班': 7}# document_count属性tokenizer.document_count# 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需要注意的点是，由于书写习惯，英文文本的单词之间是用空格隔开的，split=' ' 这个参数可以直接对英文文本进行空格分词。但是对中文不行，因此使用 tokenizer.fit_on_texts(text) 时，text如果是英文文本，可以直接 text = ["Today is raining.", "I feel tired today."] ，但是text是中文文本的话，需要先将中文文本分词再作为输入text： text = ["今天 北京 下 雨 了", "我 今天 加班"]，因此，keras的Tokenizer对于英文文档可以做分词+嵌入 两步，对于中文的话，其实只有嵌入这步。如下：from tf.keras.preprocessing.text import Tokenizerfrom tf.keras.preprocessing.sequence import pad_sequences# 1. 创建分词器 Tokenizer 对象tokenizer = Tokenizer() # 里面的参数可以自己根据实际情况更改# 2. 整理整体语料，中文需空格分词text = ["今天 北京 下 雨 了", "我 今天 加班"]# 3. 将Tokenizer拟合语料，生成字典，形成新的tokenizertokenizer.fit_on_texts(text)# 4. 保存tokenizer，避免重复对同一语料进行拟合import joblibjoblib.dump(tokenizer, save_path)# 5. 整合需要做嵌入的文本，中文需要空格分词new_text = ["今天 回家 吃饭", "我 今天 生病 了"]# 6. 将文本向量化list_tokenized = tokenizer.text_to_sequence(new_text)# 7. 生成训练数据的序列X_train = pad_sequences(list_tokenized, maxlen=200)————————————————版权声明：本文为CSDN博主「BoCong-Deng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/DBC_121/article/details/108038858
-
写在前面如果觉得写得好，或者有所帮助，记得点个关注和点个赞，不胜感激！我发现最近经常会遇到一些需要通过数学分析去解决的问题，做的时候想着各种方法，然后看到题解，发现可以用数学分析的方式，找到非常快的解决办法，整个人就emmmmm了，所以这里开这篇博文，用来记录自己碰到的可以用数学分析的方式解决的算法问题，不断更新。“树根”相关问题“树根”在维基百科的定义如下：在数学中，数根(又称位数根或数字根Digital root)是自然数的一种性质，换句话说，每个自然数都有一个数根。数根是将一正整数的各个位数相加（即横向相加），若加完后的值大于10的话，则继续将各位数进行横向相加直到其值小于十为止，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于10，则7为54817的数根。那么“树根”又有什么用途呢？数根可以计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。另外，数根也可以用来判断数字的整除性，如果数根能被3或9整除，则原来的数也能被3或9整除。接下来讨论我们怎么求出树根。我们把 1 到 30 的树根列出来。原数: 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数根: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 1 2可以发现数根 9 个为一组， 1 - 9 循环出现。我们需要做就是把原数映射到树根就可以，循环出现的话，想到的就是取余了。结合这个规律，对于给定的 n 有三种情况。 n 是 0 ，数根就是 0。 n 不是 9 的倍数，数根就是 n 对 9 取余，即 n mod 9。 n 是 9 的倍数，数根就是 9。我们可以把两种情况统一起来，我们将给定的数字减 1，相当于原数整体向左偏移了 1，然后再将得到的数字对 9 取余，最后将得到的结果加 1 即可。原数是 n，树根就可以表示成 (n-1) mod 9 + 1，可以结合下边的过程理解。原数: 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偏移: 0 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取余: 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 数根: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 1 2 3 4所以，求一个数的树根，一句代码就可以实现，即(num - 1) % 9 + 1;，这里给出一个题目，一句代码即可。在这里插入图片描述public int addDigits(int num) { return (num - 1) % 9 + 1;} 1 2 3计算阶乘0的个数这个我之前单独写过一篇文章，这里就不赘述了，地址。四平方和定理四平方和定理，意思是任何正整数都能表示成四个平方数的和。少于四个平方数的，像 12 12 12 这种，可以补一个 0 0 0 也可以看成四个平方数， 12 = 4 + 4 + 4 + 0 12 = 4 + 4 + 4 + 0 12=4+4+4+0。知道了这个定理，对于题目要找的解，其实只可能是 1 , 2 , 3 , 4 1, 2, 3, 4 1,2,3,4 其中某个数。Legendre’s three-square theorem ，这个定理表明，如果正整数 n 被表示为三个平方数的和，那么 n n n 不等于 4 a ∗ ( 8 b + 7 ) 4^a*(8b+7) 4a∗(8b+7)， a a a 和 b b b 都是非负整数。换言之，如果 n = = 4 a ∗ ( 8 b + 7 ) n == 4^a*(8b+7) n==4a∗(8b+7) ，那么他一定不能表示为三个平方数的和，同时也说明不能表示为一个、两个平方数的和，因为如果能表示为两个平方数的和，那么补个 0 0 0，就能凑成三个平方数的和了。一个、两个、三个都排除了，所以如果 n = = 4 a ∗ ( 8 b + 7 ) n == 4^a*(8b+7) n==4a∗(8b+7)，那么 n n n 只能表示成四个平方数的和了。所以代码的话，我们采取排除的方法。 首先考虑答案是不是 1 1 1，也就是判断当前数是不是一个平方数。 然后考虑答案是不是 4 4 4，也就是判断 n 是不是等于 4 a ∗ ( 8 b + 7 ) 4^a*(8b+7) 4a∗(8b+7)。 然后考虑答案是不是 2 2 2，当前数依次减去一个平方数，判断得到的差是不是平方数。 以上情况都排除的话，答案就是 3 3 3。在这里插入图片描述public int numSquares(int n) { if (isSquare(n)) { return 1; } int temp = n; while (temp % 4 == 0) { temp /= 4; } if (temp % 8 == 7) { return 4; } for (int i = 1; i * i < n; i++) { if (isSquare(n - i * i)) { return 2; } } return 3;}private boolean isSquare(int n) { int sqrt = (int) Math.sqrt(n); return sqrt * sqrt == n;}————————————————版权声明：本文为CSDN博主「BoCong-Deng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/DBC_121/article/details/106218081
-
目录•写在前面•什么是编辑距离？•思路•思路可视化•代码实现•写在前面编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。最简单的方法是检查所有可能的编辑序列，从中找出最短的一条。但这个序列总数可能达到指数级，但完全不需要这么多，因为我们只要找到距离最短的那条而不是所有可能的序列。这个概念是由俄罗斯科学家Vladimir Levenshtein在1965年提出来的，所以也叫 Levenshtein 距离。总是比较相似的，或多或少我们可以考虑编辑距离。我们在解决这个问题中，使用动态规划的思想进行求解。•什么是编辑距离？这里给一个题目的描述：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作。 插入一个字符 删除一个字符 替换一个字符为了更好的理解，我这里给出两个示例，帮助理解这个概念示例一： 输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')示例二： 输入: word1 = "intention", word2 = "execution" 输出: 5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')•思路我们的目的是让问题简单化，比如说两个单词 horse 和 ros 计算他们之间的编辑距离 D，容易发现，如果把单词变短会让这个问题变得简单，很自然的想到用 D[n][m] 表示输入单词长度为 n 和 m 的编辑距离。具体来说，D[ i ][ j ] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。更通俗的理解，假设我们可以使用d[ i , j ]个步骤（可以使用一个二维数组保存这个值，使用动态规划的思想），表示将串s[ 1…i ] 转换为串t [ 1…j ]所需要的最少步骤个数，那么，在最基本的情况下，即在 i 等于 0 时，也就是说串 s 为空，那么对应的d[ 0 , j ] 就是 增加 j 个字符，使得 s 转化为 t，在 j 等于 0 时，也就是说串 t 为空，那么对应的 d[ i, 0] 就是 减少 i 个字符，使得 s 转化为 t。更一般的情况，加一点动态规划的想法，我们要想得到将 s[1..i] 经过最少次数的增加，删除，或者替换操作就转变为 t[1..j]，那么我们就必须在之前可以以最少次数的增加，删除，或者替换操作，使得现在串 s 和串 t 只需要再做一次操作或者不做就可以完成 s[1..i] == t[1..j] 的转换。所谓的“之前”分为下面三种情况： 要得到 s[1…i] == t[1…j-1]，需要 k 个操作 要得到 s[1..i-1] == t[1..j]，需要 k 个操作 要得到 s[1…i-1] == t [1…j-1]，需要 k 个操作在上面的这三种情况的基础下，我们需要得到 s[1..i] == t[1..j] ，我们分别给出解决思路，如下 第1种情况，只需要在最后将 t[1…j-1] 加上 s[i] 就完成了匹配，这样总共就需要 k+1 个操作。 第2种情况，只需要在最后将 s[1..i-1] 加上 t[j] 就完成了匹配，所以总共需要 k+1 个操作。 第3种情况，只需要在最后将 s[ i ] 替换为 t[ j ]，使得满足 s[1..i] == t[1..j]，这样总共也需要 k+1 个操作。特别注意：而如果在第3种情况下，s[i]刚好等于t[j]，那我们就可以仅仅使用k个操作就完成这个过程。最后，为了保证得到的操作次数总是最少的，我们可以从上面三种情况中选择消耗最少的一种最为将s[1..i]转换为t[1..j]所需要的最小操作次数。我们把储存k的二维数组命名为 D[ ][ ] ，显而易见，当我们获得 D[i-1][j]，D[i][j-1] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。如果两个子串的最后一个字母相同，即word1[i] = word2[i] 的情况下：D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1]-1)如果两个子串的最后一个字母不相同，即word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同：D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1])•思路可视化在上面的思路描述下，我们大致能够理解了，当然，如果还是有点迷糊的，这里我将思路用表格一步一步的表示出来，帮助理解。首先我们先初始化一个二维数组，如下。“.” 代表空串。第一行和第一列按照个数进行初始化，这一步要想明白，想明白了之后就好理解了。如果两个子串的最后一个字母相同，即word1[i] = word2[i] 的情况下：D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1]-1)，图形如下。如果两个子串的最后一个字母不相同，即word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同：D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1])，图形如下。最后我们会得到如下的结果，二维数组最后的 3 就是我们的答案。•代码实现 public int minDistance(String word1, String word2){ int n = word1.length(); int m = word2.length(); if(n * m == 0) return n + m; int[][] d = new int[n + 1][m + 1]; for (int i = 0; i < n + 1; i++){ d[i][0] = i; } for (int j = 0; j < m + 1; j++){ d[0][j] = j; } for (int i = 1; i < n + 1; i++){ for (int j = 1; j < m + 1; j++){ int left = d[i - 1][j] + 1; int down = d[i][j - 1] + 1; int left_down = d[i - 1][j - 1]; if (word1.charAt(i - 1) != word2.charAt(j - 1)) left_down += 1; d[i][j] = Math.min(left, Math.min(down, left_down)); } } return d[n][m];}————————————————版权声明：本文为CSDN博主「BoCong-Deng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/DBC_121/article/details/104198838
-
写在前面的话偶尔出来发个大招谨以此篇献给我最爱的grandpa, 你知道的没有你就没有我。我觉得我对你说我爱你说的太少了。只有你会在我发烧时候每隔5分钟来摸摸我的脑袋。为我跑遍整个昆明城买我最喜欢的食物，为我跑遍整个昆明城帮我办公交卡，在我人生低谷，不吃不喝的时候濒临奔溃的时候一直安安静静的陪我哭，帮我想办法，让我活过来。只有你，会为我剪报纸，帮我搜集高考每一所学校的录取学校，做成美美的小册子。我上班太辛苦了，你总是说宝宝，我们家不缺钱，不用这么拼，外公养你一辈子，你在家给我做做饭就够了，钱够花就行。我初中赖床，不起床复习，你总是把我吼起来，你说你看看你上次年纪第三，这次考第五，都下降了，咱们能严格要求下自己么。我上班起不来，我叫你叫我起床，你说几点，我说8点，你总是说让你没有成就感，哪有人8点还要人叫起床的。我出国交流，回家躺倒床上就睡，你总是提着拖把闯进来，把我拎起来，问我为什么还不复习雅思。为什么不好好准备考试。我每次躺倒床上没几分钟，你就过来闹觉，我每次都是装作听不见。谢谢你在初中的时候一直教我电路图，我们一起做插座，一起动手安装家具，我们一起卖废品，一起收集瓶子，一起卖废报纸，一起去购物，你总是喜欢坐在超市的沙发上享受一会。你喜欢偷怕我和外婆。所以我叫你冠希哥。我总是用脚戳你，你一趟在沙发上。你总是倔强，不许我乱花钱，自己动手做床。我们一起种了树，很多树，家里很美，我们种了很多花。你帮我做镜子，还把我小学二年级的照片黏在后面，我说干嘛要粘这么马肯头的一张，你说，我孙女是全世界最美的。我用你手机照了一张相，你见人就炫耀，你看，我孙女是不是全世界最美的小姑娘，这么标志，简直是遗传外婆的所有优点。哪有小孩子5岁都不断奶，因为都是你惯的，你每天晚上都要给我起来煮奶。我们一起吹泡泡，一起喂鸡，我帮你洗你的臭袜子，你背着我每周二去集市买大白兔，搞的我一口虫牙。你每天吃饭都会出脑筋急转弯给我。你说我们这臭脾气很像，对呀，我不像你像谁，我是你骄傲，这么会这么轻易让人超越。我们一直就是这么霸气侧漏，我们不用逼自己变优秀。你跟我开家长会总是在拉自己的胡子。哈哈，你还从床上睡到掉下来，你真的好笨！我知道的血液就是你血脉的延续，所以我做每一件事都是你的标识。我会把我做的每一件事情都做到极致，跟自己约定，等明年的时候，我会在全球最好的会议上亲自告诉最顶尖的科研人员，我会做最好的研究，用最踏实的态度活好每一天，那是因为你。你说如果你接受和我一样的教育，你会成为比我厉害一百倍的科学家，我说，你会。我跟你开玩笑说，外公，你这么厉害，你一定能比屠呦呦厉害。以后我们家都靠你养了，你也去发明个什么青蒿素，完全不是问题。外公，我要让全世界看见，你的血液里面最闪光的所有宝藏。I promise。在我心跳停止的之前，我会努力做到让全世界为你致敬，把你所有美好的品质发挥到极致。你说的，我是你的骄傲，我会一直是你最好的骄傲。always and forever, we are family, I love you, always and forever.我说你是全世界最聪明的老爷爷，你这么努力，你这么能干，你是我的骄傲，我会加油。你要好好照顾自己，I miss you.感觉自己真的很任性，一次一次说我是为自己的梦想，每次都不顾一切不考虑你的年纪，让我比同龄人慢了很多，你总是这么倔，你就为给我省钱不好好照顾自己。我自己也不好，没有固执的带你去看医生，没有固执给你买我所有想买给你的东西。你总是嫌我品味差，给你买的鞋子难看。给你买的皮鞋你一次都没有穿过。对不起，对不起，对不起。我这么不好，我这么不好，固执，倔强，蛮横，执拗，你还是这么一直一直很好很好的给我全世界最好的爱。感觉自己欠了外公10年的时光。我会努力，明年我就在家里最好的地方买一幢别墅给外婆，不用让你再去爬楼梯，我会给你买最好的地方，让你可以每天可以看到八百里滇池的日出日落，每天都可以吹吹海风。我们一直是家人对不对，I love you.好像图论和树在计算机的数据结构中，都有种魔咒，好难，代码也不好写。我觉得难的是心态，要是预先给我们自己定了一个这个东西很难的调调，然后我们永远做不好这事。只要用心，没有什么是我们不可以实现的，我们做的每一件事就是为了创造奇迹而存在的。这是我外公教我的，他每天都是这么实践的。图的定义图（graph）G=（V，E）由顶点（vertex）的集V和边（Edge）的集E组成。顶点代表了对象，在示意图中我们使用点或圆来表示它；边代表了两个对象的连接关系，在示意图中我们使用连接两顶点的线段来表示。有时也把边称作弧（arc），如果点对（v，w）是有序的，那么图就叫做有向的图（有向图）。如果点对(v,w)是无序的，那么图就叫做无向的图（无向图）。简单的讲，边没有指向性的图叫做无向图，边具有指向性的图叫做有向图。顶点v和w邻接（adjacent）当且仅当（v，w）属于E。我们可以给边赋予各式的属性，比如权值（cost）。权值可以表示从一个顶点到另一个顶点的距离，也可以表示一个顶点到另一个顶点说话费的代价（比如时间、金钱等）。一个边上带权值的图称为网络（network）。如果无向图中从每一个顶点到其他每个顶点都存在一条路径，则称该无向图是连通的（connected）。具有这样性质的有向图称为是强连通的的（strongly connected）。如果有向图不是强连通的，但它的基础图（underlying graph）（也就是其弧上去掉方向说形成的图）是连通的，那么称该有向图是弱连通的（weakly connected）。完全图（complete graph）是其每一对顶点间都存在一条边的图。这里写图片描述度（degree）指的是顶点v的边的条数。这里写图片描述如果具有n个顶点，e条边的图G的顶点i的度为di，则G的边数为：$ e =\frac { \sum_{0}^{n-1} d_i} {2} $这个是针对无向图来说的。我们以上面这个图来详细的说明一下整个问题：这里写图片描述我们给每个节点编号根据每个节点对应的度来求这个图的边：这里写图片描述刚好是7。这个高中的时候学欧拉公式应该很熟练了（新教材被删减了，我又暴露年龄了），因为针对每一条边，它的每天边被每个顶点重复利用了一次。对于边1-2和变2-1其实是相同的事情。所以在这里我们是需要除以二的。但是对于有向图，我们只需要计算每个顶点的出度或者是入度就可以知道这个图总共是有多少条边。这里写图片描述这《数据结构与算法C语言版》的这本书中这个比较经典的图形，我们计算这个图形的边，同样可以先把它看成是无向图。按照上面的公式来计算：这里写图片描述又或者你可以根据这个图的出度或者是入度中的任意一个来计算，下面我们选择的是出度来计算这个有向图的边。这里写图片描述图的存储表示方式图主要有3种常用的存储表示方式：邻接矩阵（adjacency matrices），邻接表（adjacency lists），邻接多重表（adjacency multilists）##邻接矩阵邻接矩阵使用|V|∗|V|的二维数组来表示图。g[i][j]表示的是顶点i和顶点j的关系。1）因为在无向图中，我们只需要知道顶点i和顶点j是否是相连的，因此我们只需要将g[i][j]和g[j][j]设置为1或是0表示相连或不相连即可。如下图所示。这里写图片描述2）而在有向图中，我们只需要知道是否有从顶点i到顶点j的边，因此如果顶点i有一条指向顶点j的边，那么g[i][j]就设为1，否则设为0。有向图与无向图不同，并不需要满足g[i][j]=g[j][i]。这里写图片描述3）在带权值的图中，g[i][j]表示的是顶点i到顶点j的边的权值。由于在边不存在的情况下，如果将g[i][j]设为0，就无法和权值为0的情况区分开来，因此选取适当的较大的常数INF（只要能和普通的权值区别开来就可以了），然后令g[i][j]=INF就好了。当然，在无向图中还是要保持g[i][j]=g[j][i]。在一条边上有多种不带权值的情况下，定义多个同样的|V|∗|V|数组，或者是使用结构体或类作为数组的元素，就可以和原来一样对图进行处理了。这里写图片描述使用这种存储方式，可以很方便地判断任意两个顶点之间是否有边以及确定顶点的度，这也是这种表示法最大的优势。任意一个顶点i的度等于其邻接矩阵中顶点i所对应的行中的数字之和：$ \sum_{j=0}^{n-1} g[i][j] $在这种表示法中扫描所有边至少需要O(n2)时间，因为必须检查矩阵中的n2−n个元素才能确定图中边的条数（邻接矩阵对角线上的n个元素都是0，因此不用检查。又因为无向图的邻接矩阵是对称的，实际只需检查邻接矩阵的一半元素）。通常把边很少的图成为稀疏图（sparse graphs）图的同构我们先看一个简单的例子：图一对于上面这个简单图，我们用邻接矩阵来表示这个图，得到的形式如下所示：这里写图片描述 首先，我们需要明确一点，图的邻接矩阵是不唯一，取决于顶点的排列顺序. 无向图的邻接矩阵是对称的定义同构的图：本质上相同的图，表示了类似的集合和关系这里写图片描述下面两个图是同构的：这里写图片描述函数f满足f(u1)=v1,f(u2)=v4 ,f(u3)=v3 ,f(u4)=v2 ,它是V和W之间的一一对应。为了看出这个对应保持相邻关系，注意G里相邻的顶点是u1和u2， u1和u3，u2和u4，以及u3和u4，由f(u1)=v1和f(u2)= v4 ，f(u1)=v1 和f(u3)= v3 ，f(u2)= v4和f(u4)= v2 ，以及f(u3)= v3和f(u4)= v2所组成的每一对顶点都是在H里相邻的。图的同构是一个一一对应关系，但是子图同构在严格的意义上讲不能叫做映射。why?我们先说明完图的同构问题. 同构的充分条件，可用于判定同构 给出一个顶点的一一对应，按相应的顺序求出邻接矩阵 邻接矩阵相同 ==》那么图是同构 同构的必要条件，可用于判定不同构 （1）顶点数相同 （2）边数相同 （3）顶点度相同 （4）同度顶点构成的子图都同构这里写图片描述G和H都具有5个顶点和6条边。不过，H有1度顶点e而G没有1度顶点。我们可以看出在H这个图中节点e只有一个度，在图G中我们根本找不到节点的度是1的。所以G与H是不同构的。重要的事情多说几遍，我们判断两个图是不是同构的，可以根据节点的度来判断 .这里写图片描述图G和H都具有8个顶点和10条边。它们都具有4个2度顶点和4个3度顶点。因为这些不变量都相同，所以可能想到它们是同构的.然而G和H不是同构的。为了看明白这一点，注意到因为在G里deg(a)=2，所以a必然对应于H里的t，u，x或y，这是因为这些顶点是H里的2度顶点。不过， H里的这4个顶点中每一个都与H里另一个2度顶点相邻，但是在H里a却不是这样的。图同构的，那么度相同的节点构成的子图也是同构的。我们看一下这两个图中度为三的节点构成的子图是什么样子的：如下图所示：这里写图片描述根据上图所示，这两个图明显是不同构。————————————————版权声明：本文为CSDN博主「君的名字」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/chichoxian/article/details/52674252
-
写在前面的话k-means 算法是一个聚类的算法 也就是clustering 算法。是属于无监督学习算法，也是就样本没有label(标签)的算分，然后根据某种规则进行“分割”， 把相同的或者相近的objects 物体放在一起。在这里K就是我们想要分割的的聚类的个数。当然了，很多资料都会说这个算法吧，毕竟简单粗暴可依赖算法描述首先我们有以下的几个点 A1 (2,10)A2 (2,5)A3 (8,4)A4 (5,8)A5 (7,5)A6 (6,4)A7 (1,2)A8 (4,9)这个算法不能帮助我们自动分类，所以我们需要指定我们需要的个数。其实在很多实际应用当中，我们很难知道我们的数据是什么分布的，应该分成几类比较好。这也是k-means自身的一个缺陷，所以不能帮助我们自动的聚类。注：如果我在本文中说了分类，其实是分割的意思，我想表达的意思是聚类。中文和英文切换，在意思上表达真的有点差距。现在假设我们需要把上面的数据点分成三类。我们需要遵循下面的几个步骤 选取三个类的初始中心 计算剩余点到这三个中心的距离 将距离中心点距离最短的点归为一类 依次划分好所有的数据点 重新计算中心 重复2-5 个步骤，直到中心点不会在变化为止现在看完步骤，其实可能会有一些疑问：1. 怎么选择我们的初始中心点？2. 怎么计算点之间的距离呢。选择中心点中心点怎么选择，一般情况下我们是随机的从我们的数据集中选择的。当然还会有其他的方法，我们在之后的文章中可能会讨论。如果我还有时间去写的话，一般我会有时间写的。甚至这个中心点的选择可以是完全随机的，甚至都不需要从我们的数据集中选取，在这里，我们的数据集是一个二维的，所以我们可以选择在XY坐标上的任意三个点，随你高兴都是可以的注意：中心点的选取不同，最后的聚类结果可能大不相同在这里我们假设我们的三个初始点是A，在这里我们选取的初始点是A1，A4，A7在这里我们定义两个点之间的距离用曼哈顿聚类距离，也可以叫做城市街区距离。在这里插入图片描述在这里我们是二维坐标，所以我们可以按照下面这个公式：在这里插入图片描述下面是一个例子：在这里插入图片描述计算的一般过程：我们先看第一轮：在这里插入图片描述选取距离最近的归为一类这个时候我们得到的聚类的结果：在这里插入图片描述得到了第一轮的结果我们需要重新的计算每个聚类的中心cluster1对于第一个聚类只有一个点所以它的聚类的中心就是它自己。Cluster2X:(8+5+7+6+4)/5 = 6Y:(4+8+5+4+9)/5 = 6这个时候它的中心就变成了（6,6）Cluster3：X：（2+1）/2 = 1.5Y：（5+2）/2 = 3.5这个时候在进行第二轮迭代：在这里插入图片描述这个时候再次计算中心：在这里插入图片描述这个时候用我们的新的中心再来计算一遍：在这里插入图片描述这个时候我们在重新根据新的聚类重新计算我们的中心：在这里插入图片描述得到新的点之后我们在重新计算新的聚类在这里插入图片描述这个时候发现和上一次的结果是一致的，这个时候我们就可以停止我们的算法了。下面我们来看一下这个迭代过程的图谱。这个是我们的的初始过程在这里插入图片描述之后是我们选取中心点：在这里插入图片描述依次迭代的过程：在这里插入图片描述在这里插入图片描述————————————————版权声明：本文为CSDN博主「君的名字」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/chichoxian/article/details/84075128
上滑加载中
推荐直播
-
华为云IoT开源专家实践分享：开源让物联网平台更开放、易用2024/05/22 周三 16:30-18:00
张俭 华为云IoT DTSE技术布道师
开源，意味着开放、共享、互助、共赢。作为万物上云及各行业数字化的物联网底座，华为云IoT积极拥抱开源，借助行业开源的最佳实践，构建可靠、易用的物联网平台，并通过开放南北向SDK，助力开发者快速构建物联网应用。本期直播，华为云IoT开源专家、物联网平台资深“程序猿”张俭，带你了解华为云IoT的开源生态，并手把手教你玩转开源社区！
去报名 -
华为云开发者日·广州站2024/05/23 周四 14:30-17:30
华为云专家团
华为云开发者日HDC.Cloud Day是面向全球开发者的旗舰活动，汇聚来自千行百业、高校及科研院所的开发人员。致力于打造开发者专属的技术盛宴，全方位服务与赋能开发者围绕华为云生态“知、学、用、创、商”的成长路径。通过前沿的技术分享、场景化的动手体验、优秀的应用创新推介，为开发者提供沉浸式学习与交流平台。开放创新，与开发者共创、共享、共赢未来。
去报名
热门标签