Быстрый модуль для задачи коммивояжёра

Суть проблемы - отсортировать список картинок (одинакового размера) так чтобы соседи были максимально похожи.
Сейчас у меня боттлнек (самое долгое по вычислениям) - это непосредственно сама сортировка.
Матрицу смежности сделал через sklearn.metrics.pairwise.manhattan_dista nces (на выходе матрица numpy.ndarray)
В качестве решалки Коммиваяжора пока взял python_tsp.heuristics, но данное решение меня не удовлетворяет по производительности, хоть оно и эврестическое.
Да, точное решение для меня не обязательно, "хорошее" приближенное тоже подойдет.
Какой модуль Питона посоветуете ?

Из альтернатив есть вариант просто выбирать картинки по одной, выбирая следующую как самую подходящую из оставшихся. Но хотелось бы не так топорно подходить к проблеме
Картинок порядка 500 тысяч 500х700, в идеале, конечно, хотелось бы их целиком (приблизительно) отсортировать, но пока рассматриваю вариант сортировки только внутри небольших отрезков.
Думал про всяких "хэши", но пока пришел к выводу что они не дают требуемого результата. "Хэши" для поиска "похожих" картинок не работают точно, мне нужно учитывать метрику расстояния между картинками, а хэш далек от нее. Пытался выдумывать свой хэш, но ничего хорошего не вышло.

0

wingblack,

Сообщение от wingblack Матрицу смежности сделал через sklearn.metrics.pairwise.manhattan_dista nces

500К х 500К? И что, правда посчиталось? Она же терабайт в памяти должна весить, я не ошибаюсь?
Эвристик много можно придумать, вопрос соотношения времени/качества.
Можете погуглить LKH for TSP. Возможно есть библиотеки.

0

Сообщение от Red white socks 500К х 500К? И что, правда посчиталось?

Нет конечно, я пробовал делать "отрезками".

Сообщение от Red white socks Она же терабайт в памяти должна весить, я не ошибаюсь?

1 терабайт при условии использования 32-битных чисел, да.

В самом начале работы над задачей требовалось делать относительно быстро, чтобы за относительно короткое время сформировать видео-архив. Для таких условий в худшем случае подходили отрезки по 100 картинок, но тогда сортировка почти не имеет смысла на таком малом отрезке.
После разных попыток пришел к выводу сначала сделать видео-архив (в отличном качестве сжатия), а потом уже написать программу которая будет не спеша сортировать индексы в таком архиве, с хранением в БД и возможностью перезапуска с продолжением.

На данный момент задача разбилась на несколько более мелких, самая крупная - 250 тысяч картинок (дальнейшее уменьшение пока не предвидится).


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

Хорошо, посмотрю LKH, реализация на C внушает доверие, только пока полностью не понял как ему данные подготовить.

0

wingblack, а чем вам кластерный анализ не подходит?

0

Сообщение от Red white socks wingblack, а чем вам кластерный анализ не подходит?

Какие-то более конкретные предложения для данного случая ?
Обозрительно про кластеризацию знаю, но на практике не было необходимости использовать

0

Сообщение от wingblack Какие-то более конкретные предложения для данного случая ?

Куда уж конкретнее? Если вам надо сгруппировать картинки по степени схожести, то это кластерный анализ. Возможно я не правильно понял стоящую перед вам задачу.

0

Сообщение от Red white socks Если вам надо сгруппировать картинки по степени схожести, то это кластерный анализ.

Основная задача - создать список картинок где два соседа хоть немного "похожи" друг на друга.

Группировка по схожести - как идея чтобы пришлось вычислять и хранить меньше ребер. Но без опыта в кластеризации я не могу сказать что кластеризация тут применима. Ну не вижу я это в алгоритме "вычислить расстояние от текущей картинки А ко всем картинкам В(i), где В - картинки находящиеся в некотором радиусе от картинок С(j), где C - картинки в некотором радиусе от А"
Ну и да, тот момент что список или матрицу смежности еще надо построить, причем операция произвольного порядка чтения - весьма дорогая (но это так, к слову).

0

Сообщение от wingblack Основная задача - создать список картинок где два соседа хоть немного "похожи" друг на друга

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

Сообщение от wingblack Ну не вижу я это в алгоритме "вычислить расстояние от текущей картинки А ко всем картинкам В(i), где В - картинки находящиеся в некотором радиусе от картинок С(j), где C - картинки в некотором радиусе от А"

Думал, более-менее серьезная тема, но в таком ключе не готов поддерживать беседу. Не видите - ок, я откланиваюсь. Удачи!

0

Сообщение от Red white socks Думал, более-менее серьезная тема, но в таком ключе не готов поддерживать беседу. Не видите - ок, я откланиваюсь. Удачи!

Не знаю о чем вы подумали, это просто часть мысли про ограничение количества ребер в графе для уменьшения сложности TSP.

- вычисление веса ребер для случайных пар вершин
- для каждой вершины вычислить веса ребер между ее ближайшими соседями, как вариант - вычисление ребер в некоторой "окрестности" (в рамках уже построенного графа) текущей вершины
- если количество ребер у вершины достаточно много - удалить часть самых "тяжелых"
- повторять до достижения некоторого критерия, будь то время выполнения или отсутствие улучшение самого худшего из лучших расстояний на протяжении нескольких итераций.



Что же до кластерного анализа, то, в моем понимании, кластеризация используется когда стоит задача разделить точки на небольшое количество групп. А тут, получается, или таких групп нет вообще (по условию задачи), либо нужно считать что каждая точка образует вокруг себя отдельную группу "лучшие друзья" (если интерпретировать мои предыдущие неполные формулировки), т.е. количество групп огромно, и вообще не вписывается в типичные примеры задач по кластеризации (группировке) точек.
Причем изначально у нас нет полной картины, поскольку вычисление весов полносвязного графа не только несколько долгая процедура, но и под сами веса потребуется достаточно много памяти, которой компьютер не сможет оперировать единовременно, а каждый раз запрашивать веса через базу данных - очередные накладные расходы.

0