Brīnišķīgas figūriņas
Leģendāro Tetris pagājušā gadsimta 80. gados radīja Aleksejs Pajitnovs. Matemātiķis
Pajitnovs izlaida vienu no pirmajām spēles versijām padomju mikrodatorā "Electronics-60"
Tetris mērķis ir pārvietoties un pagriezt krītotģeometriskas formas, lai spēles laukuma apakšā izveidotu pilnīgas rindas, gūstot punktus. No praktiskā viedokļa šī ir reakcijas ātruma un koncentrēšanās spēle, taču matemātiķi uz to raugās no cita leņķa. Zinātnieki analizēja Tetris algoritma skaitļošanas sarežģītību un noteica, ka tas pieder NP-pilnīga klasei - nedeterministisks polinoms; šādām lietām nav efektīvu risinājumu algoritmu.
Galvenā problēma ir tā, ka daudzumsrisinājuma atrašanai aprēķins pieaug eksponenciāli, palielinoties mainīgo skaitam (problēmas lielums). Piemēram, ja ir četri parametri, tad ir nepieciešamas 16 iterācijas, un, ja 100, tad 2 ^ 100, kas ir vairāk nekā atomi Visumā (!). Tipisks dators, ja tas ir pareizi noregulēts, var veikt vairākus miljardus šo iterāciju sekundē. Attiecīgi viņš var viegli atrisināt nelielas NP problēmas, uzskaitot, un, kad mainīgie kļūst ievērojami lielāki par 15, viņš pārtrauks risināt.
Kas attiecas uz Tetris.Klasiskās spēles uzdevuma lielums ir mazs: atsevišķā solī stiklā (spēles laukā) ir aktuāla ainava - tas ir parametrs, tas būtiski neietekmē aprēķinu apjomu. Ir informācija par pašreizējo un nākamo figūru - tās ir divas mainīgo grupas: katrai figūrai ir ne vairāk kā četras (lai gan kvadrātam - tikai viena) orientācijas telpā un ne vairāk kā 10 "nosēšanās" koordinātas. figūras. Katram gājienam ir 40 štati, diviem ir 1600, vairāk informācijas nav, tā ir neliela NP problēma. Lai gan Tetris var būt sarežģīts: palieliniet šūnu skaitu līdz 100 un pārliecinieties, ka spēlētājs zina ne tikai to, kāds būs nākamais skaitlis, bet arī simts nākamo, tad būtu problēmas.
Jūs arī nezināt citas NP pilnīgas spēlesno dzirdēm: mīnu meklētājs, sudoku, tags un pat nekomerciāla Super Mario versija. Neskatoties uz to noteikumu vienkāršību, noteiktos apstākļos to izmērs palielinās, dators nevar piedāvāt ideālu risinājumu. Kāpēc matemātiķiem tas rūp? Jo labākā maršruta izvēle, procesa vai grafika optimizēšana arī ir NP klases problēmas.
Klasiskais "Mario" izskatījās šādi
Loģiskās spēles ir ārkārtīgi ērta testēšanas vietatestēšanas algoritmi un to programmatūras ieviešana. Puzles visbiežāk ir “tīras”, bez dažāda veida izņēmumiem noteikumos, kas ir raksturīgi praktiskām problēmām. Šādu problēmu stāvokļu telpai ir regulējama dimensija, un, mērogojot, rekvizīti nemainās (piemēram, tagi 2x2, 4x4, 3x6). Visi stāvokļi ir aprakstīti vienādi. Arī mīklu matemātiskais apraksts, kā likums, nav tik sarežģīts kā dzīves problēmu apraksts.
"Kvantu" rotaļlietu laiks
Tā pati problēma ar mugursomu (kā ievietot vairāk lietuierobežotā telpā) diezgan atgādina Tetris spēli, un efektīvais rezultāts noderēs loģistikas uzņēmumiem, jo ļaus izvairīties no resursu izšķērdēšanas. Ja kādai no šīm problēmām vai spēlēm tiek atrasts “polinomi ātrs” algoritms, tad tikpat “ātri” var atrisināt jebkuru citu NP klases problēmu. Teorētiski kvantu datori tam palīdzēs, taču pagaidām ir tikai šo nākotnes datoru prototipi. 2018. gadā pat tika izgudrots jauns jēdziens, lai aprakstītu pašreizējo kvantu procesoru ražošanas stāvokli – NISQ laikmetu (trokšņains vidēja mēroga kvantu laikmets) jeb subkvantu tehnoloģiju laiku.
Kamēr zinātnieki strādā, lai uzlabotu kvantuprocesus, uzņēmumu vadītāji meklē mūsdienīgus analogus, kas palīdz optimizēt ražošanas darbu. Šāds "aizstājējs" ir kļuvis par kvantu iedvesmotiem algoritmiem, kas atrod 95–99% optimālu risinājumu parastajos datoros. Krievijā QuSolve to dara - uzdevumi, ar kuriem uzņēmums strādā, pieder pie NP klases, un matemātiķi izstrādā un pilnveido biznesa problēmu risināšanas algoritmus. Programmā QuSolve, lai pārbaudītu savu risinātāju (risinātāju), viņi izmantoja tagus, kas palīdzēja atrast pāris kļūdas algoritmā un veikt papildinājumus programmatūras pakotnes saskarnē.
Vai tiešām mūsdienu zinātnieki nedara neko citu kā vienVai domājat, kā visu uzlabot un optimizēt? Protams, ka nē. Brīvajā laikā viņi turpina izdomāt spēles. Izstrādātāji jau ir spējuši pārvērst lielāko daļu spēļu par NP, pievienojot nelielu kvantu fizisko parādību burvību.
Tā pēdējo 10 gadu laikā ir parādījušās kvantu tehnoloģijas.dambrete, kvantu jūras kaujas un kvantu tic-tac-toe. Īpašu popularitāti ir ieguvis kvantu šahs, kurā pat notiek turnīri, un čempionam tiek piešķirts lielmeistara tituls. Lielākā daļa jauno "kvantu spēļu" ir veidotas pēc kvantu mehānikas pamatprincipa - superpozīcijas.
Piemēram, šaha figūriņas var būt iekšāvairākas vietas uz galda vienlaicīgi, kas nozīmē, ka ir grūtāk aizsargāties un uzbrukt - tas padara spēli neparedzamu un iespaidīgu. 2016. gadā viņi pat filmēja īsfilmu, kurā tika demonstrēta kvantu šaha spēle starp Stīvenu Hokingu un Polu Radu, aktieri, kurš pazīstams ar savu Skudrcilvēka lomu filmā Marvel Cinematic Universe.
Spēles ekrānuzņēmums. Šādi izskatījās tiešsaistes dēlis spēlē starp Hokingu un Rūdu. Tad aktieris pārspēja leģendāro fiziķi
Mēs nezinām, vai šīs spēles būs tādas nākotnētikpat ikdienišķi kā parasts tic-tac-toe, tetris un tag, taču tie noteikti iedvesmos matemātiķus izveidot unikālus algoritmus praktisku biznesa problēmu risināšanai un tehnoloģiju attīstībai. Par to nav šaubu.
Lasīt vairāk:
Zinātnieki atklājuši, ka Piena ceļa forma nepavisam nav tāda, kādu mēs visu laiku domājām
Dzīvojamās zonas malā atrastas divas superzemes: vienai no tām ir komfortabla temperatūra
Atrasts melnais caurums, kas iznīcina zvaigžņu rekordu tuvu Zemei