Автор Тема: А сколько методов знаете вы для сборки Кубика 3х3х3?  (Прочитано 20814 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн sm

  • Постоялец
  • ***
  • Сообщений: 226
  • Пол: Мужской
Всем привет!

Решил освежить память и вспомнить все основные методы для сборки 3х3х3, которые я знаю и использую.

Методы буду описывать в той последовательности, в которых я их изучал.

Обычно в качестве первого слоя я использую белый, в качестве последнего слоя желтый. В описании я буду придерживаться этого.

Метод 1 – схема идущая с кубиками Рубикс
Это первый метод изученный мною.
Последовательность:
  • Сборка 2-х слоев;
  • Перестановка угловых элементов – здесь я придумал свой способ, который позволяет переставить либо 2 угла стоящих рядом, либо 2 угла стоящих по диагонали;
  • Ориентация угловых элементов (переворот желтым вверх) используя алгоритм Sune;
  • Сборка желтых ребер (перестановка и ориентация) при помощи алгоритмов сальто влево (и его обратный вариант) и сальто вправо.
Схема сборки последнего слоя: https://vk.com/doc185254069_158533131
Здесь дополнительно вариант для диагональной перестановки углов: https://vk.com/doc185254069_229875947

Здесь на этапах 2 и 3 используются так сказать "грязные" алгоритмы, которые дополнительно меняют положение/ориентацию желтых ребер. Но из-за того, что на этапе 2 и 3 нас не заботит расположение желтых ребер, углы можно собирать достаточно быстро.

Метод 2 – сборка последнего слоя коммутаторами (трициклами)
Узнал о нем анализируя запись сборки в программе KubRub (увы, сайт программы сейчас кажется, не существует).
Последовательность:
  • Сборка 2-х слоев;
  • Сборка коммутаторами 4-х желтых ребер – по сути это алгоритмы "сальто влево" и его обратный вариант;
  • Сборка коммутаторами 4-х желтых углов – можно сказать здесь задействован тот же самый алгоритм, что использовался на этапе 2.
Схема сборки последнего слоя: https://vk.com/doc185254069_158281959

Т.к. в данном методе используются чистые трициклы, то последовательность этапов 2 и3 можно менять. Здесь удобно то, что нужно знать всего только 2 алгоритма и их обратные варианты (т.к. это чистые трициклы, то обратный вариант здесь можно получить так же если выполнить 2 раза основной алгоритм).

Метод 3 – сборка последнего слоя четверками [X, Y, X', Y']
Об этом методе я узнал по видео Дмитрия Зайцева, так же четверки используются в видео Романа Байбусинова (для ориентации желтых углов).
Последовательность:
  • Сборка 2-х слоев;
  • Ориентация желтых ребер – это можно легко сделать интуитивно (принцип примерно следующий загоняем реберный элемент через одну грань в слот неправильной стороной, а выгоняем через другую грань желтой стороной вверх);
  • Перестановка желтых ребер (сборка желтого креста) – применяется Sune-алгоритм;
  • Сборка углов четверками [X, Y, X', Y'] (перестановка и ориентация) – желтый крест собранный ранее выступает в качестве ориентиров.
Из-за легкости 2-4 этапов этот метод я использую для сборки мегаминкса и многих модификаций кубика 3х3х3 (сердце, пираморфикс, кирпич и т.п.). Так же это основной метод, по которому я учу других собирать Кубик Рубика.

Метод 4 – сборка последнего слоя тройками
Наконец-то я изобрел свой метод сборки!
На идею подтолкнул алгоритм перестановки 3-х желтых углов, о котором я узнал из видео Романа Байбусинова. Проанализировав данный алгоритм я получил свой алгоритм для этой цели – минимальную единицу алгоритма я назвал тройкой. Эти тройки применяются для перестановки и одновременной ориентации трех желтых углов.
Последовательность:
  • Сборка 2-х слоев;
  • Ориентация желтых ребер – как в методе 3;
  • Перестановка желтых ребер (сборка желтого креста) – как в методе 3;
  • При помощи троек ставим правильно первый угол на свое место;
  • При помощи установочных ходов и троек ставим правильно оставшиеся 3 угла на свои места. Здесь позже я вывел свои алгоритмы для переворота углов стоящих на своих местах.
Отдельная тема: http://twistypuzzles.ru/forum/index.php/topic,318.0.html

Т.к. тройки при длительном использовании становятся интуитивно понятными, я так же использую этот способ для сборки последнего слоя мегаминкса.

Метод 5 – сэндвич
Этот метод получился в результате моих экспериментов, официальное название "Сэндвич".
Последовательность:
  • Сборка белых углов;
  • Сборка желтых углов – используя все знания полученные ранее;
  • Собираем попарно белые и желтые ребра – интуитивно. В результате получим 2 собранных противоположенных слоя;
  • Сборка центрального пояса. Беру пояс вертикально (центры на местах). Пояс на +90°(вверх); Шапка на 180°; Пояс на -90°; Шапка на 180°; (формула: M' U2 M U2). Повторяя эти действия, ставлю все ребра на места;
  • Если 2 ребра встали перевернуто, то собираю их, а после ставлю 3 смещенных ребра в одну линию и переставляю по схеме 2 (они собираются). Полный алгоритм для переворота получается примерно такой - M U M' U' M U M U M2 U x (M' U2 M U2) B. Если нужно перевернуть 4 ребра пояса, то повторяю это действие 2 раза.
Алгоритмы сборки для шагов 3-5 вывел в результате экспериментов самостоятельно.

Метод 6 – метод Морозова
Метод изучение, которого далось самым сложным, т.к. нужно было поломать много стериотипов.
Последовательность:
  • Переворот белых и желтых углов в противоположенные стороны (белый и желтый цвет считаем пока за один);
  • Полная сборка углов;
  • Сборка 4-х столбиков – ставим на места ребра не содержащие белый и желтые цвета;
  • Переворот белых и желтых ребер в противоположенные стороны, соблюдаем допустимое расположение центров;
  • Сборка всех ребер;
  • Перестановка центров.

Отдельная тема: http://twistypuzzles.ru/forum/index.php/topic,308.0.html

Только после изучения этого метода я стал видеть куб в целом. Для этого метода я написал подробную инструкцию со схемами для каждого этапа.
На мой взгляд, это самый интуитивный метод, существующий на данный момент, но чтобы понять его в целом, возможно, придется приложить немало усилий.

Метод 7 – сначала ребра
Собрать данным способом я решил после тем опубликованных Евгением Бенеком (он же Леннон).
Последовательность:
  • Собираем все ребра – сейчас я могу сделать это интуитивно, не придерживаясь, каких либо без правил;
  • Переставляем и ориентируем углы, используя подстановки прямые и обратные движения.
Отдельная тема: http://twistypuzzles.ru/forum/index.php/topic,588.0.html

Т.к. я имею немалый опыт, то данный метод для себя я так же могу назвать интуитивным.

Метод 8 – Roux
Последовательность:
  • Сборка 2-х противоположенных блоков 2х2х3 – интуитивно;
  • CMLL - сборка желтых углов в 2 шага (ориентация и пермутация) – это то, что мне не нравится в данном методе, собрать 4 угла и при этом, не разрушив 2 собранных блока 2х2х3, без знания формул очень сложно;
  • LSE - сборка оставшихся ребер – здесь можно использовать схемы из метода Морозова.
Инструкция по Roux для начинающих: http://speedcubing.ru/forum/index.php?topic=944.0
Мои схемы для этапов CMLL и LSE: http://twistypuzzles.ru/forum/index.php/topic,607.0.html

Все бы хорошо, но шаг 2 очень усложняет метод, хотя его можно сделать, используя методы 1-4.
По моему мнению данный метод больше предназначен для спидкуберов, по этому оптимально собирать им можно только изучая формулы для этапа CMLL.

Метод 9 – Heice
Последовательность:
  • Сборка 4-х блоков 2х2 (3 внешних и 1 внутренний) – интуитивно;
  • Правильная расстановка блоков с одновременной ориентацией ребер – в итоге получим 2 собранных слоя без одного слота, плюс 5 ориентированных ребер. Делается интуитивно, но нужна должная сноровка;
  • Сборка желтого креста – интуитивно, так же при должной сноровке;
  • Сборка оставшихся 5 углов – применяю тройки из методов 4 и 7.
Инструкция от автора метода (на англ.): http://www.ryanheise.com/cube/heise_method.html
Моя схема для перестановки ребер: http://twistypuzzles.ru/forum/index.php/topic,617.0.html

Достаточно интересный и понятный метод (но скорее всего для опытных сборщиков). Этим методом у меня сейчас, получается, собирать наиболее оптимально по количеству ходов – верхняя планка 65 ходов, рекорд 45 ходов (но пока это больше при везении).

Еще я изучал метод Петруса (http://lar5.com/cube/), но он после Heice как-то не прижился у меня, по этому я им практически не собираю и не стал включать в список методов, которые я знаю.

А сколько методов применяете для сборки 3х3х3 вы? Поделитесь своим опытом и впечатлениями.
« Последнее редактирование: 16 Октября 2014, 07:39:54 от sm »

Оффлайн pytlivyj

  • Постоялец
  • ***
  • Сообщений: 214
  • Пол: Мужской
Ещё методы:

1) Собрать 1-ю сторону, затем 2-ю, 3-ю, 4-ю, и 5-ю с 6-й в любой последовательности и ориентации на кубе;

2) Собирать как сиамский кубик, например, если полностью "заморозить" на нём любой собранный сначала цельный элемент размером 1х1х2, 1х1х3 (ребро), 1х2х2 или 1х2х3 - на выбор.
Маленький недостаток метода. Т. к. куб изначально был перемешан не как сиамский, то при сборке с "замороженными" цельными элементами 1х1х3 (ребро) или 1х2х3 в 50% случаев возникает ситуация, когда дополнительно необходимо применить алгоритм 3-цикла угловых элементов. Это происходит из-за того, что куб при этих вариантах сборки имеет степени свободы вращения слоёв, параллельные 2-м плоскостям, а любой алгоритм 3-цикла угловых выполняется при условии наличия степеней свободы вращения слоёв, параллельных всем 3-м плоскостям;

3) Поштучная сборка кубиками с помощью универсальной формулы 3-цикла;

4) Сборка от угла к противоположному диагональному углу (спирально или параллельно);

5) Кубоидная сборка - собираем в любой последовательности элементов между собой два противоположных слоя, потом переставляем эти элементы на свои места исключительно алгоритмами кубоида: боковые грани вращаем только на 180 градусов, а горизонтальные слои на +90, -90 или на 180 градусов. Аналогично алгоритмами кубоида собираем оставшиеся элементы среднего слоя.
Маленький недостаток метода. Т. к. куб изначально был перемешан не как кубоид, то при сборке среднего слоя в 50% случаев возникает необходимость дополнительно применить алгоритм разворота 2-х рёберных элементов, а при 25% - алгоритм разворота всех 4-х рёберных элементов;

6) Сборка из перемешанного состояния заведомо известного симметричного узора на кубе (например, шахматного кубика, мезона, ромбов, крестов и т. д.), затем сборка в целый кубик по короткому алгоритму узора;

7) Самая интересная сборка (!!!). На уже перемешанном кубе хаотично разворачиваем все элементы так, чтобы на противоположных гранях куба присутствовали только элементы этих двух граней (т.е. 3 раза попарных "перемесов" элементов противоположных граней). Теперь попробуйте собрать куб, вращая любой слой только на 180 градусов!
Маленький недостаток метода. Т. к. куб изначально был перемешан не вращением всех слоёв на 180 градусов, то в конце сборки в 50% случаев возникает ситуация, когда дополнительно необходимо применить алгоритм 3-цикла угловых или рёберных элементов.

P. S. Несмотря на небольшие несовершенства методов сборки №№ 2, 5 и 7, они тоже являются весьма интересными, т.к. дают "логическую пищу" нашему уму, так постоянно необходимую настоящему головоломщику;)
« Последнее редактирование: 25 Октября 2014, 11:56:39 от pytlivyj »

Оффлайн Леннон

  • Ветеран
  • *****
  • Сообщений: 1 305
  • Пол: Мужской
  • Спящий.
Попробовал сосчитать.

Основных методов четыре:

1. "Рёбра-уголки" - самый первый метод.
2. "уголки-рёбра" (уголки-рёбра-центра, если точнее) - идея метода принадлежит В.Морозову.
3. Пояс-метод. (начало со сборки пояса, дальнейшие стадии переменные, может быть похож на HTA-метод).
4. Начиная с двух противоположных сторон. (ещё более переменная схема сборки, в чём-то также может быть похож на HTA).

Эти четыре метода, относительно просты и универсальны.
Они иногда подходят для сборки других головоломок, мало нуждаются в сложных алгоритмах, и даже наоборот - могут служить источниками, для их синтеза.

Иногда применялись другие методы.

5. Сборка блоками. - 13 частей из 20 собираются интуитивно, остаётся "дорожка" не собранных 7 частей в виде буквы Т или Z. Дальше можно попытаться разрулить коммутаторами.
Метод в чём-то удобный, постепенно переходящий в разряд основных  :)

6. HTA-метод - последнее приобретение  :)
https://www.speedsolving.com/wiki/index.php/Human_Thistlethwaite
http://www.ryanheise.com/cube/human_thistlethwaite_algorithm.html
Самой трудной для понимания, была G1-стадия (она во многом похожа на EO-line, из ZZ-метода), остальные в целом уже были известны и понятны.
Сейчас этот метод выдаёт наименьшее число ходов - до 52х пока конечно не дотягиваю  :) но вот за 54 хода в среднем, складывать получается, ещё как.

7. Хаотичная сборка частей (как хочу так и собираю!) - например, сначала поставим на место это ребро, потом тот угол и т.д. Чёткая схема тут практически отсутствует.
Правда в конце, всё сводится к некоторым известным позициям (три переставленных ребра или угла, два развернутых ребра или угла, три развернутых уголка, два переставленных ребра + 2 угла).
Не знаю, насколько это можно назвать методом, но вещь прикольная. Заставляет порой сильно задуматься.

(сборку одной формулой рассматривать не нужно, поскольку она будет совпадать с тем или иным методом по схеме)

В настоящее время практически не применяемые методы:

8. "8355" - "гибрид" рёбер-уголков, и послойного метода. Одно время использовал для более быстрой сборки.

9. Послойный метод. Это стараюсь избегать всеми правдами и неправдами.

10. CFOP - Ранее этот метод использовал. Да, он удобный и быстрый. Но сильно нуждается в алгоритмах - это и 21 PLL, и 57 OLL, и некоторые F2L - удержать всё это в голове, редко применяя, довольно трудно. Формулы постепенно "теряются"  :(
Вот и получается в итоге, что почти два года назад, пользоваться этим методом получалось, а вот сейчас - уже нет.

11. Roux, ZZ, Petrus - идея этих методов в целом понятна, но поскольку тут также необходимо знать массу алгоритмов, использовать их проблематично.

(ZB и "треугольник Франциско" - есть и такие методы. Первый слишком перегружен формулами, у второго причудливая схема сборки).

12. Heise-метод - пока под вопросом.
F R U L D * 252

Онлайн Philipp

  • Администратор
  • *****
  • Сообщений: 2 361
  • Пол: Мужской
  • С Администратором лучше не спорить.
Какой метод позволяет решить наименьшим количеством ходов?

Как решает компьютер? То есть когда идёт проверка на наименьшее количество ходов? Простой перебор всех состояний из исходного? Не много получится? Может есть алгоритм оптимизации какой-нибудь? Программу ведь человек написал. Может ли мозг человека приблизиться к подобному анализу в разумное время?

Оффлайн SergR

  • Постоялец
  • ***
  • Сообщений: 135
  • Пол: Мужской
  • Ростовская обл., г.Красный Сулин
    • Нешарнирные головоломки
Какой метод позволяет решить наименьшим количеством ходов?

Как решает компьютер? То есть когда идёт проверка на наименьшее количество ходов? Простой перебор всех состояний из исходного? Не много получится? Может есть алгоритм оптимизации какой-нибудь? Программу ведь человек написал. Может ли мозг человека приблизиться к подобному анализу в разумное время?
Я поднимал эту тему http://twistypuzzles.ru/forum/index.php/topic,585.0.html. Интерес проявлял больше к сдвигашкам, но попадались и темы про кубик Рубика. Принцип вкратце такой - из какого-то состояния строится дерево всех возможных состояний. Ну например:
  • U
  • U-1
  • B
  • B-1
  • ...
  • R
  • R-1
Затем из этих положений строятся свои положения и т.д. Вот приблизительно так (на примере сдвигашек 3*3)

Применяется два типа алгоритмов - информативный и неинформативный. Второй применять - жизни не хватит, вычислительных возможностей и памяти вычислительной техники (практически полный перебор всех состояний, пока не найдется решение, при том оно будет кратчайшим). Информативный позволяет быстрее найти решение, но возникает одно препятствие - правильно подобранная эвристическая функция. Эвристика - функция, позволяющая определить наиболее вероятный путь к решению. Так вот нахождение эвристики очень нетривиальная задача. Даже для сдвигашек  существует несколько разных эвристик и для некоторых сдвигашек буквально методом подбора можно определить какая подходит. При неправильном применении эвристики можно как минимум найти не оптимальное решение, а как максимум приблизиться к неинформативному методу и не решить задачу за разумное время.
« Последнее редактирование: 28 Октября 2014, 08:48:41 от SergR »
www.nontwistypuzzles.ru - нешарнирные головоломки - обновление 10.04.2015

Оффлайн sm

  • Постоялец
  • ***
  • Сообщений: 226
  • Пол: Мужской
pytlivyj, Леннон, рад видеть вас! Надеюсь на пополнения наших рядов! :)
Ещё методы:
2) Собирать как сиамский кубик;
3) Поштучная сборка кубиками с помощью универсальной формулы 3-цикла;
7) Самая интересная сборка (!!!).
С некоторыми сиамскими кубиками я экспериментировал, там действительно не всегда удается собрать куб, если изначально он замешан как не сиамский. Опытным путем пришел к выводу, что если на сиамском кубе можно реализовать 3 смежные вращающиеся грани, то его можно собрать с любого замеса.
Собирать только при помощи трициклов так же пробовал - очень полезное занятие для их закрепления, так же развивает умение ориентироваться по всем цветам куба. Здесь так же можно дополнительно можно использовать подстановочные движения - тоже полезно упражнение для развития ориентации на всем кубе.

3. Пояс-метод. (начало со сборки пояса, дальнейшие стадии переменные, может быть похож на HTA-метод).
4. Начиная с двух противоположных сторон. (ещё более переменная схема сборки, в чём-то также может быть похож на HTA).
6. HTA-метод - последнее приобретение  :)
Метод 7 у Пытливого и 3, 4 у Ленона имеют что-то общее с HTA.
Это, наверное, то чем я вплотную займусь после метода Хейс. Вообще, я уже пробовал, собирать противоположенными цветами, но из-за присутствующих маленьких недостатков, с которыми нужно будет разбираться, пока отложил его (хочется научиться исправлять эти недостатки осознано, т.к. я очень не люблю применять формулы). Ленон, если будет время, можешь понятным языком расписать этапы HTA и его нюансы?

Какой метод позволяет решить наименьшим количеством ходов?
Как решает компьютер?
Из всех опробованных мной методов оптимальней всего у меня получается собирать методом Хейс - сейчас часто удается уложиться в 50 ходов. Но я пока собираю не самым продвинутым вариантом Хейс, а можно сказать самым простым в 5 этапов (4 блока 1х1х4, ориентация ребер, пермутация ребер, 2 угла по местам, 3 оставшихся угла по местам). Я думаю, оптимальным является сборка куба блоками, продвинутый метод Хейс как раз использует эту идею. Плюс метода Хейс в том, что он не использует заготовленных формул как таковых и в свою очередь остается понятным для человека, но собирать им требует не дюжей практики, у меня порой даже на простом варианте Хейс иногда мозг "закипает", а о сборке последнего слоя блоками и подумать пока страшно. Вот моя тема на английском форуме посвященная анализу оптимальной сборке 3-х углов - http://twistypuzzles.com/forum/viewtopic.php?f=8&t=27872
Я думаю, знание Хейс также будет полезно для тех, кто занимается сборкой разнообразных бандажей.

По поводу, какие методы используются для решения на компьютере я не знаю. Сейчас вроде самый продвинутый в этом плане алгоритм Косиембы. Надеюсь, что кто-нибудь из форумчан сможет раскрыть эту тему простым и понятным языком.
« Последнее редактирование: 28 Октября 2014, 08:59:34 от sm »

Оффлайн Леннон

  • Ветеран
  • *****
  • Сообщений: 1 305
  • Пол: Мужской
  • Спящий.
Если верить этому http://speedcubing.ru/wiki/%D0%A1%D0%B1%D0%BE%D1%80%D0%BA%D0%B0_%D0%BD%D0%B0_%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%BE_%D1%85%D0%BE%D0%B4%D0%BE%D0%B2
то методов, явно выигрывающих по количеству ходов, всё-таки нет :)

Последний абзац, п. №7, цитата: ни одна из представленных методик по-одиночке не дает в среднем даже 40 ходов.
А ведь чемпионы выдают решения почти как у компьютера - 20 ходов... спрашивается, КАК? Каким таким методом?

А просто.... путём комбинирования.
Причина недостаточной эффективности отдельных методов, заключается наверное в самих схемах.

Например: мы решаем куб всегда послойно. Сначала первый слой, потом второй, потом третий, и никак иначе.
А что если попался случай, когда по КХ гораздо выгоднее собрать сначала первый и третий слои, и только потом - второй?
Или выгоднее собрать два первых слоя одновременно?
Или выгоднее сначала собрать все 8 уголков?
Или блок 2*2*3, а потом по Петрусу?

И любой другой отдельно взятый метод (даже сильно развитый и сложнейший), от таких "а что если"/"или" полностью не застрахован.

Именно потому, комбинирование схем оказывается более эффективно, продвинутый в этом деле сборщик должен уметь выбирать из разных вариантов более эффективный в данном случае - ему даётся на это час времени. И если умеет - то может получить отличный результат, вплоть до 20 ходов...



Что касается компьютера... он "решает" кубы, иначе :)

Его метод - найти к каждому возможному состоянию 3*3*3 его "частное решение" кратчайшее, или почти кратчайшее по КХ.
Понятно, что в сумме таких "частных решений" - огромное множество, они не вписываются в одну чёткую схему, да и осилить это может разве что ЭВМ (тут уж программистам виднее, как это делается, и как вообще это создавалось).
F R U L D * 252

Онлайн Philipp

  • Администратор
  • *****
  • Сообщений: 2 361
  • Пол: Мужской
  • С Администратором лучше не спорить.
Про сборку компьютером, приходит на память решение кубика конструктором Лего и процессором от Йфона. Причём довольно быстро и похоже не послойным методом. Эта малютка умудряется использовать метод полного перебора?
И ещё. Когда доказывали на компьютере минимальное количество ходов сборки кубика, там без полного перебора не обойтись. Да годы, но не жизнь. А надо было перебрать все варианты из всех состояний. И ходов 19. И программу человек написал.
Хочется понять каков алгоритм при методе простого перебора вариантов. Просто подбор под количества ходов, например 19, пока не подойдёт один из случайных? Или есть анализ? Вот бы знать его. Вдруг есть человеческие мозги, которые смогут ну хотя бы приблизиться к этому методу по времени и результату.
« Последнее редактирование: 28 Октября 2014, 10:02:08 от Philipp »

Оффлайн SergR

  • Постоялец
  • ***
  • Сообщений: 135
  • Пол: Мужской
  • Ростовская обл., г.Красный Сулин
    • Нешарнирные головоломки
Про сборку компьютером, приходит на память решение кубика конструктором Лего и процессором от Йфона. Причём довольно быстро и похоже не послойным методом. Эта малютка умудряется использовать метод полного перебора?
И ещё. Когда доказывали на компьютере минимальное количество ходов сборки кубика, там без полного перебора не обойтись. Да годы, но не жизнь. А надо было перебрать все варианты из всех состояний. И ходов 19. И программу человек написал.
Хочется понять каков алгоритм при методе простого перебора вариантов. Просто подбор под количества ходов, например 19, пока не подойдёт один из случайных? Или есть анализ? Вот бы знать его. Вдруг есть человеческие мозги, которые смогут ну хотя бы приблизиться к этому методу по времени и результату.
43,252,003,274,489,856,000 возможных комбинаций - 1 371 512 026 715 лет по одной секунде на поворот.
В момент построения очередного уровня дерева состояний проверяется на достижения цели. Поэтому можем не перебирать все варианты, при плохом стечении обстоятельств решение может быть в в конце всего перебора. При использовании эвристических методов поиска мы отбрасываем неэффективные (с точки зрения эвристики) ветки дерева и движемся в наиболее вероятном пути к решению.
www.nontwistypuzzles.ru - нешарнирные головоломки - обновление 10.04.2015

Онлайн Philipp

  • Администратор
  • *****
  • Сообщений: 2 361
  • Пол: Мужской
  • С Администратором лучше не спорить.
Вот я про эти эвристические методы и пытаюсь узнать. Насколько они применимы в реальности человеком, хоть и неординарным, а не компьютером? Ну и описание их.

Оффлайн SergR

  • Постоялец
  • ***
  • Сообщений: 135
  • Пол: Мужской
  • Ростовская обл., г.Красный Сулин
    • Нешарнирные головоломки
На примере сдвигашек применяются следующие эвристики:
  • Кол-во блоков стоящих не на своем месте
  • Манхэтенское расстояние - сумма расстояний всех блоков от текущей позиции до целевой
  • Линейный конфликт (не разобрался)
  • Кол-во машин препятствующих проезду целевой (для Rush Hour)
  • Штрафные какие-то эвристики
  • Различные их сочетания
На каждом уровне развернутого дерева для каждой позиции вычисляется эвристика и выбирается позиция с наименьшей стоимостью и от нее строится следующий уровень и т.д.
Даже не представляю каким неординарным надо быть человеком, что бы в уме это все прокрутить. Хотя не исключаю что человек может все это просчитать, но только на подсознательном уровне (т.е. все это он делает, но не догадывается что он применил какую-то эвристику  :) ).
Сейчас есть новое направление в алгоритмах - генетический (типа повторяет развитие и жизнь живых организмов), но я пока в нем не разобрался, как и в других тоже (набрался вершков, т.к. вся информация на английском)
« Последнее редактирование: 28 Октября 2014, 10:55:54 от SergR »
www.nontwistypuzzles.ru - нешарнирные головоломки - обновление 10.04.2015

Оффлайн sm

  • Постоялец
  • ***
  • Сообщений: 226
  • Пол: Мужской
Если верить этому ...
то методов, явно выигрывающих по количеству ходов, всё-таки нет :)
Последний абзац, п. №7, цитата: ни одна из представленных методик по-одиночке не дает в среднем даже 40 ходов.
А ведь чемпионы выдают решения почти как у компьютера - 20 ходов... спрашивается, КАК? Каким таким методом?
А просто.... путём комбинирования.
Причина недостаточной эффективности отдельных методов, заключается наверное в самих схемах.
Да, с этим утверждением я полностью согласен. Комбинирование методик, может дать наиболее оптимальный вариант. 40 ходов это пока для меня недосягаемая планка любым из методов которые я использую (редкие случаи везения я не беру в расчет). Но все методики, которыми я пользуюсь, носят последовательный характер, и если исходить из этого, то Хейс дает у меня максимальный результат, но тут возможно еще дает выигрыш большой опыт послойной сборки.
В общем, сборка на количество ходов - очень неординарная задача, думаю, требующая приложения опыта и интеллектуальных усилий не менее чем игра в шахматы. И думаю, в этой области человеческий мозг тоже может потягаться с компьютером на силу интеллекта и оригинальность решения.

Оффлайн Isaev

  • Старожил
  • ****
  • Сообщений: 363
  • Пол: Мужской
Вот я про эти эвристические методы и пытаюсь узнать. Насколько они применимы в реальности человеком, хоть и неординарным, а не компьютером? Ну и описание их.
Это как раз и есть интуитивная сборка. Эвристикой пытаются описать компьютеру как человек интуитивно выбирает следующий наиболее выгодный ход. И чем более точно это удастся описать программисту и чем быстрее будет работать проверка каждой стадии эвристики, тем более быстро алгоритм достигнет цели. Задача не тривиальная и требует практики и творческого подхода) Естественно, чем больше практики в сборке у программиста, тем более качественно он сможет научить свою программу. На практике часто берут стандарные приёмы и формулы (ну или построение полного дерева и отсечение комбинаций по "числу бога" например, если ищем самое короткое решение), т.к. не всегда програмист вообще умеет собирать кубик, потому качественных реализаций довольно мало.
« Последнее редактирование: 10 Марта 2016, 19:03:55 от Isaev »

Оффлайн sm

  • Постоялец
  • ***
  • Сообщений: 226
  • Пол: Мужской
После почти годового перерыва, моя копилка пополнилась еще двумя замечательными методами – HTA и ZZ.
Но в чистом виде я их не использую, а использую в виде симбиоза с ранее изученными методами: