Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m33pal:uloha1-2014 [2014/10/15 17:03]
roziana
+++ courses:a4m33pal:uloha1-2014 [2025/01/03 18:28] (aktuální)
@@ Řádek 12: / Řádek 12: @@
   * Doporuceni: je lepsi pocitat uz vsechny mozne hrany (NxN) a vsechna mozna krizeni a ukladat to nekam, napriklad do pole a pak jen precist obsah pole v pripade potreby. Program bude o dost rychly diky tomu.
+===== Jak na to 1 =====
+Zadání úlohy směřuje na hledání hamiltonovské kružnice v úplném grafu, tak, aby výsledný graf byl planární a zároveň cesta splňovala určité paramatry, např. maximální délka cesty. Stavový prostor pro tuto úlohu tvoří permutace všech uzlů. Tento prostor lze procházet trochu modifikovaným rekurzivním DFS (uzel z něhož se nelze již nikam dostat nezůstává CLOSED, ale vrátí se do stavu FRESH). Následující příklad je uveden pro 5 uzlů s indexy 0..4.
+Na začátku začneme např. s uzlem na indexu 0. Jelikož se jedná o úplný graf, následníci každého uzlu jsou všechny ostatní uzly. Výsledné permutace z ostatních uzlů budou:
+1 2 3 4  (lépe uvidíte, pokud si je zakreslíte do grafu, kde kořenem je prvek 0):
+- - - 4 3
+- - 3-2-4
+..
+..
+4 3 2 1
+Tento strom tedy tvoří stavový prostor prohledávání. Počet listů je bohužel roven (n - 1)!, proto bude nutné tento prostor ořezat (neprocházet již další hladiny) na základě podmínek ze zadání plus využít některé vlastnosti permutací.
+Ořezávací podmínky ze zadání:
+  * délka cesty do následujícího uzlu nesmí přesáhnout hodnotu ze zadání
+  * úsečka mezi aktuálním a případným následníkem nesmí křížit již "nakresléné" úsečky.
+Z těchto podmínek plyne, že alespoň u druhé podmínky si musíme pamatovat uzly v aktuální cestě pro kontrolu křížení. Aktuální vzdálenost lze předávat např. jako parametr do rekurzivního volání.
+Ořezávací podmínky z vlastnosti permutace:
+  * Cílem je vytvořit kružnici. Tedy kružnice 0 4 3 2 1 je stejná jako 0 1 2 3 4. Na stromě stavového prostoru zjistíte, že všechny podstromy z 0 4 x x x již byly jednou projity. Lze tedy oříznout větev (vynechat jako souseda) s nejvyšším číslem uzlu vycházejícím z kořene (v našem případě z uzlu 0). !Pozor, souseda nesmíte vynechávat všude (hladina > 1), pouze pokud jde z kořene.
+  * Když už procházíte některou větev v hloubce např. 2, tedy jste 0 1 2 <--- zde a chystáte se navštívit souseda č. 3, proč rovnou nezkontrolovat kružnici 0 1 2 0, dále pak 0 1 2 3 0, atd. Jedním průchodem zjistíte různé vzdálenosti pro vrchol 0. I zde platí podobné vlastnosti permutace jako v případě a) (viz váš strom). Pro start hledání kružnice např. postačí jednoduchá podmínka, že historie_cesty[hladina 1]  < číslo_aktuálního_uzlu, jinak jde opět o cestu již projitou.
+Pokud projdete statovýv prostor pro např. všech 5-ti prvků a zjistíte, že takováto cesta neexistuje, lze využít obdobného postupu pro uzel 1 jako kořen s tím, že uzel 0 bude pro vás již uzavřený a nebudete ho brát v potaz. Následně pro 2, 3, ... atd, až do doby, kdy vám zbydou alespoň 3 uzly (nutné pro vytvoření kružnice).
+====== Doporučení ======
+  * Předpočítat vzdáleností pro všechny kombinace bodů, např. float vzdálenosti[počet uzlů][počet uzlů].
+  * Předpočítat křížení pro všechny kombinace bodů, např. bool křížení[počet uzlů][počet uzlů][počet uzlů][počet uzlů] a posléze se dotazovat, jestli se kříží úsečka s uzly 0,1 a úsečka 2,3 tak, že true == křížení[0][1][2][3]?
+  * Omezit volání method, funkcí, podprocedur a raději vše vypočítávát v rekurzivní funkci. Ačkoliv by to mohl kompilátor zjistit, nevím, zda jsou zapnuté optimalizace při překladu.
+  * Ukládat pouze minimální délku cestu pro danou hladinu. Informace jaký byl kořen, či uzly v cestě není relevantní.

courses/a4m33pal/uloha1-2014.1413385380.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru