Всичко, което трябва да знаете за алгоритъма за първо търсене на широчина

Методите за обръщане на графики винаги са ме очаровали. От осъществяването на ефективна равностойна комуникация до намиране на най-близките ресторанти и кафенета с помощта на GPS, методите за обхождане имат разнообразен набор от приложения в реалния сценарий. В този блог за Breadth-First Search Algorithm ще обсъдим логиката на методите за обхождане на графики и ще използваме примери, за да разберем работата на алгоритъма за първо търсене на широчина.

За да получите задълбочени познания по изкуствен интелект и машинно обучение, можете да се запишете на живо от Edureka с денонощна поддръжка и доживотен достъп.

Ето списък с теми, които ще бъдат обхванати в този блог:

използване на charat в java

1. Въведение в обхождането на графики
2. Какво е търсенето на първо ниво?
3. Разбиране на алгоритъма за първо търсене на ширина с пример
4. Псевдокод за алгоритъм за първо търсене на широчина
5. Приложения за първоначално търсене

Въведение в обхождането на графики

Процесът на посещение и изследване на графика за обработка се нарича обръщане на графика. За да бъдем по-конкретни, всичко е свързано с посещение и изследване на всеки връх и ръб в графика, така че всички върхове да бъдат изследвани точно веднъж.

Това звучи просто! Но има уловка.

Има няколко техники за обхождане на графики, като например търсене на ширина-първо, първо търсене на дълбочина и така нататък. Предизвикателството е да се използва графика обходна техника, която е най-подходяща за решаване на определен проблем. Това ни води до техниката за първо търсене на ширина.

Какво представлява алгоритъмът за първо търсене на широчина?

Breadth-First Search алгоритъм е техника за пресичане на графика, при която избирате произволен начален възел (източник или корен възел) и започвате да обхождате графиката по слой по такъв начин, че всички възли и съответните им възли деца да бъдат посетени и изследвани.

Преди да преминем по-нататък и да разберем Breadth-First Search с пример, нека се запознаем с два важни термина, свързани с обръщането на графики:

1. Посещение на възел: Точно както подсказва името, посещението на възел означава да посетите или изберете възел.
2. Проучване на възел: Проучване на съседни възли (дъщерни възли) на избран възел.

Вижте горната фигура, за да разберете по-добре това.

Разбиране на алгоритъма за първоначално търсене с пример

Широкият алгоритъм за първо търсене следва прост подход, основан на ниво, за решаване на проблем. Помислете за бинарното дърво по-долу (което е графика). Нашата цел е да прекосим графиката с помощта на алгоритъма за първо търсене на широчина.

Преди да започнем, трябва да сте запознати с основната структура на данните, включена в алгоритъма за търсене на ширина-първо.

Опашката е абстрактна структура от данни, която следва методологията First-In-First-Out (първо ще бъдат получени данни, въведени първи). Той е отворен от двата края, където единият край винаги се използва за вмъкване на данни (опашка), а другият се използва за премахване на данни (отмяна).

Сега нека да разгледаме стъпките, свързани с обхождането на графика, като използваме Търсене на ширина първо:

Етап 1: Вземете празна опашка.

Стъпка 2: Изберете начален възел (посещение на възел) и го поставете в опашката.

Стъпка 3: При условие, че опашката не е празна, извлечете възела от опашката и вмъкнете нейните дъщерни възли (проучване на възел) в опашката.

Стъпка 4: Отпечатайте извлечения възел.

Не се притеснявайте, ако сте объркани, ще разберем това с пример.

Погледнете графиката по-долу, ние ще използваме алгоритъма за първо търсене на ширина, за да преминем през графиката.

В нашия случай ще присвоим възел „a“ като основен възел и ще започнем да се движим надолу и да следваме стъпките, споменати по-горе.

Горното изображение изобразява процеса от край до край на алгоритъма за първо търсене на широчина. Нека да обясня това по-задълбочено.

1. Задайте ‘a’ като основен възел и го вмъкнете в опашката.
2. Извлечете възел „а“ от опашката и вмъкнете дъщерните възли на „а“, т.е. „b“ и „c“.
3. Печат на възел „а“.
4. Опашката не е празна и има възел „b“ и „c“. Тъй като „b“ е първият възел в опашката, нека го извлечем и вмъкнем дъщерните възли на „b“, т.е. възел „d“ и „e“.
5. Повторете тези стъпки, докато опашката не се изпразни. Имайте предвид, че възлите, които вече са посетени, не трябва да се добавят към опашката отново.

Сега нека разгледаме псевдокода на алгоритъма за първо търсене на ширина.

Широчина-Първо алгоритъм за търсене Псевдокод

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

Въвеждане: s като възел BFS на източника (G, s) нека Q бъде опашка. Q.enqueue (и) маркират s като посетени докато (Q не е празен) v = Q.dequeue () за всички съседи w от v в Графика G, ако w не е посетен Q.enqueue (w) маркират w като посетени

В горния код се изпълняват следните стъпки:

1. (G, s) е въведено, тук G е графиката и s е коренният възел
2. Опашка „Q“ се създава и инициализира с възела на източника „s“
3. Всички дъщерни възли на „s“ са маркирани
4. Извлечете ‘s’ от опашката и посетете дъщерните възли
5. Обработете всички дъщерни възли на v
6. Съхранява w (дъщерни възли) в Q за по-нататъшно посещение на неговите дъщерни възли
7. Продължете, докато ‘Q’ стане празен

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

Приложения на алгоритъм за първо търсене на широчина

Широкото търсене е прост метод за обхождане на графики, който има изненадващ набор от приложения. Ето няколко интересни начина, по които се използва търсенето на хляб:

Роботи в търсачките: Breadth-First Search е един от основните алгоритми, използвани за индексиране на уеб страници. Алгоритъмът започва да преминава от изходната страница и следва всички връзки, свързани със страницата. Тук всяка уеб страница ще се разглежда като възел в графика.

GPS навигационни системи: Breadth-First Search е един от най-добрите алгоритми, използван за намиране на съседни местоположения с помощта на GPS системата.

Намерете най-краткия път и минималното обхващащо се дърво за непретеглена графика: Когато става въпрос за непретеглена графика, изчисляването на най-краткия път е съвсем просто, тъй като идеята зад най-краткия път е да се избере път с най-малък брой ръбове. Широкото първо търсене може да позволи това чрез обхождане на минимален брой възли, започвайки от изходния възел. По същия начин, за обхващащо дърво, можем да използваме един от двата метода за търсене на ширина първо или дълбочина първо, за да намерим обхващащо дърво.

Излъчване: Мрежата използва това, което наричаме пакети за комуникация. Тези пакети следват метод на обхождане, за да достигнат до различни мрежови възли. Един от най-често използваните методи за преминаване е търсене на ширина-първо. Той се използва като алгоритъм, който се използва за комуникация на излъчвани пакети през всички възли в мрежата.

Партньорска мрежа: Широкото първо търсене може да се използва като метод за обхождане, за да се намерят всички съседни възли в Peer to Peer Network. Например, BitTorrent използва Breadth-First Search за равнопоставена комуникация.

Така че всичко беше свързано с работата на алгоритъма за първоначално търсене. След като знаете как да прекосявате графики, съм сигурен, че сте любопитни да научите повече. Ето няколко подходящи блога, за да се интересувате:

3. Въведение в веригите на Марков с примери - Веригите на Марков с Python

С това стигнахме до края на този блог. Ако имате въпроси относно тази тема, моля, оставете коментар по-долу и ние ще се свържем с вас.

Ако искате да се запишете за пълен курс по изкуствен интелект и машинно обучение, Edureka има специално подготвен което ще ви направи владеещи техники като контролирано обучение, ненаблюдавано обучение и обработка на естествен език. Включва обучение за най-новите постижения и технически подходи в областта на изкуствения интелект и машинното обучение като дълбоко обучение, графични модели и обучение за подсилване.