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

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

Փնտրում դեպի լայնություն
Breadth-first-tree.svg
Տեսակuninformed search algorithm? և graph traversal?
Դասփնտրման ալգորիթմ
Տվյալների կառուցվածք
Վատագույն դեպքում կատարումը
Օգտագործում էգրաֆ
ՀայտնաբերողԿոնրադ Ցուզե


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

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

ՓսեուդոկոդԽմբագրել

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

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

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

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)

Ավելի մանրամասնԽմբագրել

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

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

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

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

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

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

ՕրինակԽմբագրել

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

ԾանոթագրություններԽմբագրել

  1. «Graph500 benchmark specification (supercomputer performance evaluation)»։ Graph500.org, 2010։ Արխիվացված է օրիգինալից 2015-03-26-ին։ Վերցված է 2016-08-23 
  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