Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Сезон 2002 - 2003
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2001 - 2002
Сезон 2000 - 2001
Задача 6 - ДВИЖЕНИЕ НА РОБОТ - Анализ

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

За решаването на задачи от КГ, обаче, са необходими и сериозни познания от общата теория на алгоритмите и структурите от данни, без които е невъзможно създаването на ефективни алгоритмични решения. Шестата задача от нашия конкурс е от един от дяловете на КГ, наричан планиране на движението. Задачи от подобен тип възникват съвсем естествено, и най-вече, при програмирането на  роботи и роботизирани системи, но са интересни и в други области на приложение на компютрите. Например, при създаване на компютърни игри, за да се постигне реалистичност на движението на основните фигури в сцената на играта, когато върху нея са разположени неподвижни препятствия.

 

                                                                 

                        Фиг. 1                                                             Фиг. 2

 

Да започнем изграждане на решението отзад напред. Тъй като задачата е свързана с намирането на път, това естествено ни води до идеята за използване на граф в зададеното пространство (сцената), тъй като задачата за намиране на път в граф е достатъчно добре известна. На Фиг.1 е показана една примерна сцена, на която препятствията, контурите на които са прости полигони, са защриховани. За да опростим нещата, за сега ще считаме, че препятствията не се припокриват. На фигурата е показан и геометричен граф, върховете и ребрата на който са разположени в свободната от препятствия част на сцената – т.е. нито връх, нито точка от ребро на графа са вътре или по контура на някой полигон. Построяването на такъв граф очевидно решава поставената задача.

За построяването на графа ще използваме т.н. трапецоидна карта (ТК) на сцената. На Фиг. 2 е показана ТК на сцената от Фиг.1. Преди да сме дали точна дефиниция можем да кажем, че тя е разбиване на свободната част на сцената на трапеци, две от страните, на които са успоредни на вертикалната ос. (По традиция в аналитичната геометрия считаме вертикалните прави за “изродени”. Ако “обърнем” тази традиция, бихме могли да строим ТК и така, че успоредните страни на всеки трапец да са успоредни на хоризонталната ос.)

Нека на сцена с правоъгълна форма и страни успоредни на координатните оси е зададено множество от отсечки S={s1,s2,…,sn}, които не се пресичат (но могат да имат общи краища) и между зададените отсечки (засега) няма вертикални. За такова множество от отсечки казваме, че са в общо положение. През края на всяка отсечка да прекараме вертикална права до пресичането й с най-близките отгоре и отдолу отсечки от множеството или със страна на обхващащия правоъгълник. Не е трудно да се види че всяка част на сцената получена от прекарването на такива прави има 1 или 2 вертикални и точно 2 невертикални страни. Значи в общия случай тя е трапец, а в частния случай, при 1 вертикална страна, съответният трапец е изроден в триъгълник. Очевидно никой трапец на разбиването не съдържа във вътрешността си точки, принадлежащи на отсечките от множеството. Това разбиване на сцената наричаме трапецоидна карта. На Фиг. 3 е показана ТК на множество от 2 отсечки в общо положение.

 

                       

                        Фиг. 3.                                                                                    Фиг. 4

 

Нека в някакви структури да сме запазили данните за зададените отсечки и техните краища. ТК може да бъде представена в паметта на компютъра като за всеки трапец D се пазят указатели към ограничаващите го отдолу и отгоре отсечки от S – да ги означим с bottom(D) и top(D), както и указатели към двата края на отсечки, породили вертикалните линии, ограничаващи трапеца – да ги означим с  leftp(D) и rightp(D).

За да получим алгоритъм за построяване на ТК е необходима специализирана структура данни, с помощта на която да можем да извършваме необходимите операции. На Фиг. 4 е показана двоична дървовидна структура с наредба на синовете D, предназначена за търсене в T(S). Всеки лист  на D (представен с квадратче) съответства на трапец от T(S). За еднозначност всички листа съответни на един и същ трапец са събрани в едно, така че D в същност е даг (ориентиран ацикличен граф). T(S) и D са взаимно свързани, като всеки трапец е свързан с указател със съответния му лист в D и обратно. Освен листата, които съответстват на трапеците, в D има още два типа върхове – кръглите защриховани върхове съответстват на отсечките от S и се наричат y-върхове, а кръглите незащриховани върхове съответстват на краищата на отсечките от S и се наричат x-върхове. За всеки y-връх лявото му поддърво описва частта от ТК, намираща се над съответната отсечка, а дясното – частта под съответната отсечка. За всеки x-връх лявото му поддърво описва частта от ТК, намираща се вляво на съответната му точка, а дясното – частта вдясно на съответната точка.

За съжаление структурата D не притежава никакво свойство подобно на “балансираност” и скоростта на алгоритъма ще зависи много от взаимното положение на отсечките и редът по който се разглеждат. Вместо да се прави сложен анализ на данните в търсене на оптимална подредба, се използва обичайната в такива случаи техника – рандомизацията. Ето и рандомизираният алгоритъм за построяване на ТК за множество отсечки в общо положение:

1.      Създаваме началните T и D от правоъгълника, в който са разположени отсечките и който е частен случай на трапец. Структурата D ще съдържа само един лист съответен на този трапец.

2.      Подреждаме отсечките в S по случаен начин – s1, s2,…, sn

3.      За всяка отсечка si, i=1,2,…,n:

3.1.  Намираме последователността от трапеци D1, D2,…, Dk, които si пресича в този ред отляво надясно.

3.2.  Изтриваме D1,D2,…,Dk от T и ги заменяме с новите d1,d2,…,dk’, породени от пресичането на D1, D2,…, Dk  с si.

3.3.  Изтриваме листата на D съответни на D1,D2,…,Dk и ги заменяме с нови, съответни на d1,d2,…,dk’, като свързваме новите листа с нови нелиста в D, както е описано по-долу.

Ето и някои детайли на този алторитъм. Нека si пресича изцяло всеки трапец от D1,D2,…,Dk. Когато si пресича изцяло трапеца D, тогава D се разделя на две трапецовидни части – горната половина на D и долната половина на D. Всички горни половини на трапеци от D1,D2,…,Dk, които имат една и съща отсечка s за горна страна (и значи са един до друг в последователността) обединяваме в нов трапец с горна страна s и долна страна si. За новополучения трапец bottom(), top(), leftp() и rightp() се намират лесно. По същия начин постъпваме и с долните половини. Получените по този начин нови трапеци d1,d2,…,dk’ заменят старите D1,D2,…,Dk в картата. За обновяването на D в такъв случай е достататъчно да изтрием листата, съответни на D1,D2,…,Dk и вместо тях да поставим нови, съответни на d1,d2,…,dk’. За всеки два нови трапеци (един горен D’ и един долен D’’), които имат общи гранични точки по si да поставим в D нов y-връх надписан с si. За ляв син на новия y-връх поставяме листа на D’, а за десен – на D’’. 

Ако левият край pi на si с лежи във вътрешността на трапеца D1, тогава вертикалната права през pi разделя D1 на ляв трапец D и дясна част, която от своя страна се дели от si на горен трапец D’ и долен трапец D’’. В този случай D става един от d1,d2,…,dk’, а  D’ и D’’ се включват в последователностите от горни и долни трапеци и работата на алгоритъма продължава както по-горе. В такъв случай в D се създава нов x-връх надписан с pi. За ляв син на новия x-връх поставяме листа на D, а за десен – нов y-връх надписан с si. За ляв син на този y-връх поставяме листа на трапеца, в който е влязал D’, а за десен – на този, в който е влязъл D’’. По симетричен начин постъпваме, когато десният край qi на si с лежи във вътрешността на трапеца Dk.

Оставяме на читателите да съобразят как да постъпят в крайния частен случай когато si лежи изцяло във вътрешността на единствен трапец. Да посочим само, че в такъв случай старият трапец се заменя от 4 нови, а при обновяването на D ще се добавят два нови x-върха за краищата на si и един нов y-връх за самата si.

Остана само да посочим как могат да бъдат намерени трапеците D1,D2,…,Dk, пресичани от отсечката s с ляв край p и десен край q:

1.      Намираме в D трапец D1, които съдържа p.

2.      I=1

3.      Докато q е вдясно от rightp(DI)

3.1. Ако rightp(DI) лежи над s тогава DI+1 е трапецът вдясно и по-долу от DI

3.2. Ако rightp(DI) лежи под s тогава DI+1 е трапецът вдясно и по-горе от DI

3.3.  I=I+1        

Нека споменем как може да се използва структурата D за да намерим трапеца D1, които съдържа p. Започваме от корена на D и докато не сме в лист правим следното: ако се намираме в x-връх надписан с точката p’, тогава продължаваме с левия му син, ако p е вляво от p’, а в противен случай – с десния син. Аналогично,  ако се намираме в y-връх надписан с отсечката s, тогава продължаваме с левия му син, ако p е под s, а в противен случай – с десния син. За да намерим трапец стоящ от дясно даден трапец D, трябва да тръгнем от листа съответен на D в D и да вървим към корена до срещането на първия x-връх, в който влизаме отляво. След което започваме движение надолу към десния син на този x-връх (вижте отново Фиг.3 и Фиг. 4). Ако десният син е лист, той съответства на единствения трапец, стоящ вдясно от D. Ако е x-връх, тогава тръгваме към левия му син и повтаряме горните съображения. Ако пък е y-връх надписан с правата s, тогава продължаваме с левия или десния син в зависимост от това дали rightp(D) лежи над s или под нея.

За да завършим с построяването на ТК нека да видим какво може да се направи, ако сред страните на препятствията има вертикални отсечки. Най-простото решение на този проблем е да се подложи сцената на следната трансформация. Избираме достатъчно малък ъгъл a и подлагаме всяка точка на въртене на ъгъл a с център проекцията и върху хоризонталната ос. Ако ъгълът се избере подходящо, всяка вертикална линия ще престане да бъде вертикална и никоя близка до вертикална няма да стане вертикална. За целта трябва да намерим измежду всички “почти” вертикални отсечки, чийто горен край се отклонява вляво от вертикалната права през долния край тази, при която ъгълът на отклонение b е най малък и да изберем a<b (най-добре е да вземем a=b/2).

Нека сега имаме ТК на сцената на нашата задача. Първо да изключим от картата всеки трапец, който влиза в някой от полигоните. След това във вътрешността на всеки трапец D от свободната част на сцената да изберем по един връх vD на бъдещия граф – това спокойно може да бъде центърът на трапеца. Върху всяка вертикална отсечка t, която e част от страни на съседните трапеци D’ и D’’ да изберем връх на графа vt -  това спокойно може да бъде средата на t, и да свържем с ребра vt с vD и vD’’. Да добавим началната и крайната точка сред върховете на графа и да ги свържем с ребра с центровете на трапеците, който ги съдържат. Очевидно е че всички ребра на получения граф лежат изцяло (включително и краищата им) в свободната част на сцената и не докосват препятствия. Намирането на искания в задачата път вече е много просто и може да стане, например, с построяване на покриващо дърво в ширина в получения граф, с начален връх дадената начална точка.  Предвид ограничението за дължината на пътя в условието на задачата, то ако полученият път е твърде дълъг ще се наложи да се “изправя” пътя. Най-лесно за “изправяне” vt’ vD vt’’ да се замени с vt’ vt’’ когато vt’ и vt’’ са върху срещуположните успоредни страни на трапеца.

Ще оценим качествата на предложения алгоритъм като функция на броя n на отсечките, които са страни на препятствията. За оценката е важна следната:

Теорема: За всяко множество от n отсечки, съответната ТК съдържа не повече от 3n+1 трапеци и не повече от 6n+4 точки.

Тази теорема показва, че за съхраняването на всички структури от данни ще е необходима  памет от порядък O(n) и подсказва каква времева сложност трябва да очакваме. За рандомизирания алгоритъм за построяване на ТК е доказано, че очакваната му сложност (т.е. сложността в средния случай) е O(n.logn), тъй като “усреднената” височина на структурата за търсене D е O(logn). Колкото до построявания от алгоритъма граф, от теоремата следва че порядъкът на върховете му е  O(n). Доколкото графът е планарен (никое ребро не пресича друго ребро във вътрешна точка), то и броят на ребрата му е от същия порядък. Затова построяването на графа, както и търсенето на път в него ще бъдат със сложност O(n). И така, имаме решение, което “обработва” зададена сцена със сложност O(n.logn), а след това, за произволни зададени начална и крайна точка, намира път или съобщава, че такъв път не съществува, със сложност O(n).

Ако страните на препятствията не са в общо положение, както е в задачата, тогава е необходимо предварително да се намерят всички пресечни точки на отсечките-страни и всяка отсечка пресичаща друга отсечка да се раздели на части от получените пресечни точки. За целта може да се използва техниката на сканиращата линия, която е със сложност O(nlogn + klogn), където k е броят на пресечните точки. Разбира се k може да е доста голямо и макар, че в реални сцени това няма да е така, по-добре е да се използва алгоритъм със сложност O(nlogn + k) – описан в статиите “A fast planar partition algorithm” на К.Mulmuley, “An optimal algorithm for finding segment intersections” на I.J.Balaban и др. В същност, алгоритъмът Mulmuley строи ТК, като междувременно намира и пресечните точки.

Друг подход към задачата е вместо да се построява ТК да се направи триангулация


За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.