Как отсортировать массив элементов некоторого множества по минимальному расстоянию между ними?

Есть массив элементов некоторого множества и заданна операция расстояния между элементами данного множества. Вопрос - как отсортировать массив так, что бы расстояние между двумя соседними элементами массива было минимальным.
  • Вопрос задан
  • 549 просмотров
Решения вопроса 1
@gimntut
Александр, т.е. нужно найти такую последовательность, при которой сумма расстояний соседних элементов массива будет минимальной? Тогда, это классическая задача коммивояжера.
Например, для задачи "Пусть у нас есть 4 числа: 1, 10, 2, 8. Пусть расстоянием будет модуль разницы чисел" есть два решения: 1, 2, 8, 10 и 10, 8, 2, 1. Всё зависит от того, какую точку брать за первую.

https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
2ball
@2ball
Хардкор кодер
Расстояние Левенштейна - показать похожести 2-х строк, а не всех строк. Т.е. эталонная строка и сравниваемая. Оно всегда высчитывается относительно одной строки, при неограниченном количестве сравниваемых.

Эталонная строка есть? Опишите задачу более подробно.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы