Марчук Людмила Василівна учитель інформатики Черкаської загальноосвітньої школи І-ІІІ ступенів

Задача про три будинки і 3 колодязі Є 3 будинки та 3 колодязя. Провести від кожного будинку до кожного колодязя стежку так, щоб стежки не перетиналися (рис.1.4). Рис.1.4 Ілюстрація до задачі про трьох будинках та трьох колодязях Ця задача була вирішена Куратовским в 1930 році. А спробуйте Ви вирішити дану задачу!)

Задача про чотири фарби Завдання полягає в доказі (або спростуванні) наступного визначення: чотирьох різних фарб достатньо для того, щоб розфарбувати будь-яку карту так, щоб ніякі дві області, що мають загальну ділянку кордону, не були пофарбовані в один і той же колір. Ця пропозиція підтверджується у всіх відомих приватних випадках (повідомлення про його доказ було опубліковано лише в 1976). Рис.1.5 Ілюстрація до задачі про чотирьох фарбах Розфарбовуючи географічну карту природно користуватися по можливості меншою кількістю кольорів, проте так, щоб дві країни, які мають спільну частину кордону (не тільки спільну точку), були пофарбовані по-різному

У 1852 році Френсіс Гутрі (Guthrie), складаючи карту графств Англії, звернув увагу, що для такої мети цілком вистачає чотирьох фарб. Його брат, Фредерік, повідомив про це спостереження відомому математику О. Де Моргану (DeMorgan), а той - математичній громадськості. Точне формулювання гіпотези опубліковане А. Келі (Cayley, 1878)

Граф мережі доріг Геометрично граф можна представити як набір вершин (точок), визначені пари яких з'єднані лініями. Наприклад, мережа доріг, що з'єднує міста Е1, Е2, Е3, Е4, Е5 можна представити у вигляді графа таким чином: міста позначимо точками (вершинами), а дороги неорієнтованих лініями (рис.2.1) Неорієнтовані лінії означають наявність двостороннього руху між відповідною парою міст. Перетину лінією не вважаються вершинами. Рис.2.1 Граф мережі доріг

Розглянемо інший приклад: Нехай виробнича дільниця виготовляє два види виробів Е9 і Е10. Виріб Е9 збирається з вузлів Е6, Е7 і деталі Е2, а виріб Е10 - з вузлів Е7, Е8 та деталі Е5. У свою чергу вузол Е6 збирається з двох деталей Е1 і однієї деталі Е2, вузол Е7 - з деталей Е2, Е3 і Е5, а вузол Е8 - з деталей Е4 і Е5. Застосовність вузлів і деталей зобразимо у вигляді графа. Вершинами графа поставимо у відповідність вузли, деталі та вироби, а зв'язки між ними (входження деталей у вузли і вироби і вузлів у вироби) зобразимо орієнтованими лініями (рис. 2.2) Рис.2.2 Граф виробничої дільниці

7 Приклад 2: Дискретне завдання про рюкзак На складі є N предметів, для яких відомі їхні вага w[1..N] і їхня вартість v[1..N]. На склад пробрався злодій, що хоче украсти скарб на максимальну суму грошей. Однак вага, що злодій може винести, обмежена і рівняється TotalW. Які предмети повинен взяти злодій, щоб їхня сумарна вартість була найбільшою, а вага була обмежена величиною TotalW?

Жадібний алгоритм працює так: обчислюється ціна одиниці ваги кожного предмета, тобто prіce[і]:= v[і]/w[і]. Потім предмети сортуються в порядку убування prіce[і], і злодій починає пхати у свій рюкзак предмети один по одному (і=1,2,...N) з відсортованого списку. Якщо предмет і "не лізе" (обмеження вільної ваги, що залишилося, у рюкзаку) - злодій розглядає наступний предмет і+1 (prіce[і+1]<prіce[і]), і так до кінця. Жадібність складається буквально в тім, що злодій на кожному кроці намагається взяти предмет з найбільшою ціною.

Як підібрати коробки так, щоб їхня вартість була максимальною, а сумарна вага не більше 15 кг?

) (4)*7+(2)*1=15$ 2) (1)*1+(4)*1+(3)*1=8$ 3) (2)*10+(3)*5=20$ 4) (5)*3+(4)*1+(3)*1=34$ 5) (5)*3+(3)*3=36$

Приклад 3: Безперервне завдання про рюкзак Умова та ж сама, з тією лише різницею, що предмети можна ділити на частини. Таке буває, наприклад, коли предмети не штучні (наприклад, золотий пісок) і злодій може украсти частину предмета. У такому завданні застосуємо жадібний алгоритм, описаний вище (з тією лише різницею, що якщо черговий предмет з відсортованого списку не поміститься в рюкзак цілком, те злодій забирає ту його частину, що поміститься в рюкзак). Таким чином, якби ми розглядали той же приклад із трьох предметів 1 - ($60, 10 кг), 2 - ($100, 20 кг), 3 - ($120, 30 кг), злодій би взяв цілком перший з них, потім другий; залишилося вільним 20 кг у рюкзаку; злодій відокремив би 2/3 частини від третього предмета (що складе рівно 20 кг) і в кінці кінців забере в сумі $60+$ /3*$120 = $240. Для безперервного завдання про рюкзак жадібний алгоритм буде давати оптимальне рішення.

Залишається лише дати відповідь на трохи часто виникаючих питань. 1) Як для конкретного завдання довідатися, чи видасть жадібний алгоритм оптимальне рішення? На жаль, тут немає загальних рецептів. Крім критерію оптимальності для підзадач, існує ще одна особливість - принцип жадібного вибору. Говорять, що до завдання застосуємо принцип жадібного вибору, якщо послідовність локально-оптимальних (жадібних) виборів дає глобально оптимальне рішення. 2) Яке ж розходження між жадібними алгоритмами й динамічним програмуванням? На кожному кроці жадібний алгоритм бере "самий жирний шматок", а потім уже намагається зробити найкращий вибір серед того що залишилося.

Умова задачі: В економічному регіоні розміщено 6 пунктів (міст). Комівояжер, який виїжджає з міста 1, має побувати в кожному місті один раз і повернутися до вихідного пункту. Знайти найкоротший маршрут, якщо відстані між містами відомі (наведені в км на рис.1). Задача Комівояжера

Розв'язання. Маємо 6 пунктів, де має побувати комівояжер. Отже, - бульові (цілочислові) змінні. Запишемо числову економіко-математичну модель задачі комівояжера за даних умов. Виходячи з рис.1, висновуємо, що всіх можливих маршрутів є 12. З першого міста можна потрапити до кожного з інших п'яти, відповідні маршрути позначимо змінними Друге місто пов'язане лише з трьома іншими, а саме, з першим, четвертим та п'ятим, отже, маємо такі три змінні: Аналогічно позначаємо змінні, що відповідають можливим маршрутам пересувань з третього, четвертого, п'ятого та шостого міст: з третього – x31, x34, x36; з четвертого –x41, x42, x43, x45, x46; з п'ятого - x51, x52, x,54, x56; з шостого - x61, x63, x64, x65.

Загалом отримали 24 змінні. Однак деякі змінні, наприклад, x12 та x21, x13 та x31 описують один маршрут, довжина якого за умовою задачі не змінюється залежно від напрямку пересування (у разі переїзду з першого міста до другого чи з другого до першого необхідно подолати 50 км). Отже, коефіцієнт у цільовій функції при таких змінних буде однаковим.

Критерій оптимальності - мінімізація довжини всього маршруту комівояжера: а)обмеження щодо одноразового в'їзду в кожне місто:

Б)ОБМЕЖЕННЯ ЩОДО ОДНОРАЗОВОГО ВИЇЗДУ З КОЖНОГО МІСТА : в)обмеження щодо усунення під маршрутів: цілі числа

Такі задачі розвязуються спеціальними методами. У результаті оримуємо оптимальний варіант пересування таким маршрутом. Тобто з першого міста за оптимальним планом необхідно переїжджати до четвертого, з четвертого - до третього, з третього - до шостого, з шостого - до п'ятого, з п'ятого - до другого, а з другого - до першого. Довжина цього маршруту, яка є мінімальною, дорівнює 300 км. Зауважимо, що аналогічні задачі нерідко виникають на практиці, особливо у дрібному бізнесі. Типовим може бути, наприклад, таке завдання: «Фірма у місті має 25 кіосків, які торгують безалкогольними напоями. Щоденно з бази автомобілем розвозять до них товар. Як оптимально організувати розвезення певного обсягу товару?».

Жадібні алгоритми Усім відомий афоризм "жадібність фраєра погубить". Це в житті. А в алгоритмічному мисленні всі по-іншому, іноді навіть виходить навпаки - жадібність програміста рятує. Тут ми розглянемо застосовність цього феномена в конкретних алгоритмах і покажемо всі сильні й слабкі його сторони. Жадібний алгоритм робить на кожному кроці локально оптимальний вибір, допускаючи, що кінцеве рішення виявиться оптимальним. Однак це не завжди так, і тому іноді буває, що жадібний алгоритм у термінах вищезгаданого визначення є не повноцінним алгоритмом, а приблизним алгоритмом. Але для великої кількості алгоритмічних завдань жадібні алгоритми дійсно дають оптимум.

Приклад 1: Завдання про вибір заявок Нехай задані N заявок на проведення занять в одній і тій же аудиторії. Для кожного заняття відомо відрізок часу його проведення [bі, eі], де bі - час початку заняття, eі - час закінчення. Два різних заняття не можуть перекриватися в часі, але домовимося, що початок одного може збігатися із закінченням іншого. Завдання полягає в тім, щоб вибрати максимальне число сполучених у часі занять. Жадібний алгоритм працює так: упорядкуємо заявки в порядку зростання часу закінчення: e1 = e2 = … = en

Проаналізуємо, як це все працює. Спочатку А містить заявку j=1. Далі в циклі по і із заявки, що починається не раніше, ніж кінчається заявка j. Якщо така знайдена, вона включається в безліч А і змінній j привласнюється її номер. Алгоритм вимагає всього лише O(n) кроків (без обліку попереднього сортування). Жадібність цього алгоритму полягає в тому, що на кожному кроці він робить вибір так, щоб вільний час, що залишається, був максимальним (це і є локально-оптимальний вибір).

Насамперед, доведемо, що існує оптимальне рішення завдання про вибірку заявок, що містить заявку 1 (із самим раннім часом закінчення). Справді, якщо в якійсь оптимальній безлічі заявок заявка 1 не втримується, то можна замінити в ньому заявку із самим раннім часом закінчення на заявку 1, що не ушкодить спільності заявок (тому що заявка 1 кінчається ще раніше, ніж колишня, і ні із чим перетнутися не може) і не змінить їхньої загальної кількості. Так, можна шукати оптимальну безліч заявок А утримуючи заявку 1. Після того як ми домовилися розглядати тільки набори, що містять заявку 1, всі неспільні з нею заявки можна викинути, і завдання зведеться до вибору оптимального набору заявок з безлічі заявок, що залишилися (спільних із заявкою 1). Інакше кажучи, ми звели завдання до аналогічного завдання з меншим числом заявок. Міркуючи по індукції, одержуємо, що, роблячи на кожному кроці жадібний вибір, ми прийдемо до оптимального рішення.

Завдання про Черепашку Черепашці необхідно потрапити з пункту А в пункт В. На кожному куті вона може повертати тільки на північ або тільки на схід. Час руху по кожній вулиці зазначено на малюнку. Потрібно знайти мінімальний час, за який Черепашка може потрапити з пункту А в пункт В.

Шлях, показаний на малюнку лініями зі стрілкою, вимагає 21 одиницю часу. Відзначимо, що кожний шлях складається з 6 кроків: трьох на північ і трьох на схід. Кількість можливих шляхів Черепашки 20 (З63 ). Ми можемо перебрати всі шляхи й вибрати найшвидший. Це метод повного перебору (відповідь - 21). Для обчислення кожного часу потрібно п'ять операцій додавання, а для знаходження відповіді 100 операцій додавання й 19 операцій порівняння. Завдання вирішується вручну

Однак при N, рівному 8, у Черепашки вже шляхів. Підрахунок часу для кожного шляху вимагає 15 операцій додавання, а в цілому додавань і порівнянь, тобто порядку операцій. Комп'ютер при швидкодії операцій у секунду знайде рішення за 0.2 секунди, а людина? Припустимо, що N дорівнює 30, тоді кількість різних шляхів 60!*(30!*30!). Це дуже велике число, його порядок Кількість операцій, необхідних для пошуку рішення, дорівнює 60*1017. Комп'ютер зі швидкодією операцій у секунду виконає за рік порядку 3.2*1013 операцій (підрахуйте). А зараз не важко прикинути кількість років, необхідних для рішення завдання.

Повернемося до вихідного завдання. Почнемо будувати шлях Черепашки від пункту В. Кожному куту привласнимо вагу, рівна мінімального часу руху Черепашки від цього кута до пункту В. Як його знаходити? Від кутів X, Y очевидно. Для кута Z час руху Черепашки в пункт У через кут X 15 одиниць, а через кут Y 11 одиниць. Беремо мінімальний, тобто вага кута буде дорівнює 11. Продовжимо обчислення. Їхні результати наведені на малюнку. Шлях, відзначений стрілками, є відповіддю завдання. Оцінимо кількість обчислень. Для кожного кута необхідно виконати не більше двох операцій додавання й однієї операції порівняння, тобто три операції. При N, рівному 300, кількість операцій - 3*301*301, це менше , і комп'ютеру буде потрібно менше однієї секунди. Отже, багато років при N=30 і 1 секунда при N=300.

Метод "решета". Бики та корови Комп'ютер та дитина грають у наступну гру. Дитина загадує послідовність із чотирьох (не обов'язково різних) кольорів, обраних із шести заданих. Для зручності будемо позначати кольори цифрами від 1 до 6. Комп'ютер повинен відгадати послідовність, використовуючи інформацію, що він одержує з відповідей дитини.

Комп'ютер відображає на екрані послідовність, а дитина повинна відповісти (використовуючи для уведення відповіді клавіатуру) на два питання: скільки правильних кольорів на неправильних місцях; скільки правильних кольорів на правильних місцях. Приклад. Припустимо, що дитина загадала послідовність Один з можливих способів відгадати послідовність така:

Метод "решета". Бики та корови Написати програму, що завжди відгадує послідовність не більш ніж за шість питань, у найгіршому разі - за десять. Пояснимо на прикладі ідею решета. Нехай довжина послідовності дорівнює двом, а кількість кольорів - чотирьом. Дитина загадала 32, а комп'ютер запитав 24. Відповідь дитини 1 0, фіксуємо його в змінних kr (1) і bk(0). Отже, було 16 можливих питань, після першого залишилося чотири - робота решета.

Подальша робота із завданням вимагає відповіді на наступні питання: Чи залежить значення cnt від вибору першого ходу? Установіть експериментальним шляхом. Як логіка вибору чергового ходу впливає на результат гри? Дослідити. Наприклад, вибрати той елемент А (відповідний елемент В повинен дорівнювати true), у якому кількість незбіжних цифр максимально.

Література Басакер Р., Сааті Т. Кінцеві графи та мережі. М.: Наука, c. Бєлов В. В., Воробйов Є. М., Шаталов В. Є. Теорія графів - М.: Вища. школа, С Берж К. Теорія графів та її застосування. М.: ІЛ, c. Емелічев В. А., Мельников О. І., Сарванов В. І., Тишкевич Р. І. Лекції з теорії графів. М.: Наука, с. (Ізд.2, испр. М.: УРСС, с.) Зиков А. А. Основи теорії графів - М.: "Вузівська книга", С ISBN (М.: Наука, c.)ISBN