请教，这个相似度怎么计算？

Ysu2008

[这个贴子最后由Ysu2008在 2012/03/30 03:03pm 第 1 次编辑]

A、B两张大小相同的网格图（网格数相同，宽高一致），两张图都分布着相同数量的点，只是点位置坐标不同。
以A图为目标，移动B图上的点（每次只能移动一个点，且只能移动一格），移动若干次后，B图将完全与目标A图重合。
我想知道的是，在移动过程中产生的中间过渡图，如何比较任意两张图与目标A图的接近程度（或说相似）？

我想用搜索法实现一个推箱子游戏的自动策略求解器。B图中的点是由计算机随机移动的，移动后的图可能会比之前更远离目标A图，如果能比较两张图相对于目标A图的接近程度，就可以提前选择最有可能到达目标的分支，从而引导算法穿过巨大的状态空间。
与此相似的是寻找路径问题（网格世界），给出一个起始点和一个目标点，求解到达目标的最短路径。这相当于A图和B图中各有一个点，在只有一个点的情形下，可以通过计算所谓“曼哈顿距离”来比较两张图对目标的接近程度（起止两点XY坐标差绝对值的和），在有多个起止点的情形下，该怎么计算呢？
我目前采取的办法是：将B图中的一个点依次与A图中的所有点计算曼哈顿距离，取其最小者作为该点的曼哈顿距离，将B图中所有点的曼哈顿距离之和作为该图的曼哈顿距离。但我不知道这样是否有问题，在实际运行过程中，似乎不太理想。

Ysu2008

画图说明。如图中所示，A为目标图，B、C为中间过渡图，C图显然要比B图更接近目标A图。但该如何计算呢？

Ysu2008

A、B两张大小相同的网格图（网格数相同，宽高一致），两张图都分布着相同数量的点，只是点位置坐标不同。
以A图为目标，移动B图上的点（每次只能移动一个点，且只能移动一格），移动若干次后，B图将完全与目标A图重合。
我想知道的是，在移动过程中产生的中间过渡图，如何比较任意两张图与目标A图的接近程度（或说相似）？

drc2000

[这个贴子最后由drc2000在 2012/04/05 04:26pm 第 1 次编辑]

；一:先给各个图中的元素标记符号
目标图A中三元素可认为是(1,0);E(1,3),F(3,2),
过渡图B中三元素可认为是(3,0);E(1,2);F(2,2),
过渡图C中三元素可认为是(0,0);E(1,3),F(3,2),
二：数据标准化：先都减去平均值，再除以标准差。这样数据的平均值都为0，标准差都为1，不同的数据才可以比较。
三：计算相关系数：
(具体公式我需要翻翻概率统计的书……)
相关系数越小，两列元素越接近。
相关系数越大，两列元素离的远。
相关系数ρ=lxy/√（lxx*lyy）
其中xy，xx，yy均为下标