| | shēn dù yōu xiān sōu suǒ shì yī zhǒng zài kāi fā pá chóng zǎo qī shǐ yòng jiào duō de fāng fǎ。 tā de mùdì shì yào dá dào bèi sōu suǒ jié gòu de yè jié diǎn ( jí nà xiē bù bāo hán rèn hé chāo liàn de html wén jiàn )。 zài yī gè html wén jiàn zhōng， dāng yī gè chāo liàn bèi xuǎn zé hòu， bèi liàn jiē de html wén jiàn jiāng zhí xíng shēn dù yōu xiān sōu suǒ ， jí zài sōu suǒ qí yú de chāo liàn jiēguǒ zhī qián bì xū xiān wán zhěng dì sōu suǒ dān dú de yī tiáo liàn。 shēn dù yōu xiān sōu suǒ yán zhe html wén jiàn shàng de chāo liàn zǒu dào bù néng zài shēn rù wéi zhǐ， rán hòu fǎn huí dào mǒu yī gè html wén jiàn， zài jì xù xuǎn zé gāi html wén jiàn zhōng de qí tā chāo liàn。 dāng bù zài yòu qí tā chāo liàn kě xuǎn zé shí， shuō míng sōu suǒ yǐ jīng jié shù。 yōu diǎn shì néng biàn lì yī gè web zhàn diǎn huò shēn céng qiàn tào de wén dàng jí hé； quē diǎn shì yīn wéi web jié gòu xiāng dāng shēn ,， yòu kě néng zào chéng yī dàn jìn qù， zài yě chū bù lái de qíng kuàng fā shēng。
( jìn huà lùn mì mǎ 'àn : yóu yú yǐ shàng yī duàn miáo shù běn rén bù néng kàn dǒng , suǒ yǐ zàn shí bǎo liú zhī .)
shì shí shàng , shēn dù yōu xiān sōu suǒ shǔ yú tú suàn fǎ de yī zhǒng , yīng wén suō xiě wéi dfs jí depthfirstsearch. qí guò chéng jiǎn yào lái shuō shì duì měi yī gè kě néng de fēn zhī lù jìng shēn rù dào bù néng zài shēn rù wéi zhǐ , ér qiě měi gè jié diǎn zhǐ néng fǎng wèn yī cì .
jǔ lì shuō míng zhī : xià tú shì yī gè wú xiàng tú , rú guǒ wǒ men cóng a diǎn fā qǐ shēn dù yōu xiān sōu suǒ ( yǐ xià de fǎng wèn cì xù bìng bù shì wéi yī de , dì 'èr gè diǎn jì kě yǐ shì b yě kě yǐ shì c,d), zé wǒ men kě néng dé dào rú xià de yī gè fǎng wèn guò chéng :a->b->e( méi yòu lù liǎo ! huí sù dào a)->c->f->h->g->d( méi yòu lù , zuì zhōng huí sù dào a,a yě méi yòu wèi fǎng wèn de xiāng lín jié diǎn , běn cì sōu suǒ jié shù ).
b--e
/
a-c--f
>h
d--g
jiǎn yào shuō míng shēn dù yōu xiān sōu suǒ de tè diǎn : měi cì shēn dù yōu xiān sōu suǒ de jiēguǒ bì rán shì tú de yī gè lián tōng fènliàng . shēn dù yōu xiān sōu suǒ kě yǐ cóng duō diǎn fā qǐ . rú guǒ jiāng měi gè jié diǎn zài shēn dù yōu xiān sōu suǒ guò chéng zhōng de " jié shù shí jiān " pái xù ( jù tǐ zuò fǎ shì chuàng jiàn yī gè list, rán hòu zài měi gè jié diǎn de xiāng lín jié diǎn dōuyǐ bèi fǎng wèn de qíng kuàng xià , jiāng gāi jié diǎn jiā rù list jié wěi , rán hòu nì zhuǎn zhěng gè liàn biǎo ), zé wǒ men kě yǐ dé dào suǒ wèi de " tuò pū pái xù ", jí topologicalsort.
dāng rán , dāng rén men gāng gāng zhǎng wò shēn dù yōu xiān sōu suǒ de shí hòu cháng cháng yòng tā lái zǒu mí gōng . shì shí shàng wǒ men hái yòu bié de fāng fǎ , nà jiù shì guǎng dù yōu xiān sōu suǒ (bfs). zhuàng tài（ state): zhuàng tài shì zhì wèn tí qiú jiě guò chéng zhōng měi yī bù de zhuàng kuàng。
suàn fú（ operater） suàn fú shì bǎ wèn tí cóng yī zhǒng zhuàng tài biàn huàn dào lìng yī zhǒng zhuàng tài de fāng fǎ dài hào。 suàn fú de qū zhǐ fàn wéi jiù shì sōu suǒ de fàn wéi。（ yī bān shè wéi jú bù biàn liàng )。
jié diǎn（ node） : yòng lái biǎo míng zhuàng tài tè zhēng jí xiāng guān xìn xī。 | | shēn dù yōu xiān sōu suǒ shì yī zhǒng zài kāi fā pá chóng zǎo qī shǐ yòng jiào duō de fāng fǎ。 tā de mùdì shì yào dá dào bèi sōu suǒ jié gòu de yè jié diǎn ( jí nà xiē bù bāo hán rèn hé chāo liàn de HTML wén jiàn )。 zài yī gè HTML wén jiàn zhōng， dāng yī gè chāo liàn bèi xuǎn zé hòu， bèi liàn jiē de HTML wén jiàn jiāng zhí xíng shēn dù yōu xiān sōu suǒ ， jí zài sōu suǒ qí yú de chāo liàn jiēguǒ zhī qián bì xū xiān wán zhěng dì sōu suǒ dān dú de yī tiáo liàn。 shēn dù yōu xiān sōu suǒ yán zhe HTML wén jiàn shàng de chāo liàn zǒu dào bù néng zài shēn rù wéi zhǐ， rán hòu fǎn huí dào mǒu yī gè HTML wén jiàn， zài jì xù xuǎn zé gāi HTML wén jiàn zhōng de qí tā chāo liàn。 dāng bù zài yòu qí tā chāo liàn kě xuǎn zé shí， shuō míng sōu suǒ yǐ jīng jié shù。 yōu diǎn shì néng biàn lì yī gè Web zhàn diǎn huò shēn céng qiàn tào de wén dàng jí hé； quē diǎn shì yīn wéi Web jié gòu xiāng dāng shēn ,， yòu kě néng zào chéng yī dàn jìn qù， zài yě chū bù lái de qíng kuàng fā shēng。
( jìn huà lùn mì mǎ 'àn : yóu yú yǐ shàng yī duàn miáo shù běn rén bù néng kàn dǒng , suǒ yǐ zàn shí bǎo liú zhī .)
shì shí shàng , shēn dù yōu xiān sōu suǒ shǔ yú tú suàn fǎ de yī zhǒng , yīng wén suō xiě wéi DFS jí DepthFirstSearch. qí guò chéng jiǎn yào lái shuō shì duì měi yī gè kě néng de fēn zhī lù jìng shēn rù dào bù néng zài shēn rù wéi zhǐ , ér qiě měi gè jié diǎn zhǐ néng fǎng wèn yī cì .
jǔ lì shuō míng zhī : xià tú shì yī gè wú xiàng tú , rú guǒ wǒ men cóng A diǎn fā qǐ shēn dù yōu xiān sōu suǒ ( yǐ xià de fǎng wèn cì xù bìng bù shì wéi yī de , dì 'èr gè diǎn jì kě yǐ shì B yě kě yǐ shì C,D), zé wǒ men kě néng dé dào rú xià de yī gè fǎng wèn guò chéng :A->B->E( méi yòu lù liǎo ! huí sù dào A)->C->F->H->G->D( méi yòu lù , zuì zhōng huí sù dào A,A yě méi yòu wèi fǎng wèn de xiāng lín jié diǎn , běn cì sōu suǒ jié shù ). tú
jiǎn yào shuō míng shēn dù yōu xiān sōu suǒ de tè diǎn : měi cì shēn dù yōu xiān sōu suǒ de jiēguǒ bì rán shì tú de yī gè lián tōng fènliàng . shēn dù yōu xiān sōu suǒ kě yǐ cóng duō diǎn fā qǐ . rú guǒ jiāng měi gè jié diǎn zài shēn dù yōu xiān sōu suǒ guò chéng zhōng de " jié shù shí jiān " pái xù ( jù tǐ zuò fǎ shì chuàng jiàn yī gè list, rán hòu zài měi gè jié diǎn de xiāng lín jié diǎn dōuyǐ bèi fǎng wèn de qíng kuàng xià , jiāng gāi jié diǎn jiā rù list jié wěi , rán hòu nì zhuǎn zhěng gè liàn biǎo ), zé wǒ men kě yǐ dé dào suǒ wèi de " tuò pū pái xù ", jí topologicalsort.
dāng rán , dāng rén men gāng gāng zhǎng wò shēn dù yōu xiān sōu suǒ de shí hòu cháng cháng yòng tā lái zǒu mí gōng . shì shí shàng wǒ men hái yòu bié de fāng fǎ , nà jiù shì guǎng dù yōu xiān sōu suǒ (BFS). zhuàng tài（ state): zhuàng tài shì zhì wèn tí qiú jiě guò chéng zhōng měi yī bù de zhuàng kuàng。
suàn fú（ operater） suàn fú shì bǎ wèn tí cóng yī zhǒng zhuàng tài biàn huàn dào lìng yī zhǒng zhuàng tài de fāng fǎ dài hào。 suàn fú de qū zhǐ fàn wéi jiù shì sōu suǒ de fàn wéi。（ yī bān shè wéi jú bù biàn liàng )。
jié diǎn（ node） : yòng lái biǎo míng zhuàng tài tè zhēng jí xiāng guān xìn xī。
zài wǒ men yù dào de yī xiē wèn tí dāng zhōng， yòu xiē wèn tí wǒ men bù néng gòu què qiē de zhǎo chū shù xué mó xíng， jí zhǎo bù chū yī zhǒng zhí jiē qiú jiě de fāng fǎ， jiě jué zhè yī lèi wèn tí， wǒ men yī bān cǎi yòng sōu suǒ de fāng fǎ jiě jué。 sōu suǒ jiù shì yòng wèn tí de suǒ yòu kě néng qù shì tàn， àn zhào yī dìng de shùn xù、 guī zé， bù duàn qù shì tàn， zhí dào zhǎo dào wèn tí de jiě， shì wán liǎo yě méi yòu zhǎo dào jiě， nà jiù shì wú jiě， shì tàn shí yī dìng yào shì tàn wán suǒ yòu de qíng kuàng（ shí jì shàng jiù shì qióng jǔ）；
duì yú wèn tí de dì yī gè zhuàng tài， jiào chū shǐ zhuàng tài， yào qiú de zhuàng tài jiào mù biāo zhuàng tài。
sōu suǒ jiù shì bǎ guī zé yìng yòng yú shí shǐ zhuàng tài， zài qí chǎn shēng de zhuàng tài zhōng， zhí dào dé dào yī gè mù biāo zhuàng tài wéi zhǐ。
chǎn shēng xīn de zhuàng tài de guò chéng jiào kuò zhǎn（ yóu yī gè zhuàng tài， yìng yòng guī zé， chǎn shēng xīn zhuàng tài de guò chéng）
sōu suǒ de yào diǎn：（ 1） chū shǐ zhuàng tài；
（ 2） chóngfù chǎn shēng xīn zhuàng tài；
（ 3） jiǎn chá xīn zhuàng tài shì fǒu wéi mù biāo， shì jié shù， fǒu zhuǎn（ 2）；
rú guǒ sōu suǒ shì yǐ jiē jìn qǐ shǐ zhuàng tài de chéng xù yǐ cì kuò zhǎn zhuàng tài de， jiào kuān dù yōu xiān sōu suǒ。
rú guǒ kuò zhǎn shì shǒu xiān kuò zhǎn xīn chǎn shēng de zhuàng tài， zé jiào shēn dù yōu xiān sōu suǒ 。
shēn dù yōu xiān sōu suǒ
shēn dù yōu xiān sōu suǒ yòng yī gè shù zǔ cún fàng chǎn shēng de suǒ yòu zhuàng tài。
（ 1） bǎ chū shǐ zhuàng tài fàng rù shù zǔ zhōng， shè wéi dāng qián zhuàng tài；
（ 2） kuò zhǎn dāng qián de zhuàng tài， chǎn shēng yī gè xīn de zhuàng tài fàng rù shù zǔ zhōng， tóng shí bǎ xīn chǎn shēng de zhuàng tài shè wéi dāng qián zhuàng tài；
（ 3） pàn duàn dāng qián zhuàng tài shì fǒu hé qián miàn de chóngfù， rú guǒ chóngfù zé huí dào shàng yī gè zhuàng tài， chǎn shēng tā de lìng yī zhuàng tài；
（ 4） pàn duàn dāng qián zhuàng tài shì fǒu wéi mù biāo zhuàng tài， rú guǒ shì mù biāo， zé zhǎo dào yī gè jiě dá， jié shù suàn fǎ。
（ 5） rú guǒ shù zǔ wéi kōng， shuō míng wú jiě。
duì yú pascal yǔ yán lái jiǎng， tā zhī chí dì guī， zài dì guī shí kě yǐ zì dòng shí xiàn huí sù（ lì yòng jú bù biàn liàng） suǒ yǐ shǐ yòng dì guī biān xiě shēn dù yōu xiān sōu suǒ chéng xù xiāng duì jiǎn dān， dāng rán yě yòu fēi dì guī shí xiàn de suàn fǎ。
xiàn zài yǐ zhè tí lái jǔ lì ( mí gōng )
1111010101010111
jì lù qǐ diǎn wéi (1,1) zhǎo dào suǒ yòu de dào (4,4) de lù jìng .
chéng xù rú xià：
const
b:array[1..4,1..4]ofinteger=((1,1,1,1),(0,1,0,1),(0,1,0,1),(0,1,1,1));
c:array[1..4,1..2]of-1..1=((0,1),(0,-1),(1,0),(-1,0));
var
a:array[1..16,1..2]ofinteger;
procedureprint;
var
i,j:integer;
begin
fori:=1to4do
begin
forj:=1to4do
write(b[i,j]:3);
writeln;
end;
writeln('--------------');
end;
proceduretry(k:integer);
var
i:integer;
begin
if(a[k,1]=4)and(a[k,2]=4)thenbeginprint;exit;end;
fori:=1to4do
begin
a[k+1,1]:=a[k,1]+c[i,1];
a[k+1,2]:=a[k,2]+c[i,2];
if(a[k+1,1]>=1)and(a[k+1,1]<=4)and(a[k+1,2]>=1)and(a[k+1,2]<=4)and
(b[a[k+1,1],a[k+1,2]]=1)thenbegin
b[a[k+1,1],a[k+1,2]]:=2;
try(k+1);
b[a[k+1,1],a[k+1,2]]:=1;
end;
end;
end;
begin
a[1,1]:=1;
a[1,2]:=1;
b[1,1]:=2;
try(1);
end.
zhè jiù shì shuō shì shuō jìn xíng sōu suǒ yī tiáo lù zhí dào bù néng zǒu wéi zhǐ , huàn lìng yī tiáo lù . | | |
|
|