Изучение алгоритмов поиска пути и решения лабиринта для людей, не связанных с CS: выберите свое собственное приключение
В детстве я любил книги Выбери свое собственное приключение. Для вас, миллениалы, это было как ClickVentures, только с книгами. Читатель должен принять решение о том, как продолжить рассказ - Повернуть налево? перейдите на страницу 10. Поверните направо? Перейдите на страницу 57. (Ой-ой! Вы попали в рыболовную сеть. КОНЕЦ). В то время я этого не знал, но это форма решения лабиринта. Это метод проб и ошибок - мы прорабатываем каждое решение, пока не встретим неудачный конец, либо не решим головоломку и не добьемся успеха (или мы обманываем и просто пролистываем, пока не найдем лучший конец). Что-то вроде этого:
Выглядит знакомо? Если вы изучали деревья, вы, вероятно, заметили, что это похоже на то, как мы ищем их. Может быть, поэтому, когда я впервые попытался написать алгоритм поиска пути, я придумал что-то вроде этого. Я пытался решить проблему кодирования (найдите ее здесь на CodeWars), которая обманчиво проста - у вас есть простой 2D-лабиринт с начальной точкой и целью, которая выглядит примерно так: (X - стены, __ ' s - пути, S - начало, G - цель).
S___XX
__X__X
X_XX__
__XXX_
_XXG__
Мы можем идти только в 4 направлениях - вверх, вниз, влево и вправо. Это легко решить людям - Вправо, Вправо, Вниз, Вправо, Вниз, Вправо, Вниз, Вниз, Влево, Цель! Всего 10 шагов. Но как насчет компьютеров? Работает ли наш алгоритм «выбери свое приключение»? Да! Будет. Мы просто пробуем каждый путь, пока не перестанем идти дальше или не достигнем цели. Оно работает. Моим решением было прохождение тестов для маленьких лабиринтов, но время ожидания для больших лабиринтов истекло. Он не мог их закончить вовремя. Я думал, что проблема в том, как я написал алгоритм. Я перешел на рекурсивное решение с итеративного решения - qaru. Я избавился от всех своих медленных операций - array.shift работает слишком медленно !! Сделайте это хеш-таблицей !! string.indexOf по сравнению со строкой [i], что быстрее ??? Может быть, Javascript недостаточно быстр, может, мне нужно использовать C # !! Были постепенные улучшения времени, более чем на 20%, но этого было недостаточно. Процесс занял слишком много времени или превышен максимальный размер стека вызовов.
В конце концов мне пришлось столкнуться с фактами - все оптимизации в мире мне не помогли. Пробовать каждый путь грубой силой просто слишком долго. Что делать, если лабиринт имеет размер 1 000 x 1 000 или 1 000 000 x 1 000 000? Наш оригинальный алгоритм работает, но ОЧЕНЬ медленно. В худшем случае нам нужно искать каждого соседа каждой точки на графике. (Каждое ребро и каждая вершина в терминах информатики). Мы можем записать это как O (| V | + | E |). Поскольку у большинства наших точек 4 соседа, мы знаем, что в худшем случае потребуется больше времени, чем O (n²), где n - длина стороны квадратного лабиринта. Этого недостаточно.
Итак, как мы можем сделать алгоритм лучше? Особенность книг по выбору приключений заключалась в том, что через некоторое время вы устали и вас обманули. Вы просматривали книгу, пока не нашли хороший конец, а оттуда прокручивали путь назад, пока не нашли правильный путь. (По крайней мере, я это сделал. Я также пытался снимать и перемещать наклейки на моем кубике Рубика) Мы можем сделать то же самое с нашим графиком. Мы уже знаем, где находится финал, поэтому можем угадать, приближаемся мы или отдаляемся от него с каждым шагом. Если мы только попытаемся приблизиться к цели, мы доберемся до нее быстрее, чем просто попробуем любой старый путь, который встретим. Это эвристика. Это ярлык, который помогает нам быстрее решить проблему.
В нашей задаче о двумерном лабиринте мы можем просто использовать расстояние, чтобы проверить, приближаемся ли мы к нашей цели или отдаляемся. если мы приближаемся, продолжай! Если мы уходим еще дальше, лучше сначала попробуй другой путь. Вот и все.
Используя этот новый алгоритм, мое решение наконец прошло испытания. Это было более чем в 10 раз быстрее, чем исходное решение, и оно включает в себя множество трудоемких операций, таких как array.shift и * gasp * сортировка массива на каждой итерации. Но это неважно. Алгоритм намного лучше, и это нивелирует разницу во времени отдельных операций.
Мораль истории: во-первых, постарайтесь делать что-то по старинке. Если это слишком медленно, обманывайте. Вы можете обнаружить, что у вас есть инсайдерская информация, которую вы можете использовать для получения несправедливого преимущества.
Удачного кодирования.
Ресурсы: Книги CYOA, Поиск пути, Алгоритм поиска A *, моя страница на GitHub
