apodavalov 29 мар в 07:55

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

Средний

8 мин

1.3K

Алгоритмы*

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

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

Прямоугольный и описывается матрицей размера $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). Данная статья немного отличается от обычных моих статей на канале, так как рассматривает довольно специализированный алгоритм.

Теги:

Хабы:

Алгоритмы

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

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

Идея решений

Сложение

Сравнение

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

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

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

Сложение

Сравнение

Бонус

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

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

Публикации

Истории

Ближайшие события