| | simulate anneal arithmetic (saa, mó nǐ tuì huǒ suàn fǎ )
mó nǐ tuì huǒ suàn fǎ
mó nǐ tuì huǒ suàn fǎ lái yuán yú gù tǐ tuì huǒ yuán lǐ， jiāng gù tǐ jiā wēn zhì chōng fēn gāo， zài ràng qí xú xú lěng què， jiā wēn shí， gù tǐ nèi bù lì zǐ suí wēn shēng biàn wéi wú xù zhuàng， nèi néng zēng dà， ér xú xú lěng què shí lì zǐ jiàn qū yòu xù， zài měi gè wēn dù dū dá dào píng héng tài， zuì hòu zài cháng wēn shí dá dào jī tài， nèi néng jiǎn wéi zuì xiǎo。 gēn jù metropolis zhǔn zé， lì zǐ zài wēn dù t shí qū yú píng héng de gàilǜ wéi e-Δe/(kt)， qí zhōng e wéi wēn dù t shí de nèi néng， Δe wéi qí gǎi biàn liàng， k wéi boltzmann cháng shù。 yòng gù tǐ tuì huǒ mó nǐ zǔ hé yōu huà wèn tí， jiāng nèi néng e mó nǐ wéi mù biāo hán shù zhí f， wēn dù t yǎn huà chéng kòng zhì cān shù t， jí dé dào jiě zǔ hé yōu huà wèn tí de mó nǐ tuì huǒ suàn fǎ ： yóu chū shǐ jiě i hé kòng zhì cān shù chū zhí t kāi shǐ， duì dāng qián jiě chóngfù“ chǎn shēng xīn jiě → jì suàn mù biāo hán shù chā→ jiē shòu huò shěqì” de dié dài， bìng zhú bù shuāi jiǎn t zhí， suàn fǎ zhōng zhǐ shí de dāng qián jiě jí wéi suǒ dé jìn sì zuì yōu jiě， zhè shì jī yú méng tè kǎ luó dié dài qiú jiě fǎ de yī zhǒng qǐ fā shì suí jī sōu suǒ guò chéng。 tuì huǒ guò chéng yóu lěng què jìn dù biǎo (coolingschedule) kòng zhì， bāo kuò kòng zhì cān shù de chū zhí t jí qí shuāi jiǎn yīn zǐ Δt、 měi gè t zhí shí de dié dài cì shù l hé tíng zhǐ tiáo jiàn s。
1. mó nǐ tuì huǒ suàn fǎ de mó xíng
mó nǐ tuì huǒ suàn fǎ kě yǐ fēn jiě wéi jiě kōng jiān、 mù biāo hán shù hé chū shǐ jiě sān bù fēn。
mó nǐ tuì huǒ de jī běn sī xiǎng :
(1) chū shǐ huà： chū shǐ wēn dù t( chōng fēn dà )， chū shǐ jiě zhuàng tài s( shì suàn fǎ dié dài de qǐ diǎn )， měi gè t zhí de dié dài cì shù l
(2) duì k=1， ……， l zuò dì (3) zhì dì 6 bù：
(3) chǎn shēng xīn jiě s ′
(4) jì suàn zēng liàng Δt′ =c(s′ )-c(s)， qí zhōng c(s) wéi píng jià hán shù
(5) ruò Δt′ <0 zé jiē shòu s′ zuò wéi xīn de dāng qián jiě， fǒu zé yǐ gàilǜ exp(-Δt′ /t) jiē shòu s′ zuò wéi xīn de dāng qián jiě .
(6) rú guǒ mǎn zú zhōng zhǐ tiáo jiàn zé shū chū dāng qián jiě zuò wéi zuì yōu jiě， jié shù chéng xù。
zhōng zhǐ tiáo jiàn tōng cháng qǔ wéi lián xù ruò gān gè xīn jiě dōuméi yòu bèi jiē shòu shí zhōng zhǐ suàn fǎ。
(7)t zhú jiàn jiǎn shǎo， qiě t->0， rán hòu zhuǎn dì 2 bù。
suàn fǎ duì yìng dòng tài yǎn shì tú：
mó nǐ tuì huǒ suàn fǎ xīn jiě de chǎn shēng hé jiē shòu kě fēn wéi rú xià sì gè bù zhòu：
dì yī bù shì yóu yī gè chǎn shēng hán shù cóng dāng qián jiě chǎn shēng yī gè wèi yú jiě kōng jiān de xīn jiě； wéi biàn yú hòu xù de jì suàn hé jiē shòu， jiǎn shǎo suàn fǎ hào shí， tōng cháng xuǎn zé yóu dāng qián xīn jiě jīng guò jiǎn dān dì biàn huàn jí kě chǎn shēng xīn jiě de fāng fǎ， rú duì gòu chéng xīn jiě de quán bù huò bù fēn yuán sù jìn xíng zhì huàn、 hù huàn děng， zhù yì dào chǎn shēng xīn jiě de biàn huàn fāng fǎ jué dìng liǎo dāng qián xīn jiě de lín yù jié gòu， yīn 'ér duì lěng què jìn dù biǎo de xuǎn qǔ yòu yī dìng de yǐng xiǎng。
dì 'èr bù shì jì suàn yǔ xīn jiě suǒ duì yìng de mù biāo hán shù chā。 yīn wéi mù biāo hán shù chā jǐn yóu biàn huàn bù fēn chǎn shēng， suǒ yǐ mù biāo hán shù chā de jì suàn zuì hǎo 'àn zēng liàng jì suàn。 shì shí biǎo míng， duì dà duō shù yìng yòng 'ér yán， zhè shì jì suàn mù biāo hán shù chā de zuì kuài fāng fǎ。
dì sān bù shì pàn duàn xīn jiě shì fǒu bèi jiē shòu , pàn duàn de yǐ jù shì yī gè jiē shòu zhǔn zé， zuì cháng yòng de jiē shòu zhǔn zé shì metropo1is zhǔn zé : ruò Δt′ <0 zé jiē shòu s′ zuò wéi xīn de dāng qián jiě s， fǒu zé yǐ gàilǜ exp(-Δt′ /t) jiē shòu s′ zuò wéi xīn de dāng qián jiě s。
dì sì bù shì dāng xīn jiě bèi què dìng jiē shòu shí， yòng xīn jiě dài tì dāng qián jiě， zhè zhǐ xū jiāng dāng qián jiě zhōng duì yìng yú chǎn shēng xīn jiě shí de biàn huàn bù fēn yú yǐ shí xiàn， tóng shí xiū zhèng mù biāo hán shù zhí jí kě。 cǐ shí， dāng qián jiě shí xiàn liǎo yī cì dié dài。 kě zài cǐ jī chǔ shàng kāi shǐ xià yī lún shì yàn。 ér dāng xīn jiě bèi pàn dìng wéi shěqì shí， zé zài yuán dāng qián jiě de jī chǔ shàng jì xù xià yī lún shì yàn。
mó nǐ tuì huǒ suàn fǎ yǔ chū shǐ zhí wú guān， suàn fǎ qiú dé de jiě yǔ chū shǐ jiě zhuàng tài s( shì suàn fǎ dié dài de qǐ diǎn ) wú guān； mó nǐ tuì huǒ suàn fǎ jù yòu jiàn jìn shōu liǎn xìng， yǐ zài lǐ lùn shàng bèi zhèng míng shì yī zhǒng yǐ gàilǜ l shōu liǎn yú quán jú zuì yōu jiě de quán jú yōu huà suàn fǎ； mó nǐ tuì huǒ suàn fǎ jù yòu bìng xíng xìng。
2 mó nǐ tuì huǒ suàn fǎ de jiǎn dān yìng yòng
zuò wéi mó nǐ tuì huǒ suàn fǎ yìng yòng， tǎo lùn huò láng dān wèn tí (travellingsalesmanproblem， jiǎn jì wéi tsp)： shè yòu n gè chéng shì， yòng shù mǎ 1,… ,n dài biǎo。 chéng shì i hé chéng shì j zhī jiān de jù lí wéi d(i， j)i,j=1,… ,n ． tsp wèn tí shì yào zhǎo biàn fǎng měi gè yù shì qià hǎo yī cì de yī tiáo huí lù， qiě qí lù jìng zǒng cháng dù wéi zuì duǎn .。
qiú jiě tsp de mó nǐ tuì huǒ suàn fǎ mó xíng kě miáo shù rú xià：
jiě kōng jiān jiě kōng jiān s shì biàn fǎng měi gè chéng shì qià hǎo yī cì de suǒ yòu huí lù， shì {1，……， n} de suǒ yòu xún huán pái liè de jí hé， s zhōng de chéng yuán jì wéi (w1,w2,……， wn)， bìng jì wn+1=w1。 chū shǐ jiě kě xuǎn wéi (1，……， n)
mù biāo hán shù cǐ shí de mù biāo hán shù jí wéi fǎng wèn suǒ yòu chéng shì de lù jìng zǒng cháng dù huò chēng wéi dài jià hán shù：
wǒ men yào qiú cǐ dài jià hán shù de zuì xiǎo zhí。
xīn jiě de chǎn shēng suí jī chǎn shēng 1 hé n zhī jiān de liǎng xiāng yì shù k hé m， ruò k(w1,w2,…， wk,wk+1,…， wm,…， wn)
biàn wéi：
(w1,w2,…， wm,wm-1,…， wk+1,wk,…， wn).
rú guǒ shì k>m， zé jiāng
(w1,w2,…， wk,wk+1,…， wm,…， wn)
biàn wéi：
(wm,wm-1,…， w1,wm+1,…， wk-1,wn,wn-1,…， wk).
shàng shù biàn huàn fāng fǎ kě jiǎn dān shuō chéng shì“ nì zhuǎn zhōng jiān huò zhě nì zhuǎn liǎng duān”。
yě kě yǐ cǎi yòng qí tā de biàn huàn fāng fǎ， yòu xiē biàn huàn yòu dú tè de yōu yuè xìng， yòu shí yě jiāng tā men jiāo tì shǐ yòng， dé dào yī zhǒng gèng hǎo fāng fǎ。
dài jià hán shù chā shè jiāng (w1,w2,……， wn) biàn huàn wéi (u1,u2,……， un), zé dài jià hán shù chā wéi：
gēn jù shàng shù fēn xī， kě xiě chū yòng mó nǐ tuì huǒ suàn fǎ qiú jiě tsp wèn tí de wěi chéng xù：
proceduretspsa:
begin
init-of-t;{t wéi chū shǐ wēn dù }
s={1，……， n};{s wéi chū shǐ zhí }
termination=false;
whiletermination=false
begin
fori=1toldo
begin
generate(s′ forms);{ cóng dāng qián huí lù s chǎn shēng xīn huí lù s′ }
Δt:=f(s′ ))-f(s);{f(s) wéi lù jìng zǒng cháng }
if(Δt<0)or(exp(-Δt/t)>random-of-[0,1])
s=s′ ;
ifthe-halt-condition-is-truethen
termination=true;
end;
t_lower;
end;
end
mó nǐ tuì huǒ suàn fǎ de yìng yòng hěn guǎng fàn， kě yǐ jiào gāo de xiàolǜ qiú jiě zuì dà jié wèn tí (maxcutproblem)、 0-1 bēibāo wèn tí (zerooneknapsackproblem)、 tú zhuósè wèn tí (graphcolouringproblem)、 diào dù wèn tí (schedulingproblem) děng děng。
3 mó nǐ tuì huǒ suàn fǎ de cān shù kòng zhì wèn tí
mó nǐ tuì huǒ suàn fǎ de yìng yòng hěn guǎng fàn， kě yǐ qiú jiě np wán quán wèn tí， dàn qí cān shù nán yǐ kòng zhì， qí zhù yào wèn tí yòu yǐ xià sān diǎn：
(1) wēn dù t de chū shǐ zhí shè zhì wèn tí。
wēn dù t de chū shǐ zhí shè zhì shì yǐng xiǎng mó nǐ tuì huǒ suàn fǎ quán jú sōu suǒ xìng néng de zhòng yào yīn sù zhī yī、 chū shǐ wēn dù gāo， zé sōu suǒ dào quán jú zuì yōu jiě de kě néng xìng dà， dàn yīn cǐ yào huā fèi dà liàng de jì suàn shí jiān； fǎn zhī， zé kě jié yuē jì suàn shí jiān， dàn quán jú sōu suǒ xìng néng kě néng shòu dào yǐng xiǎng。 shí jì yìng yòng guò chéng zhōng， chū shǐ wēn dù yī bān xū yào yǐ jù shí yàn jiēguǒ jìn xíng ruò gān cì tiáozhěng。
(2) tuì huǒ sù dù wèn tí。
mó nǐ tuì huǒ suàn fǎ de quán jú sōu suǒ xìng néng yě yǔ tuì huǒ sù dù mìqiè xiāng guān。 yī bān lái shuō， tóng yī wēn dù xià de“ chōng fēn” sōu suǒ ( tuì huǒ ) shì xiāng dāng bì yào de， dàn zhè xū yào jì suàn shí jiān。 shí jì yìng yòng zhōng， yào zhēn duì jù tǐ wèn tí de xìng zhì hé tè zhēng shè zhì hé lǐ de tuì huǒ píng héng tiáo jiàn。
(3) wēn dù guǎn lǐ wèn tí。
wēn dù guǎn lǐ wèn tí yě shì mó nǐ tuì huǒ suàn fǎ nán yǐ chǔlǐ de wèn tí zhī yī。 shí jì yìng yòng zhōng， yóu yú bì xū kǎo lǜ jì suàn fù zá dù de qiē shí kě xíng xìng děng wèn tí， cháng cǎi yòng rú xià suǒ shì de jiàng wēn fāng shì：
t(t+1) ＝ k×t(t)
shì zhōng k wéi zhèng de lüè xiǎo yú 1.00 de cháng shù， t wéi jiàng wēn de cì shù | | Simulate Anneal Arithmetic (SAA, mó nǐ tuì huǒ suàn fǎ )
mó nǐ tuì huǒ suàn fǎ
mó nǐ tuì huǒ suàn fǎ lái yuán yú gù tǐ tuì huǒ yuán lǐ， jiāng gù tǐ jiā wēn zhì chōng fēn gāo， zài ràng qí xú xú lěng què， jiā wēn shí， gù tǐ nèi bù lì zǐ suí wēn shēng biàn wéi wú xù zhuàng， nèi néng zēng dà， ér xú xú lěng què shí lì zǐ jiàn qū yòu xù， zài měi gè wēn dù dū dá dào píng héng tài， zuì hòu zài cháng wēn shí dá dào jī tài， nèi néng jiǎn wéi zuì xiǎo。 gēn jù Metropolis zhǔn zé， lì zǐ zài wēn dù T shí qū yú píng héng de gàilǜ wéi e-ΔE/(kT)， qí zhōng E wéi wēn dù T shí de nèi néng， ΔE wéi qí gǎi biàn liàng， k wéi Boltzmann cháng shù。 yòng gù tǐ tuì huǒ mó nǐ zǔ hé yōu huà wèn tí， jiāng nèi néng E mó nǐ wéi mù biāo hán shù zhí f， wēn dù T yǎn huà chéng kòng zhì cān shù t， jí dé dào jiě zǔ hé yōu huà wèn tí de mó nǐ tuì huǒ suàn fǎ ： yóu chū shǐ jiě i hé kòng zhì cān shù chū zhí t kāi shǐ， duì dāng qián jiě chóngfù“ chǎn shēng xīn jiě→ jì suàn mù biāo hán shù chā→ jiē shòu huò shěqì” de dié dài， bìng zhú bù shuāi jiǎn t zhí， suàn fǎ zhōng zhǐ shí de dāng qián jiě jí wéi suǒ dé jìn sì zuì yōu jiě， zhè shì jī yú méng tè kǎ luó dié dài qiú jiě fǎ de yī zhǒng qǐ fā shì suí jī sōu suǒ guò chéng。 tuì huǒ guò chéng yóu lěng què jìn dù biǎo (CoolingSchedule) kòng zhì， bāo kuò kòng zhì cān shù de chū zhí t jí qí shuāi jiǎn yīn zǐ Δt、 měi gè t zhí shí de dié dài cì shù L hé tíng zhǐ tiáo jiàn S。
mó nǐ tuì huǒ suàn fǎ qǐ yuán yú wù lǐ tuì huǒ。
wù lǐ tuì huǒ guò chéng：
（ 1） jiā wēn guò chéng
（ 2） děng wēn guò chéng
（ 3） lěng què guò chéng
1. mó nǐ tuì huǒ suàn fǎ de mó xíng
mó nǐ tuì huǒ suàn fǎ kě yǐ fēn jiě wéi jiě kōng jiān、 mù biāo hán shù hé chū shǐ jiě sān bù fēn。
mó nǐ tuì huǒ de jī běn sī xiǎng :
(1) chū shǐ huà： chū shǐ wēn dù T( chōng fēn dà )， chū shǐ jiě zhuàng tài S( shì suàn fǎ dié dài de qǐ diǎn )， měi gè T zhí de dié dài cì shù L
(2) duì k=1，……， L zuò dì (3) zhì dì 6 bù：
(3) chǎn shēng xīn jiě S′
(4) jì suàn zēng liàng Δt′ =C(S′ )-C(S)， qí zhōng C(S) wéi píng jià hán shù
(5) ruò Δt′ <0 zé jiē shòu S′ zuò wéi xīn de dāng qián jiě， fǒu zé yǐ gàilǜ exp(-Δt′ /T) jiē shòu S′ zuò wéi xīn de dāng qián jiě .
(6) rú guǒ mǎn zú zhōng zhǐ tiáo jiàn zé shū chū dāng qián jiě zuò wéi zuì yōu jiě， jié shù chéng xù。
zhōng zhǐ tiáo jiàn tōng cháng qǔ wéi lián xù ruò gān gè xīn jiě dōuméi yòu bèi jiē shòu shí zhōng zhǐ suàn fǎ。
(7)T zhú jiàn jiǎn shǎo， qiě T->0， rán hòu zhuǎn dì 2 bù。
suàn fǎ duì yìng dòng tài yǎn shì tú：
mó nǐ tuì huǒ suàn fǎ xīn jiě de chǎn shēng hé jiē shòu kě fēn wéi rú xià sì gè bù zhòu：
dì yī bù shì yóu yī gè chǎn shēng hán shù cóng dāng qián jiě chǎn shēng yī gè wèi yú jiě kōng jiān de xīn jiě； wéi biàn yú hòu xù de jì suàn hé jiē shòu， jiǎn shǎo suàn fǎ hào shí， tōng cháng xuǎn zé yóu dāng qián xīn jiě jīng guò jiǎn dān dì biàn huàn jí kě chǎn shēng xīn jiě de fāng fǎ， rú duì gòu chéng xīn jiě de quán bù huò bù fēn yuán sù jìn xíng zhì huàn、 hù huàn děng， zhù yì dào chǎn shēng xīn jiě de biàn huàn fāng fǎ jué dìng liǎo dāng qián xīn jiě de lín yù jié gòu， yīn 'ér duì lěng què jìn dù biǎo de xuǎn qǔ yòu yī dìng de yǐng xiǎng。
dì 'èr bù shì jì suàn yǔ xīn jiě suǒ duì yìng de mù biāo hán shù chā。 yīn wéi mù biāo hán shù chā jǐn yóu biàn huàn bù fēn chǎn shēng， suǒ yǐ mù biāo hán shù chā de jì suàn zuì hǎo 'àn zēng liàng jì suàn。 shì shí biǎo míng， duì dà duō shù yìng yòng 'ér yán， zhè shì jì suàn mù biāo hán shù chā de zuì kuài fāng fǎ。
dì sān bù shì pàn duàn xīn jiě shì fǒu bèi jiē shòu , pàn duàn de yǐ jù shì yī gè jiē shòu zhǔn zé， zuì cháng yòng de jiē shòu zhǔn zé shì Metropo1is zhǔn zé : ruò Δt′ <0 zé jiē shòu S′ zuò wéi xīn de dāng qián jiě S， fǒu zé yǐ gàilǜ exp(-Δt′ /T) jiē shòu S′ zuò wéi xīn de dāng qián jiě S。
dì sì bù shì dāng xīn jiě bèi què dìng jiē shòu shí， yòng xīn jiě dài tì dāng qián jiě， zhè zhǐ xū jiāng dāng qián jiě zhōng duì yìng yú chǎn shēng xīn jiě shí de biàn huàn bù fēn yú yǐ shí xiàn， tóng shí xiū zhèng mù biāo hán shù zhí jí kě。 cǐ shí， dāng qián jiě shí xiàn liǎo yī cì dié dài。 kě zài cǐ jī chǔ shàng kāi shǐ xià yī lún shì yàn。 ér dāng xīn jiě bèi pàn dìng wéi shěqì shí， zé zài yuán dāng qián jiě de jī chǔ shàng jì xù xià yī lún shì yàn。
mó nǐ tuì huǒ suàn fǎ yǔ chū shǐ zhí wú guān， suàn fǎ qiú dé de jiě yǔ chū shǐ jiě zhuàng tài S( shì suàn fǎ dié dài de qǐ diǎn ) wú guān； mó nǐ tuì huǒ suàn fǎ jù yòu jiàn jìn shōu liǎn xìng， yǐ zài lǐ lùn shàng bèi zhèng míng shì yī zhǒng yǐ gàilǜ l shōu liǎn yú quán jú zuì yōu jiě de quán jú yōu huà suàn fǎ； mó nǐ tuì huǒ suàn fǎ jù yòu bìng xíng xìng。
2 mó nǐ tuì huǒ suàn fǎ de jiǎn dān yìng yòng
zuò wéi mó nǐ tuì huǒ suàn fǎ yìng yòng， tǎo lùn huò láng dān wèn tí (TravellingSalesmanProblem， jiǎn jì wéi TSP)： shè yòu n gè chéng shì， yòng shù mǎ 1,… ,n dài biǎo。 chéng shì i hé chéng shì j zhī jiān de jù lí wéi d(i， j)i,j=1,… ,n． TSP wèn tí shì yào zhǎo biàn fǎng měi gè yù shì qià hǎo yī cì de yī tiáo huí lù， qiě qí lù jìng zǒng cháng dù wéi zuì duǎn .。
qiú jiě TSP de mó nǐ tuì huǒ suàn fǎ mó xíng kě miáo shù rú xià：
jiě kōng jiān jiě kōng jiān S shì biàn fǎng měi gè chéng shì qià hǎo yī cì de suǒ yòu huí lù， shì {1，……， n} de suǒ yòu xún huán pái liè de jí hé， S zhōng de chéng yuán jì wéi (w1,w2,……， wn)， bìng jì wn+1=w1。 chū shǐ jiě kě xuǎn wéi (1，……， n)
mù biāo hán shù cǐ shí de mù biāo hán shù jí wéi fǎng wèn suǒ yòu chéng shì de lù jìng zǒng cháng dù huò chēng wéi dài jià hán shù：
wǒ men yào qiú cǐ dài jià hán shù de zuì xiǎo zhí。
xīn jiě de chǎn shēng suí jī chǎn shēng 1 hé n zhī jiān de liǎng xiāng yì shù k hé m， ruò k(w1,w2,…， wk,wk+1,…， wm,…， wn)
biàn wéi：
(w1,w2,…， wm,wm-1,…， wk+1,wk,…， wn).
rú guǒ shì k>m， zé jiāng
(w1,w2,…， wk,wk+1,…， wm,…， wn)
biàn wéi：
(wm,wm-1,…， w1,wm+1,…， wk-1,wn,wn-1,…， wk).
shàng shù biàn huàn fāng fǎ kě jiǎn dān shuō chéng shì“ nì zhuǎn zhōng jiān huò zhě nì zhuǎn liǎng duān”。
yě kě yǐ cǎi yòng qí tā de biàn huàn fāng fǎ， yòu xiē biàn huàn yòu dú tè de yōu yuè xìng， yòu shí yě jiāng tā men jiāo tì shǐ yòng， dé dào yī zhǒng gèng hǎo fāng fǎ。
dài jià hán shù chā shè jiāng (w1,w2,……， wn) biàn huàn wéi (u1,u2,……， un), zé dài jià hán shù chā wéi：
gēn jù shàng shù fēn xī， kě xiě chū yòng mó nǐ tuì huǒ suàn fǎ qiú jiě TSP wèn tí de wěi chéng xù：
ProcedureTSPSA:
begin
init-of-T;{T wéi chū shǐ wēn dù }
S={1，……， n};{S wéi chū shǐ zhí }
termination=false;
whiletermination=false
begin
fori=1toLdo
begin
generate(S′ formS);{ cóng dāng qián huí lù S chǎn shēng xīn huí lù S′ }
Δt:=f(S′ ))-f(S);{f(S) wéi lù jìng zǒng cháng }
IF(Δt<0)OR(EXP(-Δt/T)>Random-of-[0,1])
S=S′ ;
IFthe-halt-condition-is-TRUETHEN
termination=true;
End;
T_lower;
End;
End
mó nǐ tuì huǒ suàn fǎ de yìng yòng hěn guǎng fàn， kě yǐ jiào gāo de xiàolǜ qiú jiě zuì dà jié wèn tí (MaxCutProblem)、 0-1 bēibāo wèn tí (ZeroOneKnapsackProblem)、 tú zhuósè wèn tí (GraphColouringProblem)、 diào dù wèn tí (SchedulingProblem) děng děng。
3 mó nǐ tuì huǒ suàn fǎ de cān shù kòng zhì wèn tí
mó nǐ tuì huǒ suàn fǎ de yìng yòng hěn guǎng fàn， kě yǐ qiú jiě NP wán quán wèn tí， dàn qí cān shù nán yǐ kòng zhì， qí zhù yào wèn tí yòu yǐ xià sān diǎn：
(1) wēn dù T de chū shǐ zhí shè zhì wèn tí。
wēn dù T de chū shǐ zhí shè zhì shì yǐng xiǎng mó nǐ tuì huǒ suàn fǎ quán jú sōu suǒ xìng néng de zhòng yào yīn sù zhī yī、 chū shǐ wēn dù gāo， zé sōu suǒ dào quán jú zuì yōu jiě de kě néng xìng dà， dàn yīn cǐ yào huā fèi dà liàng de jì suàn shí jiān； fǎn zhī， zé kě jié yuē jì suàn shí jiān， dàn quán jú sōu suǒ xìng néng kě néng shòu dào yǐng xiǎng。 shí jì yìng yòng guò chéng zhōng， chū shǐ wēn dù yī bān xū yào yǐ jù shí yàn jiēguǒ jìn xíng ruò gān cì tiáozhěng。
(2) tuì huǒ sù dù wèn tí。
mó nǐ tuì huǒ suàn fǎ de quán jú sōu suǒ xìng néng yě yǔ tuì huǒ sù dù mìqiè xiāng guān。 yī bān lái shuō， tóng yī wēn dù xià de“ chōng fēn” sōu suǒ ( tuì huǒ ) shì xiāng dāng bì yào de， dàn zhè xū yào jì suàn shí jiān。 shí jì yìng yòng zhōng， yào zhēn duì jù tǐ wèn tí de xìng zhì hé tè zhēng shè zhì hé lǐ de tuì huǒ píng héng tiáo jiàn。
(3) wēn dù guǎn lǐ wèn tí。
wēn dù guǎn lǐ wèn tí yě shì mó nǐ tuì huǒ suàn fǎ nán yǐ chǔlǐ de wèn tí zhī yī。 shí jì yìng yòng zhōng， yóu yú bì xū kǎo lǜ jì suàn fù zá dù de qiē shí kě xíng xìng děng wèn tí， cháng cǎi yòng rú xià suǒ shì de jiàng wēn fāng shì：
T(t+1)＝ k×T(t)
shì zhōng k wéi zhèng de lüè xiǎo yú 1.00 de cháng shù， t wéi jiàng wēn de cì shù
4、 mó nǐ tuì huǒ suàn fǎ de yōu quē diǎn
yōu diǎn： jì suàn guò chéng jiǎn dān， tōng yòng， lǔ bàng xìng qiáng， shì yòng yú bìng xíng chǔlǐ， kě yòng yú qiú jiě fù zá de fēi xiàn xìng yōu huà wèn tí。
quē diǎn： shōu liǎn sù dù màn， zhí xíng shí jiān cháng， suàn fǎ xìng néng yǔ chū shǐ zhí yòu guān jí cān shù mǐn gǎn děng quē diǎn。
jīng diǎn mó nǐ tuì huǒ suàn fǎ de quē diǎn：
(1) rú guǒ jiàng wēn guò chéng zú gòu huǎn màn， duō dé dào de jiě de xìng néng huì bǐ jiào hǎo， dàn yǔ cǐ xiāng duì de shì shōu liǎn sù dù tài màn ;
(2) rú guǒ jiàng wēn guò chéng guò kuài， hěn kě néng dé bù dào quán jú zuì yōu jiě。
mó nǐ tuì huǒ suàn fǎ de gǎi jìn
(1) shè jì hé shì de zhuàng tài chǎn shēng hán shù， shǐ qí gēn jù sōu suǒ jìn chéng de xū yào
biǎo xiàn chū zhuàng tài de quán kōng jiān fēn sàn xìng huò jú bù qū yù xìng。
(2) shè jì gāo xiào de tuì huǒ cè lüè。
(3) bì miǎn zhuàng tài de yū huí sōu suǒ。
(4) cǎi yòng bìng xíng sōu suǒ jié gòu。
(5) wéi bì miǎn xiàn rù jú bù jí xiǎo， gǎi jìn duì wēn dù de kòng zhì fāng shì
(6) xuǎn zé hé shì de chū shǐ zhuàng tài。
(7) shè jì hé shì de suàn fǎ zhōng zhǐ zhǔn zé。
yě kě tōng guò zēng jiā mǒu xiē huán jié 'ér shí xiàn duì mó nǐ tuì huǒ suàn fǎ de gǎi jìn。
zhù yào de gǎi jìn fāng shì bāo kuò：
(1) zēng jiā shēng wēn huò zhòng shēng wēn guò chéng。 zài suàn fǎ jìn chéng de shìdàng shí jī， jiāng wēn dù shìdàng tí gāo， cóng 'ér kě jī huó gè zhuàng tài de jiē shòu gàilǜ， yǐ tiáozhěng sōu suǒ jìn chéng zhōng de dāng qián zhuàng tài， bì miǎn suàn fǎ zài jú bù jí xiǎo jiě chù tíng zhì bù qián。
(2) zēng jiā jì yì gōng néng。 wéi bì miǎn sōu suǒ guò chéng zhōng yóu yú zhí xíng gàilǜ jiē shòu huán jié 'ér yí shī dāng qián yù dào de zuì yōu jiě， kě tōng guò zēng jiā cún chǔ huán jié， jiāng yī xiē zài zhè zhī qián hǎo de tài jì yì xià lái。
(3) zēng jiā bǔ chōng sōu suǒ guò chéng。 jí zài tuì huǒ guò chéng jié shù hòu， yǐ sōu suǒ dào de zuì yōu jiě wéi chū shǐ zhuàng tài， zài cì zhí xíng mó nǐ tuì huǒ guò chéng huò jú bù xìng sōu suǒ。
(4) duì měi yī dāng qián zhuàng tài， cǎi yòng duō cì sōu suǒ cè lüè， yǐ gàilǜ jiē shòu qū yù nèi de zuì yōu zhuàng tài， ér fēi biāo zhǔn SA de dān cì bǐ jiào fāng shì。
(5) jié hé qí tā sōu suǒ jī zhì de suàn fǎ， rú yí chuán suàn fǎ、 hùn dùn sōu suǒ děng。
(6) shàng shù gè fāng fǎ de zōng hé yìng yòng。 | | | | | mó nǐ tuì huǒ suàn fǎ | yí chuán mó nǐ tuì huǒ suàn fǎ | duō yàng xìng mó nǐ tuì huǒ suàn fǎ | |
|
|
|