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

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

Փնտրում դեպի լայնություն
Տեսակ	uninformed search algorithm? և graph traversal?
Դաս	փնտրման ալգորիթմ
Տվյալների կառուցվածք	$O(|V|)=O(b^{d})$
Վատագույն դեպքում կատարումը	$O(|V|+|E|)=O(b^{d})$
Օգտագործում է	գրաֆ
Հայտնաբերող	Կոնրադ Ցուզե

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

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

Փսեուդոկոդ

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

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

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

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»։

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

Օրինակ

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

Ծանոթագրություններ

Վիքիպահեստն ունի նյութեր, որոնք վերաբերում են «Փնտրում դեպի լայնություն» հոդվածին։