Փնտրում դեպի լայնություն

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Փնտրում դեպի լայնություն
Breadth-first-tree.svg
Տեսակ algorithm in graph theory
Դաս փնտրման ալգորիթմ
Օգտագործում է գրաֆ


Փնտրում դեպի լայնության անիմացիոն օրինակ

Փնտրում դեպի լայնություն, գրաֆը շրջանցելու մեթոդներից մեկը։ Այն սկսվում է ծառի արմատից (կամ կամայական այլ հանգույց, երբեմն անվանում են «փնտրման բանալի»[1]) և սկզբում բացահայտում է հարևան հանգույցներին մինչև մյուս կարգի հարևաններին բացահայտելը։

Ալգորիթմը ստեղծվել է ուշ 1950-ականներին Էդվարդ Մուրի կողմից, ով օգտագործել է լաբիրինթից կարճագույն ճանապարհը գտնելու համար,[2] և իրարից անկախ բացահայտվել է Լիի կողմից, որպես լարի երթուղայնացման ալգորիթմ (հրատարակվել է 1961)։[3][4]

Փսեուդոկոդ[խմբագրել | խմբագրել կոդը]

Մուտք: Գրաֆ և գրաֆի սկզբնական գագաթը

Ելք: Բոլոր գագաթները հասանելի են այն արմատից, որը բացահայտված է։

Փնտրում դեպի լայնության ոչ-ռեկուրսիվ ներկայացումը

 1 Breadth-First-Search(Graph, root):
 2 
 3     for each node n in Graph:            
 4         n.distance = INFINITY        
 5         n.parent = NIL
 6 
 7     create empty queue Q      
 8 
 9     root.distance = 0
10     Q.enqueue(root)                      
11 
12     while Q is not empty:        
13     
14         current = Q.dequeue()
15     
16         for each node n that is adjacent to current:
17             if n.distance == INFINITY:
18                 n.distance = current.distance + 1
19                 n.parent = current
20                 Q.enqueue(n)

Ավելի մանրամասն[խմբագրել | խմբագրել կոդը]

Այս ոչ-ռեկուրսիվ ներկայացումը նման է փնտրում դեպի խորության ոչ-ռեկուրսիվ ներկայացմանը, բայց տարբերվում է երկու բանով․

  1. օգտագործում է հերթ սթեքի փոխարեն
  2. այն ստուգում է, թե հանգույցը բացահայտվել է, մինչ հերթի մեջ գցվելը, այլ ոչ թե հետաձգում ստուգումը, մինչև գագաթը դուրս կբերեն հերթից։

Յուրաքանչյուր գագաթի (կամ հանգույցի) երկարությունը պետք է, երբ գրաֆի գագաթների միջև փնտրում ենք կարճագույն ճանապարհը։ Ալգորիթմի սկզբում յուրաքանչյուր գագաթի երկարությունը անսահմանություն է, որը ուղակի ցույց է տալիս, որ գագաթը դեռ չի բացահայտվել, այսպիսով այն սկզբնական գագաթից չունի հեռավորություն։ Կարող ենք օգտագործել ուրիշ սիմվոլներ, օրինակ՝ -1:

Յուրաքանչյուր գագաթի ծնող հատկությունը կարող է օգտակար լինել կարճագույն ճանապարհը գտնելու համար:

«NIL»-ը ուղակի սիմվոլ է, որը ցույց է տալիս ինչ-որ բանի բացակայությունը, այս դեպքում ցույց է տալիս ծնող (կամ նապորդի) հանգույցի բացակայությունը, երբեմն, «NIL»-ի փոխարեն օգտագործում են «null», «none» կամ «nothing»։

Նշում, որ հանգույց բառը երբեմն փոխվում է գագաթ բառով։

Օրինակ[խմբագրել | խմբագրել կոդը]

Լայնության ծառի հետևյալ օրինակը ստացվել է՝ կիրառելով փնտրում դեպի լայնություն՝ Ֆրանկֆուրտից։

MapGermanyGraph.svg
GermanyBFS.svg

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. «Graph500 benchmark specification (supercomputer performance evaluation)»։ Graph500.org, 2010 
  2. Skiena, Steven (2008). The Algorithm Design Manual. Springer. էջ 480. doi:10.1007/978-1-84800-070-4_4. 
  3. Leiserson Charles E., Schardl Tao B. (2010)։ A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers)։ ACM Symp. on Parallelism in Algorithms and Architectures 
  4. Lee C. Y. (1961)։ «An Algorithm for Path Connections and Its Applications»։ IRE Transactions on Electronic Computers