Хотя алгоритм поиска решения я сделал (он не идеальный, но достаточно хороший для тех условий, в которых он будет применяться), пятнашки затянули, и мне захотелось перебрать
все возможные расстановки пятнашек. Тогда можно было бы, например, проверить,
действительно ли максимум – 80 ходов. Так как количество вариантов –– 16! (это
примерно 20,9 триллиона), необходимо либо значительно сократить пространство
перебора (это – интересная задача для математика), либо оптимизировать хранение
информации о пройдённых вариантах. Эта оптимизация мне, как программисту,
показалась очень интересной задачей. Я потратил достаточно много времени на
неё, но пока не сделал. Так как практического смысла в ней уже нет, я её
отложил и ради развлечения перебрал все варианты для варианта пятнашек 4 на 3.
Т.е. когда необходимо собрать поле
все возможные расстановки пятнашек. Тогда можно было бы, например, проверить,
действительно ли максимум – 80 ходов. Так как количество вариантов –– 16! (это
примерно 20,9 триллиона), необходимо либо значительно сократить пространство
перебора (это – интересная задача для математика), либо оптимизировать хранение
информации о пройдённых вариантах. Эта оптимизация мне, как программисту,
показалась очень интересной задачей. Я потратил достаточно много времени на
неё, но пока не сделал. Так как практического смысла в ней уже нет, я её
отложил и ради развлечения перебрал все варианты для варианта пятнашек 4 на 3.
Т.е. когда необходимо собрать поле
1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 |
Результатами этого эксперимента я и хочу поделиться.
Итак, для пятнашек 4*3 существует 12! вариантов, это чуть больше 479 миллионов. Ровно для половины этих вариантов не существует решения, так как у них другая чётность, чем у комбинации, приведённой выше. При таком количестве вариантов достаточно было завести три битовых массива по 60 МБ и реализовать функции для кодирования расстановки числом и
раскодирования обратно. Для задачи 4*4 я пробовал разные варианты такой функции, чтобы добиться большей локальности, т.е. чтобы расстановки, получаемые за один ход из текущей имели коды, как можно более близкие числовые к коду текущей расстановки. Для 4*3 это не имеет существенного значения. Главное, чтобы любое число от 0 до 12!-1 соответствовало одной своей комбинации.
раскодирования обратно. Для задачи 4*4 я пробовал разные варианты такой функции, чтобы добиться большей локальности, т.е. чтобы расстановки, получаемые за один ход из текущей имели коды, как можно более близкие числовые к коду текущей расстановки. Для 4*3 это не имеет существенного значения. Главное, чтобы любое число от 0 до 12!-1 соответствовало одной своей комбинации.
Поиск шёл в ширину, начиная с расстановки-решения.
Максимальное количество ходов, необходимое для решения любой комбинации правильной чётности оказалось равно 53. Достаточно неплохо, учитывая, что максимум суммы расстояний от каждой плашки до её места в решении равен 37. Т.е. если можно было бы каждый ход перемещать любую плашку на одну клетку не взирая на то, что клетка занята, то максимальное количество ходов было бы 37.
сначала растёт быстро, затем всё медленнее: до 5 шагов – в два и более раза за шаг, до 27 шагов – в 1.5 и более раза. Если обозначить количество вариантов, которые можно решить ровно за n шагов за С(n), то максимум C(n) будет около 22 миллионов. N при этом равно 36. Меня это удивило, я думал будет симметрично, т.е. С(n) будет равно C(nmax- n).
Для пятнашек 4*4 S(n) растёт быстрее, чем степень двойки довольно долго – до 13 шага включительно. Мне удалось построить варианты для 4*4 до 29-го шага. Там S(29) равно примерно 822 миллионам, S(28) – 465 млн., т.е. в 1.74 раза меньше.
Количество комбинаций, решаемых за 53 хода – не 1, как я предполагал, а 18. У всех у них сумма расстояний по горизонтали от каждой плашки до её места в решении равна 21 (максимально возможное – 22).
До 28 шагов включительно попадаются комбинации, в которых сумма расстояний по вертикали от каждой плашки до её места в решении равно 4. Например, надо 28 шагов чтобы решить
5 | 2 | 3 | 8 |
1 | 6 | 7 | 4 |
9 | 10 | 11 |
Михаил Машуков.
Так же см. https://docs.google.com/document/pub?id=1Z3wx4s4lHqJ656iXmDNdUuLNR_MkIAb-qRFodh-UA8c
приветствую.. очень бы хотелось узнать об этом поподробнее, в частности, какие структуры и типы данных были использованы, а то мой вариант структуры занимает сегодня 18Б (на один узел) и при таком размере я не могу выйти даже на 25 уровней.. начинал же я с 44Б на узел.. использую деревья, а альтернативу я пока не нашёл.. думаю, как структуру сохранять в файл, вероятно, что этот вариант может чем-то мне помочь..
ОтветитьУдалитьотбой.. :) задачу решил заменой одной проблемы другой.. память не использую вообще (5МБ на всю программу).. будет интересно - пиши.. :) всех благ..
ОтветитьУдалить