Решение лабиринта с числовым бункером

18

Моему 8-летнему надоело создавать обычные лабиринты, и он занялся созданием вариантов, которые выглядят так:

Образец номерного бункера

Идея состоит в том, чтобы начать с x и достичь o по обычным правилам. Кроме того, вы можете переходить с любого целого числа a на любое другое целое число б , но вы должны заплатить |a-б|долларов за привилегию. Цель состоит в том, чтобы решить лабиринт за наименьшую стоимость. В приведенном выше примере мы можем перейти от x к o через x-14-18-27-28-o по цене 5, но дешевле перейти к x-13-11-9-8-29-28-o только 4.

Итак, вот мой вопрос: какое наилучшее решение (с точки зрения асимптотического времени выполнения) вы можете придумать для решения этой проблемы? Вы можете сделать любые разумные предположения о формате ввода.

Примечание. Я использую тег «головоломки», потому что у меня есть ответ О(N2) , но я не уверен, что он оптимален, и хотел бы посмотреть, сможет ли кто-нибудь еще улучшить мое решение. (Здесь N - число целых чисел в лабиринте.)

Fixee
источник
7
Реквизит вашего ребенка для создания таких творческих и математических головоломок!
bbejot
2
@bbejot Вы должны увидеть некоторые вещи, которые он спрашивает у меня ... иногда я не могу ответить на его вопросы. Например, math.stackexchange.com/questions/33094/…
Fixee
1
Я не уверен, что ваши расчеты стоимости верны. x-14-18-27-28-o должен стоить а x-13-11-9-8-29-28-o - 2 + 2 + 1 + 21 + 1 = 27 . 4+9+1знак равно142+2+1+21+1знак равно27
Дейв Кларк,
1
@ Не все переходы - это прыжки. Мы могли бы написать 'ab' для прыжков (которые имеют стоимость ) и 'a-> b' для перехода по графику от a до b (который имеет стоимость 0 ), что разрешено только в том случае, если они достижимы, не ломая стену в лабиринте. В этой записи мы имеем x-> 14-18-> 27-28-> o и стоимость 5 и x-> 13-11-> 9-8-> 29-28-> o. Я чувствую, что Fixee не вводил эту запись из-за ее избыточности: нет смысла прыгать дважды, и, таким образом, прыжки и прогулки в лабиринте будут чередоваться. |ab|0
Артем Казнатчеев
2
Это отличная домашняя задача!
Джефф

Ответы:

15

Вы можете решить это за используя вариацию алгоритма Дейкстры. Мы можем избежать не всех обновлений расстояния при посещении нового узла. Если мы посещаем узел y , нам нужно только обновить расстояния всего, что можно пройти, от y до 0 и обновить расстояния до двух узлов y - и y + с ближайшими значениями до y, меньшими и большими, чемO(nlogN)YYY-Y+Y которые не имеют был выбранY

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

Каждый узел обновляется до 0 не более одного раза (если мы выталкиваем все узлы с нулевым расстоянием из очереди, чтобы избежать квадратичного поведения), и каждый раз, когда мы добавляем узел, мы делаем только O (1) других обновлений. Поиск значений и y + можно выполнить за линейное время, если мы также сохраним упорядоченный двусвязный список всех узлов, отсортированный по их целочисленным значениям. Построение этого двусвязного списка занимает O ( n log n ) времени, и, наконец, O ( n ) обновляется и выскакивает из кучи, занимает O ( n log n ) времени, для общего времени выполненияY-Y+О(NжурналN)О(N)О(NжурналN)О(NжурналN)

Дейв
источник
Вероятно, это можно немного улучшить, используя сортировку и очереди приоритетов, которые специализированы для целых чисел, но вы не можете сделать это лучше, чем целочисленная сортировка, как видно из следующего сокращения: если у нас есть список целочисленных значений , установите x, чтобы он был в два раза меньше их, а o, чтобы он был в два раза больше максимума. Создайте область со значениями 2 x i и 2 x i + 1 друг для друга x i . Наилучшее решение проходит через каждый регион в порядке сортировки по x i и, таким образом, производит сортировкуx1,...,ИксNИксо2Икся2Икся+1ИксяИкся значения. Икся
Дейв
Дэйв прав, это можно уменьшить до , только обновив y + и y - . Кроме того, вместо того, чтобы соединять каждый узел в области с каждым другим узлом в регионе, их нужно только соединить с 1 или 2 другими узлами в регионе (создавая путь). Таким образом, каждый узел имеет только до 4 ребер. Тогда алгоритм Дейкстры (с очередью с минимальным приоритетом) может быть применен, предоставляя O ( n l g n ) время. О(NLграммN)Y+Y-О(NLграммN)
bbejot
@bbejot: Но если это так, разве очередь с интегрированным приоритетом от Thorup не улучшит время выполнения до О(NжурналжурналN) или даже до с помощью некоторого дополнительного метода группирования в неориентированной ситуации? О(N)
Сянь-Чи Чан 4 之
4

Я чувствую, что может быть лучшим, что вы можете получить.О(N2)

Кажется естественным преобразовать это в задачу кратчайшего пути со специальным начальным узлом (x) и конечным узлом (0). Также будет один другой узел для каждого из номеров. И x, и 0 имеют ребра веса 0 для всех числовых узлов, которые достижимы в лабиринте. Все числовые узлы связаны либо с весом 0 (если числа достижимы по лабиринту), либо с разницей между числами (если недоступно по лабиринту).

Кратчайший путь в этом графе не может быть решен менее чем за потому что граф имеет примерно n 2 ребер, и в худшем случае каждый должен был бы просматривать каждый случай один раз. Таким образом, алгоритм Дейкстры для кратчайшего пути занимает время O ( n 2 ) и является оптимальным в худшем случае.О(N2)N2О(N2)

bbejot
источник
Это ответ, который я имел в виду; Конечно, вы должны использовать правильную структуру данных с алгоритмом Дейкстры, чтобы получить времени выполнения. Использование типичной двоичной кучи даст O ( n 2 lg n )О(N2)О(N2Л.Г.N) .
Fixee
1
Я думал об этой проблеме сегодня утром, и ее можно немного ускорить. Вместо использования одного узла для каждого числа в лабиринте, используйте один узел для каждой области лабиринта. Тогда стоимость между узлами - это наименьшая стоимость перехода из одного региона в другой. Начальным узлом является область с x, а конечным узлом является область с 0. Если имеется областей, то это можно решить за O ( r 2 ) способами, которые мы обсуждали. rO(r2)
bbejot
Вам также нужно время для создания графика, поэтому общее время работы должно быть O ( r 2 + n log n ) . Даже если есть только две области, вам нужно найти ближайшую пару между двумя наборами чисел, и для этой задачи в модели дерева алгебраических вычислений существует нижняя граница Ω ( n log n ) . (Битовые уловки могут, вероятно, уменьшить или устранить логарифмический фактор.)O(nlogn)O(r2+nlogn)Ω(nlogn)
Джеффс
Ω(N2) нижняя граница на основе числа ребер не применяется , потому что края не являются частью ввода - они подразумеваются. Вам не нужно смотреть на все из них, потому что вы можете вычислить соответствующие.
Дейв