Поиск пути в ВГД-лабиринте / forpes.ru

Главная
Поиск пути в ВГД-лабиринте

Поиск пути в ВГД-лабиринте

29.03.2024 04:55

apodavalov 5 729 Источник

Введение и постановка задачи

Будем обозначать лабиринт аббревиатурой ВГД, если он.

Прямоугольный и описывается матрицей размера $m \times n$ , где в каждой клетке (ячейки матрицы) закодирован признак проходимости.
Из каждой проходной клетки можно пройти в любую соседнюю проходную клетку по вертикали, по горизонтали и по обеим диагоналям, при условии что последняя существует.

Стоимость перемещения в соседнюю клетку по вертикали или по горизонтали равна . Стоимость перемещения в соседнюю клетку по любой из диагоналей равна $\sqrt2$ .

Перемещение в соседнюю клетку будем называть элементарным перемещением.

Поставка задачи. Найти кратчайший путь в заданном лабиринте между двумя проходными клетками этого лабиринта. При нахождении пути допускается использовать только целочисленные переменные. Погрешности в вычислениях не допускаются. Алгоритм должен (хотя бы в теории) работать со сколь угодно большими лабиринтами.

Идея решений

Для нахождения кратчайшего пути можно использовать либо алгоритм Беллмана-Форда, либо алгоритм Дейкстры. Алгоритм Ли (волновой алгоритм) не подходит, так как он подразумевает, что все ребра графа имеют одинаковую стоимость. Алгоритм Флойда-Уоршелла для поиска кратчайших путей от каждой к каждой вершине тоже теоретически будет работать, но будет требовать (как минимум в худшем случае) $m^2 \times n^2$ памяти для промежуточных вычислений и результата.

Итак, как уже можно догадаться, необходимо придумать и запрограммировать некоторый тип данных, который будет хранить расстояния.

Оба алгоритма предполагают использование всего лишь двух операций с числами.

Сложение
Сравнение

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

Если просуммировать только длины элементарных перемещений по горизонталям и вертикалям, то получится число вида: , где – целое неотрицательное число.

Если просуммировать только длины элементарных перемещений по диагоналям, то получится число вида: $b\sqrt2$ , где – целое неотрицательное число.

Таким образом, длина всего пути будет равна сумме этих двух чисел: $a+b\sqrt2$ . Далее будем называть такие числа составными. Соответствующий тип данных тоже будем называть составным числом. Очевидно, что в качестве полей составного числа будут только два значения и .

Для составных чисел достаточно реализовать операцию сложения и операцию сравнения. Если это удастся сделать, то и вышеперечисленные алгоритмы смогут использовать составные числа для решения поставленной задачи: нахождение кратчайшего пути.

Приступим к анализу операций.

Сложение

Постановка задачи. Пусть имеются два числа: $c_1=a_1+b_1\sqrt2$ и $c_2=a_2+b_2\sqrt2$ , где – некоторые целые числа. Нужно найти их сумму: .

Решение. Находим: $c=a_1+b_1\sqrt2+a_2+b_2\sqrt2=(a_1+a_2) + (b_1+b_2)\sqrt2$ . Таким образом, для нахождения суммы достаточно просто сложить соответствующие части исходных чисел.

Сравнение

Общие сведения и вспомогательное свойство

Для обоих алгоритмов достаточно реализовать операцию больше. Тем не менее, алгоритм Дейкстры для нахождения непосещенной вершины с минимальной длиной пути может использовать очередь с приоритетом вместо линейного поиска. Какой бы ни был тип элемента такой очереди, необходимо уметь его сравнивать с другим объектом того же типа. Зачастую для этого используют компаратор, который способен показать как соотносятся два объекта. Такой компаратор принимает два объекта и выдает одно из следующих трех значений.

Меньше: первый аргумент меньше второго (обычно кодируется значением )
Равно: аргументы равны (обычно кодируется значением )
Больше: первый аргумент больше второго (обычно кодируется значением )

Будем рассматривать сравнение двух наших чисел “сквозь призму” реализации такого компаратора. Далее операцию, которую реализует такой компаратор будем называть операцией соотношения и обозначать символом $\Leftrightarrow$ .

Введем унарную операцию инвертирования результата операции соотношения. Покажем, что получается в результате ее применение в следующей таблице.

Результат операции соотношения	Инвертирование результата операции соотношения
Меньше	Больше
Равно	Равно
Больше	Меньше

При кодировании результата вышеуказанными значениями, операция инвертирования результата операции соотношения есть ни что иное как операция унарный минус. Поэтому для краткости будем называть ее унарным минусом и обозначать знаком –.

В рамках задачи, которая будет поставлена ниже, необходимо будет решить 4 неравенства $(>,<,\leq, \geq)$ и уравнение. Для того чтобы обобщить эти решения, перейдем от решения неравенств и уравнений к решению соотношений. Как нетрудно догадаться, соотносить два объекта будем с помощию операции $\Leftrightarrow$ .

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

Будем использовать знак $\bullet$ для обобщения всех знаков неравенств.

Умножение неравенства на отрицательное число можно разбить на два этапа. Пусть производится умножение некоторого неравенства на отрицательное число . Число всегда можно разложить на следующие множители: и . Обе части неравенства можно сначала умножить на положительное число . А затем уже умножить неравенство на и поменять знак на противоположный. Так как это всегда можно сделать, далее будем говорить только об умножении неравенства на .

Пусть у нас имеется некоторое верное неравенство $x \bullet y$ . Выполним следующую последовательность действий с этим неравенством. На каждом шаге вновь полученное неравенство остается верным.

Умножим обе части неравенства на , знак неравенства при этом меняется на противоположный.
Перенесем правую часть неравенства влево, а левую часть неравенства – вправо.
Снова умножим обе части неравенства на и поменяем знак.

Так как при переносе из одной части неравенства в другую происходит смена знака переносимой части на противоположный, то в результате выполненных действий произошла смена знака дважды. Неравенство приняло вид: $-y \bullet -x$ . Данный факт означает, что умножение на отрицательное число и смены знака неравенства равносильно умножению на то же самое отрицательное число и обмену левой и правой части неравенства. При этом смены знака неравенства не происходит.

Очевидно, что операция соотношения тоже должна выдавать тот же результат, если оба аргумента умножены на и произведен их обмен. Как меняется результат операции соотношения, если произведен обмен аргументов? Очевидны следующие утверждения.

Если результат операции был больше, то он должен стать меньше.
Если результат операции был меньше, то он должен стать больше.
Если результат операции был равно, то он должен остаться без изменений.

Таким образом, если мы вернем аргументы на свои места, но оставим их умноженными на , то результат операции должен быть инвертирован.
Итак, получилось многословно, но вспомогательное свойство, которое пригодится позже получено: $-x \Leftrightarrow -y \equiv -(x \Leftrightarrow y )$ .

Постановка задачи и решение

Постановка задачи. Пусть имеются два числа: $c_1=a_1+b_1\sqrt2$ и $c_2=a_2+b_2\sqrt2$ , где , , , – некоторые целые числа. Соотнести и .

Решение. Наше соотношение имеет вид: $a_1+b_1\sqrt2 \Leftrightarrow a_2+b_2\sqrt2$ .

Перенесем все в левую сторону и сгруппируем: $(a_1-a_2)+(b_1-b_2)\sqrt2 \Leftrightarrow 0$ .
Заметим, что выполненное действие есть ни что иное как вычитание. Введем следующие замены: , . Подставляем и получаем: $a+b\sqrt2 \Leftrightarrow 0$ . Видно, что соотношение упростилось, поэтому наше составное число получает еще одну операцию: вычитание. А соотносить будем разность первого и второго аргумента с нулем.

Итак, наше соотношение $a+b\sqrt2 \Leftrightarrow 0$ . Перенесем $b\sqrt2$ вправо и получим $a \Leftrightarrow -b\sqrt2$ .
Домножим левую часть неравенства на , а правую на $|b\sqrt2|$ . Это почти возведение в квадрат, но и в то же время умножение на неотрицательное число. Модуль затем можно будет раскрыть, рассмотрев 4 случая.

Итак, имеем: $a|a| \Leftrightarrow -|b\sqrt2|b\sqrt2$ .
Сведем случаи в таблицу.

№ п/п	Описание случая	Неравенство
1	$a \geq 0, b \geq 0$	$a^2 \Leftrightarrow -2b^2$
2	$a \geq 0, b < 0$	$a^2 \Leftrightarrow 2b^2$
3	$a < 0, b \geq 0$	$-a^2 \Leftrightarrow -2b^2 \rightarrow -(a^2 \Leftrightarrow 2b^2)$
4		$-a^2 \Leftrightarrow 2b^2$

После некоторого осмысливания полученных результатов введем функцию получения знака числа: $Sgn(v) =\{1, v>0; 0, v=0;-1,v<0\}$ и набросаем следующий алгоритм.

.
Если или , то возвращаеми завершаем алгоритм.
Если , то возвращаем и завершаем алгоритм.
Возвращаем $s_a \times (a^2 \Leftrightarrow 2b^2)$ .

Опишем шаги более подробно.

Вычисление знаков и .
Рассмотрим три случая.
1. Если и и , то значит и и , из чего следует, что соотносимые числа равны. Поэтому возвращаем значение .
2. Если $s_a \neq 0$ и , то . Число, которое соотносится с нулем: $a+0\sqrt2=a$ . Если , то , что означает, что первый аргумент больше второго. Если , то , что означает, что первый аргумент меньше второго.
3. Если и $s_b \neq 0$ , то . Число, которое соотносится с нулем: $0+b\sqrt2=b\sqrt2$ . Если , то , что означает, что первый аргумент больше второго. Если , то , что означает, что первый аргумент меньше второго.
На этом шаге мы уже точно знаем, что $s_a,s_b \in \{-1;1\}$ . Условие проверяет одинаковые ли знаки чисел и или нет. Если да, то любое (так как они одинаковые) из этих значений и будет результатом соотношения.
1. Если и , а значит и . Т. е. число, которое соотносится с нулем – положительное. Последнее означает, что первый аргумент больше второго.
2. Если и , а значит и . Т. е. число, которое соотносится с нулем – отрицательное. Последнее означает, что первый аргумент меньше второго.
На этом шаге мы уже точно знаем, что осталось два случая.
1. Если и , а значит и . Тогда нужно вернуть $a^2 \Leftrightarrow 2b^2$ . Умножение на ничего не меняет, так как это умножение на единицу.
2. Если и , а значит и . Тогда нужно вернуть $-(a^2 \Leftrightarrow 2b^2)$ . Умножение на меняет знак на противоположный.

Нюансы машинных вычислений

Сложение

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

Итак, теоретически кратчайший путь максимальный длины – это путь проходящий через все клетки лабиринта. Длина такого пути (т. е. ограничение сверху):

, если все перемещения между клетками по вертикали или по горизонтали
$mn\sqrt2$ , если все перемещения между клетками по диагонали.

В первом случае достигает , во втором – . Таким образом, самое большое значение которое могут принимать и – это . Так как и знаковые целые числа, то целочисленный тип для них нужно выбирать так, чтобы $mn \leq 2^{x-1}-1$ , где – натуральное число, количество бит в разрядной сетке. Обычно выбираются значения с размером разрядной сетки 8, 16, 32, 64 и т. д. битов.

Сравнение

Для анализа операции сравнения на предмет переполнений можно выполнить следующие шаги.

Найти максимальное по абсолютному значению число (результат).
Возвести это значение в квадрат, а затем удвоить.
Посмотреть на получившееся значение и понять какая разрядная сетка требуется для поддержания корректности.

В постановке задачи выше не требуется использование составных чисел ни для чего иного, кроме как для поиска кратчайшего пути. Тем не менее, хочется решить задачу “красиво”. Поэтому попытаемся сделать составные числа более универсальными и, таким образом, “оторвать” их от лабиринтов. Для этого вышеприведенный способ не годится (точнее он не самый лучший). Почему это так? Любопытному читателю предлагается разобраться самостоятельно.

Продолжим. Преобразуем выражение $a^2 \Leftrightarrow 2b^2$ поэтапно следующим образом.

$a^2 \Leftrightarrow b^2+b^2$
$a^2-b^2 \Leftrightarrow b^2$

Далее будем работать только с выражением $a^2-b^2 \Leftrightarrow b^2$ .

Как видим, в первую очередь надо вычислить и . Максимально возможное значение получается при возведении в квадрат следующего числа: $(2^{x-1}-1)-(-2^{x-1})=2^x-1$ , где– размер разрядной сетки. Возводим: $(2^x-1)^2=2^{2x}-2^{x+1}+1$ .

Значение полученное выше входит в диапазон чисел без знака разрядной сетки удвоенного размера: $0<2^{2x}-2^{x+1}+1<2^{2x}-1$ . В диапазон чисел со знаком разрядной сетки удвоенного размера значение входит только тогда, когда . Это можно легко проверить, решив неравенство $2^{2x}-2^{x+1}+1 \leq 2^{2x-1}-1$ . Разрядная сетка размера 1 для решения поставленной задачи вряд ли будет интересна.

Таким образом, для вычисления правильных значений выражений и достаточно использования разрядной сетки удвоенного размера. Значение должно быть беззнаковое. Пример: если и являются 32-битными числами со знаком, то их квадраты нужно хранить в 64-битных числах без знака.

Далее заметим, что если , то , значит результат должен быть меньше, так как любое отрицательное число меньше неотрицательного. Если же $a^2 \geq b^2$ , то переноса при вычитаний не возникнет и можно будет соотнести и без проблем.

Замечание: операция вычитания теперь включает в себя расширение разрядной сетки. Так как теперь это довольно специализированная процедура, выносить ее в таком виде в интерфейс составных чисел нет необходимости. Поэтому наше составное число либо совсем лишается этой операции, либо она должна быть реализована отдельно от сравнения.

Итоговый алгоритм вычисления $a^2-b^2 \Leftrightarrow b^2$ (используется в 4-ом пункте основного алгоритма сравнения). Числа и – это результат вычитания соотносимых чисел. Для их хранения используется уже удвоенная (относительно аргументов соотношения) разрядная сетка.

Вычислить абсолютное значение и преобразовать к числу без знака c разрядной сеткой той же размерности.
Возвести полученное на предыдущем шаге значение в квадрат.
Выполнить предыдущие пункты для значения .
Если или , то вернуть . В противном случае, вернуть .

Бонус

Для использования с лабиринтами и алгоритмами поиска кратчайших путей удобно выделить следующие элементарные значения нашего составного числа: , , $\sqrt2$ .

Значение


$\sqrt2$

Примеры лабиринтов и найденных путей

Вместо заключения

Весь код тут: https://github.com/apodavalov/maze. Алгоритм сравнения незначительно отличается от описанного в этой статье.

Насколько описаное в этой статье полезно – решать Вам. Задача минимум точно решена: получился хороший just for fun.

Статьи в подобном стиле, разбирающие различные алгоритмы и структуры данных, можно найти на моём Telegram канале (https://telegram.me/GetHiredByFAANG). Данная статья немного отличается от обычных моих статей на канале, так как рассматривает довольно специализированный алгоритм.

Комментарии (5)

wataru
30.03.2024 09:40
#26668469
Немного странная постановка задачи. Обычно, если ходы по клеточкам в соседние, то все ребра считаются одинаковой длины.А если и брать фактическую геометрическую длину отрезков, то тогда непонятно, почему рассматриваются только 8 соседей? Почему бы тогда не ходить еще и по ходам коня, например? И вообще по любым отрезкам, не пересекающим препятствия? Не поймите неправильно, любая задача имеет право на жизнь. Просто мне интересно, почему именно так?

Идея со счетом в целых числах за счет работы в алгебраическом расширении целых чисел корнем из двух - весьма интересная. Однако, инетерсно было бы провести эксперимент: при каких размерах лабиринтов точности вещественных чисел будет не хватать. Может, смысла вообще в целых числах считать на практике и нет? Ибо когда речь зайдет о длинной арифметике, там уже сам лабиринт ни в какую память не влезет.

Алгоритм Ли (волновой алгоритм) не подходит, так как он подразумевает, что все ребра графа имеют одинаковую стоимость.

На самом деле есть обобщение алгоритма обхода в ширину, который ищет кратчайший путь, даже если в графе ребра разной длины. Правда, они все дложны быть целыми и ограниченными (скажем, от 0 до небольшого k). Идея алгоритма в том, чтобы поддерживать k+1 очередь вместо одной единственной в исходном алгоритме. Вершины достаются из текущей очереди и кладутся в очередь с номером + длина ребра (по модулю k+1, очереди как бы в циклическом буффере). К сожалению, этот алгоритм в вашей задаче неприменим, но мне показалось уместным его тут упомянуть.
1. apodavalov Автор
  30.03.2024 09:40
  #26669955
  Отличие от рассмотрения большего количества соседей ведет к появлению "скачков". Даже если мы включим ходы конем, то это уже будет неэлементарное перемещение, так как при ходе конем есть промежуточные клетки, которые нужно пройти. При рассмотрении только 8 соседей никаких промежуточных клеток между ними не возникает.
  
  По поводу окрестности, где ходы по всем 8 направлениям стоят одинаково. Разумеется такая "классическая" постановка тоже имеет место быть. Давайте рассмотрим, почему и диагональные ходы равные корню из двух тоже имеют место быть. Для начала придумаем легенду к этой задаче. Пусть по лабиринту ездит робот. Он не поворачивается, у него есть лишь механизм переключения колес по 4 направлениям. В каждом направлении есть прямая и обратная передача. Затраты энергии на переключение колес пренебрежительно малы. Затраты энергии на передвижение пропорциональны пройденному расстоянию.
  
  А теперь рассмотрим следующий кусочек лабиринта (# - стена, . - пустота, p и q - опорные точки, там тоже пустота).
  
  ........ .p#####. ..##.... ...##..q ....##.. .....##. ........
  
  Рассмотрим следующие пути между p и q.
  
  Вверх, 6 раз вправо, 3 вниз.
  
  Вниз, 4 раз вниз-вправо (диагональ), вправо, вверх-вправо, 2 раза вверх.
  
  Если по всем 8 направлениям стоимость пути одинаковая, то стоимость первого пути равна 10, а стоимость второго - равна 9. Второй путь короче первого.
  Если же по диагоналям стоимость пути равна корню квадратному из двух, то длина первого пути равна 10, а длина второго - равна $4+5\sqrt2$ . Первый путь короче второго.
  
  Очевидно, что для задачи с роботом подходит именно второй подход.
  
  По поводу того насколько быстро работают числа. В постановке задачи ничего не сказано про то, что это должно работать быстрее, чем float или double. Тем не менее? некоторые попытки сделать оптимизации присутствуют. В исходном коде есть похожий тест, можно из него сделать benchmark. Я, честно сказать, не пробовал.
  
  По поводу точности: проблемы (кстати как раз вышеописаная) начнется всего скорее тогда, когда при сложении дробная часть начнет полностью отбрасываться. Для float это уже может случаться при размерах лабиринта 2897x2897. Для double 94906265x94906265. Я, честно сказать, досконально сейчас не проверял, может быть еще что-то упустил. Замечу, что понять максимумы с составными числами гораздо проще.
  1. wataru
    30.03.2024 09:40
    #26670923
    По поводу задачи, да, можно придумать любую задачу. И хотя бы теоретический интерес тут всегда есть. Хоть требования дискретности предвижения по клеточками и физического вычисления длины отрезков и противоречат друг другу.
    
    > По поводу того насколько быстро работают числа.
    
    Нет, я не имел ввиду скорость. Просто, зачем усложнять, если 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; }
    
    apodavalov Автор
    30.03.2024 09:40
    #26671807
    Смотрите, в Вашем примере не учтена накопительная ошибка вычисления, которая безусловно будет при сложении. Вот тут даже описано насколько может быть все плохо. Мои оценки выше по максимальной размерности лабиринта получены следующим образом.
    
    Для float/double длины мантисс соответственно 23 и 53 бита.
    
    Найдем значение когда при сложении дробная часть будет полностью отсутствовать в числе и игнорироваться при сложении. Это значения $2^{23}=8388608$ и $2^{53}$ соответственно. Далее распишу только для float.
    
    Полученное число есть верхняя граница длины пути в лабиринте. А как мы уже знаем кратчайший путь точно не больше количества всех клеток в лабиринте. Поэтому 8388608 - это площадь лабиринта. В случае квадратного лабиринта размеры будут ~2897x2897.
    
    При полученных размерах лабиринта теоретически может возникнуть ситуация когда мы прибавляем корень из двух, а по факту прибавляется просто 1.
    
    Насколько вычислительные ошибки влияют в первом и последующих двоичных знаках после запятой тоже можно выяснить, но тогда оценка будет еще меньше.
    
    Можно конечно попытаться обосновать, что кратчайший путь в пустом лабиринте - это точно не проход по всем клеткам лабиринта. Но тогда надо как-то пытаться уточнять верхнюю границу и доказывать это.
    
    Что мне нравится в способе с целыми числами: простая доказательная база, которая еще и легко масштабируется. А мне нравится когда что-то доказано, нежели получено экспериментами с написанием кода.
    
    Дополнительным плюсом является сравнение на равенство при извлечении из очереди с приоритетом. В случае с double/float придется либо вводить точность сравнения, либо слепо обрабатывать такие вершины. В случае с составными числами - это просто операция ==.
    
    Так или иначе, наличие нашей с Вами дискуссии свидетельствует о более сложной природе float и double по сравнению с целыми числами.
    
    wataru
    30.03.2024 09:40
    #26671855
    Да, вы правы, ошибка случится гораздо раньше из-за прибавления маленьких чисел к большому. И я считал, что путь идет почти прямой, но вы правы - он может быть весьма извилисто и плотно упакован в лабиринт. Думаю, что ваши оценки, все-таки довольно сильно занижены, ибо путь хоть и может быть плотным в лабиринте, надо, чтобы было несколько путей примерно одинаковой длины. Возможно это можно сделать лишь слегка поизменяв окресность финиша.
    
    В любом случае, float вообще никуда не годится - это точно.