Блог

Главная - Вопросы по программированию - Найти такой способ, чтобы максимальное расстояние перехода в пути было возможно минимальным

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

#algorithm #graph #dynamic-programming #greedy

#алгоритм #График #динамическое программирование #жадный

Вопрос:

Существуют платформы, которые могут быть размещены на разных высотах. Например, эта карта показывает, как были размещены платформы (в программе она представлена в виде матрицы NxM, |N|, |M| <= 100 

       _ _ _    
    D _   _ _  
            _ _
              _
    S _ _ _ _ _

На этой карте space означает space , _ — платформа, S — платформа, с которой мы начинаем, D — пункт назначения. Монстр, который ходит по этой карте, может прыгать вверх, вниз или перемещаться влево или вправо.
Возможный способ добраться D от S монстра:

            
D          
           
           
S

или он может достичь D таким образом:

       _ _ _    
    D _   _ _  
            _ _
              _
    S _ _ _ _ _

Итак, комбинации достижения точки назначения могут варьироваться многими способами, но главное в том, что в первом случае максимальное расстояние прыжка, которое совершает монстр, равно 1 , потому что максимальное расстояние между двумя платформами таким образом равно 1 . Во втором случае монстр достиг цели очень быстро, но он совершил прыжок на расстояние 2 . Основная цель монстра — добраться до точки назначения и не совершать больших прыжков (как можно меньше), и из-за этого предпочтителен первый способ. Вопрос в том, какой алгоритм я должен использовать, чтобы найти такой способ, при котором максимальное расстояние перехода было бы минимальным?

Я подумал о двух способах:

  1. Перебор, но это будет неудобно, когда количество платформ будет =N*M ;
  2. Каким-то образом перенесите эту матрицу в граф, где каждая платформа представлена как узел графа, а ребра представлены расстояниями переходов, и найдите минимальное связующее дерево, но, во-первых, я не знаю, как создать матрицу смежных таким образом, и это будет правильно.

Ответ №1:

Для анализа карты и поиска узлов:

 for i from 1 to N
    for j from 1 to M
        if map(i, j) == 'S' 
            nodes.add(i, j);
            start = nodes.Count;
        elseif map(i, j) == 'D' 
            nodes.add(i, j);
            dest = nodes.Count;
        elseif map(i, j) == '_'
            nodes.add(i, j);
        end
    end
end

В приведенном выше псевдокоде я предполагаю, что nodes.add(i, j) добавляет новый узел с node.x = 1 и node.y = j в список узлов.

Затем построить матрицу смежности:

 n = nodes.Count;
adj = n by n matrix, filled with  inf;
for i from 1 to n
    for j from i   1 to n
       if (nodes[i].x == nodes[j].x) || (nodes[i].y == nodes[j].y)
           adj(i, j) = abs(nodes[i].x - nodes[j].x)  
               abs(nodes[i].y - nodes[j].y);
       end
    end
end

Остальное — проблема кратчайшего пути. Используйте алгоритм Дейкстры, чтобы найти кратчайший путь между start dest узлами и.

Комментарии:

1. Мне не нужно находить кратчайший путь! Мне нужно найти путь, содержащий минимальные ребра!

2. @AyratArifullin Конечно, но алгоритм тот же. При увеличении пути и обновлении текущего кратчайшего пути вам не нужно сравнивать sum(weights) , но max(weights) .

3. @AyratArifullin Кроме того, что, если бы было несколько путей с одинаковым значением самого длинного перехода? Разве вы не хотите вернуть кратчайший? Или, может быть, тот, у которого наименьшее количество переходов с максимальной длиной. Все они используют один и тот же алгоритм, но с разными способами сравнения двух путей.

4. @AyratArifullin Имейте в виду, что Дейкстра на самом деле является алгоритмом оптимизации и пытается минимизировать «стоимость», а «длина» исходит только из терминологии хорошо известной проблемы «Проблема кратчайшего пути». Теперь, когда «стоимость» в вашей задаче является «самым длинным скачком», просто используйте свою собственную стоимость в том же алгоритме.

5. Я немного исправил ваше предложение и принял решение. Вы можете проверить это ниже. Спасибо, что поддержали мою идею! Вы только что подтолкнули меня дальше

Ответ №2:

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

  1. Из заданной карты платформ необходимо создать граф, в котором один узел представляет одну платформу (включая начальную и конечную платформы), а ребра между узлами представлены как расстояние между ними;
  2. Когда вы сформировали график, ваша цель — найти минимальное связующее дерево и найти максимальный вес ребра в этом дереве — это ответ. Код очень большой, и, пожалуйста, проверьте его на моем github! Обратите внимание, что 1 означает платформу, 2 означает начало и 3 является пунктом назначения:

Проверьте эту ссылку на github!