前处理网格生成的算法有哪些

A. 谁有数学建模十大算法的详细介绍啊

1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，
同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法）
2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，
而处理数据的关键就在于这些算法，通常使用Matlab作为工具）
3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，
很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现）
4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，
涉及到图论的问题可以用这些方法解决，需要认真准备）
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）
6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法
（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，
但是算法的实现比较困难，需慎重使用）
7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，
当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具）
8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）
9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比
如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）
10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，
这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理）

B. CFD网格生成技术如何入门

强烈不推荐自己从头写网格生成程序。商业软件之所以能拿出来卖钱就是因为它已经把解决方案做的比较完整了，而且结构网格生成已经非常成熟，基本没有什么算法改进的余地了。局部加密如果指的是生成网格时调节网格密度的话，Pointwise和ICEM CFD都有非常完整的支持；如果指的是根据流场自适应加密网格，那么这件事情应该交给solver而不是网格生成程序。如果想要半自动生成网格， 至少ICEM CFD是支持使用脚本参数化生成网格的。至于网格生成效率，我只能说复杂外形生成结构化网格本身就是一件效率不高的事情，和你用什么软件无关。推荐的Gmsh的确是简单网格生成的利器。用脚本生成网格非常快。但是输出的网格似乎只支持以非结构网格的形式存储，不知道答主使用的solver是否支持。如果想尽可能快地上手生成网格，推荐使用Pointwise。自底向上生成网格的思路和一般人的思维方式比较契合。对于一个CAE工程师，他的工作也就只能飞机，汽车，轮船，火箭等等中的一个对于一个干工程的CAE博士或者硕士，可能三到五年工作只能是其中的一个部件了你几年可能就面对这一个部件，还要low到用四面体去划分比如燃气轮机流体工程师毕生面对的都是叶片，所以就有TUROGRID、AUTOGRID分叶片流场结构化网格模块又如电子件传热工程师面对的是总是电子器件，就有ICEPAK这种能自动分结构网格的专业前处理软件。

C. 什么是网格搜索法如何用它来优化学习算法

网格搜索法是指定参数值的一种穷举搜索方法，通过将估计函数的参数通过交叉验证的方法进行优化来得到最优的学习算法。
即，将各个参数可能的取值进行排列组合，列出所有可能的组合结果生成“网格”。然后将各组合用于SVM训练，并使用交叉验证对表现进行评估。在拟合函数尝试了所有的参数组合后，返回一个合适的分类器，自动调整至最佳参数组合，可以通过clf.best_params_获得参数值

D. 不同网格划分软件的方法

开发网格工具主要是软件工程师的工作，仿真应用工程师主要是使用网格软件工具。
网格是有限元分析中很重要的一个因素，从技术方面考虑：
1. 网格的数量影响到求解的精度和效率
2. 网格的质量影响到求解的精度(网格单元是否畸形，网格密度是否合理)
3. 网格的阶次影响到计算精度
4. 不同分析类型对网格类型要求不同(相同的几何，流体，热，结构所需要的网格不同)
5. 复杂几何网格错误难以检查
从以下几个方面介绍前处理器中的网格开发：网格生成算法、网格类型与质量检查、网格加密/自适应网格划分、网格显示、网格开源工具、网格商业工具
结构化网格：结构化网格具有统一的拓扑结构，区域可以划分为规则的单元，节点之间有规律的索引。结构化单元只适合于求解模型简单，几何规则的情况。结构化网格算法也比较简单很容易实现。
非结构化网格：大部分工程案例几何都不规则，网格需要使用非结构化网格。

E. 栅格化的基本实现方法

最基础的栅格化算法将多边形表示的三维场景渲染到二维表面。多边形由三角形的集合表示，三角形由三维空间中的三个顶点表示。在最简单的实现形式中，栅格化工具将顶点数据映射到观察者显示器上对应的二维坐标点，然后对变换出的二维三角形进行合适的填充。 一旦三角形顶点转换到正确的二维位置之后，这些位置可能位于观察窗口之外，也可能位于屏幕之内。裁剪就是对三角形进行处理以适合显示区域的过程。
最常用的技术是Sutherland-Hodgeman裁剪算法。在这种方法中，每次测试每个图像平面的四条边，对于每个边测试每个待渲染的点。如果该点位于边界之外，就剔除该点。对于与图像平的面边相交的三角形边，即边的一个顶点位于图像内部一个位于外部，那么就在交叉点插入一个点并且移除外部的点。 传统的栅格化过程的最后一步就是填充图像平面中的二维三角形，这个过程就是扫描变换。
第一个需要考虑的问题就是是否需要绘制给定的像素。一个需要渲染的像素必须位于三角形内部、必须未被裁掉，并且必须未被其它像素遮挡。有许多算法可以用于在三角形内进行填充，其中最流行的方法是扫描线算法。
由于很难确定栅格化引擎是否会从前到后绘制所有像素，因此必须要有一些方法来确保离观察者较近的像素不会被较远的像素所覆盖。最为常用的一种方法是深度缓存，深度缓存是一个与图像平面对应的保存每个像素深度的二维数组。每个像素进行绘制的时候都要更新深度缓存中的深度值，每个新像素在绘制之前都要检查深度缓存中的深度值，距离观察者较近的像素就会绘制，而距离较远的都被舍弃。
为了确定像素颜色，需要进行纹理或者浓淡效果计算。纹理图是用于定义三角形显示外观的位图。每个三角形顶点除了位置坐标之外都与纹理以及二维纹理坐标 (u,v) 发生关联。每次渲染三角形中的像素的时候，都必须在纹理中找到对应的纹素，这是根据在屏幕上像素与顶点的距离在与纹理坐标相关联的三角形顶点之间插值完成的。在透视投影中，插值是在根据顶点深度分开的纹理坐标上进行的，这样做就可以避免透视缩减（perspective foreshortening）问题。
在确定像素最终颜色之前，必须根据场景中的所有光源计算像素上的光照。在场景中通常有三种类型的光源。定向光是在场景中按照一个固定方向传输并且强度保持不变的光。在现实生活中，由于太阳距离遥远所以在地球上的观察者看来是平行光线并且其衰减微乎其微，所以太阳光可以看作是定向光。点光源是从空间中明确位置向所有方向发射光线的光源。在远距离的物体上的入射光线会有衰减。最后一种是聚光灯，如同现实生活中的聚光灯一样，它有一个明确的空间位置、方向以及光锥的角度。另外，经常在光照计算完成之后添加一个环境光值以补偿光栅化无法正确计算的全局照明效果。
有许多可以用于光栅化的浓淡算法。所有的浓淡处理算法都必须考虑与光源的距离以及遮蔽物体法向量与光照入射角。最快的算法让三角形中的所有像素使用同样的亮度，但是这种方法无法生成平滑效果的表面。另外也可以单独计算顶点的亮度，然后绘制内部像素的时候对顶点亮度进行插值。速度最慢也最为真实的实现方法是单独计算每点的亮度。常用的浓淡模型有 Gouraud shading 和 Phong shading。

F. 什么事结构网格，什么是非结构网格各有什么优缺点

结构化网格：

结构化网格是指网格区域内所有的内部点都具有相同的毗邻单元。

非结构化网格：

非结构化网格是指网格区域内的内部点不具有相同的毗邻单元。

结构化网格优点：

1、实现区域的边界拟合，适于流体和表面应力集中等方面的计算。

2、网格生成的速度快。

3、网格生成的质量好。

4、数据结构简单。

5、对曲面或空间的拟合采用参数化以及样条插值的方法得到，区域光滑，与实际的模型更接近。

结构化网格缺点：

1、比较窄，随着近几年的计算机和数值方法的快速发展，人们对求解区域的复杂性的要求越来越高，在这种情况下,结构化网格生成技术就显得力不从心了。

2、网壳结构可以构成大空间，但当矢高很大时，增加了屋面面积和不必要的建筑空间，增加了建筑材料和能源的消耗。

非结构网络优点：

1、速度快。

2、网格的尺寸比较容易控制。

非结构网络缺点：

1、对边界的恢复比较困难，很可能造成网格生成的失败。

(6)前处理网格生成的算法有哪些扩展阅读：

网格的优点：

网格结构空间刚度大，整体性和稳定性好，有良好的抗震性能和较好的建筑造型效果，适用于各种支承条件和各种平面形状、大小跨度的工业和民用建筑。

网格结构具有多向受力性能和内力重分布的特点，可用于地基条件较差而可能出现不均匀沉降的建筑。

网格结构杆件和节点比较单一，便于制作，安装也较方便。

网格主要采用钢材，结构自重轻，具有用钢量节省的优点。

G. 网格光顺

网格光顺是通过改变结点坐标的方式来提高网格整体质量的一项技术。对于某一个结点来讲，该结点可能位于网格边界或内部，相应的，该结点被称为边界结点或内部结点。通常情况下，为了保持与其他网格之间拓扑相容，网格光顺所能够移动的只能是内部结点，而固定边界结点。

网格光顺最常用的方法是Laplacian光顺，Laplacian光顺是将某一结点移动到与之相邻结点的中心。这种方法，算法简单，程序实现容易，但计算量大。本节介绍的另外一种网格光顺方法是优化平面及曲面三角网格的直接法，该方法的主要思想是通过移动结点使每个三角形都尽可能地趋近于正三角形，从而达到优化网格的效果。

3.5.1.1 直接法

Balendran于1999年提出了优化平面及曲面三角网格的直接法，该方法的主要思想是将网格作为可变形体，在不改变网格拓扑关系的前提下，通过移动结点使每个三角形都尽可能地趋近于正三角形，从而达到优化网格的效果(Balen-dran，1999)。在移动结点时需要注意该结点是否为约束点，所谓约束点即是在生成初始网格和优化时需要保持位置固定的结点，通常情况下，约束点为网格边界结点和内部“硬”点。优化时只能改变非约束点的位置而保持约束点固定不变。

图3.26 Laplacian光顺优化三角形网格实例

H. 数据挖掘干货总结（四）--聚类算法

本文共计2680字，预计阅读时长七分钟

聚类算法

一 、 本质

将数据划分到不同的类里，使相似的数据在同一类里，不相似的数据在不同类里

二 、 分类算法用来解决什么问题

文本聚类、图像聚类和商品聚类，便于发现规律，以解决数据稀疏问题

三 、 聚类算法基础知识

1. 层次聚类 vs 非层次聚类

– 不同类之间有无包含关系

2. 硬聚类 vs 软聚类

– 硬聚类：每个对象只属于一个类

– 软聚类：每个对象以某个概率属于每个类

3. 用向量表示对象

– 每个对象用一个向量表示，可以视为高维空间的一个点

– 所有对象形成数据空间（矩阵）

– 相似度计算：Cosine、点积、质心距离

4. 用矩阵列出对象之间的距离、相似度

5. 用字典保存上述矩阵（节省空间）

    D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}

6. 评价方法

– 内部评价法（Internal Evalution）：

• 没有外部标准，非监督式

• 同类是否相似，跨类是否相异

DB值越小聚类效果越好，反之，越不好

– 外部评价法（External Evalution）：

• 准确度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)

• 精度（Precision）: C11 / (C11 + C21 )

• 召回（Recall）: C11 / (C11 + C12 )

• F值（F-measure）：

β表示对精度P的重视程度，越大越重视，默认设置为1，即变成了F值，F较高时则能说明聚类效果较好。

四 、 有哪些聚类算法

主要分为 层次化聚类算法 ， 划分式聚类算法 ， 基于密度的聚类算法 ， 基于网格的聚类算法 ， 基于模型的聚类算法等 。

4.1 层次化聚类算法

又称树聚类算法，透过一种层次架构方式，反复将数据进行分裂或聚合。典型的有BIRCH算法，CURE算法，CHAMELEON算法，Sequence data rough clustering算法,Between groups average算法,Furthest neighbor算法,Neares neighbor算法等。

凝聚型层次聚类 ：

先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。

算法流程：

1. 将每个对象看作一类，计算两两之间的最小距离；

2. 将距离最小的两个类合并成一个新类；

3. 重新计算新类与所有类之间的距离；

4. 重复2、3，直到所有类最后合并成一类。

特点：

1. 算法简单

2. 层次用于概念聚类（生成概念、文档层次树）

3. 聚类对象的两种表示法都适用

4. 处理大小不同的簇

5. 簇选取步骤在树状图生成之后

4.2 划分式聚类算法

预先指定聚类数目或聚类中心，反复迭代逐步降低目标函数误差值直至收敛，得到最终结果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等

经典K-means：

算法流程：

1. 随机地选择k个对象，每个对象初始地代表了一个簇的中心；

2. 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；

3. 重新计算每个簇的平均值，更新为新的簇中心；

4. 不断重复2、3，直到准则函数收敛。

特点：

1.K的选择

2.中心点的选择

– 随机

– 多轮随机：选择最小的WCSS

3.优点

– 算法简单、有效

– 时间复杂度：O(nkt)

4.缺点

– 不适于处理球面数据

– 密度、大小不同的聚类，受K的限制，难于发现自然的聚类

4.3 基于模型的聚类算法

为每簇假定了一个模型，寻找数据对给定模型的最佳拟合，同一”类“的数据属于同一种概率分布，即假设数据是根据潜在的概率分布生成的。主要有基于统计学模型的方法和基于神经网络模型的方法，尤其以基于概率模型的方法居多。一个基于模型的算法可能通过构建反应数据点空间分布的密度函数来定位聚类。基于模型的聚类试图优化给定的数据和某些数据模型之间的适应性。

SOM 神经网络算法 ：

该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。

SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。

算法流程：

1. 网络初始化，对输出层每个节点权重赋初值；

2. 将输入样本中随机选取输入向量，找到与输入向量距离最小的权重向量；

3. 定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢；

4. 提供新样本、进行训练；

5. 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类结果。

4.4 基于密度聚类算法

只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类，擅于解决不规则形状的聚类问题，广泛应用于空间信息处理,SGC,GCHL，DBSCAN算法、OPTICS算法、DENCLUE算法。

DBSCAN：

对于集中区域效果较好，为了发现任意形状的簇，这类方法将簇看做是数据空间中被低密度区域分割开的稠密对象区域；一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据中发现任意形状的簇。

4.5 基于网格的聚类算法

    基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构（即量化空间）上进行。这种方法的主要优点是它的处理 速度很快，其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但这种算法效率的提高是以聚类结果的精确性为代价的。经常与基于密度的算法结合使用。代表算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。