To enhance the low efficiency of producing the clustering result with given number of clusters by Affinity propagation clustering (AP), the fast multi-grid searching method is proposed. The proposed method uses multi-grid searching to reduce the calling times of AP, and improves the upper bound of preference parameter to reduce the searching scope, so that it can largely enhance the speed performance of AP under given number of clusters. The experimental results show that the proposed method is very effective and reduces the running time by 22%-90%, compared with the existing method.