Све што треба да знате о алгоритму прве претраге ширине



У овом блогу о алгоритму претраживања ширине првог, разговараћемо о логици метода прелажења графова и разумети рад истих.

Методе преласка графикона су ме увек прилично фасцинирале. Од извођења ефикасне равноправне комуникације до проналажења најближих ресторана и кафића помоћу ГПС-а, методе преласка имају разноврстан скуп апликација у стварном сценарију. У овом блогу о алгоритму претраживања најшире ширине разговараћемо о логици метода прелажења графова и на примерима ћемо разумети рад алгоритма претраживања најшире ширине.

Да бисте стекли детаљно знање о вештачкој интелигенцији и машинском учењу, можете се пријавити уживо Едурека са 24/7 подршком и доживотним приступом.





Ево листе тема које ће бити покривен на овом блогу:

  1. Увод у прелазак графикона
  2. Шта је ширина прва претрага?
  3. Разумевање алгоритма „Ширина-прво претраживање“ на примеру
  4. Псеудокод алгоритма за претрагу најшире ширине
  5. Примене најшире претраге

Увод у прелазак графикона

Процес посете и истраживања графа ради обраде назива се прелазак графа. Да будемо прецизнији, све се односи на посећивање и истраживање сваког темена и ивице на графикону тако да се сви врхови истражују тачно једном.



То звучи једноставно! Али ту је квака.

Постоји неколико техника преласка графова, као што је претрага ширина-прва, дубина прва претрага и тако даље. Изазов је користити графикон техника преласка која је најпогоднија за решавање одређеног проблема. Ово нас доводи до технике претраживања најшире ширине.

Шта је алгоритам претраживања ширине и ширине?

Алгоритам претраживања у ширину је техника прелажења графа, при којој одабирете случајни почетни чвор (изворни или коренски чвор) и започињете обилазак графа у слоју на такав начин да се сви чворови и њихови одговарајући подређени чворови посећују и истражују.



Пре него што кренемо даље и на примеру схватимо Бреадтх-Фирст Сеарцх, упознајмо се са два важна израза у вези са преласком графова:

Прелазак графикона - Алгоритам првог претраживања ширине - Едурека

  1. Посета чвору: Баш као што и само име говори, посета чвору значи посетити или одабрати чвор.
  2. Истраживање чвора: Истражујући суседни чворови (подређени чворови) изабраног чвора.

Погледајте горњу слику да бисте ово боље разумели.

Разумевање алгоритма претраге ширине и ширине на примеру

Широки алгоритам претраживања следи једноставан приступ заснован на нивоу за решавање проблема. Размотрите доле дато бинарно стабло (које је графикон). Наш циљ је да пређемо граф користећи алгоритам претраживања ширине и ширине.

Пре него што започнемо, морате бити упознати са главном структуром података која је укључена у алгоритам претраживања ширине и ширине.

Ред је апстрактна структура података која следи методологију Фирст-Ин-Фирст-Оут (прво ће се приступити подацима који су први уметнути). Отворен је на оба краја, при чему се један крај увек користи за уметање података (енкуеуе), а други за уклањање података (декуеуе).

Сада ћемо погледати кораке који су укључени у прелажењу графа помоћу претраживања ширина-прва:

Корак 1: Узмите празан ред.

Корак 2: Изаберите почетни чвор (посетите чвор) и убаците га у Ред.

Корак 3: Под условом да Ред није празан, извуците чвор из реда и уметните његове подређене чворове (истражујући чвор) у Ред.

Корак 4: Одштампајте извучени чвор.

Не брините ако сте збуњени, разумећемо ово на примеру.

Погледајте доњи графикон, користићемо алгоритам за претрагу у ширину да бисмо се кретали по графикону.

У нашем случају ћемо доделити чвор „а“ као основни чвор и започети кретање надоле и следити горе поменуте кораке.

Горња слика приказује завршени процес алгоритма за претрагу ширине и ширине. Дозволите ми да ово објасним детаљније.

  1. Доделите „а“ као основни чвор и убаците га у Ред.
  2. Извадите чвор „а“ из реда и уметните подређене чворове „а“, тј. „Б“ и „ц“.
  3. Чвор за испис „а“.
  4. Ред није празан и има чвор „б“ и „ц“. Будући да је „б“ први чвор у реду, извуцимо га и убацимо подређене чворове „б“, тј. Чвор „д“ и „е“.
  5. Понављајте ове кораке док се ред не испразни. Имајте на уму да чворови који су већ посећени не треба додавати у ред опет.

Погледајмо сада псеудокод алгоритма за претрагу најшире ширине.

Псеудокод алгоритма за претрагу најшире ширине

Ево псеудокода за примену алгоритма за претрагу ширине прва:

Улаз: с као изворни чвор БФС (Г, с) нека К буде ред. К.енкуеуе (с) означавају посећене док (К није празно) в = К.декуеуе () за све суседе в од в на Графикону Г ако в није посећен К.енкуеуе (в) означавају в као посећене

У горњем коду извршавају се следећи кораци:

  1. (Г, с) је улаз, овде је Г графикон, а с је коријенски чвор
  2. Ред „К“ се креира и иницијализује изворним чвором „с“
  3. Означени су сви подређени чворови „с“
  4. Издвојите „с“ из реда и посетите подређене чворове
  5. Обрадите све подређене чворове в
  6. Чува в (подређене чворове) у К да би даље посетио његове подређене чворове
  7. Наставите док не истекне „К“ празна

Пре него што завршимо са блогом, погледајмо неке примене алгоритма за претрагу најшире ширине.

Примене алгоритма за претрагу ширине прве

је магистарска диплома која се сматра постдипломском

Претраживање ширине ширине је једноставна метода прелажења графова која има изненађујући спектар примена. Ево неколико занимљивих начина на које се користи претрага од прве врсте хлеба:

Пописивачи у претраживачима: Широко претраживање прво је један од главних алгоритама који се користи за индексирање веб страница. Алгоритам започиње прелазак са изворне странице и прати све везе повезане са страницом. Овде ће се свака веб страница сматрати чвором на графикону.

ГПС навигациони системи: Бреадтх-Фирст Сеарцх је један од најбољих алгоритама који се користи за проналажење суседних локација помоћу ГПС система.

Пронађите најкраћи пут и минимално распонско дрво за непондерисани графикон: Када је реч о непондерисаном графу, израчунавање најкраће путање је прилично једноставно, јер је идеја најкраће путање одабрати путању са најмањим бројем ивица. Претрага у ширину може то да дозволи прелазећи минимални број чворова почевши од изворног чвора. Слично томе, за дрвеће које се протеже, можемо да користимо било коју од две методе претраживања ширине-прве или дубине-прво за проналажење стабла растезања.

Емитовање: Умрежавање користи оно што називамо пакетима за комуникацију. Ови пакети следе методу обилажења да би дошли до различитих мрежних чворова. Једна од најчешће коришћених метода преласка је претрага ширина-прва. Користи се као алгоритам који се користи за комуникацију емитираних пакета преко свих чворова у мрежи.

Пеер то Пеер умрежавање: Ширина-прво претраживање може се користити као метод обилажења да би се пронашли сви суседни чворови у Пеер то Пеер мрежи. На пример, БитТоррент користи широку претрагу за равноправну комуникацију.

Дакле, то је било све о раду алгоритма „Ширина-прво претраживање“. Сад кад знате како да прелазите графиконе, сигуран сам да сте радознали да сазнате више. Ево неколико релевантних блогова који ће вас занимати:

  1. Увод у Марковљеве ланце са примерима - Марковљеви ланци са Питхоном

Овим смо дошли до краја овог блога. Ако имате питања у вези са овом темом, оставите коментар испод и јавићемо вам се.

Ако желите да се упишете на комплетан курс о вештачкој интелигенцији и машинском учењу, Едурека има посебно курираног то ће вас оспособити за технике попут учења под надзором, учења без надзора и обраде природног језика. Обухвата обуку о најновијим достигнућима и техничким приступима у вештачкој интелигенцији и машинском учењу као што су дубоко учење, графички модели и учење ојачања.