Метрики

17 февраля 2012

Расстояние

См. также: Jaap's Puzzle Page (Metrics).

В математике метрикой на множестве X называется функция

d : X × XR

(где R – множество действительных чисел). Для любых x, y, z ∈ X,

  1. d(x, y) ≥ 0
  2. d(x, y) = 0 тогда и только тогда, когда x = y
  3. d(x, y) = d(y, x)
  4. d(x, z) ≤ d(x, y) + d(y, z)

Функция d называется расстоянием.

Пусть X – множество всех достижимых конфигураций комбинаторной головоломки. Тогда расстоянием между двумя конфигурациями называется минимальное количество ходов, необходимое для того, чтобы перейти от одной конфигурации к другой. Предполагается, что это возможно; в противном случае, расстояние считается положительной бесконечностью.

Метрики на скользяшках

Чтобы найти расстояние между двумя конфигурациями, необходимо определить количество ходов в оптимальном решении. Чтобы считать ходы, нужно знать, что такое ход. Таким определением является метрика на комбинаторной головоломке.

При анализе кубика Рубика 3 × 3 × 3 используются две основные метрики: QTM (quarter-turn metric, метрика, которая рассматривает поворот грани на 180o как два хода) и FTM (face-turn metric, метрика, рассматривающая поворот на 180o как один ход).

На целочисленной головоломке с плитками 1 × 1 можно определить по меньшей мере две метрики. Во-первых, можно считать, что каждый ход изменяет положение только одной материальной плитки. Такая метрика называется STM (single tile metric). Метрика STM в основном используется в исследованиях.

Некоторым людям удобнее перемещать плитки целыми рядами, а не по одной. Например, в классических "Пятнашках" можно перемещать по три плитки за один раз. Метрика, считающая такое перемещение за один ход, называется MTM (multi tile metric).

На целочисленной прямоугольной головоломке, возможны следующие определения хода (вместе с предлагаемыми сокращениями для соответствующих метрик):

  1. NMM (Natural Move Metric): перемещение одной плитки в любом направлении или по ломаной линии. Эдвард Хордерн в своей книге "Sliding Piece Puzzles" утверждал, что такое определение хода является наиболее естественным.
  2. OMM (Orthogonal Move Metric): перемещение одной плитки в любом одном направлении. Непрерывное перемещение одной и той же плитки по ломаной линии не считается за один ход.
  3. GMM (Group Move Metic): перемещение любого количества плиток вместе в одном и том же направлении.
  4. SMM (Short Move Metric): перемещение одной плитки в любом ортогональном направлении на расстояние 1 (размер клетки доски). Последовательные перемещения одной и той же плитки в одном и том же направлении считаются как отдельные ходы. Эта метрика является обобщением метрики STM.
  5. PMM (Push Move Metric): перемещение любого количества плиток в любом направлени, так же как и в п.3; отличие состоит в том, что за один ход разрешается касаться только одной плитки. Эта плитка используется для того, чтобы "толкать" другие плитки, участвующие в ходе. Метрика PMM является обобщением метрики MTM.