«Փնտրում դեպի լայնություն»–ի խմբագրումների տարբերություն
Content deleted Content added
հեռացվել է Կատեգորիա:Ալգորիթմներ ՀոթՔաթ գործիքով |
No edit summary |
||
| Տող 9. | Տող 9. | ||
Ալգորիթմը ստեղծվել է ուշ [[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> |
Ալգորիթմը ստեղծվել է ուշ [[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> |
||
== Pseudocode == |
|||
'''Մուտք''': Գրաֆ և գրաֆի սկզբնական գագաթը |
|||
'''Ելք''': Բոլոր գագթնորը հասանելի են այն արմատից, որը բացահայտված է։ |
|||
Փնտրում դեպի լայնության ոչ-ռեկուրսիվ ներկայացումը |
|||
<source lang="java" line="1"> |
|||
Breadth-First-Search(Graph, root): |
|||
for each node n in Graph: |
|||
n.distance = INFINITY |
|||
n.parent = NIL |
|||
create empty queue Q |
|||
root.distance = 0 |
|||
Q.enqueue(root) |
|||
while Q is not empty: |
|||
current = Q.dequeue() |
|||
for each node n that is adjacent to current: |
|||
if n.distance == INFINITY: |
|||
n.distance = current.distance + 1 |
|||
n.parent = current |
|||
Q.enqueue(n) |
|||
</source> |
|||
== Ծանոթագրություններ == |
== Ծանոթագրություններ == |
||
12:29, 23 Օգոստոսի 2016-ի տարբերակ
| Փնտրում դեպի լայնություն | |
|---|---|
 | |
| Տեսակ | uninformed search algorithm? և graph traversal? |
| Դաս | փնտրման ալգորիթմ |
| Տվյալների կառուցվածք | Գրաֆ |
| Վատագույն դեպքում կատարումը | |
| Վատագույն դեպքում տարածքի բարդությունը | |
| Օգտագործում է | գրաֆ |
| Հայտնաբերող | Կոնրադ Ցուզե |
Փնտրում դեպի լայնությունը գրաֆը շրջանցելու մեթոդներից մեկը։ Այն սկսվում է ծառի արմատից(կամ կամայական այլ հանգույց, երբեմն անվանում են «փնտրման բանալի»[1]) և սկզնում բացահայտում է հարևան հանգույցներին մինչև մյուս կարգի հարևաններին բացահայտելը։
Ալգորիթմը ստեղծվել է ուշ 1950-ականներին Է․Ֆ․ Մուրի կողմից, ով օգտագործել է լաբիրինթից կարճագույն ճանապարհը գտնելու համար,[2] և իրարից անկախ բացահայտվել է Լիի կողմից, որպես լարի երթուղայնացման ալգորիթմ (հրատարակվել է 1961)։[3][4]
Pseudocode
Մուտք: Գրաֆ և գրաֆի սկզբնական գագաթը
Ելք: Բոլոր գագթնորը հասանելի են այն արմատից, որը բացահայտված է։
Փնտրում դեպի լայնության ոչ-ռեկուրսիվ ներկայացումը
Breadth-First-Search(Graph, root):
for each node n in Graph:
n.distance = INFINITY
n.parent = NIL
create empty queue Q
root.distance = 0
Q.enqueue(root)
while Q is not empty:
current = Q.dequeue()
for each node n that is adjacent to current:
if n.distance == INFINITY:
n.distance = current.distance + 1
n.parent = current
Q.enqueue(n)
Ծանոթագրություններ
- ↑ «Graph500 benchmark specification (supercomputer performance evaluation)». Graph500.org, 2010.
- ↑ Skiena, Steven (2008). The Algorithm Design Manual. Springer. էջ 480. doi:10.1007/978-1-84800-070-4_4.
- ↑ Leiserson, Charles E.; Schardl, Tao B. (2010). A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) (PDF). ACM Symp. on Parallelism in Algorithms and Architectures.
- ↑ Lee, C. Y. (1961). «An Algorithm for Path Connections and Its Applications». IRE Transactions on Electronic Computers.
 | Վիքիպահեստն ունի նյութեր, որոնք վերաբերում են «Փնտրում դեպի լայնություն» հոդվածին։ |
|
