Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 21
А нельзя разбросать точки в случайном порядке, измерить расстояние между ними, сопоставить с реальными расстояниями и потом просто «подогнать»?
Можно, получится аналог метода многомерного шкалирования. Но я не пробовал, предполагаю, что подгонка постоянно будет скатываться в локальные минимумы.
Из локальных минимумов можно выходить.
Возможно эти минимумы должны асимптотически приближаться к глобальному минимуму. Должен же быть какой то градиент.
Хочется попробовать, но как всегда есть куча других дел. Попробуйте описать задачу и свое решение более детально. Чувствуется, что для вас многие вещи очевидны, но для читателя это может звучать как, как «Авада Кедабра!» из Гари Поттера.
Хочется попробовать, но как всегда есть куча других дел. Попробуйте описать задачу и свое решение более детально. Чувствуется, что для вас многие вещи очевидны, но для читателя это может звучать как, как «Авада Кедабра!» из Гари Поттера.
Совсем не обязательно, что для данной задачи последовательность все более и более глубоких локальных минимумов имеет в пределе глобальный минимум. К тому же здесь любой локальный минимум вместо глобального — это неверное решение задачи.
Это, к примеру, существенно отличается от задач машинного обучения, где локальный минимум — это некоторый достигнутый уровень обобщения данных, на котором уже можно делать предсказания, а стремление получить именно глобальный минимум зачастую контрпродуктивено, поскольку может приводить к переобучению сети.
Это, к примеру, существенно отличается от задач машинного обучения, где локальный минимум — это некоторый достигнутый уровень обобщения данных, на котором уже можно делать предсказания, а стремление получить именно глобальный минимум зачастую контрпродуктивено, поскольку может приводить к переобучению сети.
Да, с глобальным минимумом — точно не факт. Хотя, все таки интересно, какова зависимость количества локальных минимумов от количества точек. Ведь если точек всего три, то локальных минимумов нет? А если точек четыре? Пять?
Этот вопрос интересен тем, что ответ на него является совсем не таким, каким ожидается.
Рассмотрим более формально алгоритм, которым Вы пытаетесь решать задачу. У нас на входе есть множество чисел ΔX, которое представляет собой совокупность всех n^2 парных расстояний между n точками, локализованных на окружности с периметром L. Множество ΔX можно записать в виде квадратной матрицы вида:
ΔX = {{ 0, Δx_12, .., Δx_1n},
{ L — Δx_12, 0, .., Δx_2n },
…
{ L — Δx_1n, L-Δx_2n, .., 0 }}
где учтено следующее: а) во множество ΔX включены точки Δx_kk = x_k — x_k = 0; б) длины путей между точками по часовой и против часовой стрелки связаны отношением Δx_ij = L — Δx_ji.
Далее по окружности раскидываются n точек с координатами {ξ_1, ξ_2, .., ξ_n} и формируется матрица расстояний:
Δξ = {{ 0, Δξ_12, .., Δξ_1n},
{ L — Δξ_12, 0, .., Δξ_2n },
…
{ L — Δξ_1n, L-Δξ_2n, .., 0 }}
Ожидается, что минимизируя функцию ошибок Σ_ij (Δx_ij — Δξ_ij)^2 можно получить решение.
Однако, в такой постановке уже есть две скрытых проблемы. Первая связана с размещением элементов множества ΔX в матрицу, вторая с сопоставлением рядов и колонок матриц ΔX и Δξ друг с другом. Обе решаются комбинаторным способом.
Итого, можно оценить возможное число вариантов с которых нужно стартовать процесс минимизации как (n(n-1))!! n! Возможно далеко не все старты дадут уникальные минимумы (как это происходит при малых значениях n), но все равно — это немало.
Однако я хотел сказать другое. Поставленный вопрос «о зависимости числа локальных минимумов от числа точек» ничего не дает для решения beltway проблемы. Дело в том, что любая строка (колонка) матрицы ΔX с правильным размещением элементов уже является решением, что обессмысливает дальнейшую минимизацию.
Рассмотрим более формально алгоритм, которым Вы пытаетесь решать задачу. У нас на входе есть множество чисел ΔX, которое представляет собой совокупность всех n^2 парных расстояний между n точками, локализованных на окружности с периметром L. Множество ΔX можно записать в виде квадратной матрицы вида:
ΔX = {{ 0, Δx_12, .., Δx_1n},
{ L — Δx_12, 0, .., Δx_2n },
…
{ L — Δx_1n, L-Δx_2n, .., 0 }}
где учтено следующее: а) во множество ΔX включены точки Δx_kk = x_k — x_k = 0; б) длины путей между точками по часовой и против часовой стрелки связаны отношением Δx_ij = L — Δx_ji.
Далее по окружности раскидываются n точек с координатами {ξ_1, ξ_2, .., ξ_n} и формируется матрица расстояний:
Δξ = {{ 0, Δξ_12, .., Δξ_1n},
{ L — Δξ_12, 0, .., Δξ_2n },
…
{ L — Δξ_1n, L-Δξ_2n, .., 0 }}
Ожидается, что минимизируя функцию ошибок Σ_ij (Δx_ij — Δξ_ij)^2 можно получить решение.
Однако, в такой постановке уже есть две скрытых проблемы. Первая связана с размещением элементов множества ΔX в матрицу, вторая с сопоставлением рядов и колонок матриц ΔX и Δξ друг с другом. Обе решаются комбинаторным способом.
- Для матрицы ΔX нули ставятся однозначно на диагональ. Далее, последовательно выбираем элементы из множества ΔX и выставляем их в верхний треугольник матрицы ΔX. Первый элемент Δx_12 выбирается n(n-1) способами, далее ему нужно поставить пару L — Δx_12 симметрично относительно диагонали в нижний треугольник, что удаляет еще один элемент из ΔX. Второй элемент Δx_13 в матрицу выбирается n(n-1)-2 способами и т.д. Итого, имеем (n(n-1))!! вариантов.
- Число сопоставлений матрицы Δξ к матрице ΔX равно n! (число возможных перестановок множества из n рядов + синхронная перестановка колонок с теми же номерами).
Итого, можно оценить возможное число вариантов с которых нужно стартовать процесс минимизации как (n(n-1))!! n! Возможно далеко не все старты дадут уникальные минимумы (как это происходит при малых значениях n), но все равно — это немало.
Однако я хотел сказать другое. Поставленный вопрос «о зависимости числа локальных минимумов от числа точек» ничего не дает для решения beltway проблемы. Дело в том, что любая строка (колонка) матрицы ΔX с правильным размещением элементов уже является решением, что обессмысливает дальнейшую минимизацию.
Гомотопию пробовали? Dimension reduction?
Гомотопию не пробовал, нет идей как это сделать. Однако отображение из дискретного пространства точек множества на непрерывное сделал. При этом удалось обобщить метод и получить красивые формулы, но самое главное удалось решить проблему в случае наличия большого шума в спектрах.
Dimension reduction? Не пробовал. Причины в ответе на комментарий uchitel.
Dimension reduction? Не пробовал. Причины в ответе на комментарий uchitel.
Спасибо за отклики. К сожалению, в течении недели не смогу отвечать на комментарии. Приглашаю посетить конференцию Постгеном 2018 в Казанском федеральном университете, (естественно, у кого есть возможность). На хабре пока выставлена только половина от доклада.
Возможно ли в полиномиальное время восстановить координаты множества точек, если известно множество всех парных расстояний между ними?Имеется ввиду, что расстояния даны без привязки к номеру точки? То есть мы не знаем, какой паре точек какое расстояние соответствует?
А почему нельзя тупо взять CAD, нарисовать там эти отрезки и соединить?
Очевидно, что если число решений растет по экспоненте, то и время их получения медленней расти не может.
Верно ли я понял, что ставится задача нахождения всех решений, а для нахождения хотя бы одного решения полиномиальный алгоритм может существовать? Или такая постановка задачи не актуальна?
В биоинформатике к beltway проблеме в том или ином виде сводятся задачи: partial digestion problem (PDP) для цикличной ДНК, cyclic peptide sequencing problem (CPS) для циклических пептидов и ряд других. Решение beltway проблемы не означает автоматического решения исходных задач. Чтобы найти какое из решений соответствует реальности требуется дополнительный анализ. То есть, мы не можем избежать поиска всех решений. Это особенно актуально для PDP, где решений много. Для CPS ситуация лучше, решение чаще всего одно. То есть, если есть уверенность, что решение единственно, то постановка задачи нахождения одного решения вполне разумна.
Полиномиальный алгоритм для поиска одного решения может существовать, но не для любых данных. Возможность его существования — это скорее особенность самих данных, а не особенность алгоритма. Один и тот же алгоритм, тот же backtracking для turnpike (Zhang, 1982), для одних данных получает решение за квадратичное время, а для других — за экспоненциальное. Замечу также, что если не использовать прореживание данных, и пытаться решить beltway проблему чуть ли не методом грубой силы, то для данных с малым дублированием решение также может быть получено в полиномиальное время (хотя и на много порядков медленней). Для иллюстрации привожу рисунок, где верхняя кривая показывает время работы алгоритма построенного на графах. Верхняя кривая дальше не идет из-за нехватки памяти (32G).
Зависимость от данных — хорошо известный факт для программистов, хотя на него мало обращают внимание. К примеру, тот же qSort для большинства данных сортирует за время O(n log n), однако есть данные, где это время равно O(n^2).
Полиномиальный алгоритм для поиска одного решения может существовать, но не для любых данных. Возможность его существования — это скорее особенность самих данных, а не особенность алгоритма. Один и тот же алгоритм, тот же backtracking для turnpike (Zhang, 1982), для одних данных получает решение за квадратичное время, а для других — за экспоненциальное. Замечу также, что если не использовать прореживание данных, и пытаться решить beltway проблему чуть ли не методом грубой силы, то для данных с малым дублированием решение также может быть получено в полиномиальное время (хотя и на много порядков медленней). Для иллюстрации привожу рисунок, где верхняя кривая показывает время работы алгоритма построенного на графах. Верхняя кривая дальше не идет из-за нехватки памяти (32G).
Зависимость от данных — хорошо известный факт для программистов, хотя на него мало обращают внимание. К примеру, тот же qSort для большинства данных сортирует за время O(n log n), однако есть данные, где это время равно O(n^2).
Один и тот же алгоритм, тот же backtracking для turnpike (Zhang, 1982), для одних данных получает решение за квадратичное время, а для других — за экспоненциальное.
А у вас есть пример таких данных?
В диссертации Dakic T (в главе 3.3), доступной по ссылке
www.nlc-bnc.ca/obj/s4/f2/dsk1/tape3/PQDD_0014/NQ61635.pdf
описано как генерировать примеры для которых backtracking алгоритм для turnpike работает экспоненциальное время. Реализация кода несложна.
www.nlc-bnc.ca/obj/s4/f2/dsk1/tape3/PQDD_0014/NQ61635.pdf
описано как генерировать примеры для которых backtracking алгоритм для turnpike работает экспоненциальное время. Реализация кода несложна.
Вот сгенерил несколько Zhang примеров. Это множества X. Множества ΔX получатся из них вычислением разностей между элементами.
x = [13]{ 0 3 6 9 12 15 18 21 24 27 33 36 39 }
x = [21]{ 0 4 8 12 16 32 33 36 37 40 41 44 45 48 49 53 57 69 73 77 81 }
x = [22]{ 0 4 8 12 24 32 33 36 37 40 41 44 45 48 49 53 61 65 69 73 77 81 }
x = [23]{ 0 5 10 15 20 30 50 55 60 65 70 75 80 85 90 95 100 110 115 120 125 130 135 }
x = [30]{ 0 6 12 18 24 30 42 60 72 78 84 90 93 96 99 102 105 108 111 117 123 129 135 165 171 177 183 189 195 201 }
x = [32]{ 0 6 12 18 24 30 48 54 66 72 78 84 90 93 96 99 102 105 108 111 117 123 129 141 159 165 171 177 183 189 195 201 }
x = [32]{ 0 6 12 18 24 30 42 72 78 84 90 93 96 99 102 105 108 111 117 123 129 135 141 147 153 165 171 177 183 189 195 201 }
x = [37]{ 0 7 14 21 28 35 42 49 63 98 105 112 119 126 132 133 139 140 146 147 153 160 167 174 181 188 195 202 209 223 237 244 251 258 265 272 279 }
x = [13]{ 0 3 6 9 12 15 18 21 24 27 33 36 39 }
x = [21]{ 0 4 8 12 16 32 33 36 37 40 41 44 45 48 49 53 57 69 73 77 81 }
x = [22]{ 0 4 8 12 24 32 33 36 37 40 41 44 45 48 49 53 61 65 69 73 77 81 }
x = [23]{ 0 5 10 15 20 30 50 55 60 65 70 75 80 85 90 95 100 110 115 120 125 130 135 }
x = [30]{ 0 6 12 18 24 30 42 60 72 78 84 90 93 96 99 102 105 108 111 117 123 129 135 165 171 177 183 189 195 201 }
x = [32]{ 0 6 12 18 24 30 48 54 66 72 78 84 90 93 96 99 102 105 108 111 117 123 129 141 159 165 171 177 183 189 195 201 }
x = [32]{ 0 6 12 18 24 30 42 72 78 84 90 93 96 99 102 105 108 111 117 123 129 135 141 147 153 165 171 177 183 189 195 201 }
x = [37]{ 0 7 14 21 28 35 42 49 63 98 105 112 119 126 132 133 139 140 146 147 153 160 167 174 181 188 195 202 209 223 237 244 251 258 265 272 279 }
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
О разрешимости beltway проблемы в полиномиальное время