Comments 7
Немного странная постановка задачи. Обычно, если ходы по клеточкам в соседние, то все ребра считаются одинаковой длины.А если и брать фактическую геометрическую длину отрезков, то тогда непонятно, почему рассматриваются только 8 соседей? Почему бы тогда не ходить еще и по ходам коня, например? И вообще по любым отрезкам, не пересекающим препятствия? Не поймите неправильно, любая задача имеет право на жизнь. Просто мне интересно, почему именно так?
Идея со счетом в целых числах за счет работы в алгебраическом расширении целых чисел корнем из двух - весьма интересная. Однако, инетерсно было бы провести эксперимент: при каких размерах лабиринтов точности вещественных чисел будет не хватать. Может, смысла вообще в целых числах считать на практике и нет? Ибо когда речь зайдет о длинной арифметике, там уже сам лабиринт ни в какую память не влезет.
Алгоритм Ли (волновой алгоритм) не подходит, так как он подразумевает, что все ребра графа имеют одинаковую стоимость.
На самом деле есть обобщение алгоритма обхода в ширину, который ищет кратчайший путь, даже если в графе ребра разной длины. Правда, они все дложны быть целыми и ограниченными (скажем, от 0 до небольшого k). Идея алгоритма в том, чтобы поддерживать k+1 очередь вместо одной единственной в исходном алгоритме. Вершины достаются из текущей очереди и кладутся в очередь с номером + длина ребра (по модулю k+1, очереди как бы в циклическом буффере). К сожалению, этот алгоритм в вашей задаче неприменим, но мне показалось уместным его тут упомянуть.
Отличие от рассмотрения большего количества соседей ведет к появлению "скачков". Даже если мы включим ходы конем, то это уже будет неэлементарное перемещение, так как при ходе конем есть промежуточные клетки, которые нужно пройти. При рассмотрении только 8 соседей никаких промежуточных клеток между ними не возникает.
По поводу окрестности, где ходы по всем 8 направлениям стоят одинаково. Разумеется такая "классическая" постановка тоже имеет место быть. Давайте рассмотрим, почему и диагональные ходы равные корню из двух тоже имеют место быть. Для начала придумаем легенду к этой задаче. Пусть по лабиринту ездит робот. Он не поворачивается, у него есть лишь механизм переключения колес по 4 направлениям. В каждом направлении есть прямая и обратная передача. Затраты энергии на переключение колес пренебрежительно малы. Затраты энергии на передвижение пропорциональны пройденному расстоянию.
А теперь рассмотрим следующий кусочек лабиринта (# - стена, . - пустота, p и q - опорные точки, там тоже пустота).
........
.p#####.
..##....
...##..q
....##..
.....##.
........Рассмотрим следующие пути между p и q.
Вверх, 6 раз вправо, 3 вниз.
Вниз, 4 раз вниз-вправо (диагональ), вправо, вверх-вправо, 2 раза вверх.
Если по всем 8 направлениям стоимость пути одинаковая, то стоимость первого пути равна 10, а стоимость второго - равна 9. Второй путь короче первого.
Если же по диагоналям стоимость пути равна корню квадратному из двух, то длина первого пути равна 10, а длина второго - равна 
. Первый путь короче второго.
Очевидно, что для задачи с роботом подходит именно второй подход.
По поводу того насколько быстро работают числа. В постановке задачи ничего не сказано про то, что это должно работать быстрее, чем float или double. Тем не менее? некоторые попытки сделать оптимизации присутствуют. В исходном коде есть похожий тест, можно из него сделать benchmark. Я, честно сказать, не пробовал.
По поводу точности: проблемы (кстати как раз вышеописаная) начнется всего скорее тогда, когда при сложении дробная часть начнет полностью отбрасываться. Для float это уже может случаться при размерах лабиринта 2897x2897. Для double 94906265x94906265. Я, честно сказать, досконально сейчас не проверял, может быть еще что-то упустил. Замечу, что понять максимумы с составными числами гораздо проще.
По поводу задачи, да, можно придумать любую задачу. И хотя бы теоретический интерес тут всегда есть. Хоть требования дискретности предвижения по клеточками и физического вычисления длины отрезков и противоречат друг другу.
> По поводу того насколько быстро работают числа.
Нет, я не имел ввиду скорость. Просто, зачем усложнять, если double хватает с головой? Можно было бы численный эксперимент провести: сгенерировать через цепные дроби приближения к sqrt(2) (пусть будет a/b) и сравнивать -a+b*sqrt(2) с 0 как double и как у вас в статье. При каких размерах оно выдаст разный результат - это и будет размер плохого лабиринта.
Мой эксперимент показал ошибку при дроби 30122754096401/21300003689580. Т.е. в лабиринте вам придется сделать суммарно более 50 триллионов шагов, чтобы точности перестало хватать. Из них по крайней мере 20 триллионов надо будет сделать по диаганали. Т.е. размер лабиринта должен быть 50x20 триллионов. Это вообще ни в какие рамки не влезает. Кстати, float сыпется при 1855077841/1311738121 - тоже ни в какую память вы лабиринт со сторанами в пару миллиардов не засунете.
код вычисления
int main()
{
long long a = 1;
long long b = 2;
double s2 = sqrt((double)2);
std::cout.precision(20);
// Цепная дробь 1+1/(2+1/(2+1/(2+1/(2+...))
while (true) {
std::cout << a+b << '/' << b << '=' << (a+b)/(double)b <<"\n";
double x = -(a+b) + b*s2;
if ((x < 0 && b*b > a*a+2*a*b) || (x > 0 && b*b < a*a+2*a*b)) {
std::cout <<"Bad at " << a+b << " " << b << "\n";
break;
}
a+=2*b;
std::swap(a,b);
}
return 0;
}Смотрите, в Вашем примере не учтена накопительная ошибка вычисления, которая безусловно будет при сложении. Вот тут даже описано насколько может быть все плохо. Мои оценки выше по максимальной размерности лабиринта получены следующим образом.
Для float/double длины мантисс соответственно 23 и 53 бита.
Найдем значение когда при сложении дробная часть будет полностью отсутствовать в числе и игнорироваться при сложении. Это значения
и 
соответственно. Далее распишу только для float.Полученное число есть верхняя граница длины пути в лабиринте. А как мы уже знаем кратчайший путь точно не больше количества всех клеток в лабиринте. Поэтому 8388608 - это площадь лабиринта. В случае квадратного лабиринта размеры будут ~2897x2897.
При полученных размерах лабиринта теоретически может возникнуть ситуация когда мы прибавляем корень из двух, а по факту прибавляется просто 1.
Насколько вычислительные ошибки влияют в первом и последующих двоичных знаках после запятой тоже можно выяснить, но тогда оценка будет еще меньше.
Можно конечно попытаться обосновать, что кратчайший путь в пустом лабиринте - это точно не проход по всем клеткам лабиринта. Но тогда надо как-то пытаться уточнять верхнюю границу и доказывать это.
Что мне нравится в способе с целыми числами: простая доказательная база, которая еще и легко масштабируется. А мне нравится когда что-то доказано, нежели получено экспериментами с написанием кода.
Дополнительным плюсом является сравнение на равенство при извлечении из очереди с приоритетом. В случае с double/float придется либо вводить точность сравнения, либо слепо обрабатывать такие вершины. В случае с составными числами - это просто операция ==.
Так или иначе, наличие нашей с Вами дискуссии свидетельствует о более сложной природе float и double по сравнению с целыми числами.
Да, вы правы, ошибка случится гораздо раньше из-за прибавления маленьких чисел к большому. И я считал, что путь идет почти прямой, но вы правы - он может быть весьма извилисто и плотно упакован в лабиринт. Думаю, что ваши оценки, все-таки довольно сильно занижены, ибо путь хоть и может быть плотным в лабиринте, надо, чтобы было несколько путей примерно одинаковой длины. Возможно это можно сделать лишь слегка поизменяв окресность финиша.
В любом случае, float вообще никуда не годится - это точно.
"Хотим искать кратчайшие в евклидовой метрике пути в лабиринте на квадратной сетке где можно ходить на 8 соседей, при этом погрешности недопустимы. Для этого берём любой алгоритм поиска кратчайшего пути, длину представляем в виде суммы целой части с частью содержащей квадратный корень в качестве множителя, учимся сравнивать представленные таким образом числа - для этого группируем целые части и части с корнями и сравниваем их квадраты." Это всё содержание статьи. Какой смысл несет остальная псевдоматематически-формальная вода?
Вы описали "что" делается в статье. Но сама статья о том "как" это делается.
Как не написать "простыню" из if'ов при реализации сравнения.
Как сделать так, чтобы сравнение работало на всех возможных парах в рамках выбранной разрядной сетки. С доказательной базой.
Как сделать так, чтобы при сравнении не использовать разрядную сетку в 4 раза больше.
Как от решений неравенств и уравнений перейти сразу к компараторам. Эта часть может быть использована везде, где написание компаратора сводится к решению уравнений/неравенств.
Анализ максимумов (размер лабиринта) и (неявная) демонстрация простоты ее обоснования (по сравнению с float/double).
Поиск пути в ВГД-лабиринте