Форум программистов, компьютерный форум CyberForum.ru

Метод ближайшего соседа через STL Algorithm - C++

Восстановить пароль Регистрация
 
Peperovich
43 / 43 / 4
Регистрация: 17.05.2011
Сообщений: 162
29.05.2014, 11:35     Метод ближайшего соседа через STL Algorithm #1
Добрый день. Подскажите можно метод ближайшего соседа сделать через сортировку с функтором?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2014, 11:35     Метод ближайшего соседа через STL Algorithm
Посмотрите здесь:

C++ algorithm
<algorithm> C++
STL. Не работает вывод через << в поток когда использую итераторы :( C++
Организовать find в векторе через STL!!! C++
метод erase для list(STL) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
29.05.2014, 12:50     Метод ближайшего соседа через STL Algorithm #2
А подробнее постановку задачи никак нельзя записать?
Peperovich
43 / 43 / 4
Регистрация: 17.05.2011
Сообщений: 162
29.05.2014, 13:03  [ТС]     Метод ближайшего соседа через STL Algorithm #3
Да пожалуйста. Есть несколько точек с расстоянием между ними, которые должна объехать машина и есть гараж из которого она должна выехать. Так вот самая простая реализация которая приходит на ум, это пройти все точки определить какая ближайшая к гаражу, это будет 1 точка в маршруте, потом оставшиеся пройти и определить которая из них ближайшая к 1 точке, которую уже нашли и так далее.
Но сложность такого алгоритма N! где N количество точек. Вот и хотел спросить, может можно с помощью std::sort как то отсортировать точки, только не знаю как написать оператор сравнения.
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
29.05.2014, 13:12     Метод ближайшего соседа через STL Algorithm #4
Не думаю, что это хорошая затея. Уж лучше непосредственный перебор. Чо вы собираетесь хранить в контейнере, что бы его сортировать?
Peperovich
43 / 43 / 4
Регистрация: 17.05.2011
Сообщений: 162
29.05.2014, 13:15  [ТС]     Метод ближайшего соседа через STL Algorithm #5
Ну в контейнере просто номера точек хранятся. Мне его надо отсортировать вот так, как будто методом ближайшего соседа прошел по нему.
Мне именно важна скорость алгоритма.
Yandex
Объявления
29.05.2014, 13:15     Метод ближайшего соседа через STL Algorithm
Ответ Создать тему
Опции темы

Текущее время: 23:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru