Алгоритм: Оптимизация разъемов

Question

Предположим, что в 3D-пространстве есть n, а именно P1, P2, P3, ..., Pn.

Определите соединитель, C, как упорядоченный набор сегментов линии, где следующий элемент в наборе должен иметь общую вершину с предыдущей. Например, { P1-P2, P2-P4, P4-P7 } - это разъем, а { P1-P2, P3-P4,P4-P2 } - нет.

Определите содержимое соединителя как набор точек, которые входят в разъем.

Определите величину соединителя, чтобы быть длиной самого длинного отдельного сегмента в разъеме.

Определите соединитель как правильный разъем, если самый длинный отдельный сегмент является первым или последним сегментом в разъеме.

Считается, что набор точек соединен, если объединение содержимого разъемов над точками является множеством точек.

Проблема заключается в том:

Учитывая, что k соответствующие разъемы (k < n) одного и того же величины m могут соединить n точки, координаты которых приведены, минимизировать m.

Какова должна быть суть алгоритма? Я не знаю, с чего начать.

Answer 1

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

• Соединитель не может иметь петли (точку можно посетить только один раз)
• Правильный разъем не может иметь преимущество, которое больше, чем первый один

NB: Последнее условие является слишком сильным, потому что последний край надлежащего разъема может быть разрешено быть больше, чем первый , но я принимаю во внимание, что алгоритм также проделает еще одну попытку с таким «последним» фронтом, как первое ребро, но в oppo Направление участка: поэтому я могу исключить этот край на этом этапе.

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

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

Вот немного более формальный эскиз для такого алгоритма:

Pre-processing: 
    List for each point all the other points in order of increasing distance from it. 

    set m = 0 

Repeat: 
    set max_dist = 0, list = empty 
    For each point p: 
     Find the first neighbor q for which distance(p,q) > m 
     if distance(p,q) >= max_dist: 
      if distance(p,q) > max_dist: 
       clear list 
      append (p,q) to the list 

    let m = max_dist 
    For each pair (p,q) in the list (all these pairs have same distance m): 
     Let result = [] 
     Let connector be [p,q] 
     Let p = q 

     Recursive part (p): 
      let end_point = True 
      For each neighbor q of p (in order of distance): 
       If distance(p,q) > m: 
        break loop 
       If q not in connector: 
        let end_point = False 
        Append q to connector 
        Call the recursive part for q 
        size(result) >= k and all points are in result: 
         exit recursion 
        Remove q from connector (backtracking) 

      If end_point: 
       append clone of connector to result 

     If size(result) >= k and all points are in result: 
      return m, as final result 

Answer 2

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

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

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

Итерационный подход: Соедините все узлы любым способом. Затем попробуйте обменивать узлы. Выберите узел B с разъемами с наивысшей величиной и Q случайным образом, с разъемами AB, BC и PQ, QR. Производите AQ, QC и PB, BR и сохраняйте своп, если их величина уменьшается.

Возможно использование линейное программирование.