S knihou sa nenudím ani počas niekoľkohodinového čakania a ak aj nemám knihu, nie je problém sa príjemne zabaviť - len tak v mysli. Minule ma počas dlhej cesty autom (samozrejme keď som nešoféroval!) napadla takáto úloha:Predpokladajme, že v rovine máme párny počet bodov. Zdá sa intuitívne zrejmé, že tieto body môžeme pospájať úsečkami do dvojíc tak, aby sa žiadne dve z týchto úsečiek nepretínali. Vedeli by ste vymyslieť úplne jasný dôkaz, že to je naozaj tak? A vedeli by ste popísať nejaký efektívny algoritmus, ktorý také párovanie bodov nájde?
Prve, co mi napadlo, boli najmensie vzdialenosti. Ale to neslo uplne hladko.
OdpovedaťOdstrániťDruhy bol vejar useciek z jedneho bodu - ale to pada dost na kolinearite.
Treti napad sa mi vidi schodny. Urobi sa konvexny obal mnoziny, ten ma na okraji minimalne tri usecky. Vyberie sa jedna z nich, taka, ktora nelezi medzi dvoma inymi bodmi na tej istej priamke. Tato sa spoji. Ostatok ma konvexny obal, ktory nepretina tuto usecku, takze postupnou redukciou sa pride az do konca.
Mne zasa napadlo toto: Začnime s ľubovolným párovaním a zvoľme ľubovoľné 4 body. Ak sa úsečky spájajúce tieto 4 body pretínajú, potom prepárujme tieto body inak (máme 2 možnosti). Obe vedú k striktnému zníženiu súčtu dĺžok úsečiek (trojuholníková nerovnosť v prípade že všetky 4 neležia na jednej priamke, ak ležia je to jasné).
OdpovedaťOdstrániťToto sa dá opakovať len konečne veľa krát pretože žiadne dve párovania nemôžu byť rovnaké...
Azda treba vychytať nejaké detaily ale myslím že takto by to tiež šlo...
Teraz by ma zaujímalo ako najlepšie by sa to dalo spraviť čo sa týka zložitosti. Plus by ma zaujímalo či sa dajú všetky riešenia opísať ako lokálne minimá nejakej peknej funkcie...
A čo takto:
OdpovedaťOdstrániťUsporiadajme všetky body podľa x-ovej súradnice (n log n). Ak sú všetky tieto súradnice iné, máme po probléme. Spojíme bod s najmenšou súradnicou s bodom s druhou najmenšou atď. Ak napríklad máme k bodov s najmenšou x-ovou súradnicou, tak ak je k párne, zasa nemáme problém. Pospájama tieto bodíky podľa y-ovej súradnice a ideme na body s druhou najmenšou x-ovou. Ak je k nepárne, pospájame k-1 bodov "zhora dolu", zbavíme sa ich a iterujeme.
Treba opísať ešte zopár prípadov ale myslím že je jasné ako to celé bude prebiehať.
Zložitosť teda vyzerá byť O(n log n).
No a ešte mám jeden nápad: Rekurzívny nekonštrukčný dôkaz.
OdpovedaťOdstrániťPredpokladajme že sa dá dokázať že ak máme v rovine množinu M s párnym počtom bodov, potom vždy možno nájsť priamku, ktorá striktne oddeľuje M na dve množiny A a B, kážda obsahujúc nenulový párny počet bodov.
Stačí ak pod striktne rozumieme že aspoň jedna z množín A, B nemá prienik s priamkou, i keď sa myslím dá dokázať, že existuje priamka taká že obe množiny s ňou nemajú prienik.
Oukej. Trošku dlhý úvod. No ak toto vieme, tak dôkaz plynie z rekurzie.
Dokázať eistenciu takej deliacej priamky vyzerá byť celkom jednoduché. Stačí zobrať konvexný obal M, a uvažovať ľubovoľnú jeho hranu. Touto vedieme priamku. Na tejto priamke sú aspoň dva body. Teraz priamku nakloníme tak aby práve dva body zostali na jednej strane priamky (v uzavretej polrovine danej priamkou) a všetky ostatné boli v druhej (otvorenej) polrovine. Tu sa treba trošku pohrať, ale vyzerá byť zrejmé že to pôjde. Ak chceme, malým posunutím môžeme dosiahnuť, že na priamke nebude ležať žiaden bod.
Heh. Nemôžem si pomôcť ale mám ešte dačo.
OdpovedaťOdstrániťUvažujme nad párovaním s najmenším možným súčtom dĺžok úsečiek (možno vypočítať v O(n^3) cez "Maďarskú metódu").
Žiadne dve sa nemôžu pretínať, pretože by nastala situácia ako v mojom prvom poste a jednoduchou lokálnou zámenou párov medzi 4 bodmi by sme dostali lepšie párovanie. Q.E.D.
Lev: Zdá sa, že s tým konvexným obalom máš pravdu; je to originálny nápad, aj keď naprogramovanie by bolo pomerne zdĺhavé.
OdpovedaťOdstrániťPeter, komentár 1: Veľmi nápaditý dôkaz, že to disjunkté párovanie existuje. Dal by sa na tom založiť aj algoritmus nájdenia takého párovania, ale bol by asi pomerne neefektívny, aspoň teda v porovnaní s inými možnosťami.
Peter, komentár 2: Toto napadlo aj mňa, len by som dodal, že asi stačí dané body usporiadať lexikograficky a potom spojiť body, ktoré sú v tomto usporiadaní prvý s druhým, tretí so štvrtým a tak ďalej. Toto má zložitosť O(n.log(n)). Inak lepšia asymptotická zložitosť sa nedá dosiahnuť, pretože problém usporiadania n-tice čísiel sa dá previesť na tento problém, čiže ak by toto disjunktné párovanie bolo možné urobiť s lepšou asymptotickou zložitosťou, potom by sme vedeli skonštruovať aj algoritmus na usporiadanie s ostro lepšou zložitosťou ako n.log(n), čo je myslím dokázané, že je nemožné.
Peter, komentár 3: Toto je opäť zaujímavý nápad, ale musel by som si ho trochu lepšie premyslieť, aby som sa k nemu mohol viac vyjadriť.
Peter, komentár 4: Presne toto bol môj pôvodný argument, že disjunktné párovanie existuje. Skrátka párovanie s minimálnym súčtom dĺžok spájajúcich úsečiek musí byť disjunktné. Maďarská metóda však asi nie je optimálna jednak preto, že jej zložitosť je pomerne vysoká a tiež preto, lebo na jej použitie už musíme mať vopred delenie bodov na dve skupiny a takých delení (a to aj špeciálneho typu pol na pol) je veľmi veľa.
Peter: Beriem späť tú moju poznámku o Maďarskej metóde týkajúcu sa veľkého počtu delení množiny bodov pol na pol. Samozrejme, že nie je nutné prechádzať všetkými deleniami. Stačí vytvoriť taký umelý problém optimálneho párovania, kde "workers" a aj "jobs" bude naša n-prvková množina bodov, pričom matica nákladov bude mať na diagonále nekonečno (alebo konečné, ale dostatočne veľké číslo). Ak by teda bolo cieľom nájsť takéto párovanie bodov v rovine s minimálnym súčtom dĺžok spojníc, tak by asi toto bolo jedno z najlepších riešení.
OdpovedaťOdstrániťMne napadlo riesenie pomocou konvexnych obalov podobne levovmu napadu. Majme na zaciatku mnozinu bodov M_0. Zostrojim jej konvexny obal (KO), a body vnutri KO oznacim M_1. Zostrojim KO(M_1) atd.
OdpovedaťOdstrániťPoparujem susedne body na KO(M_0), ak mi jeden zvysi, najdem ku nemu najblizsi vrchol z KO(M1), zvysne z KO(M_1) poparujem atd.
Urcite to nie je najefektivnejsie riesenie. Vyzera na prvy pohlad na O(n^2 log n).
Ten Petrov algoritmus s usporiadanim vyzera byt optimalny. Aj ked nevidim, preco by to neslo lepsie.
Pavel: Ja som to tak stručne naznačil v predchádzajúcom komentári, že si myslím, že to rýchlejšie ako tých Peťových O(n log(n)) už nepôjde. Skúsim to rozpísať podrobnejšie.
OdpovedaťOdstrániťPredstav si, že máš na toto disjunktné párovanie algoritmus A. Nech x1,...,xn (n párne) sú akékoľvek reálne čísla. Zostroj body v rovine (x1,0),...,(xn,0) a aplikuj na ne A. Potom vylúč z bodov x1,...,xn minimum a maximum (pre jednoduchosť nech x1 je minimum a xn maximum) a na body (x2,0),...,(x{n-1},0) opäť aplikuj A. Z týchto dvoch párovaní už okamžite skonštruuješ usporiadanie čísiel x1,...,xn (začneš s x1, pozrieš jeho pár v prvom párovaní, pár tohoto bodu v druhom párovaní, opäť pár tohoto bodu v prvom párovaní a tak ďalej). Všimni si tiež, že všetko toto sa dá urobiť v lineárnom čase.
Teda ak by mal A zložitosť ostro lepšiu ako O(n log(n)), tak sme postupom hore skonštruovali algoritmus na usporiadanie so zložitosťou ostro lepšou ako O(n log(n))...
Ahoj Rado ! Hoci som sa dal na dráhu medicíny, rád si zaspomínam na naše mat-olympiádové časy :-) Mne sa zdá, že s tým odborným konvexným obalom množiny je to O.K., ja som laicky prišiel na myšlienku skonštruovať z tých bodov mnohouholník o n vrcholoch a potom každú druhú spojnicu proste vynechať. Ešte by to chcelo doklepnúť v zmysle dôkazu, že taký mnohouholník ide zostrojiť, poťažmo by som vylúčil pár bodov, aby sa dal, a tak podobne. Ahoj, Valo Valášek
OdpovedaťOdstrániťNazdar Valerián! Som veľmi príjemne prekvapený, že si na mňa pamätáš! Inak viem, že si v zdravotníctve, občas si čítam Tvoj blog na SME. (Tiež som sa raz pri milionárovi chválil, že toho chlapca v kresle poznám z matematických sústredení :-)
OdpovedaťOdstrániťS tým konvexným obalom máš pravdu; tak to tiež ide. To už máme vyriešené. Ale ak máš chuť, môžeš skúsiť vyriešiť napríklad problém "konštatntnej šírky", na ktorý dosiaľ nikto neprišiel (a nie je ťažký, len treba mať vtipný nápad).
Redukcia na triedenie:
OdpovedaťOdstrániťMajme 2N rôznych čísel ktoré chceme utriediť, nazvime ich x_1 až x_{2N}. Vyrobíme 2N bodov, i-ty z nich bude [x_i,0]. Tieto podhodíme algoritmu na párovanie. Keďže naše body ležia na priamke, zjavne existuje práve jeden korektný výstup. Teraz nájdeme v lineárnom čase najmenšie a najväčšie z našich 2N čísel. Dotyčné dva body vyhodíme a spustíme párovací algoritmus pre zvyšných 2N-2 bodov. Z týchto dvoch výstupov vieme v lineárnom čase zostrojiť utriedenú postupnosť našich 2N čísel. Preto úloha popárovať body nejde riešiť v čase lepšom ako triedenie.
Konkrétny záver teraz asi závisí od použitého výpočtového modelu, ale v princípe môžem prehlásiť, že párovanie bodov v lepšom čase ako O(N log N) nejde.
misof: Je to sranda, ale Tvoj postup je prakticky identický ako ten, ktorý som ja popísal v komentári vyššie (2.7.; zrejme si to prehliadol). Kažopádne je pozorouhodné - a v matematike sa to často stáva - k ako podobným veciam ľudia môžu nezávisle dôjsť.
OdpovedaťOdstrániťAha, hej, fakt som to prehliadol :)
OdpovedaťOdstrániťSom presvedceny ze ked som cital diskusiu, nebolo to tam :D takze najskor sa mi podarilo pri citani ten prispevok nejak preskocit. Sorry za sposobeny zmatok.
A ozaj sme to napisali nejak podozrivo rovnako ;)
ok teraz je zaujimava otazka, kolko disjunktnych parovani ma 2k "vseobecne" umiestnenych bodov
OdpovedaťOdstrániťtj kolko ich tam najdem urcite vzdy
pre 4 body je to asi 2, pre 2 body je to urcite 1
uz pre 6 bodov to vyzera dost netrivialne