Сколько возможных состояний у 8-головоломки?

Классическая 8-головоломка относится к семейству скользящих блоков. Моя книга (Искусственный интеллект Современный подход Стюарта Рассела и Питера Норвига) говорит, что 8-головоломка имеет9!/2 возможные состояния. Но ПОЧЕМУ/2 ? Как ты это получил?

 dasblinkenlight12 авг. 2012 г., 18:02

Ответы на вопрос(1)

Решение Вопроса

9! это общее количество возможных конфигураций головоломки, тогда как9!/2 это общее количествоsolvable конфигурации. Например, эта конфигурация не имеет решения:

1 2 3
4 5 6
8 7

Узнайте больше о разрешимости определенных конфигураций n-головоломки в этой Википедиистатьяили как указано @dasblinkenlight в этом MathWorldобъяснение.

Один из возможных способов выяснить это9!/2 Количество решаемых конфигураций должно начинаться с решенной головоломки и генерировать из нее все возможные допустимые, неповторяющиеся движения.

 Ghost12 авг. 2012 г., 18:02
Итак, как факт, что некоторые конфигурации невозможны, заставляет нас делить его на 2?
 17 окт. 2014 г., 05:58
Я бы сошлся с первым предложением. Мы можем быть в состоянииplace 8 блоков на 9 мест в 9! конфигурации, но есть только 9! / 2 достижимых конфигураций этой скользящей головоломки.
 12 авг. 2012 г., 18:01
Хотя это может быть правильно, это (пока) не объяснение того, почему мы должны делить на 2. Или это?
 08 сент. 2012 г., 16:34
Если вы нарисуете график каждого отдельного состояния с каждым возможным выходом из этого состояния, вы получите 9! / 2 состояния с 9! переходы. Существуют состояния, которые существуют, но не попадают на график, и они являются «неразрешимыми». из них. Просто так случается, что это половина из 9!
 13 авг. 2012 г., 02:46
Простое объяснение состоит в том, чтоexactly half конфигурации не могут быть достигнуты из любой выбранной начальной точки (или, альтернативно, не могут достичь любой случайно выбранной конечной точки), поэтому мы делим общее количество конфигураций (9!) на 2, чтобы получить общее количество состояний, которые могут перейти на шаг шаг за шагом к решению. Если вы хотите знатьwhy Точно половина не может быть достигнута, вам нужно будет узнать о "четности". Разумная отправная точкаjimloy.com/puzz/15.htm

Ваш ответ на вопрос