Время для алгоритма A *, чтобы решить головоломку с 8 плитками

Question

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

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

Answer 1

Что я хотел знать, так это то, чего мне следует ожидать?

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

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

1 2 3 
4 5 6
8 7 .

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

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

Answer 2

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

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

Answer 3

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

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

Также помните, что вес очень важен. E.g.:

123
4 6 <- your final state
789

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

Надеюсь, это поможет.