За последние 24 часа нас посетили 19854 программиста и 1107 роботов. Сейчас ищут 557 программистов ...

Алгоритм ближайшего соседа в задаче коммивояжера

Тема в разделе "Решения, алгоритмы", создана пользователем Redfern89, 5 апр 2023.

  1. Redfern89

    Redfern89 Новичок

    С нами с:
    2 мар 2023
    Сообщения:
    5
    Симпатии:
    4
    Доброго времени суток! Честно, не знаю, кому это может понадобиться, но все-же выложу это тут

    PHP:
    1. function way_opt($points) {
    2.     $result = array();
    3.     $points = array_chunk($points, 2);
    4.     $route = array(0);
    5.  
    6.     do {
    7.         $distanceMin = INF;
    8.         $cordsOptimized = null;
    9.      
    10.         foreach ($points as $cords => $xy) {
    11.             if (!in_array($cords, $route)) {
    12.                 $distance = sqrt(pow($xy[0] - $points[$route[count($route) - 1]][0], 2) + pow($xy[1] - $points[$route[count($route) - 1]][1], 2));
    13.                 if ($distance < $distanceMin) {
    14.                     $distanceMin = $distance;
    15.                     $cordsOptimized = $cords;
    16.                 }
    17.             }
    18.         }
    19.         $route[] = $cordsOptimized;
    20.     } while (count($route) < count($points));
    21.  
    22.     foreach($route as $point) {
    23.         $result[] = $points[$point][0];
    24.         $result[] = $points[$point][1];
    25.     }
    26.      
    27.     return $result;
    28. }
    Все достаточно просто. В функцию передаем массив значений X, Y - она строит оптимальные расположения между этими координатами и выдает их в виде того-же массива X, Y. Все это мне нужно было для подготовки изображений на электронно-лучевую трубку. И не только изображений, так-же эта функция участвовала в конвертации шрифтов от GLCD для той-же самой трубки. Данная функция прекрасно справляется со своей задачей.
     
    musicman3 нравится это.
  2. antoniii

    antoniii Новичок

    С нами с:
    16 мар 2022
    Сообщения:
    417
    Симпатии:
    71
    А пример массива на входе и на выходе не приложишь? Или картинку применения.
     
  3. musicman3

    musicman3 Активный пользователь

    С нами с:
    30 июн 2019
    Сообщения:
    144
    Симпатии:
    12
    Адрес:
    Дыра на карте
    Спасибо за труд. Есть ли примеры работ по вершинам в виде графов с 50-100 точками к примеру на сетке 100х100 и шагом 1? Нужно глазами смотреть оптимальность маршрута я думаю, так нагляднее... Также не понятно как назначать первичную точку
     
  4. Redfern89

    Redfern89 Новичок

    С нами с:
    2 мар 2023
    Сообщения:
    5
    Симпатии:
    4
    вот к примеру символ ". Изначально, в бинарном представлении он выглядел так:

    00000000
    00000111
    00000000
    00000111
    00000000


    После преобразования его в координаты для электронно-лучевой трубки - оно выглядело так

    2,0,
    2,2,
    2,4,
    6,0,
    6,2,
    6,4

    То есть, когда заканчивается первая часть кавычек (координата Х), лучу пришлось бы перемещаться на несколько шагов вниз и рисовать вторую их часть. В масштабе одного символа (даже сравнительно больших размеров) - это вполне нормально работает, но когда символов много, при надписях возникали артефакты из-за того, что луч многократно проходил неоптимальные расстояния. После-же прогона через эту функцию координаты кавычек стали выглядеть так:

    2,0,
    2,2,
    2,4,
    6,4,
    6,2,
    6,0

    Стало видно, что как закончились данные на первой оси Х, луч сделал шаг дальше и стал рисовать картинку вниз. Возможно это не самый оптимальный подход, но артефакты заметно исчезли. В общем сия задача очень
    узкоспециализирована...
    --- Добавлено ---
    Она задана в самой функции в массиве $route
     
    musicman3 нравится это.
  5. musicman3

    musicman3 Активный пользователь

    С нами с:
    30 июн 2019
    Сообщения:
    144
    Симпатии:
    12
    Адрес:
    Дыра на карте
    Попросил создать ChatGPT функцию комивояжера. Выдал код с комментариями на русском языке, все подробно расписал. Вот что он выдал (ответ полностью в оригинале):

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

    1. Выбрать начальную точку.
    2. Найти ближайшую точку к текущей и добавить ее в путь.
    3. Повторять шаг 2, пока все точки не будут добавлены в путь.
    4. Вернуть путь, который начинается и заканчивается в начальной точке.

    Вот реализация этого алгоритма на PHP:


    PHP:
    1. <?php
    2.  
    3. function nearestNeighbor($points) {
    4.   $numPoints = count($points);
    5.   $visited = array_fill(0, $numPoints, false);
    6.   $path = array();
    7.  
    8.   // Выбираем начальную точку
    9.   $current = 0;
    10.   $path[] = $current;
    11.   $visited[$current] = true;
    12.  
    13.   while (count($path) < $numPoints) {
    14.   $next = null;
    15.   $minDist = INF;
    16.  
    17.   // Находим ближайшую точку
    18.   for ($i = 0; $i < $numPoints; ++$i) {
    19.   if (!$visited[$i] && $i != $current) {
    20.   $dist = distance($points[$current], $points[$i]);
    21.   if ($dist < $minDist) {
    22.   $minDist = $dist;
    23.   $next = $i;
    24.   }
    25.   }
    26.   }
    27.  
    28.   // Добавляем точку в путь и отмечаем как посещенную
    29.   $path[] = $next;
    30.   $visited[$next] = true;
    31.   $current = $next;
    32.   }
    33.  
    34.   // Добавляем начальную точку в конец пути
    35.   $path[] = 0;
    36.  
    37.   return $path;
    38. }
    39.  
    40. function distance($p1, $p2) {
    41.   $dx = $p1['x'] - $p2['x'];
    42.   $dy = $p1['y'] - $p2['y'];
    43.   return sqrt($dx * $dx + $dy * $dy);
    44. }
    45.  
    46. ?>

    Эта функция принимает массив точек в формате `array(array('x' => 1, 'y' => 2), ...)`, где каждая точка имеет координаты `x` и `y`. Она возвращает массив индексов точек в порядке их посещения. Например, путь `[0, 2, 1, 3, 0]` означает, что мы начинаем с точки 0, затем идем к точке 2, затем к точке 1, затем к точке 3 и возвращаемся в точку 0.
     
    #5 musicman3, 7 апр 2023
    Последнее редактирование: 7 апр 2023
  6. Дюран

    Дюран Активный пользователь

    С нами с:
    9 мар 2018
    Сообщения:
    244
    Симпатии:
    17
    Не самый эффективный алгоритм в плане того какие пути он находит.
    Но прост в реализации, поэтому видимо ИИ в какой то библиотеке эти реализации алгоритмов берет
     
  7. Дюран

    Дюран Активный пользователь

    С нами с:
    9 мар 2018
    Сообщения:
    244
    Симпатии:
    17
    Изменил свое мнение. ИИ действительно сам программирует решения...
    Смотря что, не самые лучшие или рабочие пока , но и не фигня.
     
    musicman3 нравится это.