Сворачивание набора строк на основе заданного расстояния Хэмминга

Я придумал следующее:

Это сообщает об элементе с наивысшим баллом с суммой его баллов и баллов его ближайших соседей. Когда используется соседний объект, об этом отдельно не сообщается.

Я предлагаю использовать дерево точек обзора в качестве метрического индекса.

Алгоритм будет выглядеть так:

1. построить метрический индекс из строк и их оценок
2. построить максимальную кучу из строк и их оценок
3. для строки с наивысшим баллом в максимальной куче:
4. используйте метрический индекс, чтобы найти ближайшие строки
5. напечатайте строку и сумму ее очков и ближайших к ней строк
6. удалить из индекса метрики строку и каждую из ближайших к ней строк
7. удалить из максимальной кучи строку и каждую из ближайших строк
8. повторяйте 3-7, пока максимальная куча не станет пустой

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

1. построить метрический индекс из строк и их оценок
2. построить максимальную кучу из строк и их оценок
3. построить используемую таблицу из пустого набора
4. для строки с наивысшим баллом в максимальной куче:
5. если эта строка находится в используемой таблице: начать со следующей строки
6. используйте метрический индекс, чтобы найти ближайшие строки
7. удалить все соседние строки, которые находятся в используемой таблице
8. напечатайте строку и сумму ее очков и ближайших к ней строк
9. добавить ближайшие строки в используемую таблицу
10. повторяйте 4-9, пока максимальная куча не станет пустой

Я не могу предоставить анализ сложности.

Я думал о втором алгоритме. Часть, которая, как мне показалось, была медленной, заключалась в проверке соседства с использованным столом. В этом нет необходимости, так как удаление из дерева точек наблюдения может быть выполнено за линейное время. При поиске соседей запоминайте, где они были найдены, а затем удаляйте их позже, используя эти местоположения. Если в качестве точки наблюдения используется сосед, пометьте его как удаленный, чтобы поиск не возвращал его, но в противном случае оставьте его в покое. Это, я думаю, восстанавливает его ниже квадратичного. В противном случае это было бы что-то вроде количества элементов, умноженных на размер окрестности.

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

Это можно рассматривать как назначение лидера каждому соседству таким образом, чтобы у каждого элемента был не более одного лидера, и этот лидер на данный момент имеет наибольший общий балл. Это можно рассматривать как ориентированный граф.

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

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