Archiv článků: problém obchodního cestujícího

Jedna z verzí známé úlohy obchodního cestujícího. Jak propojit několik měst sítí silnic tak, aby byla jejich délka co nejkratší? Pro ilustraci obtížnosti této úlohy se podívejme na „snadný“ případ, kdy máme propojit pouhá čtyři města A, B, C, D, která navíc šťastnou náhodou leží ve vrcholech čtverce o straně …

Autorovi jsme položili několik otázek týkajících se toho, nakolik má řešení úlohy obchodního cestujícího pomocí lineárního programování vztah problému P vs. NP, v současnosti jednomu z hlavních otevřených matematických problémů. Clayův matematický ústav za jejich řešení nabízí milion dolarů. Nejprve tisková zpráva Matematicko-fyzikální fakulty UK Na Matfyz putuje jedno z …

DNA počítače jsou s námi už skoro 25 let. Úvodní demonstrace jejich síly při řešení problému obchodního cestujícího působila nadějně, následovala implementace problému splnitelnosti (satisfiability), pak se však vývoj zadrhl. Některé průvodní překážky, které se překonat v podstatě nikdy nepodařilo, popisuje např. i v češtině vydaná kniha Martyna Amose Na …