hé wèi qǐ fā shì sōu suǒ suàn fǎ
zài shuō tā zhī qián xiān tí tí zhuàng tài kōng jiān sōu suǒ。 zhuàng tài kōng jiān sōu suǒ， rú guǒ 'àn zhuān yè diǎn de shuō fǎ jiù shì jiāng wèn tí qiú jiě guò chéng biǎo xiàn wéi cóng chū shǐ zhuàng tài dào mù biāo zhuàng tài xún zhǎo zhè gè lù jìng de guò chéng。 tōng sú diǎn shuō， jiù shì zài jiě yī gè wèn tí
shí， zhǎo dào yī tiáo jiě tí de guò chéng kě yǐ cóng qiú jiě de kāi shǐ dào wèn tí de jiēguǒ（ hǎo xiàng bìng bù tōng sú 'ò）。 yóu yú qiú jiě wèn tí de guò chéng zhōng fēn zhī yòu hěn duō， zhù yào shì qiú jiě guò chéng zhōng qiú jiě tiáo jiàn de bù què dìng xìng， bù wán bèi xìng zào chéng de， shǐ
dé qiú jiě de lù jìng hěn duō zhè jiù gòu chéng liǎo yī gè tú， wǒ men shuō zhè gè tú jiù shì zhuàng tài kōng jiān。 wèn tí de qiú jiě shí jì shàng jiù shì zài zhè gè tú zhōng zhǎo dào yī tiáo lù jìng kě yǐ cóng kāi shǐ dào jiēguǒ。 zhè gè xún zhǎo de guò chéng jiù shì zhuàng tài kōng jiān sōu suǒ。
cháng yòng de zhuàng tài kōng jiān sōu suǒ yòu shēn dù yōu xiān hé guǎng dù yōu xiān。 guǎng dù yōu xiān shì cóng chū shǐ zhuàng tài yī céng yī céng xiàng xià zhǎo， zhí dào zhǎo dào mù biāo wéi zhǐ。 shēn dù yōu xiān shì 'àn zhào yī dìng de shùn xù qián chá zhǎo wán yī gè fēn zhī， zài chá zhǎo lìng yī gè fēn zhī
， yǐ zhì zhǎo dào mù biāo wéi zhǐ。 zhè liǎng zhǒng suàn fǎ zài shù jù jié gòu shū zhōng dōuyòu miáo shù， kě yǐ cān kàn zhè xiē shū dé dào gèng xiáng xì de jiě shì。
qián miàn shuō de guǎng dù hé shēn dù yōu xiān sōu suǒ yòu yī gè hěn dà de quē xiàn jiù shì tā mendōu shì zài yī gè gěi dìng de zhuàng tài kōng jiān zhōng qióng jǔ。 zhè zài zhuàng tài kōng jiān bù dà de qíng kuàng xià shì hěn hé shì de suàn fǎ， kě shì dāng zhuàng tài kōng jiān shí fēn dà， qiě bù yù cè
de qíng kuàng xià jiù bù kě qǔ liǎo。 tā de xiàolǜ shí zài tài dī， shèn zhì bù kě wán chéng。 zài zhè lǐ jiù yào yòng dào qǐ fā shì sōu suǒ liǎo。
qǐ fā shì sōu suǒ jiù shì zài zhuàng tài kōng jiān zhōng de sōu suǒ duì měi yī gè sōu suǒ de wèi zhì jìn xíng píng gū， dé dào zuì hǎo de wèi zhì， zài cóng zhè gè wèi zhì jìn xíng sōu suǒ zhí dào mù biāo。 zhè yàng kě yǐ shěng lüè dà liàng wú wèi de sōu suǒ lù jìng， tí dào liǎo xiàolǜ。 zài
qǐ fā shì sōu suǒ zhōng， duì wèi zhì de gū jià shì shí fēn zhòng yào de。 cǎi yòng liǎo bù tóng de gū jià kě yǐ yòu bù tóng de xiào guǒ。 wǒ men xiān kàn kàn gū jià shì rú hé biǎo shì de。
qǐ fā zhōng de gū jià shì yòng gū jià hán shù biǎo shì de， rú：
f(n)=g(n)+h(n)
qí zhōng f(n) shì jié diǎn n de gū jià hán shù， g(n) shí zài zhuàng tài kōng jiān zhōng cóng chū shǐ jié diǎn dào n jié diǎn de shí jì dài jià， h(n) shì cóng n dào mù biāo jié diǎn zuì jiā lù jìng de gū jì dài jià。 zài zhè lǐ zhù yào shì h(n) tǐ xiàn liǎo sōu suǒ de qǐ fā xìn xī，
yīn wéi g(n) shì yǐ zhī de。 rú guǒ shuō xiáng xì diǎn， g(n) dài biǎo liǎo sōu suǒ de guǎng dù de yōu xiān qū shì。 dàn shì dāng h(n)>>g(n) shí， kě yǐ shěng lüè g(n)， ér tí gāo xiàolǜ。 zhè xiē jiù shēn . |
|
|