Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Розв’язок задачі

Скачати 230.71 Kb.

Розв’язок задачі




Скачати 230.71 Kb.
Дата конвертації28.05.2017
Розмір230.71 Kb.

Розв’язок задачі «Вектори»


Автор: Рубльов Богдан Владиславович, Шаміль Ягіяєв
Дані про всі вектори можуть бути збережені в масиві Plane[1..100, 1..100].
Богдан Владиславович Рубльов (нар. 7 серпня 1964) - український математик, доктор фізико-математичних наук (2005), професор кафедри обчислювальної математики Київського національного університету імені Тараса Шевченка (2011).
Отже, значення елемента Plane[i,j] буде відповідати вектору, що знаходиться у точці (i,j).

Для пошуку циклів використаємо наступний алгоритм.

1. Спочатку усі точки фарбуємо у білий колір, який означає що точка ще не була оброблена алгоритмом.

Бі́лий ко́лір - це ахроматичний колір, точніше зорова рівноважна сукупність усіх кольорів видимого спектру сонячного світла, сприймана людиною. Має найвищу яскравість, відтінок - 0. Білий колір може бути створений шляхом поєднання трьох основних кольорів - червоного, зеленого і синього (RGB-модель), або жовтого, пурпурного і блакитного (CMYK-модель) - у рівних концентраціях при найвищій яскравості.
Обнуляємо глобальний лічильник кількості циклів.

2. Будемо виконувати наступні дії, поки на полі є білі точки.

3. Знаходимо першу білу точку, та фарбуємо її у сірий колір, який означає що ця точка обробляється зараз.

Кількість - в Арістотелівській логіці друга з 10 категорій (класів, розрядів, які спрощують процес розумового визначення будь-якої речі), побічна обставина матеріальних речей , за допомогою якої вони поширюються в просторі, вимірюються якоюсь математичною нормою і здатні бути поділеними на окремі частини.
Сірий колір - це ахроматичний колір, точніше - множина всіх кольорів, отримуваних шляхом поєднання трьох основних кольорів - червоного, зеленого і синього - в рівних концентраціях. Залежно від яскравості відтінок сірого міняється від чорного (яскравість 0%) до білого (яскравість 100%).

4. Починаючи з обраної точки рухаємося у напрямку векторів, та фарбуємо білі точки, що зустрічаються, у сірий колір.

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

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

7. Після зупинки обробки початкової точки перефарбуємо усі сірі точки у чорний колір, який означає, що з цих точок було отримано всю необхідну інформацію.

Чо́рний ко́лір - ахроматичний колір, точніше - відсутність світлового потоку від об'єкта. Відтінки чорного кольору іменуються сірим кольором.

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

Оцінимо складність алгоритму.

Складність обчислювальних процесів - це поняття теорії складності обчислень, оцінка ресурсів (зазвичай часу) необхідних для виконання алгоритму.
Кожну точку буде переглянуто рівно один раз при перевірці чи має вона білий колір (на кроці 3). Кожну точку буде рівно один раз перефарбовано у сірий колір, і рівно один раз перефарбовано у чорний колір. Кожну точку буде переглянуто не більше ніж 8 разів на кроках 5 та 6. Таким чином, кожну точку буде оброблено обмежену кількість разів, з чого можна зробити висновок, що складність алгоритму є O(MN).

Розв’язок задачі «Погодні умови»


Автор: Володимир Ткачук
Базові поняття:

Схему рейсів компанії OlympAirways можна представити неорієнтованим графом, вершинами якого є аеропорти, а ребрами – рейси між аеропортами. Тому зручно описувати розв’язки цієї задачі у термінах теорії графів.

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

По-перше, відмітимо, що за умовою наш граф є зв’язним. „Число вразливості” одного маршруту є по суті кількістю ребер, при вилученні хоча б одного з яких, один кінець маршруту стає недоступним з іншого кінця (надалі такі ребра будемо називати критичними для маршруту, або критичними для пари вершин, що є кінцями маршруту).
Розв’язок №1. (Неоптимальний по часу)

Для „лобового” розв’язку задачі достатньо базових понять: для кожної пари вершин (всього O(N2) пар) знайти кількість критичних ребер, в кінці знайти суму цих кількостей. Задача зводиться до знаходження числа вразливості однієї пари вершин. Найочевиднішим способом пошуку цього числа є послідовній перебір всіх ребер і перевірка досяжності однієї вершини пари з іншої при вилученні ребра. Для перевірки досяжності можна використати алгоритми обходу графу (наприклад пошук „у ширину” чи „у глибину”). Коректність цього розв’язку не потребує доведення. Оцінимо час його роботи: пошук „в ширину” (так само як і пошук „у глибину”) працює за час O(M N) = O(M) (для зв’язного графа, кількість ребер не менше ніж N-1), так як необхідно виконати пошук для всіх варіантів з вилученням одного ребра, то виконувати пошук доведеться M разів.

Необхідність - система зв'язків і відносин, що зумовлює зміну, поступальний рух, розвиток у жорстко визначеному напрямку з жорстко визначеними результатами. Іншими словами, необхідність - це такий зв'язок, що обов'язково призводить до певної події.
Отже складність знаходження числа вразливості для однієї пари є O(M2). Враховуючи те, що таке число треба підрахувати для кожної пари, отримуємо загальний час роботи програми – O(N2*M2).


Розв’язок №2. (Оптимізація розв’язку №1)

Зразу ж розглянемо можливу оптимізацію вище приведеного підходу.

Для цього скористаємось наступним твердженням: всі критичні для пари вершин ребра належать одразу усім маршрутам, що з’єднують ці вершини.

Критика - розгляд якогось явища, предмета, особи; його аналіз та оцінка згідно з існуючими нормами, масштабами, цінностями.[Джерело?] Аналіз і оцінка когось чи чогось із метою виявлення та усунення вад, хиб.

Отже, не потрібно розглядати всі ребра графа, достатньо перевірити тільки ребра, якогось одного маршруту з однієї вершини до іншої. Природно вибрати не довільний маршрут, а маршрут найменший за кількістю ребер, так як кожне ребро такого маршруту доведеться перевіряти на критичність. Для знаходження такого маршруту необхідно виконати ще один пошук в ширину для кожної пари (або навіть, просто для кожної вершини), що не вплине на асимптотичну оцінку часу роботи всієї програми. Така оптимізація може давати великий виграш у часі для окремих варіантів графу (наприклад для повного), для довільного графу можна сказати, що час роботи буде O(N3*M) (для кожної пари ми перевіряємо не більше ніж N-1 ребро).


Розв’язок №3. (Ідея оптимального розв’язку)

Тепер розглянемо ідею, що веде до оптимального розв’язку. При вилученні критичного ребра граф розпадеться на дві компоненти зв’язності.

Компонент (англ. component, нім. Komponente f) - різновид, складова частина чогось.
При цьому, вилучене ребро буде критичним для всіх пар вершин, таких що належать різним компонентам зв’язності, і не буде критичним для пар з однієї компоненти зв’язності. Отже, таке ребро вносить одиничний вклад в число вразливості кожної пари, для якої воно буде критичним, або вносить вклад в сумарне число вразливості рівний кількості таких пар. Підрахувати кількість пар для яких дане ребро є критичним можна так: якщо в одній компоненті зв’язності K вершин а в другій відповідно N-K, то всього пар буде K*(N-K). Знаходячи суму цих кількостей для кожного критичного ребра графа, отримуємо результат – сумарне число вразливості.

Розв’язання задачі можна умовно розділити на дві частини:


  1. Знаходження критичних ребер графу.

  2. Для кожного критичного ребра знаходження кількості вершин в компонентах зв’язності.

Час роботи програми буде залежати від того як реалізувати кожну частину програми. Найпростіший варіант: перебрати всі ребра і перевірити кожне з них на критичність (так само як і в попередньому алгоритмі), а потім для кожного ребра підрахувати кількість вершин в компонентах зв’язності (наприклад, пошуком „у ширину”). Якщо реалізовувати програму так, то час її роботи буде O(M2), що менше ніж для попереднього алгоритму.


Розв’язок №4. (Оптимальна реалізація)

Найоптимальніший розв’язок потребує деякого покращення рішення кожної з частин задачі. Опишемо алгоритми, що використовувались в авторському розв’язанні:


Алгоритм знаходження всіх критичних ребер.

Це найбільш важлива і складна частина алгоритму, опишемо основні прийоми і позначення якими будемо користуватись:



А) Обійдемо наш граф пошуком у глибину.
Про́даж - це оплатна передача майна однією особою у власність іншій особі.
Користува́ння - добування з речей їхніх корисних властивостей (наприклад, збирати врожай, вживати продукти харчування, носити одяг і взуття). Одна з трьох класичних правомочностей власника (нарівні з володінням і розпорядженням).


Б) Введемо позначки на вершинах: a(v) – номер вершини в порядку обходу її пошуком „в глибину”. Ці позначки будемо розставляти в процесі виконання „пошуку”.

Надалі будемо говорити, що вершина u є білою, якщо для неї a(u) ще не визначена (пошук ще не дійшов до неї); вершина u є чорною, якщо для неї вже визначено a(u).



В) Введемо ще одні позначки на вершинах: b(v). Пояснимо сенс цієї позначки: в процесі пошуку у глибину будується орієнтоване дерево пошуку, коренем дерева є вершина з якої почався пошук.
Де́рево (як структура даних) - динамічна нелінійна структура даних, кожен елемент якої містить власне інформацію (або посилання на те місце в пам'яті ЕОМ, де зберігається інформація) та посилання на кілька (не менше двох) інших таких же елементів.
Нехай в дереві пошуку вершина u є безпосереднім предком вершини v. Тоді в b(v) ми запишемо мінімальний з a(t), де t – вершина така, що існує шлях з v до t, який не містить ребра (v,u) (ребра, що з’єднує v з безпосереднім предком).

Очевидно, що a(v)≥b(v) (вершина завжди може бути досягнута сама з себе). Але нас цікавить нерівність між a(u) і b(v).

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



  1. a(u)

  2. a(u)≥b(v). В цьому випадку з вершини v можна потрапити до якоїсь вершини, що була обійдена пошуком раніше, ніж вершина u (або в саму вершину u). Тоді існує цикл в який входять і вершина v і вершина u (існує принаймні два шляхи з вершини v до вершини u: один безпосередньо через ребро (u,v), а другий через деякі проміжні вершини).

Отже, якщо знайти всі a(i) і b(i), то критичні ребра буде визначити дуже просто: якщо в пошуку в глибину u – безпосередній предок v і b(v)>a(u), то ребро (u,v) – критичне.

Тепер, знаходження критичних ребер, зводиться до знаходження b(i) для кожної вершини. Знайти всі ці позначки можна в процесі одного пошуку в глибину. Розглянемо момент, коли пошук „зайшов” у вершину v. Вершина v може бути з’єднана з деякими чорними і білими вершинами. В b(v) запишемо мінімум з двох мінімумів: перший це мінімум з a(i), де i – чорний сусід v, що не є безпосереднім предком v; другий – це мінімум з b(j), де j – білі на даний момент сусіди v (запускаємо для цих вершин пошук, і спочатку знаходимо b() для них). Тобто, таким чином ми запишемо в b(v), номер a() вершини, що може бути досягнута з v безпосередньо або через білі вершини.

Отже, знаходження всіх b(i) так само як і всіх критичних ребер можна зробити за один пошук у глибину, а значить за час O(M).
Алгоритм знаходження кількості вершин у компонентах зв’язності.

Цю частину задачі можна легко розв’язати знову користуючись пошуком в глибину. Треба лише додатково пам’ятати кількість обійдених пошуком вершин. „Перейшовши” через критичне ребро, пошук не „повернеться” поки не обійде всі вершини компоненти зв’язності (а отже і підрахує їх кількість). Якщо кількість вершин в одній компоненті K, то в іншій – N-K. Нам знову знадобиться лише один пошук у глибину, значить складність роботи буде O(M).

Так як обидві підзадачі розв’язуються за час O(M), то і вся задача розв’язується за цей час. Треба відмітити, що цей час є найкращим з можливих для даної задачі.

Розв’язок задачі «Шоколадні плитки»


Автор: Богдан Яковенко
Розглянемо нашу задачу мовою теорії ігор.
Тео́рія і́гор - теорія математичних моделей прийняття оптимальних рішень в умовах конфлікту. Оскільки сторони, що беруть участь в більшості конфліктів, зацікавлені в тому, щоб приховати від супротивника власні наміри, прийняття рішень в умовах конфлікту, зазвичай, відбувається в умовах невизначеності.

Маємо набір об’єктів, кожен з яких складається з двох координат (X;Y),

З об’єктом можна зробити деякі операції по його розбиттю

1. (X,Y)  (X, i);(X, Y-i) (розріз по горизонталі )

2. (X,Y)  (i, Y);

Горизонталь, ізогіпса (англ. contour lines, horizontal, isohyps, нім. Höhenkurve f, Horizontale f; рос. горизонталь, изогипса; від дав.-гр. ισος - равний і дав.-гр. ὕψος - висота) - лінія на плані (карті), яка з'єднує точки земної поверхні з однаковою абсолютною висотою.
(X-i, Y) (розріз по вертикалі)

3. (X,Y)  (X, i);(X, Y-i-1) (вилучення рядка по горизонталі)

4. (X,Y)  (i, Y);(X-i-1, Y) (вилучення рядка по вертикалі)


Також існує операція вилучення країв об'єкту:

5. (X,Y)  (X-2,Y-2), якщо X ≤ 3, Y ≤ 3


Кожна позиція гри визначається комбінацією об’єктів(з можливим повторенням):
{(X1;Y1);(X2;Y2);…;(Xk;Yk)}
Позиції бувають виграшні та програшні. Програшна – позиція з якої нема прямого ходу до програшної. Виграшна – позиція з якої існую хоча б 1 хід в програшну.
Позиція {} є програшною. Аналогічно позіції що містять скільки завгодно об’єктів (1;
Анало́гія - (грец. αναλογια - «відповідність») - подібність, схожість у цілому відмінних предметів, явищ за певними властивостями, ознаками або відношеннями.
1) є програшними.
Тепер для кожної позиції гри введемо "число виграшності"(SG1) так:

SG({}) = 0

SG всіх позицій, що зводяться до {} дорівнює 0, наприклад SG({(1,1)}) = 0

SG(A), де A – довільна множина з повторенням, що задає нашу позицію гри, дорівнює мінімальному не від’ємному числу, що не зустрічається у SG(Bi) де

Bi – набір позицій до яких можна перейти за один хід з A.
Наприклад: з позиції {(1,2)} можна перейти до {(1,1);(1,1)} а це теж саме що й {}

(SG({}) = 0), отже SG({(1,2)}) = 1


З позиції {(1,3)}, наприклад, можна перейти до {(1,1);(1,1)} {} (SG({}) = 0) та до {(1,1);(1,2)}  {(1,2)} (SG({(1,2)}) = 1)

отже SG({(1,3)}) = 2


Для того, щоб виграти кожного разу гравець повинен має ввести гравця в позицію A з

SG(A) = 0, якщо так зробити не можна(тобто ми стоїмо в позиції B з SG(B) = 0) то ця позиція – програшна.


Отже постає питання як ефективно знайти SG(A).

Наприклад, в нас є дві незалежні позиції гри A та B, ми також знаємо, що SG(A)=a, SG(B)=b

позначимо SG(A  B) = Za,b
Перейдемо до безпосереднього обчислення Zx,y
Очевидно, що Z0,0 = 0
Лема 1 x : Zx,x = 0
якщо грати симетрично, то виграти не можливо, тобто Zx,x = 0
Теорема 1 Zi,j = i xor j, де xor побітове додавання за модулем 2

 Доведемо за загальною індукцією по i та j:




БАЗА: Z00 = 0 xor 0 = 0

Тепер якщо ми доведемо, що з того, що Zkl = k xor l, для усіх k≤i та l≤j, без пари k=i та l=j, випливає що Zij = i xor j.

Додавання - бінарна арифметична операція, суть якої полягає в об'єднанні математичних об'єктів.
Симетрíя (від грец. συμμετρεῖν - міряти разом) - властивість об'єкта відтворювати себе при певних змінах, перетвореннях чи трансформаціях, які називаються операціями симетрії. Розрізняють симетрію тіл, симетрію властивостей і симетрію відношень.
Інду́кція (англ. induction) - термін широкого призначення: явище, що виникає під зовнішнім впливом; у гуманітарних науках та стосовно людського мислення - метод пізнання, що ґрунтується на формально-логічному умовиводі, який дає можливість одержати загальний висновок на основі аналізу окремих фактів.

що еквівалентне такому:
серед чисел

Zi,j-1 = i xor (j-1), Zi,j-2 = i xor (j-2),…, Zi,0 = i xor 0

Zi-1,j = (i-1) xor j, Zi-2,j = (i-2) xor j,…, Z0,j = 0 xor j

найменше число, що не зустрічається = i xor j


Очевидно, що i xor j, не може бути рівним жодному з цих чисел:
i xor (j-1), i xor (j-2), …, i xor 0, (i-1) xor j, (i-2) xor j, …, 0 xor j (1)
Отже Zi,j ≤ i xor j
Доведемо, що всі числа, що менші за i xor j входять в послідовність
Для кожного такого числа С < i xor j покажемо алґоритм, що знаходить який член з послідовності (1) рівний С.
Вирівняємо число C до однакової кількості знаків з числом i xor j.

Знайдемо перший розряд числа що відрізняє ці числа.

Розряд (позиція, місце) - це структурний елемент представлення чисел в позиційних системах числення.

В нас можуть бути такі ситуаціїї:

i: …0…


j: …1…

i xor j: …1…

C: …0…

зменшивши j можна отримати C.



i: …1…

j: …0…


i xor j: …1…

C: …0…


зменшивши i можна отримати C.

i: …1…


j: …1…

i xor j: …0…

C: …1…

зменшивши j або i можна отримати C.



i: …0…

j: …0…


i xor j: …0…

C: …1…


такого бути не може, інашке С>i xor j. 
Тепер обчислимо числа SG((X,Y)) для усіх X, Y, що не перевищують максимального параметра.
Після цього обчислення легко знайти SG, для нашої початкової позиції – проксорити SG кожного прямокутника.
Пара́метр (від дав.-гр. παραμετρέω) - відмірюю, розмірюю)(рос. параметр, англ. parameter, нім. Parameter m, Kennwert m, Kenngrösse f, Kennzahl f) - величина, що нею характеризують якусь властивість, стан, розмір або форму об'єкта, робочого тіла, процесу, явища або системи тощо.
Прямоку́тник - це чотирикутник, усі кути якого прямі. Протилежні сторони прямокутника рівні. Є окремим випадком паралелограма.

Тепер перебираючи всі можливі ходи встановлюємо SG нової позиції, якщо він 0-й, то це виграшний хід.


Складність алґортиму: , де M – максимальний X або Y.

Розв’язок задачі «Працівники»


Автор: Шаміль Ягіяєв

Розв’язок 1 (Пошук з поверненням)


Найпростіший розв’язок задачі — це перебір усіх можливих варіантів обробки деталей на верстатах. У такому випадку кожного разу, коли буде оброблятися певна деталь, буде розглянуто обидва варіанти верстатів (при цьому буде перевірено, чи задовольняє це наведеним правилом). При такому підході алгоритм буде мати складність порядку O(2N).

Розв’язок 2 (Динамічне програмування)


Твердження. Задача еквівалентна задачі обчислення кількості вірних варіантів розташування n=N/2 пар круглих дужок у арифметичному виразі.

Дійсно, обробка i-ої деталі на верстаті A може означати що i-та дужка у виразу буде відкриваючою „(”, а обробка на верстаті B, що закриваючою „)”. Неважко переконатися у тому що таке формулювання є адекватним початковому, проаналізувавши правила обробки деталей.

Будемо продовжувати розв’язувати задачу, використовуючи таке більш зручне формулювання.

Відомо, що коли кількість пар дужок n=1 кількість різних розташувань дужок дорівнює 1. Нехай K(s) — це розв’язок задачі для будь-якого s

Таким чином, кожне значення від 1 до n необхідно обрахувати 1 раз (проміжні результати потрібно зберігати), на що необхідно лінійну кількість операцій. Тобто, загальна складність такого алгоритму, повертаючись до початкового формулювання складатиме O(N).


Розв’язок 3 (Комбінаторні обчислення)


Задача про відшукання кількості розташування дужок у арифметичному виразі є досить поширеною. Послідовність чисел, які утворюються при розв’язанні цієї задачі при n=1,2,… називають послідовністю Каталана. Загальний член цієї послідовності можна обчислити за формулою:


Розв’язок 4 (Масив констант)


Можна помітити, що кількість різних вхідних даних дорівнює 13, тобто усі ці випадки можна перелічити у програмі, заздалегідь обрахував відповіді на них. Звісно, за час туру неможливо вручну перелічити усі випадки, і доведеться робити це з допомогою комп’ютера.

Розв’язок задачі «Робот»


Автор: Шаміль Ягіяєв

Аналізуючи умови задачі, можна зробити деякі висновки які потім можна буде використати при розв’язку.



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

Твердження 2. Існує оптимальна послідовність дій робота, слідуючи якій робот ніколи одночасно не тримає більше одного кубику певного кольору.

Твердження 3. Розв’язок задачі однозначно задається N бульовими значеннями — чи піднімає робот певний кубик, чи ні.

Дійсно, слідуючи твердженню 1, однозначно можна встановити, коли кожен кубик буде покладено на поле.


Розв’язок 1


Задачу можемо розв’язувати за допомогою «пошуку з поверненням» (backtracking). Потрібно переглянути усі варіанти переносів кубиків, відкидаючи ті, що заздалегідь порушують умову обмеження кількості одночасних перенесень. Складність такого алгоритму становить O(2N).

Розв’язок 2


Розглянемо більш швидкий алгоритм розв’язку задачі.

Будемо вважати, що робот має K рук, у кожній з яких він може тримати не більше одного кубика. Нехай, у кожному елементі масиву даних H[i], i=1..K, зберігається номер клітини поля, у яку було покладено останній кубик, що був перенесений у руці з номером i.



  1. Спочатку усі елементи масиву H дорівнюють нулю. Глобальний лічильник перенесених кубиків теж має значення нуль.

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

  3. Для кожної клітини j однозначно відомо, який кубик може бути покладений у цю клітину. Це буде попередній кубик, колір якого співпадає з кольором кубика у клітині j. Позначимо як p номер клітини у якій він знаходиться.

  4. Якщо p≠0 (тобто попередній кубик існує), то знайдемо номер i руки робота, у якій можна перенести цей кубик, та покласти у поточну клітину. Серед усіх рук робота оберемо ті, у яких можна перенести цей кубик з клітини p до клітини j, тобто H[i]≤p, та оберемо з них максимальне H[i] (таким чином робот буде нести у тій руці, з якої він в останнє поклав кубик на поле). Якщо такий індекс i знайдено, то до глобального лічильника перенесених кубиків додаємо одиницю, та обновлюємо значення H[i]=j.

  5. Коли усі клітини поля оброблені, то видаємо відповідь, що зберігається у глобальному лічильнику перенесених кубиків.

Складність цього алгоритму можна оцінити як O(NK).

Розв’язок задачі «Зала Круглих Столів»


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

Аналіз кругів та аналіз ліній


Круглий стіл діаметра D можна пронести через Коридор тоді й тільки тоді, коли існує шлях знизу догори, на котрому всі проходи (відстані між колонами, що знаходяться одна ліворуч одна праворуч шляху) мають ширину, не меншу D.
Діáметр кола - найдовша хорда. За величиною діаметр дорівнює двом радіусам.

Створення додаткових (віртуальних) колон


Обмеження на рух стола накладають: 1) колони; 2) зовнішні бічні стіни (ліва та права). Але бічні стіни створюють обмеження для руху стола лише тоді, коли виникає необхідність пронести стіл між колоною та бічною стіною. Якщо стіна – ліва (x координата XL) і колона має координати , то достатньо вважати, що обмеження на рух стола створює нова (віртуальна) колона з центром у точці , де R0 – радіус колони (зручніше вважати, що віртуальні колони мають той самий радіус, що й усі реальні колони, задані вхідними даними).

Щоб задати обмеження, що створюється правою стіною, достатньо ввести віртуальну колону з центром у .

Питання, де са́ме вводити віртуальні колони, можна вирішити по-різному. Найпростіший (правильний) спосіб – просто ввести ліву та праву віртуальні колони для кожної реальної. Щоправда, тоді загальна кількість колон збільшується втричі.

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

Віртуа́льність (від лат. virtus - потенційний, можливий) - вигаданий, уявний (можливо, для деяких певних цілей) об'єкт, суб'єкт, категорія, ставлення, дія тощо, не присутній в цей час в реальному світі, а створений лише грою уяви людської думки (також див. Фантазія)
Треба вводити всі ліві віртуальні колони, крім тих, для яких круг, побудований на відрізку як на діаметрі, містить центр хоча б однієї (іншої реальної) колони . Аналогічно, введемо усі праві, крім тих, для котрих круг з діаметром на містить інші центри.

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

Зв’язок між максимальним діаметром стола та діаметром колон. Ре́бра перепон


Якщо, не переміщуючи центрів колон, зменшити діаметри всіх (у тому числі віртуальних) колон на одну й ту саму величину , це призведе до збіль­шення відповіді (діаметру найбільшого столу) в точ­ності на .

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

Оптимальність - властивість, при якій забезпечується найбільша відповідність даному завданню, умовам тощо.

Тому, будемо розв’язувати задачу, вважаючи колони точками, а радіус R0 врахуємо наприкінці розв’язку.

Тепер дозволимо колонам розширятися, в тому числі настільки, щоб деякі пари колон торкалися або навіть перетиналися одна з одною.

Нехай початкова ширина проходу між деякими колонами стано­вила d, збільшення діаметрів колон . Тоді, якщо зміна діаметра колон , то прохід просто звужується до ; якщо ж , то прохід між даними колонами зникає. Будемо казати, що в такому разі з’являється ребро перепони (де кінцями ребра перепони є колони, відстань між котрими розгля­да­лася;

Ві́дстань або ві́ддаль між двома точками простору - довжина уявного відрізка прямої, що сполучає ці точки.
довжиною ребра перепони вважаємо початкову відстань d між колонами).

Граф перепон. Параметр графа перепон. Зв’язок між максимальним діаметром стола та параметром графа перепон


Якщо зафіксувати значення параметра , можна ввести наступні поняття.

Графом перепон назвемо граф, вершинами котрого є деякі із колон (т.ч. віртуальних), ребрами – ребра перепон.

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

Назвемо параметром графа перепон найбільшу з довжин (у звичайному смислі ) ребер перепон, що входять до цього графа.

Звичайно, можна фіксувати різні значення  і отримувати різні графи перепон.

Враховуючи все вищесказане, сформулюємо таке важливе твердження:

Круглий стіл діаметру D не можна пронести через коридор тоді й тільки тоді, коли існує перегороджувальний граф перепон, параметр котрого строго менший D.

Слідування в один бік (якщо є перегороджувальний граф, то не можна пронести) очевидне. Доведемо слідування в інший бік (якщо стіл не можна пронести, то існує перегороджувальний граф).

Розглянемо рух стола (фіксованого) діаметра D. Нехай він спочатку рухається знизу догори, постійно дотикаючись до лівої стіни l. Це продовжується доти, доки стіл не торкнеться деякої точки (колони) A1 такої, що відстань між нею та лівою стіною менша D. Тоді починаємо обертати стіл навколо точки A1 як центру обертання проти годинникової стрілки.

Рух, Шлях - поняття, яке використовується для позначення будь-яких змін, які відбуваються у Всесвіті. Також рух - це процес переміщення, зміна положення тіла відносно інших тіл у просторі.
Годинник (арх.: дзиґа́р, дзиґарі́) - пристрій для вимірювання часу.

Стіл може або зробити оборот навколо точки A1 так, щоб знову торкнутися лівої стіни l (тоді точку  A1 можна надалі не розглядати), або торкнутися точки A2 (A1A2<D). В такому випадку починаємо обертати стіл навколо точки A2 за тими ж правилами. Якщо при таких послідовних обертаннях навколо A1, A2, …, An стіл вернеться в деяку попередню точку Ai (1   n), то точки Ai 1, A i 2, …, An можна надалі не розглядати і продовжити обертання стола навколо Ai.

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

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

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

Назвемо щойно згадану найменшу довжину критичним параметром графа перепон.

Знаходження критичного параметра графа перепон


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

Відстань від графа перепон до даної (ще не включеної до графа перепон) вершини vi рахуватимемо як (звичайну) відстань від даної вершини vi до найближчої вершини графа перепон.


Власне алгоритм можна записати так:


  1. Ініціалізація:

    1. побудувати віртуальні колони;

    2. покласти d:=0;

    3. до графа перепон віднести всі ліві віртуальні колони;

    4. для усіх реальних та правих віртуальних колон обчислити відстань від графа перепон.

  2. Поки граф перепон не досяг правої сторони коридора, повторювати:

    1. вибрати серед вершин, ще не включених до графа перепон, вершину з міні­маль­ною відстанню від графа перепон (і включити її до графа);

    2. порівняти щойно вибрану мінімальну відстань d_curr_min з d:

      1. при d_curr_min >d, потрібно переприсвоїти d:=d_curr_min,

      2. при d_curr_mind, значення d не міняється;

    3. для всіх вершин, ще не включених до графа перепон, уточнити відстань до графа перепон (вибрати мінімум із поточної відстані до графа і відстані до щойно доданої до графа вершини).

  3. Остато́чним результатом задачі є d  2R0 (де R0 – радіус колон).
    Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.

Аргументуємо переприсвоєння значень d у пункті 2b. Якщо найменша відстань до нових вершин d_curr_min більша d, то при поточному значенні d неможливо розши­рити зв’язний граф перепон, а мінімальне значення, при котрому можна продовжити розширення – d_curr_min. Отже, щоб продовжити побудову, треба збільшити параметр графа перепон d, поклавши його рівним d_curr_min. Якщо ж d_curr_mind, це означає що раніше в процесі побудови графа вже виникла необхідність збільшити параметр до d, і зменшувати його зараз нема підстав.

Оскільки потрібне лише значення d, можна не підтримувати граф як розгалужену структуру, а зберігати лише атрибути вершин (чи належить зараз дана вершина графу перепон).
Такий алгоритм має певні спільні риси з алгоритмом Пріма побудови мінімального кістякового дерева, а також з відомою модифі­ка­цією алгоритма Дейкстри.

Мінімальне кістякове дерево у зв'язаному, зваженому, неорієнтованому графі - це кістяк цього графа, що має мінімальну можливу вагу, де під вагою дерева розуміється сума ваг його ребер.
Тобто, даний алгоритм не є ні алгоритмом Пріма, ні алгоритмом Дейкстри, але вони можуть стати відправними точками міркувань.
Міркування - зіставлення думок, пов’язання їх задля відповідних висновків, логічне мислення. Можна розглядати міркування як аналіз і синтез даних, та їхню оцінку. Хоча знання фактів і є точкою відліку у вивченні суспільних наук, людина також повинна мати здатність до логічного мислення-міркування, адже саме міркування наповнює факти, проблеми і поняття змістом: міркуючи над засвоєним знанням, людина приходить до повнішого розуміння предмета. Міркування є також предметом логіки, яка вказує нам правила, закони або норми, яким повинне підкорятися наше мислення для того, щоб бути істинним.
Алгоритм Дейкстри - алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.

Аналіз об’єму пам’яті та кількості дій


Пам’ятати потрібно лише координати колон, стани колон (чи належить колона в даний момент до графа перепон) та відстані колон від графа перепон (плюс досить багато окремих змінних). Під колонами в усіх випадках маються на увазі і реальні, і (щонайменше праві) віртуальні. Таким чином, об’єм пам’яті, потрібної для роботи алгоритму, складає O(N), але з досить великим констант­ним множником.

Час роботи алгоритму очевидно складає O(N2): са́ме стільки дій потребує виконання пунктів 1d, 2a і 2c (враховуючи, що увесь цикл 2 повторюється O(N) разів), та 1a (при використанні описаного способу вибору віртуальних колон); решта пунктів потребують або O(N), або O(1) часу.


Короткий аналіз інших методів розв’язання

Знаходження критичного параметра перегороджувального графа перепон бінарним пошуком


Якщо взяти до уваги міркування всіх розділів, по розділ “Граф перепон…” включно, але не здогадатися до описаного далі способу підбору критичного параметра, можна прийти до алгоритму: щоразу вибирати яке-небудь “пробне” значення цього параметра, і намагатися побудувати пере­городжу­вальний граф. Тоді можна буде для “пробного” значення параметра отримувати (наприклад, звичайним пошуком у глибину) відповідь (“так”/“ні”) на питання “чи існує перегоро­джуваль­ний граф?”, і на основі цих відповідей проводити бінарний пошук.
Двійкóвий пóшук - алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини (див. двійкове дерево пошуку)
В якості початкових наближень можна взяти, наприклад, та . Умова виходу з бінарного пошуку – досягнення вказаної в умові точності 10–3.

Такий алгоритм трохи простіший, ніж наведений вище “основний”, але він помітно менш ефективний. Адже запускати допоміжний алгоритм пошуку пере­городжу­валь­ного графа, нехай і трохи простіший, потрібно на кожному кроці бінарного пошуку.

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


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


Цей алгоритм набагато сильніше відрізняється від “основного”.

Нам потрiбно знайти такий шлях, по котрому можна пронести стiл найбiльшого дiаметру. Ця задача подiбна до задачi знайти маршрут, по котрому можна провести мiж пунктами найважчу машину. Як вказано у Т. Кормен, Ч. Лейзерсон, Р. Ривест, “Алгоритмы: построение и анализ”, вправа 26.4-6, це можна зробити модифікацією алгоритма Дейкстри (або деяких інших алгоритмів знаходження мінімальних шляхів), де оцінки зберігають вже не міні­мальну суму довжин ребер, а можливий макси­мальний розмір, кращою вважається не мінімальна оцінка, а максимальна, при підрахунку оцінки верши­ни рахується не сума оцінка попередньої вершини плюс довжина ребра, а береться мінімум.

Алгори́тм (латинізов. Algorithmi за араб. ім'ям узб. математика аль-Хорезмі) - набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час.

Але що саме вважати вершинами, ребрами, довжинами, … ? Одну з мож­ливих відповідей отримаємо, розглянувши триангуляцію Делоне.

За означенням, триангуляція – розбиття області на трикутники, верши­нами котрих є задані точки, а триангуляція Делоне – така триангуляція, що жодна вершина не потрапляє строго всере́дину кола, побудованого на трьох (інших) точках – вершинах трикутника триангуляції.

Тріангуля́ція Делоне́ для множини точок P на площині - це така тріангуляція DT(P), що жодна точка множини P не знаходиться всередині описаних довкола трикутників кіл в множині DT(P). Тріангуляція Делоне дозволяє якомога зменшити кількість малих кутів.
Детальніше про триангуляцію Делоне можна прочитати у М. Ласло, «Вычислительная геометрия и компьютерная графика на С », Препарата, Шеймос, «Вычислительная геометрия. Введение» та інших джерелах.

Для триангуляції Делоне (але не для довільних триангуляцій), виконується твердження:

Нехай AB, BC і CA – сторони трикутника триангуляції Делоне.

Нехай найбільший можливий діаметр стола, котрий можна про­нести через відрізок AB (в напрямку іззовні всере́дину ΔABC) дорівнює (). Тоді найбільші можливі діаметри столів, котрі можна пронести через відрізки BC та CA (в напрямку зсере́дини назовні ΔABC) визначаються як та відповідно.

(без доведення)

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

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

Зрозуміло, що такий алгоритм істотно складніший, ніж знаходження критичного параметра перегороджувального графа. Але при правильній реалі­зації він теж працюватиме дуже швидко. Точніше кажучи, його не дуже складно реалізувати з (тими самими) оцінками O(N) пам’яті, O(N2) часу, і, більш того, в принципі можлива (але технічно дуже складна, особливо при необхід­ності враховувати випадок чотирьох і більше точок на одному колі) реалізація з часовою оцінкою .

Крім того, алгоритм “Делоне Дейкстри” (єдиний із згаданих) дозволяє (при дуже незначних модифікаціях) шукати не лише діаметр найбіль­шого стола, а й шлях, по котрому слід нести такий найбільший стіл. Це не потрібно при даному формулюванні задачі, але може бути суттєвим в інших умовах.


Додаток. Приклад підбору критичного параметра графа перепон


Тут наведено процес підбору на прикладі конкретних вхідних даних. Загальний словесний алгоритм див.
Сло́во - найменша самостійна і вільно відтворювана в мовленні відокремлено оформлена значима одиниця мови, яка співвідноситься з пізнаним і вичленуваним окремим елементом дійсності (предметом, явищем, ознакою, процесом, відношенням та ін.)
у пункті “Знаходження критичного параметра графа перепон”

Колони 1–6 задані у вхідних даних, а 7 та 8 віртуальні (згідно проведеного аналізу, інші віртуальні колони не потрібні).

Граф перепон складається з самої лише вершини 8, d=0.





Найменшу (20) відстань від побудованої час­тини графа перепон має вершина 2, тож її і додаємо до графа перепон. Оскільки вибрана відстань більша за поточне значе­ння d=0, міняємо значення d.



Найменшу (≈14,143) відстань від побудо­ва­ної частини графа перепон має верши­на 4 (рахуючи її відстань до графа перепон як відстань до вершини 2), тож її і додаємо до графа перепон. Оскільки відстань до неї менша за поточне значення d=20, не міня­ємо значення d.



Найменшу (20) відстань від побудованої частини графа перепон має вершина 5 (рахуючи її відстань до графа перепон як відстань до вершини 4), тож її і додаємо до графа перепон. Очевидно, d не міняється.



Одну з однакових найменших (≈22,361) відстаней від побудо­ваної частини графа перепон має верши­на 1 (рахуючи її від­стань до графа перепон як відстань до будь-якої з вершин 2, 4 або 5), тож її і додаємо до графа перепон. Оскільки ви­брана відстань більша за пото­чне значе­ння d=20, міняємо значення d.



Найменшу (≈22,361) відстань від побудо­ваної частини графа перепон має верши­на 3 (рахуючи її відстань до графа перепон як відстань до вершини 5), тож її і додаємо до графа перепон. d не міняється.



Найменшу (≈14,143) відстань від побудо­ва­ної частини графа перепон має верши­на 6 (рахуючи її відстань до графа перепон як відстань до вершини 3), тож її і додаємо до графа перепон. Оскільки відстань до неї менша за поточне значення d≈22,361, не міня­ємо значення d.



Найменшу (20) відстань від побудо­ва­ної частини графа перепон має верши­на 7 (рахуючи її відстань до графа перепон як відстань до вершини 6), тож її і додаємо до графа перепон. Оскільки відстань до неї менша за поточне значення d≈22,361, не міня­ємо значення d.

Оскільки верши­на 7 є правою віртуальною колоною, закін­чуємо основний цикл алгоритма (навіть якби лишалися інші недосліджені колони). Критичним пара­мет­ром графа перепон є поточне значення d≈22,361.










1 Такі числа в літературі часто називаються числами Спрага-Ґрюнді


Скачати 230.71 Kb.

  • Розв’язок задачі «Погодні умови»
  • Розв’язок задачі «Шоколадні плитки»
  • Розв’язок задачі «Працівники»
  • Розв’язок 2 (Динамічне програмування)
  • Розв’язок 3 (Комбінаторні обчислення)
  • Розв’язок 4 (Масив констант)
  • Розв’язок задачі «Робот»
  • Розв’язок задачі «Зала Круглих Столів»
  • Аналіз кругів та аналіз ліній
  • Створення додаткових (віртуальних) колон
  • Зв’язок між максимальним діаметром стола та діаметром колон. Ре́бра перепон
  • Граф перепон. Параметр графа перепон. Зв’язок між максимальним діаметром стола та параметром графа перепон
  • Знаходження критичного параметра графа перепон
  • Аналіз об’єму пам’яті та кількості дій
  • Короткий аналіз інших методів розв’язання
  • Знаходження шляху пронесення столу через застосування модифікації алгоритма Дейкстри до триангуляції Делоне
  • Додаток. Приклад підбору критичного параметра графа перепон