На Открытии Пути: подробное описание для неспециалиста D* алгоритм
Используйте евклидов алгоритм 1 sup>:
- Пусть a будет большим из двух заданных натуральных чисел и [113 ] b будет меньше.
- Пусть r будет остатком от a , разделенным на b .
- Если r равно нулю, мы закончили, и b - наибольший общий делитель.
- В противном случае, пусть a принимает значение b , пусть b принимает значение r и переходят к шагу 2 .
Как только у вас будет наибольший общий делитель, вы можете разделить на него исходные два числа, что даст два числа с одинаковым отношением, но без каких-либо общих факторов, превышающих единицу.
Цитирование
1 sup> Евклид, Элементы , книга VII, предложения 1 и 2, около 300 г. до н.э.
Примечания
Евклид использовал вычитание, которое здесь было заменено на остаток.
Как только этот алгоритм заработает, вы можете рассмотреть немного более сложный двоичный GCD , который заменяет деление (которое медленно на некоторых процессорах) вычитанием и битовыми операциями.
1 ответ
Как я понимаю, в первый раз, когда Вы выполняете D*, он находит тот же путь как* почти с тем же временем выполнения. Однако то, когда узел изменяется, это - граничное значение, или узлы добавляются*, повторно вычисляет ВЕСЬ путь, в то время как D* просто повторно вычисляет непоследовательные узлы во второй раз вокруг, а не все это.
D Anthony Stentz* алгоритм (исходное техническое описание здесь) был в основном удержан от использования производными его работы. D* Облегченный и LPA* обычно найдены и намного легче кодировать/реализовать.
До опыта реального мира Joseph Carsten и Искусства Rankin из Лаборатории реактивного движения НАСА установил версию Поля D* использование элементов D* Облегченный на марсоходах Марса "Дух" и "Возможность" (слайд-шоу с марсоходами с помощью D* здесь). В 2007 Feburary это использовалось, чтобы полностью переместиться по марсоходу Марса автономно.
сопроводительный текст http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg
По-видимому, D* действительно полезно в домене робототехники, потому что роботы встроенные датчики постоянно переоценивают граничные значения. Это сделало бы это симпатичным "сражением протестированный" по моему собственному мнению.
Точно так же я нашел другое техническое описание, которое упоминает использование D* Облегченный алгоритм в Мобильных Играх.
Я закончу этот ответ путем заявления, что я никогда не реализовывал D* прежде, только A*. Из-за значительного увеличения сложности я сказал бы, что D* (или D* Облегченный) должны только использоваться в случаях, где существует значительные и частые изменения в графике. Вы описали свою ситуацию, как являющуюся подобным этому так, я скажу, определенно идут для D* Облегченный. Если НАСА использует его, Вы могли бы безопасно держать пари, что это было полностью исследовано.