Vikipedio:Projekto matematiko/Larĝiĝema trairo
El Vikipedio
 |
Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al Larĝiĝema trairo (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi. |
| Larĝiĝema trairo | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
 (Mendi, Ordo) en kiu la (verticoj, verticas) estas elvolvita |
||||||||||||
| Ĝeneralaj Datumoj | ||||||||||||
|
En komputiko, larĝiĝema trairo (_BFS_) estas arba serĉa algoritmo uzita por _traversing_ aŭ serĉanta arbo, arba strukturo, aŭ (grafikaĵo, grafeo). La algoritmo (komenciĝoj, komenciĝas, komencas) je la radika vertico kaj esploras ĉiu najbaranta (verticoj, verticas). Tiam por ĉiu de tiuj plej proksima (verticoj, verticas), ĝi esploras ilia _unexplored_ najbaro (verticoj, verticas), kaj tiel plu, ĝis ĝi trovas la golo.
Enhavo |
[redaktu] Kiel ĝi (laboroj, laboras)
Formale, _BFS_ estas _uninformed_ (serĉi, serĉo) maniero (tiu, ke, kiu) celas al elvolvi kaj ekzameni ĉiuj (verticoj, verticas) de (grafikaĵo, grafeo) sisteme en (serĉi, serĉo) de solvaĵo. En alia (vortoj, vortas), ĝi elblove (serĉadoj, serĉoj) la tuta (grafikaĵo, grafeo) sen konsideranta la golo ĝis ĝi trovas ĝi. Ĝi ne uzi heŭristiko.
De la starpunkto de la algoritmo, ĉiuj infanaj verticoj ricevis per elvolvanta vertico estas adiciita al Rektvica memoro (atendovico, vico). En tipa (realigoj, realigas), (verticoj, verticas) (tiu, ke, kiu) havi ankoraŭ ne estas ekzamenita por ilia (najbaroj, najbaras) estas lokita en iu (kontenero, ujo) (kiel (atendovico, vico) aŭ ligillisto) (nomita, vokis) "(malfermi, malfermita)" kaj tiam iam ekzamenis estas lokita en la (kontenero, ujo) "(fermita, fermis)".
[redaktu] Algoritmo (neformala)
- Meti la startanta vertico (la radika vertico) en la (atendovico, vico).
- Tiri vertico de la (komenco, komencanta) de la (atendovico, vico) kaj ekzameni ĝi.
- Se la serĉis ero estas fundamenti en ĉi tiu vertico, eksiĝi la (serĉi, serĉo) kaj redoni rezulto.
- Alie puŝi ĉiu ((do, tiel)-malproksime-_unexamined_) (postantoj, postantas) de ĉi tiu vertico enen la fino de la (atendovico, vico), se estas (ĉiu, iu).
- Se la (atendovico, vico) estas malplena, ĉiu vertico sur la (grafikaĵo, grafeo) havas estas ekzamenita -- eksiĝi la (serĉi, serĉo) kaj redoni "ne fundamenti".
- ripeti de (ŝtupo, paŝi) 2.
[redaktu] Algoritmo (formala)
funkcio _breadthFirstSearch_ (Starti, Golo) {
_enqueue_((Atendovico, Vico),Starti)
dum _notEmpty_((Atendovico, Vico)) {
Vertico := _dequeue_((Atendovico, Vico))
se Vertico = Golo {
redoni Vertico // la kodo pli sube ne preni ekzekutita
}
por ĉiu Infano en Elvolvi(Vertico) {
se _notVisited_(Infano) {
_setVisited_(Infano)
_enqueue_((Atendovico, Vico), Infano)
}
}
}
}
[redaktu] (Esprimiloj, Esprimas)
[redaktu] Spaca Komplekseco
Ekde ĉiuj (verticoj, verticas) esplorita (do, tiel) malproksime devi saviĝi, la spaca komplekseco de larĝiĝema trairo estas O(|V| + |E|) kie |V| estas la nombro de (verticoj, verticas) kaj |E| la nombro de randoj en la (grafikaĵo, grafeo). (Tononomo, Noto, Noti): alia vojo de (diranta, dirante) ĉi tiu estas (tiu, ke, kiu) ĝi estas O(B ^ M) kie B estas la maksimumo (branĉanta, alanta, forkiĝanta) faktoro kaj M estas la maksimuma voja longo de la arbo. Ĉi tiu grandega postuli por spaco estas la kaŭzo kial larĝiĝema trairo estas _impractical_ por pli granda (problemoj, problemas).
[redaktu] Tempa Komplekseco
Ekde en la plej malbona (kesto, okazo) larĝiĝema trairo havas al konsideri ĉiuj vojoj al ĉiuj ebla (verticoj, verticas) la tempa komplekseco de larĝiĝema trairo estas O(|V| + |E|) kie |V| estas la nombro de (verticoj, verticas) kaj |E| la nombro de randoj en la (grafikaĵo, grafeo).
[redaktu] Pleneco
Larĝiĝema trairo estas plenumi. Ĉi tiu (meznombroj, meznombras, signifas) (tiu, ke, kiu) se estas solvaĵa larĝiĝema trairo estos trovi ĝi sendistinge de la speco de (grafikaĵo, grafeo). Tamen, se la (grafikaĵo, grafeo) estas malfinio kaj estas ne solvaĵa larĝiĝema trairo estos (diverĝi, malkonverĝi).
[redaktu] _Optimality_
En ĝenerala larĝiĝema trairo estas ne (optima, optimala) ekde ĝi ĉiam redonas la rezulto kun la malplej randoj inter la starti vertico kaj la gola vertico. Se la (grafikaĵo, grafeo) estas pezita (grafikaĵo, grafeo) kaj pro tio havas kostas asociita kun ĉiu (ŝtupo, paŝi) golo (apuda, apud) la starti ne devi esti la plej malkara golo havebla. Ĉi tiu problemo estas solvita per pliboniganta larĝiĝema trairo al uniformo-kosta serĉo kiu konsideras la vojo kostas. Tamen, se la (grafikaĵo, grafeo) estas ne pezita, kaj pro tio ĉiuj (ŝtupo, paŝi) kostas estas egala, larĝiĝema trairo estos trovi la plej proksima kaj la plej bona solvaĵo.
[redaktu] Aplikoj de _BFS_
Larĝiĝema trairo povas kutimi solvi multaj (problemoj, problemas) en grafeteorio, ekzemple:
- Trovantaj ĉiuj koneksaj komponantoj en (grafikaĵo, grafeo).
- Trovanta ĉiuj (verticoj, verticas) en unu koneksa komponanto
- Trovanta la plej mallonga vojo inter du (verticoj, verticas) u kaj v (_unweighted_ (verticoj, verticas))
- (Testante, Testado) (grafikaĵo, grafeo) por _bipartiteness_
[redaktu] Trovanta koneksa (Komponantoj, Komponantas)
La aro de (verticoj, verticas) atingita per _BFS_ estas la plej granda koneksa komponanto enhavanta la starti vertico.
[redaktu] Provo por _bipartiteness_
Se estas randoj (aniĝanta, aliganta, aliĝanta) (verticoj, verticas) en la sama _BFS_ (markoti, markoto), tiam la (grafikaĵo, grafeo) devas enhavi nepara longa ciklo kaj esti ne-dukolora.
[redaktu] Vidi ankaŭ
- _Apriori_ algoritmo
- Profund(iĝ)ema trairo
[redaktu] Referencoj
- Tomaso H. Cormen-a, Karlo E. _Leiserson_, _Ronald_ L. _Rivest_, kaj _Clifford_ Stein-a. Enkonduko al (Algoritmoj, Algoritmas), (Sekundo, Dua) Redakcio. _MIT_ Premi kaj _McGraw_-Monteto, 2001. ISBN 0262032937. Sekcio 22.2: Larĝiĝema trairo, _pp_.531–539.
