Semestrální projekt PAR 2004/2005

Rudolf Marek

Pavel Němec

5. ročník, obor počítače, K336 FEL CVUT, Karlovo nám. 13, 121 35 Praha 2

Úloha MLC – minimální lomená čára

1. Definice problému

1.1.Vstupní data

k = přirozené číslo, k>=3, představující počet bodu v rovině
B[1..k] = množina různých bodu v rovině definovaných dvojici přirozených čísel (x, y)

1.2.Úkol

Konstrukce souvislé čáry, která spojí všech k bodu a bude obsahovat minimum zlomových bodů. Ke zlomu může dojít pouze v bodech množiny B. Čára může protínat sama sebe.

1.3.Výstup algoritmu

Souřadnice bodů, které jednoznačně popisují zkonstruovanou čáru a lze je zobrazit v programu gnuplot. Gnuplot používá formát dat, kde na každé řádce je zadán jeden bod pomocí svých souřadnic x a y. Konkrétně, vygenerujte dva soubory: v prvním souboru budou souřadnice zadaných vstupních bodů. Druhý soubor obsahuje sekvenci všech bodu, kde dochází k lomu (plus počáteční body čáry).

2.Popis algoritmu

2.1.Sekvenční algoritmus:

Řešení vždy existuje. V nejjednodušším případě, kdy všechny body leží v přímce, nebude mít čára žádný lom. V nejhorším případě se bude čára lomit v každém bode, takže čára bude mít celkem minimálně 0 a maximálně k-2 lomu. Sekvenční algoritmus je tedy typu BB-DFS s hloubkou prohledávaného prostoru omezenou na k-2.
Přípustný koncový stav je situace, kdy všechny body z množiny B leží na sestrojené lomené čáře. Cenu, kterou minimalizujeme, je počet lomů, které sestrojena čára obsahuje. V koncovém stavu musíme aktualizovat cenu nejlepšího řešení, pokud je cena nalezeného řešení lepší než do té doby nejlepší známá cena. Algoritmus končí, když cena řešení koncového stavu je rovna minimální možné ceně (tj. čára neobsahuje žádný lom), jinak algoritmus prohledává celý stavový prostor a na konci vypíše minimální počet zlomů.

2.1.1.Stav řešení

Je množina zpracovaných bodů, množina nezpracovaných bodů, počet dosavadních lomů a „servisní“ hodnota určující mohutnost množiny nezpracovaných bodů.

2.1.2.Detailnější popis řešení sekvenčního algoritmu

Na začátku se vygeneruje počáteční stav, který má plnou množinu nezpracovaných bodů prázdnou množinu zpracovaných bodů, počet lomů je nula. Tento stav se uloží na zásobník, který je schopen pracovat se strukturou stav. Funkce explode vybere jeden stav ze zásobníku, a přidá postupně vždy jeden bod z množiny nezpracovaných bodů do množiny již zpracovaných bodů. Pak se zavolá funkce která zjistí zdali přidaný bod stále leží na přímce společně s posledními dvěma body. Pokud ne zvýší se počet lomů. Pokud je množina nezpracovaných bodů prázdná porovná se počet lomů ze stavu s globálním minimem počtu lomů, pokud je řešení ze stavu lepší, globální minimum se změní. Pokud nejsou zpracovány všechny body a i tak je počet lomů větší než globální minimum, stav se zahodí.

2.2.Paralelní algoritmus:

Paralelní algoritmus je typu G-PBB-DFS-D, hledaní dárce algoritmem ACZ-AHD, dělení zásobníku pomocí D-R-ADZ. Na začátku provede proces #0 základní počet expanzí a následně distribuci zásobníku mezi procesy které ho požádají. Poté všichni provádějí stejný kód.

• Proveď expanzi

• Pokud ti došla práce žádej o práci

• Zažádej o práci a mezi tím než se to vyřídí kontroluj zprávy

• Pokud ti nikdo práci nedá přejdi do stavu ukončení a čekej na výzvu na předání výsledků

• Zkontroluj zprávy (výsledky, žádosti o práci, žádosti o ukončení

• Poté co přejdou všichni do stavu ukončení požádá proces #0 všechny ostatní o předání výsledků, vybere nejlepší a ten vytiskne. Zároveň všem ostatním předá zprávu po které se programy ukončí.

3.Analýza složitosti

V nejhorším případě musíme projít všechny možné kombinace N bodů, což vede na N! složitost. Díky ořezávání takový nejhorší případ nenastane.

4.Naměřené výsledky

4.1.Sekvenční část

Čas potřebný k vyřešení úlohy roste s rostoucím N opravdu rychle, nicméně záleží na pořadí bodů v zadání. Díky ořezávání můžeme i složitou úlohu vyřešit rychle pokud je zadána vhodná sekvence vstupních bodů.

4.2.Paralelní část

Měřili jsme tři různé instance problémů vždy pro 1, 2, 4, 8 a 12 procesorů a pro propojovací síť typu ethernet a myrinet. Zavedli jsme optimální čas, což je čas za který by podle očekávaní mělo N procesorů úlohu vyřešit (Sekvenční čas/N)

Naměřené časy výpočtu pro první úlohu:

Výsledky jsou v dobré shodě s očekáváním, pro měření v síti ethernet dostáváme křivku, která se blíží teoretickému zrychlení. V případě sítě myrinet výpočty probíhají ještě rychleji a překonávají teoreticky možné zrychlení, pravděpodobně proto, že v síti nejsou tak velké komunikační zpoždění a že se stavový prostor rychleji ořezává než při sekvenčním výpočtu.

Zadání 2:

V tomto případě se rychlost ořezávání projevuje ještě více, protože rychlejšího zrychlení než lineární dosahují obě křivky času výpočtu. Pro určité posloupnosti zadaných bodů se projevuje superlineární zrychlení, které je způsobeno „vhodným“ (náhodným) pořadím zadané posloupnosti bodů. Tento jev je dobře patrný pro 4 uzly.

Zadání 3:

Tento graf vykazuje řadu neshod, některé by mohly být vysvětlitelné jen jako komunikační problémy, nebo jako chyba v programu. Je téměř nemožné aby pro 4 uzly trvala komunikace stejně dlouho jako práce.

5.Závěr

Program se většinou choval podle očekávání. Kopíruje křivku lineárního zrychlení a pro rychlejší komunikační cestu bylo naměřené zrychlení větší.