基于并行搜索和快速插入的算法

　　針對(duì)串行A*算法時(shí)間性能較差的問(wèn)題，提出了一種基于并行搜索和快速插入（ PSFI）的算法。首先，研究了共享存儲(chǔ)平臺(tái)上的常見(jiàn)并行啟發(fā)式搜索算法；然后，通過(guò)使用一種延遲的單表搜索（ DSTS）方法和新的數(shù)據(jù)結(jié)構(gòu)，改進(jìn)了串行算法；其次，在此基礎(chǔ)上，設(shè)計(jì)出一種基于共享存儲(chǔ)平臺(tái)的并行算法；最后，采用OpenMP加以實(shí)現(xiàn)。對(duì)24數(shù)碼問(wèn)題的測(cè)試結(jié)果表明，改進(jìn)的串行和并行算法將運(yùn)行時(shí)間分別減少到原算法的1/140和1/450；與并行的NBlock優(yōu)先（ PBNF）算法相比，并行算法將加速比提高到3.2，同時(shí)，改進(jìn)算法是嚴(yán)格的最佳優(yōu)先搜索算法，保證了解的質(zhì)量，且易于實(shí)現(xiàn)。
?