• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

План

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

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

Визначимо списки суміжності для кожної вершини графа 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) = {(w₁, x_n), (w₂, x_n),...,(w_k, x_n)}. Наступними елементами перестановки будуть ті елементи M(w₁), які відсутні у формованій перестановці t. Потім, беремо всі елементи з M(w₂), і т.ін. Проходження припиняється, коли всі вершини, досяжні з х_n, будуть утримуватися в

t (w_i Ο Х, 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. Інформаційні джерела як засіб проектної технології. Класифікація джерел інформації. Пошук необхідної інформації в довідниках та журналах.

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