Верхняя граница игры в час пик
Я пытаюсь понять сложность верхней границы для головоломки Rush Hour. Я имею дело с 9x9 доска, с 22 транспортные средства, включая грузовые автомобили (длиной 3 сетки) и легковые автомобили (длиной 2 сетки).
По моей логике, учитывая тот факт, что автомобиль может двигаться 8 times через 9x9 плата в одном направлении, расчет будет 8^22что приводит к 7.34e+19, Это означает, что верхняя граница 7.34e+19 разные состояния для этой головоломки.
Это кажется мне слишком излишним, поскольку я хочу вычислить, насколько близок мой алгоритм к решению, учитывая количество повторяющихся состояний платы. Даже если предположить, что все транспортные средства являются грузовиками и поэтому могут двигаться только 7 времена кажутся слишком большими.
Моя верхняя граница завышена? Возможно, я должен учитывать, что количество подвижного пространства - это единственное пространство, не занятое транспортным средством.