Почему итерационное углубление Звезда не нуждается в проверке на наличие повторяющихся состояний?

Итеративное углубление Звезда (ID A *) - это ограниченный поиск по памяти. Мой вопрос заключается в том, что когда мы достигаем нового состояния s' из открытого состояния s в ID A *, почему мы не проверяем, находится ли s' в «открытых состояниях» или «закрытых состояниях»?Почему итерационное углубление Звезда не нуждается в проверке на наличие повторяющихся состояний?

Для некоторых проблем, например: sudoku, поскольку состояние никогда не будет достигнуто дважды, потому что «граф состояний проблемы» является деревом. Однако для другой проблемы, например: 8-головоломка, она, вероятно, снова и снова будет достигать состояния. Таким образом, определенно нужно проверить, находится ли состояние уже «посещено» (либо в открытом, либо в закрытом состоянии) или нет.

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

источник

2013-10-06 Peng Zhang

Этот вопрос не соответствует теме, поскольку речь идет о алгоритмах, не относящихся к программированию. –

Подождите. Что вы подразумеваете под не по теме? Существуют теги «алгоритм» и «поиск». Как вы можете сказать, что алгоритм не является частью программирования? –

Лично я думаю, что это по теме (хотя, возможно, лучше подходит для http://cstheory.stackexchange.com.) Прочитайте раздел справки [Какие темы можно задать здесь?] (Http://stackoverflow.com/help/on-topic) –

Мы не проверяем, является ли s 'дубликат, чтобы сохранить профиль памяти небольшим. В общем случае IDA ^*, по сути, разворачивает одно и то же состояние несколько раз.

источник

2013-10-06 20:48:37

Тогда вы имеете в виду, что даже при одном запуске поиска с определенным f-пределом (предел оценочной функции) состояние будет посещаться много раз? Я знаю, что государство будет посещаться во многих раундах. Но интуитивно, его не следует посещать много раз за один проход поиска. –

@ user2697964 - IDA * запоминает только узлы на текущем пути. Он не будет расширять государство, которое является его собственным предком. Однако, если состояние доступно из нескольких путей, оно может несколько раз увеличивать это состояние даже в пределах одного f-предела. –

@ user2697964Для предотвращения повторного поиска узлов, IDA * может быть сопряжен с таблицей транспозиций, которая использует основную память для кэширования ранее найденных узлов. Если узел был обнаружен до и искал до глубины, большей или равной текущей глубине поиска, вместо этого может использоваться его кешированное значение. См .: http://en.wikipedia.org/wiki/Transposition_table –

AI-программирование часто пытается попробовать много разных настроек алгоритмов, чтобы найти тот, который наилучшим образом соответствует вашим потребностям. Если очень вероятно, что новое состояние уже было посещено, возможно, это будет улучшение производительности, чтобы добавить дополнительные накладные расходы для определения того, было ли состояние уже посещено. Но может быть много других переменных, чтобы рассмотреть, например. как алгоритм подходит к проблеме, доступна ваша память, вычислительная мощность, масштабируемость. Я считаю, что хороший АИ-программист означает, что вы знаете плюсы и минусы различных алгоритмов и видели, как много разных проблем влияет на производительность каждого алгоритма. Я не думаю, что вы должны думать, что алгоритм, такой как ID A *, ограничен, чтобы не учитывать, достигло ли состояние. Если вы считаете, что он будет работать лучше, рассматривая повторно введенные состояния, попробуйте и посмотрите, улучшает ли ваше решение.

источник

2013-10-06 20:58:33

Почему итерационное углубление Звезда не нуждается в проверке на наличие повторяющихся состояний?

ответ

Смежные вопросы