Время для алгоритма A * для решения головоломки головоломки 8 плиток

Question

Просто интересно, может ли кто-нибудь помочь мне с кодом, который я сейчас работаю для uni. Это скользящая плитка, которую я кодирую, и я реализовал алгоритм A * с эвристикой расстояния Манхэттена. В настоящий момент время для решения головоломки может варьироваться от нескольких хеджируемых миллисекунд до примерно 12 секунд для некоторых конфигураций. То, что я хотел знать, - это тот диапазон, который я должен ожидать?

Я никогда раньше не делал никаких ИИ, и мне нужно научиться этому на лету, поэтому любая помощь будет оценена по достоинству.

Answer 1

Что я хотел знать, является ли этот диапазон во времени тем, что я должен ожидать?

Это немного сложно понять из информации, которую вы предоставили. Это поможет, если вы сможете описать, как вы реализовали A *, или если вы профилировали свое приложение и нуждались в помощи в определенных областях, которые были медленными.

Следует отметить, что, скорее всего, это ускорит ваше среднее время решения: Половина стартовых позиций любой головоломки n-tile никогда не может привести к решению, поэтому вы можете сразу же исключить определенные конфигурации очень быстро. Например, вы не можете решить 8-плитка головоломка, которая выглядит следующим образом:

1 2 3 
4 5 6 
8 7 . 

Чтобы понять почему, обратите внимание, что из-за пустое пространство должно заводиться туда, где это началось, общее число «вверх»/«вниз» должны быть равны, равно как и общее число «левых»/«правых» движений. Это означает, что общее количество ходов должно быть четным.

Но перестановка 7/8 здесь является одним удалением от стартовой головоломки, не меняя пустого положения! Таким образом, эта головоломка не может быть решена. (Однако, если бы мы сделали две транспозиции, тогда она была бы разрешима снова.)

Answer 2

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

Для отладки я бы сохранил или распечатал (но это требует времени!), На каком уровне вашего дерева вы находитесь.

Также помните, что веса очень важны. Например .:

123 
4 6 <- your final state 
789 

  213        1 3 
To change 4 6 is much more expensive than 426 
      789        789 

Я надеюсь, что помогает.

Answer 3

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

Я не хочу говорить слишком много, так как это проблема домашней работы, но если память служит, Рассел и Норвиг сходятся в контексте раздвижной головоломки ... возможно, глава третья? (Мой R + N не под рукой.)