Числовые превращения

[Ian]

Светлана, круто.
Очень приветствую, что элементы, не затронутые на текущем шаге операцией, сохраняют свою позицию, удобно проверять. И как-то помечать в случаях b=2a или 4b=13a, что некоторый элемент хотя и не изменился, но операции подвергался (если этот случай встретится)

 

[Swetlana]

Да, элементы обязательно нужно помечать. Не успела скриншоты проверить (на всякий случай всё равно проверяю) и птички расставить. К тому же хочется для n=9 до последнего шага не смешивать первую 4-ку и последующую 5-ку, и смешать только на последнем шаге, для получения начальных элементов четвёрки и пятёрки.
Но что-то не получается. Возможно, устроено более сложно, пока непонятно, как.

[Swetlana]

Слишком длинная таблица. Причём это только половина, 36 ходов для преобразования (1,2,3,4) в (1, 3, 7, -1).
Придётся отказаться от тех'а.
\begin{bmatrix}
1' & 2 & 3 & 4'' & 5 & 6 & 7 & 8 & 9\\ 
-1 & 2 & 3'' & 1' & 5 & 6 & 7 & 8 & 9\\ 
-1'' & 2 & 4 & 0'' & 5 & 6 & 7 & 8 & 9\\ 
3 & 2 & 4'' & 1' & 5 & 6 & 7 & 8 & 9\\ 
3'' & 2 & 1' & -1 & 5 & 6 & 7 & 8 & 9\\ 
4 & 2'' & 0' & -1 & 5 & 6 & 7 & 8 & 9\\ 
4 & -6'' & -2' & -1 & 5 & 6 & 7 & 8 & 9\\ 
4 & -8'' & 0 & -1' & 5 & 6 & 7 & 8 & 9\\ 
4' & 11'' & 0 & 5 & 5 & 6 & 7 & 8 & 9\\ 
1 & 19'' & 0 & 5' & 5 & 6 & 7 & 8 & 9\\ 
1' & 8 & 0 & -4'' & 5 & 6 & 7 & 8 & 9\\ 
7 & 8' & 0 & 25'' & 5 & 6 & 7 & 8 & 9\\ 
7'' & -1 & 0' & 29 & 5 & 6 & 7 & 8 & 9\\ 
-21 & -1' & -7'' & 29 & 5 & 6 & 7 & 8 & 9\\ 
-21' & 4 & 8' & 29'' & 5 & 6 & 7 & 8 & 9\\ 
-21'' & 4 & -5' & 17 & 5 & 6 & 7 & 8 & 9\\ 
-2 & 4 & 6' & 17'' & 5 & 6 & 7 & 8 & 9\\ 
-2 & 4'' & 1' & 27 & 5 & 6 & 7 & 8 & 9\\ 
-2'' & 1 & -1' & 27 & 5 & 6 & 7 & 8 & 9\\ 
-7'' & 1 & (-1') & 27 & 5 & 6 & 7 & 8 & 9\\ 
8' & 1 & 4 & 27'' & 5 & 6 & 7 & 8 & 9\\ 
-3 & 1 & 4' & 23'' & 5 & 6 & 7 & 8 & 9\\ 
-3' & 1 & -11'' & -17 & 5 & 6 & 7 & 8 & 9\\ 
2 & 1' & -6'' & -17 & 5 & 6 & 7 & 8 & 9\\ 
2 & 9' & 31'' & -17 & 5 & 6 & 7 & 8 & 9\\ 
2 & -4' & 24 & -17'' & 5 & 6 & 7 & 8 & 9\\ 
2 & 5' & 24'' & -1 & 5 & 6 & 7 & 8 & 9\\ 
2 & -9 & -7'' & -1' & 5 & 6 & 7 & 8 & 9\\ 
2' & -9 & 8'' & 4 & 5 & 6 & 7 & 8 & 9\\ 
-2' & -9'' & 2 & 4 & 5 & 6 & 7 & 8 & 9\\ 
3 & 1' & 2'' & 4 & 5 & 6 & 7 & 8 & 9\\ 
3 & (1') & 7 & 4'' & 5 & 6 & 7 & 8 & 9\\ 
3'' & -1 & 7 & 4'' & 5 & 6 & 7 & 8 & 9\\ 
4 & -1'' & 7 & 0' & 5 & 6 & 7 & 8 & 9\\ 
4'' & 3 & 7 & 1' & 5 & 6 & 7 & 8 & 9\\ 
1 & 3 & 7 & -1 & 5 & 6 & 7 & 8 & 9
\end{bmatrix}

[Swetlana]

Обозначения: один штрих - первый эл-т пары; два штриха - второй. Элемент, не изменившийся после преобразования, в скобках.
1'    2    3    4''     5 6 7 8 9 
-1   2    3''    1'     5 6 7 8 9 
-1''  2    4     0''    5 6 7 8 9 
3    2    4''    1'     5 6 7 8 9 
3''   2    1'    -1     5 6 7 8 9 
4    2''   0'    -1     5 6 7 8 9 
4   -6''  -2'    -1     5 6 7 8 9 
4   -8''   0    -1'     5 6 7 8 9 
4'  11''   0     5     5 6 7 8 9 
1  19''   0     5'     5 6 7 8 9 
1'   8     0   -4''     5 6 7 8 9 
7   8'     0   25''    5 6 7 8 9 
7''  -1    0'   29     5 6 7 8 9 
-21 -1'  -7''  29     5 6 7 8 9 
-21'  4   8'  29''     5 6 7 8 9 
-21'' 4   -5' 17      5 6 7 8 9 
-2    4   6'  17''     5 6 7 8 9 
-2    4''  1'  27      5 6 7 8 9 
-2''   1  -1'  27      5 6 7 8 9 
-7''   1 (-1') 27      5 6 7 8 9 
8'    1   4   27''     5 6 7 8 9 
-3   1   4'  23''      5 6 7 8 9 
-3'  1 -11'' -17      5 6 7 8 9 
2    1' -6''  -17      5 6 7 8 9 
2    9' 31'' -17      5 6 7 8 9 
2   -4' 24  -17''     5 6 7 8 9 
2    5' 24''  -1       5 6 7 8 9 
2   -9  -7''  -1'       5 6 7 8 9 
2'   -9  8''   4        5 6 7 8 9 
-2'  -9'' 2    4        5 6 7 8 9 
3   1'  2''    4        5 6 7 8 9 
3  (1') 7     4''       5 6 7 8 9 
3'' -1  7     4''       5 6 7 8 9 
4  -1'' 7     0'       5 6 7 8 9 
4''  3  7     1'       5 6 7 8 9 
1   3  7    -1       5 6 7 8 9 

[Swetlana]

1 3 7 -1   5    6   7   8   9
1 2   18  -1   5    6   7   8   9
1 2   37  -1   5    6   3   8  9
0 2   37  -1   5    6   4   8   9
1 2’ 37    3   5   6 4’’  8  9
1   (2)   37    3   5’   6 14’’   8  9
1    2    37 3’ 1’’  6 23   8   9
1    2    37    8’   36 6 23’’   8   9
1    2’’   37 1’   36   6 35   8   9
1    7’  37   (1)   36’’ 6 35   8   9
1  -15   37    1’ -17  6’’ 35   8   9
1  -15   37  -3’ -17’’ -5 35   8   9
1  -15   37 8 12’ -5 35’’   8   9
1  -15   37 8 1  -5  51’’   8’   9
1  -15’’ 37 8 1  -5   -49’’ -27   9
1   4   37 8 1  -5’  -48 -27’’  9
1   4   37’’ 8 1 12   -48  16   9’
1   4 6  8  1 12   -48’’ 16  -10’
1’  4 6  8  1’’ 12  14 16   18
2   4 6  8 10  12  14 16   18

[Swetlana]

прям не знаю, что делать

на такие порнографические таблицы скоро все порноспамеры слетятся

то ли скриншот таблицы прикреплять, то ли вордовский файл с таблицей
 

[Swetlana]

офтоп

А-алгоритм с большой эвристикой не перестаёт радовать запредельной глючностью 
Убрала из подсчёта эвристики поощрение за установку 0 в первый столбик и 2 в 3-й - и программа вообще перестала выдавать решения типа (_,_,_,_,5,6,7,8,9). А до этого за 1 сек. наштамповала 5 штук, одно с 1,3,7,-1 и ещё четыре новых. Хорошо, скриншоты успела сделать. 

[Swetlana]

Пожалуй, объясню причину моей буйной радости))

Модель - пространство состояний. Начальное состояние задачи (2,4,6,8,10,12,14,16,18). Конечное - (1,2,3,4,5,6,7,8,9). Имеется конечное число допустимых преобразований для перевода задачи в новое состояние. Составить план перевода задачи из начального состояния в конечное, желательно, за минимальное число ходов. Типичная задача робототехники, к слову.
Как работает А-алгоритм (в моей тупой реализации).
Берёт начальное состояние, порождает все состояния-преемники, помещает в список. Для каждого состояния рассчитывает некую оценку, степень перспективности состояния. Затем удаляет из списка состояние с минимальной оценкой, порождает для него всех преемников и заталкивает их в список.
Пусть u - текущее состояние. f(u) = g(u) + h(u), где g(u) - сколько уже прошли от начального состояния (число сделанных ходов), h(u) - эвристическая оценка оставшихся ходов до заключительного состояния. Успех дела зависит от качества эвристической оценки, больше ни от чего.
Если оценивать число оставшихся ходов оптимистически (не больше, чем на самом деле нужно), то алгоритм близок к поиску в ширину и гарантирует получение минимального решения за неизвестное конечное время, то есть не дождёшься.
А если эвристика большая, то она фокусирует поиск в направлении цели (это легко доказывается) и сквозь экспоненциальные и даже бесконечные пространства уверенной поступью быстро движемся к цели. Разумеется, большая эвристика не гарантирует даже получения решения - если слишком сфокусировали поиск, то промахнулись, прошли с рядом целевым состоянием и ушли на бесконечность.
В этой задаче тяжело придумать хорошую эвристику 
Cейчас такая. Считается отклонение d текущей конфигурации от заключительной: если в i-й клетке не число i, то штраф 1 очко. Сумма этих штрафов близка к реальному числу оставшихся ходов. Затем d умножаю на 3, чтоб ускорить поиск. Если d =2 (одна пара отклоняется от целевого состояния), то полагаю d =1 и на 3 не умножаю. Решение можно получить за 1 ход.
Ещё нужно следить за тем, чтобы не появлялись слишком большие числа (уходим по одной ветке на бесконечность). Поэтому суммирую элементы текущей конфигурации, вычисляю отклонение (по модулю) от 45 (суммы 1+2+...+9). Если это отклонение в 4 раза превышает 45, то добавляю штраф 50 очков.
Окончательно, h(u) = 3*d + shtraf. 
А в предыдущей эвристике поощрялась установка 0 и -2 в первый и третий столбик. Если было u[1]=0 или u[3]=-2, то штрафное очко не начислялось. С этой эвристикой А-алгоритм бойко наштамповал 5 приличных решений типа (_,_,_,_,5,6,7,8,9) с небольшими чиселками. А щас кое-как нашла одно и некузявое (1,34,-43,48,5,6,7,8,9).
Или ей нравится 0 и -2?  
Да, забыла сказать. Каждое порождённое состояние проверяется на новизну. Есть, конечно, вероятность, что оно совпадёт с уже удалённым, но, поскольку ходы необратимы, решила на это не закладываться.

[Swetlana]

Для n=9 уже несколько различных решений нашла, типа (_,_,_,_,5,6,7,8,9), примерно одной длины, везде нужна таблица примерно на 36 строк. Буду скриншоты постить, раз никто не скажет, как сделать таую таблицу. 

[12d3]

Я правильно понял, что в вашей трактовке задачи последовательность чисел имеет значение, т.е. (1;3;7;-1) и (-1;1;3;7) - это разные наборы? Просто в моей трактовке числа можно переставлять как угодно между собой. И тогда (1;2;3;4) преобразуется в (1;3;7;-1) за два хода.