一些简单地想法 - Something TO DO
一些简单地想法
Something TO DO
posted @ 2014年10月10日 16:05
in Multi-Agent Systems
with tags
Nearest neighbor approach
, 965 阅读
简单的基础知识
Nearest neighbor approach
The nearest neighbor algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. In it, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. It quickly yields a short tour, but usually not the optimal one.
These are the steps of the algorithm:
- stand on an arbitrary vertex as current vertex.
- find out the shortest edge connecting current vertex and an unvisited vertex V.
- set current vertex to V.
- mark V as visited.
- if all the vertices in domain are visited, then terminate.
- Go to step 2.
但是此处我们不用最近邻算法，我们采用匈牙利算法来做匹配。
The Ieteration Closest Point Algorithm
写一个小程序作为例子来说明迭代最近点算法在多智能体系统编队中的应用。
六个智能体，可以组成的编队比较多样。组成TEAM队形
1，迭代最近点算法是用来寻找两个点集之间最佳匹配的算法。
2，问题描述：
·Given: 两个相应的点集：$X={x_1,\ldots,x_n}$,$P={p_1,\ldots,p_n}$
·Wanted:求解平移量$T$和旋转矩阵$R$，使得下式平方差的和最小：
\[E(R,T)=\frac{1}{N_p}\sum ^{N_p}_{i=1}||x_i-Rp_i-t||^2\]
其中，$x_i$和$p_i$是对应点集中的点。
3，求解方法：
·首先计算两个点集的几何中心：
\[u_x=\frac{1}{N_x}\sum_{i=1}^{N_x}x_i\]
\[u_p=\frac{1}{N_p}\sum_{i=1}^{N_p}p_i\]
·计算点集中每个点与几何中心的差值：
\[X'=\{x_i-u_x\}=\{x_i'\}\]
\[P'=\{p_i-u_p\}=\{p_i'\}\]
·做一个SVD分解：
令$W=\sum_{i=1}^{N_p}x_i'p_i'^T$,
其中，$U,V\in R^{3\times 3}$ 是正定的，并且$\sigma_1>=\sigma_2>=\sigma_3$是$W$的奇异值。
·后边不加证明的给出定理：
如果$rand(W)=3$，使得$E(R,T)$最优的$R$和$T$是惟一的：
\[R=UV^T\]
\[T=u_x-Ru_p\]
仿真参考：用matlab写的针对3D数据点的匹配仿真【1】。
根据以上仿真改写2D数据点的匹配仿真。
2·然后是实际仿真
应用匈牙利算法的迭代最近点算法
【1】参考文献：http://www.mathworks.com/matlabcentral/fileexchange/27804-iterative-closest-point
2022年8月24日 15:34
Maharashtra SSC Question Paper 2023 Download – Maha 10th Important Question Paper 2023 PDF, SSC Question Paper 2023 Maharashtra Board, Maharashtra, Maharashtra SSC Question Paper 2023 Directorate of Government Examination has been released the Important Question Paper for Secondary School Leaving Certificate Class 10. The SSC examination is set to begin from 1st week of March to last week of March 2023.
2022年8月24日 16:01
HPBOSE 12th New Question Paper 2023 Download, HPBOSE is popular knows as Himachal Pradesh Board Of School Education. HP Board Matric Important Question Paper 2023 It is one of the large board in India. Himachal Pradesh Board is going to conduct Class 12th annual examination for those candidates who have successfully registered for 12th boards exams in 2023.
2023年2月02日 21:32
ISP provides unlimited calls to any network round the clock in all the BSNL broadband plans over fiber and DSL networks, and Here we update the latest BSNL broadband unlimited plans daily across India as and when the update released for home and business tariff, BSNL Broadband Plans So check each plan in detail to opt for best tariff. BSNL broadband plans over DSL and Bharat Fiber technologies are available, we categorize each plan and provide the updated information of all the circles with new plans and tariff.