Задача про густий ліс: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
оформлення, стиль |
стиль |
||
| Рядок 31: | Рядок 31: | ||
Більшість бар'єрних конструкцій такі, що той факт, що він покриває необхідний ділянку, гарантований. Однак, з огляду на довільний бар'єр T, було б бажано підтвердити, що він охоплює бажану область C. |
Більшість бар'єрних конструкцій такі, що той факт, що він покриває необхідний ділянку, гарантований. Однак, з огляду на довільний бар'єр T, було б бажано підтвердити, що він охоплює бажану область C. |
||
Як простий перший прохід можна порівняти [[Опукла оболонка|опуклі оболонки]] C і T. T охоплює не більше ніж його опуклу оболонку, тому якщо опукла оболонка T не містить строго C, то вона не може покрити T. Це дає простий [[Обчислювальна складність|O (N log n)]] алгоритм першого проходу для перевірки бар'єру. Якщо T складається з однієї [[Компонента зв'язності графа|компоненти зв'язності]], то він покриває точно її опуклу оболонку, і цей алгоритм є достатнім. Однак, якщо T містить більше однієї компоненти, він може покривати менше. Таким чином, цей тест в цілому недостатній. |
|||
Проблема визначення того, які саме області покриває будь-який даний ліс T, що складається з m компонент зв'язності та n ділянок лінії, може бути вирішена за час О (m<sup>2</sup>n<sup>2</sup>).<ref>A. Beingessner, M. Smid, Computing the Coverage of an Opaque Forest, 24th Annual Canadian Conference on Computation Geometry (2012)</ref> Основна процедура для цього проста: спочатку спростити кожну компоненту зв'язності, замінивши його своєю опуклою оболонкою. Потім для вершини p кожної опуклої оболонки виконайте кругову розгортку по площині з центром в точці p, відстежуючи, коли ця лінія не проколює опуклу оболонку (крім самої точки p). Орієнтації лінії розгортки, під час якої відбувся перетин, створюють «сонце»-подібна множина точок (набір подвійних клинів з центром в точці р). Покриття T — це перетин всіх цих «сонець» для всіх виборів p. |
Проблема визначення того, які саме області покриває будь-який даний ліс T, що складається з m компонент зв'язності та n ділянок лінії, може бути вирішена за час О (m<sup>2</sup>n<sup>2</sup>).<ref>A. Beingessner, M. Smid, Computing the Coverage of an Opaque Forest, 24th Annual Canadian Conference on Computation Geometry (2012)</ref> Основна процедура для цього проста: спочатку спростити кожну компоненту зв'язності, замінивши його своєю опуклою оболонкою. Потім для вершини p кожної опуклої оболонки виконайте кругову розгортку по площині з центром в точці p, відстежуючи, коли ця лінія не проколює опуклу оболонку (крім самої точки p). Орієнтації лінії розгортки, під час якої відбувся перетин, створюють «сонце»-подібна множина точок (набір подвійних клинів з центром в точці р). Покриття T — це перетин всіх цих «сонець» для всіх виборів p. |
||
Версія за 17:47, 21 липня 2017
В обчислювальній геометрії, проблема густого лісу може бути сформульована таким чином: «Для опуклого багатокутника С в площині, визначити мінімальний ліс Т замкнених, обмежених відрізків, таких, що кожна лінія, яка проходить через C, також перетинає Т». Т називається густим лісом, або бар'єром для C. Відповідно C називається охопленням T. У той час як будь-який ліс, що охоплює С являє собою бар'єр C, ми хочемо знайти ліс з найменшою довжиною.
Може бути, що Т обмежено як строго внутрішня або зовнішня частина C. У цьому випадку бар'єр називається внутрішнім або зовнішнім. В іншому випадку, вважається, що на бар'єр не накладається жодних обмежень.
Історія і труднощі
Проблема густого лісу спочатку була введена Стефаном Мазуркевичем[en] в 1916 році.[1] З тих пір не було досягнуто великого прогресу щодо початкової проблеми. Не існує будь-яких способів перевірити загальне рішення цієї проблеми. Насправді, оптимальне рішення навіть для простих фіксованих вхідних даних, таких як одиничний квадрат або рівносторонній трикутник, невідоме. Існують гіпотетичні оптимальні рішення для обох цих випадків, але в даний час у нас немає інструментарію для доказу того, що вони є оптимальними.[2] Хоча загальні вирішення проблеми були заявлені декількома особами,[3][4] вони або не були розглянуті експертами, або були продемонстровані як помилкові.[5][6]
Обмеження оптимального рішення
З огляду на опуклий багатокутник C з периметром p, можна обмежити значення оптимального рішення в термінах p. Ці кордони індивідуально обмежені в загальному, але через різних форм, які можуть бути надані, досить вільні один щодо одного.
У загальному випадку можна довести, що p/2 ≤ |OPT| ≤ p.
Верхня межа
Неважко переконатися, що просто простежити периметр С досить, аби покрити його. Тому p є верхньою межею для будь-якого C. Для внутрішніх бар'єрів ця межа щільна в граничному випадку, коли C — коло; Кожна точка q по периметру кола повинна міститися в T або дотична до C може бути проведена через q без перетину T. Однак для будь-якого іншого опуклого багатокутника це є неоптимальним, що означає, що це не найліпша верхня межа для більшості вхідних даних.
Для більшості вхідних даних трохи краща верхня межа для опуклих багатокутників може бути знайдена по довжині периметра, за винятком найдовшого ребра (яке є мінімальним кістяковим деревом). Більш того, можна взяти мінімальне дерево Штейнера вершин багатокутника. Для внутрішніх бар'єрів єдиним способом поліпшити цю межу є створення незв'язаного бар'єру.
Нижня межа
Різні докази нижньої межі можна знайти в[7]. Щоб переконатися, що це, взагалі кажучи, жорстке, можна розглянути випадок розтягування дуже довгого і тонкого прямокутника. Будь який густий ліс для цієї форми повинен бути принаймні таким же довгим, як прямокутник, або ж є отвір, через яке можуть проходити вертикальні лінії. Відповідно до того, як прямокутник стає довшим і тоншим, це значення наближається до p / 2. Тому ця оцінка в загальному випадку щільна. Однак для будь-якої форми, яка насправді має позитивну область, потрібна додаткова довжина, щоб охопити фігуру в інших напрямках. Отже, це не особливо гарна нижня межа для більшості вхідних даних.
Особливі випадки
Для одиничного квадрата, ці оцінки — 2 і 4 відповідно. Проте, дещо поліпшилися нижні межі 2 + 10−12 для бар'єрів, які задовольняють обмеження локальності і 2 + 10−5 для внутрішніх бар'єрів, були запитані[7] Однак доказ цього ще не перевірений.
Наближення
Через труднощі, з якими довелося зіткнутися, щоб знайти оптимальний бар'єр для навіть простих прикладів, стало дуже бажано знайти бар'єр, який наближається до оптимального з деяким постійним фактором.
Думітреску та інші[8] надають кілька лінійних наближень для оптимального рішення. Для загальних бар'єрів вони забезпечують коефіцієнт апроксимації 1/2 + (2 + √2) / π = 1,5867 …. Для пов'язаних бар'єрів вони покращують це співвідношення до 1,5716. Якщо бар'єр обмежений однією дугою, він досягає відношення (π + 5) / (π + 2) = 1,5834.
Перевірка бар'єрів і підрахунок охоплення лісів
Більшість бар'єрних конструкцій такі, що той факт, що він покриває необхідний ділянку, гарантований. Однак, з огляду на довільний бар'єр T, було б бажано підтвердити, що він охоплює бажану область C.
Як простий перший прохід можна порівняти опуклі оболонки C і T. T охоплює не більше ніж його опуклу оболонку, тому якщо опукла оболонка T не містить строго C, то вона не може покрити T. Це дає простий O (N log n) алгоритм першого проходу для перевірки бар'єру. Якщо T складається з однієї компоненти зв'язності, то він покриває точно її опуклу оболонку, і цей алгоритм є достатнім. Однак, якщо T містить більше однієї компоненти, він може покривати менше. Таким чином, цей тест в цілому недостатній.
Проблема визначення того, які саме області покриває будь-який даний ліс T, що складається з m компонент зв'язності та n ділянок лінії, може бути вирішена за час О (m2n2).[9] Основна процедура для цього проста: спочатку спростити кожну компоненту зв'язності, замінивши його своєю опуклою оболонкою. Потім для вершини p кожної опуклої оболонки виконайте кругову розгортку по площині з центром в точці p, відстежуючи, коли ця лінія не проколює опуклу оболонку (крім самої точки p). Орієнтації лінії розгортки, під час якої відбувся перетин, створюють «сонце»-подібна множина точок (набір подвійних клинів з центром в точці р). Покриття T — це перетин всіх цих «сонець» для всіх виборів p.
Хоча цей алгоритм оптимальний в найгіршому випадку, він часто робить багато непотрібної роботи, коли це не потрібно. Зокрема, коли опуклі оболонки спочатку обчислюються, багато з них можуть перекриватися. Якщо це так, то їх можна замінити на їх об'єднану опуклу оболонку без втрати спільності. Якщо після злиття всіх корпусів, що перекриваються, виник єдиний бар'єр, тоді загальний алгоритм не потрібно запускати; покриття бар'єру не перевищує його опуклу оболонку, і ми тільки що визначили, що його покриття — його опукла оболонка. Об'єднані оболонки можуть бути обчислені за час O (nlog2n). Якщо залишилося кілька корпусів, алгоритм може бути запущений на новому спрощеному наборі корпусів і завершить обчислення за менший час.[10]
Див. також
Примітки
- ↑ S. Mazurkiewicz, Sur un ensemble ferm´e, punctiforme, qui rencontre toute droite passant par un certain domaine (Polish, French summary), Prace Mat.-Fiz. 27 (1916), 11–16.
- ↑ Opaque sets; Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques; 194—205
- ↑ V. Akman, An algorithm for determining an opaque minimal forest of a convex polygon, Information Processing Letters, 24 (1987), 193—198.
- ↑ P. Dublish, An O(n3) algorithm for finding the minimal opaque forest of a convex polygon, Information Processing Letters, 29(5) (1988), 275—276.
- ↑ T. Shermer, A counterexample to the algorithms for determining opaque minimal forests, Information Processing Letters, 40 (1991), 41–42.
- ↑ J. S. Provan, M. Brazil, D. A. Thomas and J. F. Weng, Minimum opaque covers for polygonal regions, manuscript, October 2012, arXiv:1210.8139v1
- ↑ а б A, Dumitrescu and M. Jiang, The Opaque Square (2013) http://arxiv.org/pdf/1311.3323v1.pdf
- ↑ A. Dumitrescu, M. Jiang, and J. Pach. Opaque sets. Algorithmica. To appear. Online first, December 2012.
- ↑ A. Beingessner, M. Smid, Computing the Coverage of an Opaque Forest, 24th Annual Canadian Conference on Computation Geometry (2012)
- ↑ Luis Barba, Alexis Beingessner, Prosenjit Bose, Michiel H. M. Smid: Computing Covers of Plane Forests. 25th Annual Canadian Conference on Computational Geometry (2013)