Вопрос по 8-puzzle, artificial-intelligence, algorithm – Сколько возможных состояний у 8-головоломки?

16

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

Естьexplanation on MathWorld. dasblinkenlight

Ваш Ответ

1   ответ
20

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

1 2 3
4 5 6
8 7

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

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

Хотя это может быть правильно, это (пока) не объяснение того, почему мы должны делить на 2. Или это?
Я бы сошлся с первым предложением. Мы можем быть в состоянииplace 8 блоков на 9 мест в 9! конфигурации, но есть только 9! / 2 достижимых конфигураций этой скользящей головоломки.
Если вы нарисуете график каждого отдельного состояния с каждым возможным выходом из этого состояния, вы получите 9! / 2 состояния с 9! переходы. Существуют состояния, которые существуют, но не попадают на график, и они являются «неразрешимыми». из них. Просто так случается, что это половина из 9!
Итак, как факт, что некоторые конфигурации невозможны, заставляет нас делить его на 2? Ghost
Простое объяснение состоит в том, чтоexactly half конфигурации не могут быть достигнуты из любой выбранной начальной точки (или, альтернативно, не могут достичь любой случайно выбранной конечной точки), поэтому мы делим общее количество конфигураций (9!) на 2, чтобы получить общее количество состояний, которые могут перейти на шаг шаг за шагом к решению. Если вы хотите знатьwhy Точно половина не может быть достигнута, вам нужно будет узнать о "четности". Разумная отправная точкаjimloy.com/puzz/15.htm

Похожие вопросы