Comments 6
Назвать Дейкстру или A* для поиска пути заменой GA для решения задачи коммивояжёра это очень смело. А в такой постановке задача должна решать за одно действие буквально, даже в уме и имеет множество оптимальных решений.
ГА обрабатывает этот случай за 517 секунд. С ошибкой 24,7% (так себе точность мягко говоря).
Кстати, откуда ошибка взята? Оптимальное решение для теста уже известно? Как долго и чем оно искалось, интересно?
А собственно по алгориму: Это жадный алгоритм с очень простой эвристикой: добавляем точки по одной в список на позицию, минимизирующую длину пути. Такой простой алгоритм ожидаемо будет работать очень быстро. Но вот с оптимальностью ответа у него большие проблемы.
Во-первых, это известная эвристика с 1974 года: https://www2.isye.gatech.edu/~mgoetsch/cali/VEHICLE/TSP/TSP011__.HTM
При чем есть более сильная версия, где перебирается не только, куда воткнуть вершину, а и какую из них добавлять. Каждый раз выбирается локально лучший вариант. И это даже гарантирует точность 50% (максимум 2 раза длинее чем в оптимальном пути).
Далее, в задачае коммивояжора обычно надо вернуться в изначальную точку, у вас это не учитывается, судя по коду и картинкам. Похоже, это сильно испортит вашу эвристику, ведь она локальна.
Edit: В литературе это называется cheapest insertion heuristic.
cheapest insertion heuristic предлагает выбрать случайно две точки и (считается продвинутой версией )далее каждый раз строить очередь какую следующую точку добавлять , очень быстрый алгоритм и позволяет получить ошибку более 50% ,что при большом количестве точек и высокой скорости очень хороший результат. Я же предлагаю не случайно выбрать начальный набор точек отстоящих друг от друга. Это позволяет сократить время в разы и ошибку до 37-40%. Замена начального набора точек на получившийся и как следствие коррекция скелета уже за первую итерацию позволяет получить ошибку менее 20%. Пересчет маршрута не большими участками 10-15% очень быстрая операция позволяет получить ошибку сколь угодно близкую к 0. А то обстоятельство что у меня маршрут не замкнут то это только иллюстрация замыкание маршрута или не ухудшает ошибку либо увеличивает ее на 3-5%.
Я же предлагаю не случайно выбрать начальный набор точек отстоящих друг от друга. Это позволяет сократить время в разы и ошибку до 37-40%
Во-первых, никаких разов тут нет. Вы выкидываете всего 3 итерации из N. Это ускорение на какие-то проценты. Быстрее у вас, потому что вы перебираете только куда вставлять очередную (случайную) точку, когда как в cheapest insertion heuristic перебирают еще и точку и потом также перебирают, куда ее вставлять.
Во-вторых, сокращение ошибки зависит от того, как вы выберете "скелет". Вы просто берете какие-то "по краям диапазона" не очень это формализовав. Никаких рассуждений на тему почему это как-то помогает вы не привели.
Это позволяет сократить время в разы и ошибку до 37-40%
Голословное утверждение.
и как следствие коррекция скелета
Первый раз это словосочетание вижу. В статье никакой коррекции скелета нет. Вы про то, что вы добавляете новую точку в список, который был скелетом? Тогда тоже самое есть у cheapest insertion heuristic.
замыкание маршрута или не ухудшает ошибку либо увеличивает ее на 3-5%.
Опять же, голословное утверждение.
Еще раз, ваш метод отличается от известного в двух местах:
1) вы начинаете не с 1 а с 4 точек.
2) Вы перебираете только куда вставлять, а не еще и что.
Я уверен, что пункт 2 делает ваш метод гораздо хуже Cheapest insertion heuristic, потому что доказательство границы ошибки в 50% не применимо к вашему методу.
Благодарен Вам за конструктивную критику. По пункту 2 не только куда но и что вставлять написано в статье в разделе "оптимизация " предлагается анализ отдельных участков т.е. что и куда а разы появляются т.к обработка участка в 10% в 100 раз быстрее целого в 10 раз по 10% даёт выигрыш 10 раз по поводу голословности абсолютно с Вами согласен выберу время систематезирую прохождение стандартных тестов выложу . Ещё по поводу стандартного теста А280 да известно расстояние очень близкое к оптимальному , конечно точный ответ не может быть получен.
Что касается того чем решался А280. Конечно тяжесть теста в критерии получения минимальной ошибки заключается совсем не в количестве точек. Может я не прав но нет другого способа для решения запутанной задачи кроме как гонять часами муравьиный алгоритм. Ни Дейкстра ни генетический алгоритм ни жадные результат в принципе не дадут.
Задача коммивояжера: обходим 750 точек за 5 сек