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

Question

[Syxov]

Есть массив элементов некоторого множества и заданна операция расстояния между элементами данного множества. Вопрос - как отсортировать массив так, что бы расстояние между двумя соседними элементами массива было минимальным.

Comments

[matperez]

Гуглите кластеризацию, а не сортировку. Вот например bourabai.ru/tpoi/analysis6.htm.

[d'Ivan]

matperez: Правильная ссылка не должна содержать точку в конце: bourabai.ru/tpoi/analysis6.htm
Почему кластеризация? Автору вопроса не нужно разбивать массив на кластеры,а лишь отсортировать по убыванию или возрастанию.

[matperez]

Роман: кластеризация потому что сортировка подразумевает, что должен быть максимум и минимум, а их тут нет. Ему нужно сравнивать всех со всеми.

[d'Ivan]

matperez: для сортировки достаточно чтобы в сравнении один элемент был больше или меньше. В сравнении строк метрика расстояния Левенштейна как раз и даёт это.

[matperez]

Роман: хотя может вы и правы, и это не кластеризация. Но это точно не задача сортировки. Скорее что-то вроде задачи коммивояжера.

[Андрей]

Поддерживаю во мнении, что это не сортировка. Вам нужно минимизировать глобальную функцию штрафа по всем соседствующим строкам. Это нетривиальная задача, возможно решаемая только субоптимально.

Александр : А каков объем массива ? Насколько сильно отличаются строки (мат.ожидание, СКВО расстояния Левенштейна) ?

[Syxov]

Андрей: Как отсортировать строки по похожести? тут я дал более общую формулировку задачи. То есть интересует решение задачи в общем случае.

[gimntut]

Александр, , Давайте возьмём более конкретный пример. Пусть у нас есть 4 числа: 1, 10, 2, 8. Пусть расстоянием будет модуль разницы чисел, тогда сортировка для пар понятна: (1, 2), (2, 1), (10, 8), (8, 10), (2, 8) и т.д., Но я так понимаю, что вам нужно отсортировать сами числа, какой ответ, по вашему, должен получиться в данном случае?

[Syxov]

gimntut: в случае чисел и такого расстояния задача решается обычной сортировкой. Ответ в данном случае будет "1, 2, 8, 10". Разница между соседними элементами будет 1, 6 и 2. Как кажется мне, улучшить данный результат не получится.

[gimntut]

Александр, т.е. нужно найти такую последовательность, при которой сумма расстояний соседних элементов массива будет минимальной? Тогда, это классическая задача коммивояжера. Обратите внимание, что 10, 8, 2, 1, так же является решением в предложенном примере, всё зависит от того, какую точку брать за первую.

Answer 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...

Answer 2

[AJ]

Расстояние Левенштейна - показать похожести 2-х строк, а не всех строк. Т.е. эталонная строка и сравниваемая. Оно всегда высчитывается относительно одной строки, при неограниченном количестве сравниваемых.

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

Comments

[Syxov]

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

[d'Ivan]

Александр: обновите вопрос в топике, пожалуйста (редактированием)

[AJ]

Александр: если расстояние уже есть - любым алгоритмом сортировки. Начните с пузырька.

[Syxov]

AJ: есть лишь функция расстояний, но не сами расстояния. И как пользоваться пузырьком непонятно. Допустим, в процессе сортировки, мы получили, что расстояние между двумя элементами - n. Надо ли их менять местами или нет? Возможно, само слово "сортировка" тут не уместно, но я не знаю как обозвать задачу по другому.

[AJ]

Александр: тогда обозначьте вводные данные и конечную цель без технических терминов.