Доброго времени суток! Честно, не знаю, кому это может понадобиться, но все-же выложу это тут PHP: function way_opt($points) { $result = array(); $points = array_chunk($points, 2); $route = array(0); do { $distanceMin = INF; $cordsOptimized = null; foreach ($points as $cords => $xy) { if (!in_array($cords, $route)) { $distance = sqrt(pow($xy[0] - $points[$route[count($route) - 1]][0], 2) + pow($xy[1] - $points[$route[count($route) - 1]][1], 2)); if ($distance < $distanceMin) { $distanceMin = $distance; $cordsOptimized = $cords; } } } $route[] = $cordsOptimized; } while (count($route) < count($points)); foreach($route as $point) { $result[] = $points[$point][0]; $result[] = $points[$point][1]; } return $result; } Все достаточно просто. В функцию передаем массив значений X, Y - она строит оптимальные расположения между этими координатами и выдает их в виде того-же массива X, Y. Все это мне нужно было для подготовки изображений на электронно-лучевую трубку. И не только изображений, так-же эта функция участвовала в конвертации шрифтов от GLCD для той-же самой трубки. Данная функция прекрасно справляется со своей задачей.
Спасибо за труд. Есть ли примеры работ по вершинам в виде графов с 50-100 точками к примеру на сетке 100х100 и шагом 1? Нужно глазами смотреть оптимальность маршрута я думаю, так нагляднее... Также не понятно как назначать первичную точку
вот к примеру символ ". Изначально, в бинарном представлении он выглядел так: 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
Попросил создать ChatGPT функцию комивояжера. Выдал код с комментариями на русском языке, все подробно расписал. Вот что он выдал (ответ полностью в оригинале): Коммивояжер - это задача нахождения минимального пути, который проходит через все указанные точки и возвращает обратно в начальную точку. Алгоритм ближайшего соседа заключается в следующем: 1. Выбрать начальную точку. 2. Найти ближайшую точку к текущей и добавить ее в путь. 3. Повторять шаг 2, пока все точки не будут добавлены в путь. 4. Вернуть путь, который начинается и заканчивается в начальной точке. Вот реализация этого алгоритма на PHP: PHP: <?php function nearestNeighbor($points) { $numPoints = count($points); $visited = array_fill(0, $numPoints, false); $path = array(); // Выбираем начальную точку $current = 0; $path[] = $current; $visited[$current] = true; while (count($path) < $numPoints) { $next = null; $minDist = INF; // Находим ближайшую точку for ($i = 0; $i < $numPoints; ++$i) { if (!$visited[$i] && $i != $current) { $dist = distance($points[$current], $points[$i]); if ($dist < $minDist) { $minDist = $dist; $next = $i; } } } // Добавляем точку в путь и отмечаем как посещенную $path[] = $next; $visited[$next] = true; $current = $next; } // Добавляем начальную точку в конец пути $path[] = 0; return $path; } function distance($p1, $p2) { $dx = $p1['x'] - $p2['x']; $dy = $p1['y'] - $p2['y']; return sqrt($dx * $dx + $dy * $dy); } ?> Эта функция принимает массив точек в формате `array(array('x' => 1, 'y' => 2), ...)`, где каждая точка имеет координаты `x` и `y`. Она возвращает массив индексов точек в порядке их посещения. Например, путь `[0, 2, 1, 3, 0]` означает, что мы начинаем с точки 0, затем идем к точке 2, затем к точке 1, затем к точке 3 и возвращаемся в точку 0.
Не самый эффективный алгоритм в плане того какие пути он находит. Но прост в реализации, поэтому видимо ИИ в какой то библиотеке эти реализации алгоритмов берет
Изменил свое мнение. ИИ действительно сам программирует решения... Смотря что, не самые лучшие или рабочие пока , но и не фигня.