问题是： 对于两个足够大的图片，判定他们是否完全相同。 如何选用最少的像素点来判断他们完全相同。 对于不完全相同的，又如何通过最少的迭代次数找出所有相同的点？ 因为像素是数据，排列是图像，那么就无法搞出个公式出来，也就没法儿证明是否二阶可导，也就没法证明到底是npc，还是nphard。 就是这个问题，恳请指教!
我很好奇，你为啥要弄这些计算复杂性的东西啊？ 这东西没啥用，只是告诉你算法是属于P还是NP的。然后属于NP的就是无解的... 所以研究计算机理论的人很没劲，一天到晚在研究什么东西是无法解决的... 其实许多算法，都是NP的，但并不能因为NP就不想办法去计算它。
一般是用贪心法来解。例如邮递员问题，是个典型的NP问题。（http://zh.wikipedia.org/zh-sg/旅行推销员问题)。 对于这种问题，很显然贪心法是能解的，但是肯定不是最有解。 一般NP问题的近似解只要是较优解，就能接受了～ 要获得比贪心更好的解，通常需要改进贪心法的局部最优问题， 因此需要用各种迭代算法。比如遗传算法、蚁群算法之类的。 其实说穿了，这类算法的本质都是穷举。
我的意思是，所有的基于搜索的算法的本质，都是穷举。只不过与穷举相比，过滤掉不少不需要的搜索路径。然会根据过滤的方法不同，产生了各种各样的算法，深度优先，广度优先，A*，分支定界，动态规划，遗传、蚁群、退火之类的。 我想知道的是，你具体要弄个什么算法，会有可能是NP，还需要近似解。
什么问题啊？本文的这个图像匹配问题么？这个我不是在另一个thread给出解答了么... 另外什么叫“什么算法可以不定解集元素数”啊？你是指哪些算法对问题规模没有限制吧~ 算法本身对问题的规模是没有限制的。只不过不同的算法对同一个问题需要消耗的时间和空间不同。 从而导致实际不可解。
在图像处理技术中，通常做法可能是先找出每个图片的重心坐标系；把图片在重心上旋转对齐，可能还要加上缩小放大，以及色彩灰度处理。然后可以用二维Fourier变换之类的东西，把图片变成频谱。有了频谱，再用均方差之类的方法来比较两个图片的差异。
这样是不行滴～ 你的方法最大的问题： 重心选择＋旋转缩放，需要估计的参数太多了， 重心在哪里，旋转多少，放缩多少， 任何一个错了，后面就对不上了。 图片匹配算法，一般都是选用旋转、放缩无关的算法来做的。比如： 先做一次小波变化寻找图像边缘 然后分析边缘的拐点，直线特征 最后提取这些特征的位置信息，生成特征描述。 特征描述一般用特征A被哪些特征包围这样的描述方式，从而回避了旋转问题。 然后在一系列特征描述中搜索匹配的图。 最后在候选的图中，做色域上的直方图匹配，确保色彩也是匹配的。 当然我也只是随便想想给出一种方法，可能的方法也不止这一种。
最优化方法的话，只有一个解集，而解集内的元素数即像素点数，是固定的。 可是呢，实际情况是我不知道那两个图有多少相同的像素点数。 而大侠上面的种种方法，基本属于此类。而对于第一个，则是要全部像素点都要处理一遍然后再搞滴。
什么叫尽可能少的像素点.... 任何算法至少要遍历数据集一遍，才能有结果吧。 除非你这个数据集里面前面的数据包含了后面的信息。比如你已知是个排序的队列，那么你可以在不完全遍历所有的数据情况下，找出某个值。 换个说法吧，比如两本500页的书，其中一本里面有若干页是错的。你必须要把整部书都翻一遍，才能找出那些页是不同的。没有任何算法，能让你翻100页就能确定结果。如果有，那就是超能力了...