«Փնտրում դեպի լայնություն»–ի խմբագրումների տարբերություն
Content deleted Content added
No edit summary |
հեռացվել է Կատեգորիա:Ալգորիթմներ ՀոթՔաթ գործիքով |
||
Տող 1.
{{Տեղեկաքարտ Ալգորիթմ
|Անուն
|Դաս
|նկար
▲|տվյալներ = [[Գրաֆ (տվյալների կառուցվածք)|Գրաֆ]]
▲|տարածք = <math>O(|V|) = O(b^d)</math>
}}
'''Փնտրում դեպի լայնությունը''' [[գրաֆ]]ը շրջանցելու մեթոդներից մեկը։ Այն սկսվում է [[ծառ (տվյալների կառուցվածք)|ծառ]]ի արմատից(կամ կամայական այլ հանգույց, երբեմն անվանում են «փնտրման բանալի»<ref>{{cite web |url=http://www.graph500.org/specifications#sec-5 |title=Graph500 benchmark specification (supercomputer performance evaluation) |publisher=Graph500.org, 2010}}</ref>) և սկզնում բացահայտում է հարևան հանգույցներին մինչև մյուս կարգի հարևաններին բացահայտելը։
Ալգորիթմը ստեղծվել է ուշ [[1950]]-ականներին [[Էդվարդ Մուր|Է․Ֆ․ Մուրի]] կողմից, ով օգտագործել է լաբիրինթից կարճագույն ճանապարհը գտնելու համար,<ref name="skiena">{{cite book |first=Steven |last=Skiena |authorlink=Steven Skiena |title=The Algorithm Design Manual |publisher=Springer |year=2008 |page=480 |doi=10.1007/978-1-84800-070-4_4}}</ref> և իրարից անկախ բացահայտվել է Լիի կողմից, որպես լարի երթուղայնացման ալգորիթմ (հրատարակվել է 1961)։<ref>{{cite conference |title=A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) |first1=Charles E. |last1=Leiserson |authorlink1=Charles E. Leiserson |first2=Tao B. |last2=Schardl |conference=ACM Symp. on Parallelism in Algorithms and Architectures |year=2010 |url=http://supertech.csail.mit.edu/papers/pbfs.pdf}}</ref><ref>{{cite news |title=An Algorithm for Path Connections and Its Applications |first1=C. Y. |last1=Lee |journal=IRE Transactions on Electronic Computers |year=1961 |url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5219222}}</ref>
== Ծանոթագրություններ ==
{{ծանցանկ}}
{{Արտաքին հղումներ}}
[[Կատեգորիա:Փնտրման ալգորիթմներ]]
| |||