Reseni pres DFS:

• projit kazdy uzel a s kazdym zavolat DFS

• v kazdem kroku DFS udelat nasledujici

• z aktualniho vrcholu projit vsechny permutace obsahujici tento vrchol a u kazde pocitat celkouvou cestu a kontrolovat zda nevzniklo krizeni nebo cesta neprekroci D. Pokud je cesta OK, zavolat rekurzi s dalsim bodem, ktery nebyl jeste navstiveny.

• pamatovat si vzdy lepsi cestu v kazdem kroku

• 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.

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:

0 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

..

..

0 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).

• 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í.