Lepsi sw na navrh DPS

[Ladislav Vaiz]

100% výsledek znamená vyzkoušet všechny možnosti a to má neuvěřitelnou 
výpočetní složitost. V praxi to znamená, že s mírně se zvyšujícím počtem 
prvků velice rychle (exponenciála, faktoriál) roste potřebný čas. Kolem 
10-20 prvků už to může být v "rozumném čase" neřešitelné. Zajímají-li 
vás detaily, hledejte informace o NP-úplných problémech.
La'd"a

P.S. dokazovat, že tato úloha je NPC, po mě nechtějte, ale domnívám se, 
že ano


Petr King wrote:

>Prihodim taky jeden dotaz za mne - existuje autorouter, ktery je schopen 
>si sam rozvrhnout umisteni soucastek tak, aby dosahl 100% vysledku ? 
>Kriticke soucastky si zablokuji (konektory, displeje, zdroj..) a 
>autorouter se o vse postara?
>Navrhuji predevsim jednostranne spoje a nekdy je docela problem 
>rozvrhnout spoj tak, aby nebyl plny propojek, pri dnesnim vypocetnim 
>vykonu bych ocekaval, ze si autorouter poradi i s polohou soucastek a 
>usetri tak spoustu casu.
>
>P
>