From Wikipedia, the free encyclopedia
Փնտրում դեպի լայնություն, գրաֆը շրջանցելու մեթոդներից մեկը։ Այն սկսվում է ծառի արմատից (կամ կամայական այլ հանգույց, երբեմն անվանում են «փնտրման բանալի»[1]) և սկզբում բացահայտում է հարևան հանգույցներին մինչև մյուս կարգի հարևաններին բացահայտելը։
Փնտրում դեպի լայնություն | |
---|---|
Տեսակ | uninformed search algorithm? |
Դաս | graph traversal? |
Տվյալների կառուցվածք | |
Վատագույն դեպքում կատարումը | |
Օգտագործում է | գրաֆ և FIFO? |
Հայտնաբերող | Կոնրադ Ցուզե |
Ալգորիթմը ստեղծվել է ուշ 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:
Յուրաքանչյուր գագաթի ծնող հատկությունը կարող է օգտակար լինել կարճագույն ճանապարհը գտնելու համար։
«NIL»-ը ուղղակի սիմվոլ է, որը ցույց է տալիս ինչ-որ բանի բացակայությունը, այս դեպքում ցույց է տալիս ծնող (կամ նապորդի) հանգույցի բացակայությունը, երբեմն, «NIL»-ի փոխարեն օգտագործում են «null», «none» կամ «nothing»։
Նշում, որ հանգույց բառը երբեմն փոխվում է գագաթ բառով։
Լայնության ծառի հետևյալ օրինակը ստացվել է՝ կիրառելով փնտրում դեպի լայնություն՝ Ֆրանկֆուրտից։
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.