Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



М-блоковий пошук

План

Алгоритм проходження графу вшир

 

При проходженні вшир замість стека рекурсивних викликів зберігається черга, в яку записуються вершини в порядку віддалення від початкової.

Визначимо списки суміжності для кожної вершини графа G (рисунок 7.3):

1:2,3, 52:1, 3, 4 3:1,2,4,5 4:2,35:1,3

t: 1, 2, 3, 4, 5 (для обраної вершини переписуємо весь список суміжності).

Виберемо початкову вершину хn . Перші елементи шуканої перестановки t є елементами суміжного списку вершини хn, тобто М(хn). Позначимо список суміжності в такий спосіб: М(хn) = {(w1, xn), (w2, xn),...,(wk, xn)}. Наступними елементами перестановки будуть ті елементи M(w1), які відсутні у формованій перестановці t. Потім, беремо всі елементи з M(w2), і т.ін. Проходження припиняється, коли всі вершини, досяжні з хn, будуть утримуватися в

t (wi Ο Х, i=1,2,...,k)...

Знову ж таки, введемо масив used, а також створимо чергу для зберігання вершин (реалізуємо її у вигляді масиву queue; природно, можливі інші варіанти). У початок черги запишемо початкову вершину.

 

Star:=1; {початкова вершина - перша}

queue[1] = start;

used[start] = 1;

r = 1 ,w = 2;

{r - позиція черги, з якої читаємо дані, змінна w— позиція, куди дані будемо

записувати}

while (r < w) do

begin

curr:= queue[r]; {беремо перший елемент із черги}

іnсl;

for і: = 1 to N do

begin

if (used [i]:= true) and (a[curr][i]=1) then

begin

used[i] := 1;

queue[w] := I;

inc(w);

end;

end;

end;

 

Контрольні питання

 

1. Способи подання графу.

2. Поясніть основні кроки алгоритму розташування позначок.

3. наведіть приклад застосування алгоритму Дейкстри.

Тести для закріплення матеріалу

1. Визначити суміжні вершини до вершини В у графі, заданому матрицею суміжності:

а) ACD;

б) CD;

в) АС;

г) немає правильної відповіді.

 

 

2. Визначити суміжні вершини до вершини А у графі, заданому матрицею суміжності:

а) BCD;

б) CD;

в) В;

г) немає правильної відповіді.

 

 

3. Визначити суміжні вершини до вершини В у графі, заданому матрицею суміжності:

а) ACD;

б) CD;

в) АС;

г) немає правильної відповіді.

 

 

4. Визначити суміжні вершини до вершини С у графі, заданому матрицею суміжності:

а) ACD;

б) CD;

в) BE;

г) немає правильної відповіді.

 

 

5. Визначити суміжні вершини до вершини D у графі, заданому матрицею суміжності:

а) ABD;

б) CD;

в) BE;

г) немає правильної відповіді.

 

 

6. Визначити суміжні вершини до вершини Е у графі, заданому матрицею суміжності:

а) ABD;

б) CD;

в) BE;

г) немає правильної відповіді.


ЛЕКЦІЯ № 6

 

Тема: Алгоритми пошуку

 

Ціль: розглянути алгоритми пошуку стрічок: прямий пошук, Ахо-Корасика, Кнута-Моріса-Прата, Рабіна-Карпа, Боуєра-Мура. Алгоритми пошуку у масивах та списках

 

 

1 Загальна класифікація алгоритмів пошуку

2 Лінійний пошук

3 Двійковий (бінарний) пошук елемента в масиві

4 Пошук методом Фібоначчі


Читайте також:

  1. Абсолютизація формально-технічних пошуків у мистецтві ХХ ст.
  2. Багатомовна пошукова система
  3. Бібліографія. Інформаційно-пошукові мови бібліографічних фондів. Види каталогів: систематичні, предметні, абеткові.
  4. Будівельний підряд. Підряд на проектні та пошукові роботи.
  5. Визначення методу пошуку.
  6. ВІЛЬНИЙ ПОШУК (у тому числі ВАЛІДАЦІЯ) ® ПРОГНОСТИЧНЕ МОДЕЛЮВАННЯ ® АНАЛІЗ ВИКЛЮЧЕНЬ
  7. Евристичний пошук
  8. Етап 2. Пошук оновлень
  9. Зародження ” М. Стельмаха як письменника. Риси творчості та стильові пошуки.
  10. Засоби зберігання та пошуку документів
  11. Інтенсифікується пошук світового центру управління та інструментів регулювання глобальних світогосподарських процесів.
  12. Інформаційні джерела як засіб проектної технології. Класифікація джерел інформації. Пошук необхідної інформації в довідниках та журналах.




Переглядів: 897

<== попередня сторінка | наступна сторінка ==>
Алгоритм проходження графу вглиб | Методи обчислення адреси

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.104 сек.