Моему 8-летнему надоело создавать обычные лабиринты, и он занялся созданием вариантов, которые выглядят так:
Идея состоит в том, чтобы начать с x и достичь o по обычным правилам. Кроме того, вы можете переходить с любого целого числа на любое другое целое число , но вы должны заплатить долларов за привилегию. Цель состоит в том, чтобы решить лабиринт за наименьшую стоимость. В приведенном выше примере мы можем перейти от x к o через x-14-18-27-28-o по цене 5, но дешевле перейти к x-13-11-9-8-29-28-o только 4.
Итак, вот мой вопрос: какое наилучшее решение (с точки зрения асимптотического времени выполнения) вы можете придумать для решения этой проблемы? Вы можете сделать любые разумные предположения о формате ввода.
Примечание. Я использую тег «головоломки», потому что у меня есть ответ , но я не уверен, что он оптимален, и хотел бы посмотреть, сможет ли кто-нибудь еще улучшить мое решение. (Здесь - число целых чисел в лабиринте.)
Ответы:
Вы можете решить это за используя вариацию алгоритма Дейкстры. Мы можем избежать не всех обновлений расстояния при посещении нового узла. Если мы посещаем узел y , нам нужно только обновить расстояния всего, что можно пройти, от y до 0 и обновить расстояния до двух узлов y - и y + с ближайшими значениями до y, меньшими и большими, чемO(nlogN) Y Y Y- Y+ Y которые не имеют был выбранY
Этих обновлений достаточно, чтобы куча возвращала минимальный элемент, потому что любой ближайший узел, к которому вы переходите, должен был численно находиться чуть выше или чуть ниже уже посещенного узла.
Каждый узел обновляется до 0 не более одного раза (если мы выталкиваем все узлы с нулевым расстоянием из очереди, чтобы избежать квадратичного поведения), и каждый раз, когда мы добавляем узел, мы делаем только O (1) других обновлений. Поиск значений и y + можно выполнить за линейное время, если мы также сохраним упорядоченный двусвязный список всех узлов, отсортированный по их целочисленным значениям. Построение этого двусвязного списка занимает O ( n log n ) времени, и, наконец, O ( n ) обновляется и выскакивает из кучи, занимает O ( n log n ) времени, для общего времени выполненияY- Y+ O ( n logн ) O ( n ) O ( n logн ) O (n logн )
источник
Я чувствую, что может быть лучшим, что вы можете получить.O ( n2)
Кажется естественным преобразовать это в задачу кратчайшего пути со специальным начальным узлом (x) и конечным узлом (0). Также будет один другой узел для каждого из номеров. И x, и 0 имеют ребра веса 0 для всех числовых узлов, которые достижимы в лабиринте. Все числовые узлы связаны либо с весом 0 (если числа достижимы по лабиринту), либо с разницей между числами (если недоступно по лабиринту).
Кратчайший путь в этом графе не может быть решен менее чем за потому что граф имеет примерно n 2 ребер, и в худшем случае каждый должен был бы просматривать каждый случай один раз. Таким образом, алгоритм Дейкстры для кратчайшего пути занимает время O ( n 2 ) и является оптимальным в худшем случае.O ( n2) N2 O ( n2)
источник