#fyz #tech #math #hplus Oblíbený problém pro testování efektivity různých algoritmů představují pozice na velkých šachovnicích; jedná se totiž o typ úloh, kdy výpočetní složitost roste s velikostí šachovnice obvykle exponenciálně. Problém se řeší prohledáváním stavového prostoru (backtracking). V problému šachových dam máme za úkol umístit na šachovnici určitý počet dam tak, aby se vzájemně nenapadaly. Na klasické šachovnici může být dam logicky maximálně 8 (ani věží by se sem nedalo postavit víc), a ty zde lze umístit 92 způsoby. Základních pozic je 12, další získáme jejich symetriemi (1 z nich nemá 8 symetrií, proto celkový počet není 96, ale 8 x 11 + 4). Kolika způsoby lze postavit N dam na šachovnici N x N? Obecný vzorce nikdo nenašel, na šachovnici 25 x 25 jde o více než 2 miliardy pozic a nebylo vůbec lehké se k tomu výsledku dopočítat hrubou silou. Navíc si úlohu můžeme různě upravovat, třeba zakázat umístění dámy na určité diagonále, nebo na šachovnici již určitý počet dam postavit předem. S trochou práce lze najít úlohy, kdy už ve verzi 21 x 21 nedokážeme vyřešit v rozumném čase. Vědci z University of Innsbruck nyní uvádějí, že právě na tomto problému se dá dobře demonstrovat nadřazenost kvantového počítače (quantum supremacy) nad počítači klasickými.
URL:
https://sciencemag.cz/kvantove-pocitace-a-problem-sachovych-dam/
FB:
https://www.facebook.com/1733809140199804/posts/2362495263997852
Žádné komentáře:
Okomentovat