Jump to content
Forum Kopalni Wiedzy

Recommended Posts

Dwóch naukowców z Northeastern University udowodniło, że aby ułożyć słynną kostkę Rubika, wystarczy wykonać tylko 26 ruchów. Stwierdzenie to dotyczy jakiegokolwiek ustawienia kolorowych pól. To nowy rekord, poprzedni najlepszy wynik to 27 ruchów.

Niektórym zadanie wydaje się banalne, jednak nic bardziej mylnego. Profesor Gene Cooperman podkreśla, że kostka Rubika to pole testowe dla problemów z zakresu wyszukiwania i enumeracji. [...] Są to kwestie zajmujące badaczy parających się wieloma różnymi dziedzinami nauki: od sztucznej inteligencji poczynając, na operacjach kończąc. Kostka Rubika pozwala wypróbować opracowaną metodę na pojedynczym dobrze znanym problemie.

Cooperman i jego student Dan Kunkle zrobili dwie ważne rzeczy, które umożliwiły im ustanowienie rekordu: 1) użyli 7 terabajtów pamięci wirtualnej (dzięki temu mogli w niej przechowywać duże tabele z danymi) oraz 2) opracowali nową, dużo szybszą, metodę wyliczania ruchów i grup ruchów (posłużyli się teorią grup).

Zebrali wszystkie możliwe konfiguracje kostki (tworząc "rodzinę" warstw, ang. family of cosets). Następnie przyglądali się, jaki skutek będzie miało zastosowanie jednego z możliwych ruchów do wszystkich ułożeń jednocześnie. W ciągu sekundy komputer rozpatrywał 100 mln ruchów.

Dokładnie dziesięć lat temu, bo w maju 1997 roku, profesor Richard Korf z Uniwersytetu Kalifornijskiego w Los Angeles ogłosił światu, że odkrył optymalną metodę układania kostki Rubika. Ponieważ w jego badaniach mediana (wartość środkowa) wynosiła 18, uważał, że z każdej konfiguracji kostki Rubika można wybrnąć w nie więcej niż 20 ruchach. Nie potrafił jednak tego dowieść w praktyce i do dziś rekord wynosił 27.

Kunkle wyjaśnił, że Korf napisał program, który długo pracował nad jak najlepszym rozwiązaniem 1 określonej konfiguracji. Natomiast program jego zespołu przeprowadza rozbudowane operacje przedobliczeniowe, a następnie błyskawicznie, w ciągu ok. 1 sekundy, znajduje rozwiązanie dla każdego układu kostki (rozwiązanie obejmuje 26 ruchów lub mniej).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Similar Content

    • By KopalniaWiedzy.pl
      Plastik. Tworzywo XX wieku. Ma wiele zalet: można je odlewać, jest tanie... tanie... Chyba przede wszystkim tanie. Poza tym ma wiele wad: wytwarza się je z coraz droższej ropy naftowej, trudno się go przetwarza, a ogromne ilości plastikowych śmieci zalegają wysypiska. I będą zalegać przez dziesiątki tysięcy lat, jeśli się nie znajdzie na nie sposobu.
      Sposobu na utylizację lub wykorzystanie niebiodegradowalnego plastiku szuka się od dawna. Było wiele koncepcji i pomysłów, ale ostatecznie żadna nie została wykorzystana w masowej skali. Być może wynalazek inżynierów z Uniwersytetu Północno-Zachodniego w Bostonie okaże się przełomem. Udało im się opracować sposób wykorzystania nieprzetwarzalnego plastiku jako paliwa, bez emisji szkodliwych gazów i odpadów. Prototyp specjalnego, dwukomorowego pieca sprawuje się tak dobrze, że myślą już o wykorzystaniu pomysłu w skali przemysłowej.
      Dwukomorowość i samopodtrzymywanie to kluczowe rozwiązania, jakie pozwoliły na opracowanie rozwiązania. Masa plastikowa jest ładowana do górnej komory, gdzie w wysokiej temperaturze poddawana jest procesowi pirolizy. W jej wyniku ze stałych odpadków otrzymywany jest palny gaz, który przetaczany jest do dolnej komory, gdzie - po dodaniu utleniaczy - jest spalany, wytwarzając ciepło i parę. Ciepło podtrzymuje proces pirolizy w górnej komorze, natomiast parę można wykorzystać do otrzymywania elektryczności.
      Projekt jest dziełem studentów inżynierii pracujących nad dyplomem oraz absolwentów, którzy pracowali pod kierunkiem Yiannisa Levendisa, wykładowcy inżynierii materiałowej i przemysłowej. Prof. Levendis poświęcił ostatnie dwadzieścia lat na badania nad spalaniem nieużytecznych odpadów. Jego obecny cel to zgazowywanie stałych odpadów plastikowych, z założeniem jak największego zmniejszenia emisji szkodliwych substancji.
      Prototyp można bez trudu powiększyć i zainstalować na przykład obok wysypiska, czy zakładu segregacji odpadów, albo zakładu przetwarzania odpadów - mówi David Laskowski, jeden ze studentów pracujących nad projektem. - To pozwoliłoby na stały dostęp do taniego paliwa. Według jego obliczeń, nowa technologia pozwoliłaby oszczędzić rocznie nawet 462 miliony galonów ropy w samych Stanach Zjednoczonych, przy założeniu, że spala się całość plastiku, jaki trafia do śmieci.
      Oprócz prof. Yiannisa Levendisa i Davida Laskowskiego do zespołu należeli: Jeff Young, Shane McElroy, Jason Lee i Paul Conroy - studenci przed dyplomem; oraz Brendan Hall i Chuanwei Zhuo - absolwenci uczelni.
    • By KopalniaWiedzy.pl
      Kostka Rubika, jedna z najpopularniejszych zabawek logicznych wszech czasów, wciąż ma swoich wiernych fanów. Niejednokrotnie słyszeliśmy o kolejnych rekordach w szybkości jej układania.
      Tym razem rekord został pobity przez bardzo nietypowego zawodnika. Firma Robot Solutions zbudowała robota, który jest w stanie ułożyć standardową kostkę w ciągu 12 sekund. Urządzenie zostało stworzone za pomocą klocków Lego i nosi nazwę Lego Mindstorms RCX Speedcubing Robot.
       
    • By KopalniaWiedzy.pl
      Dwadzieścia pięć ośmiornic z 23 europejskich akwariów będzie układać kostkę Rubika. Naukowcy nie liczą, oczywiście, że którejś z nich uda się rozwiązać zagadkę, choć może się tak przypadkiem stać. Zamiast tego chcą sprawdzić, czy u zwierząt tych występuje ręczność, a więc czy preferują konkretne ramię lub ramiona po którejś ze stron.
      Poza zabawkami (wymienioną już wyżej kostką, klockami lego i piłką), podczas eksperymentu ośmiornice będą też dostawać pokarm (np. słoiki z dżemem). Zadaniem osób monitorujących jego przebieg będzie oznaczenie wybieranego przez głowonoga ramienia. Co wyjątkowe, ośmiornice mają ponad połowę wszystkich nerwów w ramionach, dlatego wykazano, że częściowo myślą za ich pomocą. Wiele zwierząt preferuje konkretną kończynę i zamierzamy sprawdzić, czy ośmiornice można także dopisać do tej listy – wyjaśnia Claire Little, biolog morski z Weymouth Sea Life Centre.
      Jeśli okaże się, że tak, rzuci to nowe światło na budowę mózgu Octopoda. Ich opiekunowie podkreślają też, iż są to zwierzęta bardzo podatne na stres. Wiedząc, którą stronę wolą, można by więc umilić im życie w niewoli.
      Wzdłuż akwarium wisieć będą diagramy z wizerunkiem ośmiornicy. Jej poszczególne ramiona zostaną oznaczone (prawe: P1, P2, P3, P4, lewe: L1, L2, L3, L4). Obserwując zachowanie głowonogów, odwiedzający będą mogli pomóc naukowcom w badaniach. Gdy zwierzę posłuży się kombinacją ramion, należy oznaczyć sekwencję (do 3 ruchów). Wybrane do projektu ośmiornice należą do różnych gatunków. Wśród nich znalazły się, m.in.: ośmiornice pacyficzne (Octopus dofleini) i ośmiornice pospolite (Octopus vulgaris).
      Wyniki najnowszego eksperymentu, który potrwa miesiąc, zostaną przez biologów przeanalizowane, a na wnioski trzeba będzie poczekać do jesieni.
    • By KopalniaWiedzy.pl
      Dan Krunkle i Gene Cooperman, informatycy z Northeastern University w Bostonie, udowodnili, że kostkę Rubika można ułożyć w 26 ruchach. Niezależnie od tego jak bardzo przemieszane będą kolory.
      Kunkle i Cooperman użyli superkomputera do rozwiązania zagadki kostki. Wcześniej musieli jednak dokonać pewnych uproszczeń, gdyż istnieją 43 tryliony (43 000 000 000 000 000 000) możliwych kombinacji, a to zbyt dużo nawet dla superkomputera.
      Uczeni najpierw zmniejszyli liczbę kombinacji sprawdzając, które z nich są sobie równoważne. Następnie zidentyfikowali 15 000 możliwych ustawień, które można rozwiązać w mniej niż 14 „półobrotów” kostki. Potem opracowali metodę na pogrupowanie każdej z możliwych konfiguracji i przypisanie ich do odpowiednich klas o podobnych właściwościach.
      W ten sposób dowiedzieli się, że kostkę można ułożyć w 29 ruchach. To jednak nie wystarczyło, gdyż uczeni chcieli pobić rekord wynoszący 27 ruchów. Aby zmniejszyć liczbę kombinacji odrzucili takie, o których już było wiadomo, że można je rozwiązać w 26 lub mniej ruchach. W ten sposób zostało im 80 milionów kombinacji kostki. Ich analizą zajął się superkomputer. Okazało się, że i one mogą zostać rozwiązane w co najwyżej 26 ruchach.
      Okazuje się jednak, że to jednak nie koniec prób pobicia rekordu. Większość matematyków uważa bowiem, że kostkę można ułożyć w 20 ruchach. Pozostaje jedynie przeprowadzić odpowiedni dowód.
×
×
  • Create New...