Несколько замечаний в дополнение к хорошему ответу ccoakley и комментарию stubbscroll относительно конкретного примера и нескольких общих принципов.
Что касается замечания Стаббскролла, что у этой конкретной проблемы всего 9! = 362880 разных состояний:
Одним (довольно простым) способом кодирования перестановок в виде чисел является индексация перестановок с помощью лексикографического упорядочения. Например
0 1 2 3 --> 0
0 1 3 2 --> 1
0 2 1 3 --> 2
...
1 0 2 3 --> 6
1 0 3 2 --> 7
...
3 1 2 0 --> 21
3 2 0 1 --> 22
3 2 1 0 --> 23
Хитрость в написании индекса в факториальной базе,
n = a_1 * 1! + a_2 * 2! + a_3 * 3! + a_4 * 4! + ...
, где 0 <= a_k <= k. Если у вас есть символы s, индексы варьируются от 0 до s! -1, поэтому у вас есть коэффициенты s-1 в разложении факториальной базы n, (a_1,a_2,...,a_(s-1)). Тогда перестановка с индексом n определяется следующим образом
for i = 1 to s-1
the i-th symbol becomes the (a_(s-i)+1)-th smallest unused symbol
the last symbol is the left over one
Поскольку это не очень понятно, пример. Скажем, мы ищем перестановку с индексом 4231 {1,2,3,4,5,6,7,8}. Сначала расширим 4231 в факторной базе
4231 = 1 + 2*2115 : a_1 = 1
2115 = 0 + 3* 705 : a_2 = 0
705 = 1 + 4* 176 : a_3 = 1
176 = 1 + 5* 35 : a_4 = 1
35 = 5 + 6* 5 : a_5 = 5
5 = 5 + 7* 0 : a_6 = 5
все последующие коэффициенты (здесь только a_7) равны 0. Лучше следовать записи a_i в обратном порядке (a_7, a_6, ... a_1), поэтому
coefficients symbols choice
0,5,5,1,1,0,1 1,2,3,4,5,6,7,8 1
5,5,1,1,0,1 2,3,4,5,6,7,8 7
5,1,1,0,1 2,3,4,5,6,8 8
1,1,0,1 2,3,4,5,6 3
1,0,1 2,4,5,6 4
0,1 2,5,6 2
1 5,6 6
- 5 5
Результат: 17834265.
Найдите индекс 246351:
symbols count perm index(head)
1,2,3,4,5,6 6 2,4,6,3,5,1 1 a_5 = 1
1,3,4,5,6 5 4,6,3,5,1 2 a_4 = 2
1,3,5,6 4 6,3,5,1 3 a_3 = 3
1,3,5 3 3,5,1 1 a_2 = 1
1,5 2 5,1 1 a_1 = 1
Индекс `1 * 5! + 2 * 4! + 3 * 3! + 1 * 2! + 1 * 1! = 187.
Так что теперь у нас есть довольно простой способ преобразования между перестановками и их индексами. Преобразование не очень быстрое (O (s ^ 2)), но вы получаете быстрое и простое сравнение и поиск (я видел состояние раньше?). Будет ли это усиление, предстоит решить в каждом случае.
Теперь, для данного конкретного случая, у нас есть некоторые дополнительные ограничения, уменьшающие пространство поиска.
- Каждый ход представляет собой циклическую перестановку из трех элементов, таким образом, даже перестановка.
Следовательно, все комбинации таких ходов также являются перестановками, что означает, что половина возможных состояний недоступна. Нам осталось (максимум) 9! / 2 = 181440 достижимых состояний. Индексирование даже перестановок с помощью лексикографического упорядочения лишь немного сложнее. Важным моментом является то, что перестановка является четной тогда и только тогда, когда сумма коэффициентов a_k в разложении факторного основания его индекса четна.
Уменьшите пространство поиска, используя ограничения и симметрии. Если вы используете стратегию поиска, использующую структуру со всеми возможными состояниями, это уменьшит требования к памяти на соответствующий коэффициент. Если ваша стратегия поиска касается только достижимых состояний, ограничения не уменьшают количество шагов, но они все же могут ускорить поиск из-за меньшего объема памяти. Использование симметрий может уменьшить количество шагов путем идентификации эквивалентных состояний.
В примере задачи мы имеем еще одну приятную ситуацию, когда 5 уже находится в правильном месте, и что оптимальное решение никогда не сдвинет его с места. Таким образом, нам нужно рассмотреть только четные перестановки из 8 символов, сокращая пространство поиска до 8! / 2 = 20160 возможных состояний. (Хотя это не очевидно.)
В целом, однако, трудно доказать, что оптимальное решение никогда не оставляет определенного подмножества возможных состояний, поэтому вы редко можете напрямую наложить такое ограничение на ваш поиск.
Но часто бывает так, что вы можете найти хорошее решение проблемы, используя такое ограничение, а затем использовать хорошее решение для раннего поиска оптимального решения в неограниченном пространстве поиска.
Вариант, который часто можно использовать, - это поиск аппроксимации с помощью жадной стратегии и использование ее в качестве границы для раннего обрезания в результате тщательного поиска.