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

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

Данная матрица / проблема

Красное поле → Где находится наш 1 (что мы хотим найти)
Желтое поле → Место, с которого мы начинаем поиск

Проблема очень проста, учитывая сетку матрицы n * n, будет один элемент с именем «1», и мы хотим найти это значение, другими словами, мы хотим знать координаты элемента 1.

Подход к поиску в глубину

Выше представлена ​​реализация DFS с рекурсией, и у нас есть переменная с именем visit (которая представляет собой список), чтобы отслеживать все координаты, которые мы посетили. И если координаты, которые мы хотим посетить следующим, отсутствуют в этом списке, мы собираемся посетить эту позицию. Чтобы наглядно представить начальную последовательность этого алгоритма поиска, см. Ниже.

Алгоритм поиска первым дыханием

Алгоритм BFS также очень похож на DFS. Но на этот раз у нас есть переменная очереди, чтобы отслеживать координаты следующего поиска, который мы собираемся выполнить. Также обратите внимание, что вместо того, чтобы передавать координаты x и y напрямую, мы просто передаем очереди. Опять же, чтобы визуализировать начало этого алгоритма.

Интерактивный код

Я перешел на Google Colab для интерактивных кодов! Таким образом, вам понадобится учетная запись Google для просмотра кодов, а также вы не можете запускать сценарии только для чтения в Google Colab, поэтому сделайте копию на своей игровой площадке. Наконец, я никогда не буду спрашивать разрешения на доступ к вашим файлам на Google Диске, просто к сведению. Удачного кодирования!

Для доступа к коду нажмите здесь.

Заключительные слова

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

Если будут обнаружены какие-либо ошибки, пожалуйста, напишите мне на [email protected], если вы хотите увидеть список всех моих писем, пожалуйста, просмотрите мой сайт здесь.

Тем временем подпишитесь на меня в моем твиттере здесь и посетите мой веб-сайт или мой канал Youtube для получения дополнительной информации. Я также сделал сравнение Decoupled Neural Network здесь, если вам интересно.

Ссылка

  1. python ?, C. (2018). Выбор случайных целых чисел, кроме определенного числа для python ?. Stackoverflow.com. Получено 11 марта 2018 г. с сайта https://stackoverflow.com/questions/17907213/choosing-random-integers-except-for-a-particular-number-for-python.
  2. Python ?, М. (2018). Измерять время, прошедшее в Python ?. Stackoverflow.com. Получено 11 марта 2018 г. с сайта https://stackoverflow.com/questions/7370801/measure-time-elapsed-in-python.
  3. 8.10. Queue - класс синхронизированной очереди - документация Python 2.7.14. (2018). Docs.python.org. Получено 11 марта 2018 г. с сайта https://docs.python.org/2/library/queue.html.
  4. [дубликат], Х. (2018). Как проверить, существует ли объект в очереди, прежде чем нажимать новый объект. Stackoverflow.com. Получено 11 марта 2018 г. с сайта https://stackoverflow.com/questions/27024881/how-to-check-if-object-exists-in-queue-before-pushing-new-object/27025015.
  5. Ошибка исправления - достигнута максимальная глубина рекурсии. (2013). Советы по Python. Получено 11 марта 2018 г. с сайта https://pythontips.com/2013/08/31/fixing-error-maximum-recursion-depth-reached/.
  6. П., Дж. (2013). sys.setrecursionlimit @ Серьезно, не используйте этот код !. Серьезно.dontusethiscode.com. Получено 11 марта 2018 г. с сайта http://seriously.dontusethiscode.com/2013/04/14/setrecursionlimit.html.
  7. Алгоритм поиска *. (2018). En.wikipedia.org. Получено 11 марта 2018 г. с сайта https://en.wikipedia.org/wiki/A*_search_algorithm.
  8. Поиск в ширину. (2018). En.wikipedia.org. Получено 11 марта 2018 г. с сайта https://en.wikipedia.org/wiki/Breadth-first_search.
  9. Поиск в глубину. (2018). En.wikipedia.org. Получено 11 марта 2018 г. с сайта https://en.wikipedia.org/wiki/Depth-first_search.