ГоловнаНаукаВсі новини розділу
 

Знайдено мінімальне число ходів для вирішення кубика Рубіка

Корреспондент.net, 17 серпня 2007, 02:18
0
6

Денієл Кункле і Жене Куперман з Північно-східного університету Бостона створили комп'ютерну програму, яка за 63 години роботи знайшла мінімальне число ходів, яких завжди буде досить для збірки кубика Рубіка з будь-якого початкового положення.

Учені повідомляють, що загальне число можливих комбінацій у кубика Рубіка складає 43 квінтиліони (мільярда мільярдів), тому знайти оптимальне рішення - це дуже непросте завдання. Проте фахівці університету Бостона придумали спеціальний алгоритм, який дозволив їм впритул підступитися до знаходження числа Бога (God"s Number), - так називається найменше число ходів за яких, в принципі, можлива збірка кубика з абсолютно будь-якого початкового положення.

Кункле і Куперман запрограмували комп'ютер на пошук найкоротшого рішення для однієї з 15 тисяч якихось проміжних позицій, вказавши при цьому розумне число кроків, за яке можна зібрати кубик.

З'ясувалося, що з будь-якої вихідної позиції кубика його можна зібрати максимум за 29 ходів. При цьому більшість вихідних позицій запросили всього 26, а іноді і менше, ходів для свого вирішення. Тому учені зосередили свою увагу на декількох позиціях, вирішення яких вимагало 27-29 ходів.

Виявилось, що навіть найважчі позиції можна вирішити за 26 ходів або швидше. Внаслідок чого учені зробили висновок, що число Бога, кінець кінцем, складе близько 20 ходів.

За матеріалами Мембрана

Якщо ви помітили помилку, виділіть необхідний текст і натисніть Ctrl + Enter, щоб повідомити про це редакцію.
powered by lun.ua

ЧИТАЙТЕ ТАКОЖ

Loading...

Корреспондент.net в соцмережах