Теорія графів. Пошук у глибину

У п'ятницю 11.11.11 відбулося чергове заняття ообласної чно-дистанційної школи олімпійського резерву з програмування. Тема заняття "Теорія графів. Пошук у глибину".

Пошук у глибину

Нехай дано граф G = (V, E) і фіксована початкова вершина v. При пошуку в глибину змінюється стратегія перегляду вершин графа. Рух здійснюється від однієї вершини до іншої, з нею суміжної, поступово віддаляючись від початкової вершини, доки не дійдемо до тупика. Вершина неорієнтованого графа є тупиком, якщо вже відвідані всі суміжні з нею вершини. В орієнтованому графі ним може бути вершина, з якої не виходить жодне ребро (вихідний степінь 0).

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

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

Задача. Скласти програму, що реалізує алгоритм пошуку в глибину. Зв’язний неорієнтований граф представлений за допомогою матриці суміжності. Задана вершина, з якої починається обхід графа. При відвідуванні чергової вершини програма друкує її номер.
Для розв’язання застосуємо масив lb, який містить прапорці для кожної вершини, що означають, чи відвідувалась раніше відповідна вершина.

Реалізуємо алгоритм за допомогою рекурсивної процедури. Якщо для чергової вершини знайдена суміжна з нею вершина, яка ще не була відвідана, друкуємо номер чергової вершини, помічаємо її, а для суміжної викликаємо рекурсивну процедуру.

Якщо суміжних невідвіданих вершин не знайдено, то повертаємось з рекурсії.

Задача.
Кожен кабінет інформатики в школі має власну локальну мережу. Шкільні комп’ютери мають імена, що відповідають числам від 1 до N. Для підключення всіх комп’ютерів до глобальної мережі Інтернет директор вирішив зробити об’єднану локальну мережу школи. Для цього від кожного кабінету інформатики треба протягти кабель до шкільного хаба. Скільки вільних портів повинен мати хаб для забезпечення підключення кожного кабінету?

У вхідному файлі зберігається кількість комп’ютерів в школі N та матриця суміжності, в якій зафіксовано, між якими комп’ютерами прокладені канали зв’язку в локальних мережах класів. У вихідний файл вивести кількість кабінетів інформатики в школі.

Теорія графів. Пошук у ширину

У п'ятницю 4 листопада о 15.00 відбудеться чергове заняття обласної очно-дистанційної Школи олімпійського резерву з програмування.

Тема заняття "Теорія графів. Пошук у ширину".

Пошук у ширину

Пошуком називають операцію, яка спрямована на отримання певної інформації з набору даних, що зібрані та зберігаються з певною метою.

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

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

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

Нехай дано граф G = (V, E) і фіксована початкова вершина v. При обході графа в ширину на першому кроці відвідуються всі вершини, сусідні з початковою. При другому проході відвідуються всі вершини "на відстані двох ребер" від початкової. При кожному новому проході опрацьовуються вершини, відстань від яких (кількість ребер) до початкової на одиницю більша від попередньої. У графі можуть бути цикли, тому не виключено, що одну й ту саму вершину можна досягти з початковою двома різними шляхами. Ця вершина опрацьовується один раз, коли буде досягнутою найкоротшим до неї шляхом, і відвідувати її другий раз немає сенсу. Тому, щоб попередити повторне відвідування, доцільно або вести список відвіданих вершин, або завести для кожної прапорець, який би вказував, чи опрацьована вже ця вершина.

Заняття 28.10.2011

У п'ятницю 28.10.2011 заняття обласної Школи олімпійського резерву з програмування відбудеться о 15.00.

Тема заняття "Теорія графів. Алгоритм Дейкстри".

Алгоритм Дейкстри

Цей алгоритм для розв’язання задачі знаходження найкоротших маршрутів на карті був запропонований Дейкстрой (E.W. Dijkstra) у 1959 році.

Алгоритм дозволяє знайти розв’язок задачі про найкоротші шляхи у зваженому графі від визначеної вершини до всіх інших за умови, що вага ребер невід’ємна. Ідея алгоритму полягає в тому, щоб прокладати маршрути через проміжні вершини, обираючи на кожному кроці найкоротші доступні ребра графа.

Введемо позначення для детального опису алгоритму. Вершину, для якої шукаємо шляхи до всіх інших, назвемо стартовою (її номер позначимо St). Алгоритм використовує три масиви з n чисел кожний (n – кількість вершин графа). Перший масив містить мітки з двома значеннями: 0 – вершина ще не розглянута, і 1 – вершина вже розглянута. Назвемо цей масив Lbl. Другий масив містить значення найкоротших на момент перегляду відстаней від кожної вершини графа до стартової вершини. Позначимо цей масив Dist. Третій масив містить номери вершин, відвідування яких дозволяє скоротити довжину шляху від стартової вершини Vst до поточної (попередники на шляху до поточної вершини). Ім’я третього масиву – Path. Матриця відстаней D задає довжини ребер у графі; якщо між вершинами з номерами і та k прямої дуги немає, то D[і, k] містить число, умовно рівне "машинній нескінченності".

У першому наближенні вважаємо за найкоротші шляхи від стартової вершини до всіх інших прямий шлях, довжина якого зазначена у матриці відстаней. Значення цих відстаней заносимо до масиву Dist, а номер стартової вершини – до масиву Path.

Далі намагаємось скоротити відстані, обираючи шлях через інші вершини замість прямого. Вибір проміжних вершин здійснюємо "жадібним" методом. Для цього знаходимо вершину, шлях до якої на даному кроці найкоротший (найменше значення в масиві Dist), але спроби обрати її за проміжну ще не виконувалось (відповідне їй значення в масиві Lbl дорівнює 0; замінюємо його на 1). Для кожної вершини обчислюємо довжину шляху через обрану проміжну вершину. Якщо отримана відстань скорочує шлях до стартової вершини, заносимо її до відповідного елемента масиву Dist, а номер проміжної вершини – до масиву Path. Спробу скоротити відстань повторюємо, доки не розглянемо в ролі проміжних усі вершини графа.

Для відновлення номерів вершин у найкоротших шляхах використовуємо дані з масиву Path.

Порядок виконання алгоритму наступний.

1. Ініціалізація.
У циклі від 1 до n заповнюємо нулями масив Lbl.
Заповнюємо масив Path номером стартової вершини St.
Переносимо рядок з індексом St матриці D до масиву Dist.
Lbl [St] = 1; Path [St] = 0;

2. Визначення довжини шляхів.
Повторимо n – 2 рази операцію уточнення маршруту:
2.1. Знаходимо мінімальну з відстаней до неопрацьованих вершин (тобто тих j, для яких Lbl [j] = 0; j = 1, …, n). Припустимо, що мінімум знаходиться під індексом k.
2.2. Помічаємо вершину k як опрацьовану: Lbl [k] = 1;
2.3. Для всіх неопрацьованих вершин, тобто для всіх j від 1 до n, таких що Lbl [j] = 0:
Якщо Dist [j] > Dist [k] + D [j, k], то Dist [j] = Dist [k] + D [j, k]; Path [j] = k.
Умова означає, що шлях від стартової вершии Vst до поточної Vj довший, ніж шлях через проміжну вершину: від Vst до Vk плюс шлях від Vk до Vj.
Після виконання n – 2 ітерацій масив Dist міститиме остаточні довжини шляхів від стартової вершини до всіх інших.

3. Тепер треба назвати всі вершини, що входять до найкоротшого маршруту.
Шлях від стартової вершини Vst до будь-якої зазначеної Vj виводиться у зворотному напрямку наступним чином.
3.1. Z = Path[j];
3.2. Вивести Z;
3.3. Z = Path[Z]. Якщо Z = 0, то виведення маршруту завершено, в іншому разі перейти до 3.2.

Виконання алгоритму завершено.

Алгоритму в даній реалізації потрібно n – 2 разів переглянути масив Dist з n елементів, тобто алгоритм Дейкстри має квадратичну складність: O(n2).

Теорія графів. Основні поняття

На другому занятті обласної школи олімпійського резерву з програмування 21 жовтня були розглянуті основні поняття теорії графів та алгоритм Прима-Крускала знаходження мінімального остовного дерева.

Алгоритм Прима-Крускала
Розглянемо задачу. На території плоскої країни розташовано n міст. Потрібно з’єднати всі міста телефонним зв’язком так, щоб загальна довжина телефонних ліній була мінімальною.

Алгоритм знаходження мінімального остовного дерева використовує "жадібну" стратегію – на кожному кроці обирається й додається до дерева, що будується, ребро з найменшою вагою, яке не утворює циклів з уже обраними ребрами.

Перевірка того, що ребро не утворює циклів, може виконуватися за допомогою прийому, який називають розфарбуванням графу. Він полягає в тому, що кожній вершині графа умовно дається колір, закодований числом. Якщо ребро додається до остовного дерева, то його кінці й усі пов’язані з ними вершини остовного дерева перефарбовуються в однаковий колір. Кандидатами на додавання до остовного дерева будуть лише ті ребра графа, кінці яких пофарбовані у різні кольори.

Якщо граф має n вершин, то мінімальне остовне дерево буде складатися з n – 1 ребра, тобто виконання алгоритму завершується за n – 1 крок.

Опис основних понять теорії графів та алгоритму Прима-Крускала - тут.

Школа олімпійського резерву. Сезон 2011-2012

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

14 жовтня відбулось перше заняття в режимі он-лайн. Присутні - учні шкіл Полтави та Кременчука. Тема заняття "Визначення положення точки відносно вектора". Розглянуті задачі:

1. Опукла оболонка. Задана множина з n точок на площині, жодні три з яких не лежать на одній прямій. Відомі координати цих точок. Визначити, які з них є вершинами опуклого многокутника, у середині якого містяться усі інші точки даної множини. Вивести вершини у порядку обходу.

2. Ламана. Задана множина з n точок на площині. Відомі координати цих точок. З'єднати дані точки у такій послідовності, щоб утворилася замкнена ламана, жодні дві сторони якої не перетинаються. Вивести координати вершин у порядку з'єднання.

3. Трикутник. Задані координати вершин трикутника АВС та точки М. Визначити, чи лежить точка усередині трикутника. Вивести 1, якщо точка усередині трикутника; 0 - якщо на його межах; -1 - якщо ззовні.

Додаткові завдання:

4. Для трьох точок на одній прямій визначити, як розташована третя точка по відношенню до перших двох.

5. Розв'язати задачу 1 за умови, що деякі три точки можуть лежати на одній прямій. Передбачити, що не потрібно виводити координати точок, що лежать на сторонах опуклої оболонки.

Наступне заняття Школи олімпійського резерву - у п'ятницю 21 жовтня об 11.00. Тема заняття "Теорія графів. Алгоритм Прима-Крускала".

Літо – час вчитися

З 24 червня починає працювати оздоровчий табір “Ерудит”

при Кременчуцькому педагогічному училищі ім.А.С.Макаренка. Для учасників обласної олімпіади з інформатики, які відпочиватимуть у таборі, будуть проводитись заняття з програмування.

Готуймося до зустрічі, згадуємо алгоритми.

Задача для тренування:

У табір Ерудит приїдуть N школярів з усієї області (6 < N < 10 млрд). Для поселення виділені 2-місні та 5-місні кімнати у гуртожитку. Місця для поселення вистачить на всіх. Скільки кімнат кожного виду потрібно виділити для поселення, щоб у кімнатах не залишалось жодного вільного місця, а кількість кімнат була найменшою?

Готуємося до олімпіади

Готуємося до участі в обласній олімпіаді з інформатики.

Задача "Ігри зі словами"
Два друга вирішили перевірити, наскільки добре вони вміють читати думки один одного. Кожен з них задумав слово, а потім вони визначили, наскільки збігаються задумані слова.

Допоможіть хлопцям визначити найдовшу однакову частину задуманих слів.

Приклад:
Для слів "комп'ютер" та "школа" найдовшою спільною буде частина "ко", а для слів "формат" та "трансформатор" - частина "формат".