Davson: Tohle má do obchodního cestujícího hodně daleko, protože je to uniformní po celé délce.
Trivialni, ale ruzne pro D<2 a D>2.
To zcela jistě ano (znám), já spíš přemýšlím o tom, že když je "graf" zadán jednoznačně pouhými třemi parametry, zda nebude nějaké rychlejší řešení, než NP úplné. Pro P=2 a L=2 je řešení triviální, stejně tak jako pro P a L hodně velká (po jedné straně tam, po druhé straně zpátky a pak ještě znovu na druhý konec), otázkou je, jak to bude vypadat mezi tím, s rozumným počtem domů.
To bude nějaká variace problému obchodního cestujícího, ne? http://en.wikipedia.org/wiki/Travelling_salesman_problem