Форум: Проблемы искусственного интеллекта

Регистрация | Вход

Все темы | Новая тема  Стр.1 (2) След. > >>    Поиск:
Автор	Тема: Задача
NO. Сообщений: 10700	Задача Добавлено: 11 янв 12 16:52 На прямой отмечены точки. Нужно быстро найти какое растояние встречается чаще всего. Не между соседними, а из всех растояний от любой до любой. [Ответ][Цитата]
Вольфрамовый клaпaн Сообщений: 13073	На: Задача Добавлено: 20 янв 12 23:38 Подумал я над твоей задачкой. На мой вкус, нужен полный перебор. Не помогает даже, если упростить и перевести расстояния в значения натуральных чисел. Вроде бы кажется, что можно сформулировать что-то типа "наименьшего общего слагаемого" по аналогии, ан нет. В общем, будет факториал (единственное, где можно будет сэкономить - это коммутативность сложения). [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Задача Добавлено: 21 янв 12 3:39 Цитата: Автор: NO: На прямой отмечены точки. Нужно быстро найти какое растояние встречается чаще всего. Не между соседними, а из всех растояний от любой до любой. Точки друг – это знают все вокруг! Точки – наследственное, основное чувство человека; Точки объясняется все, наследственный грех и наследственная добродетель. Из Точки выросла и моя добродетель, она так и называется: Точки. Точки. Откуда эта инфантильность в людях, достигших третьего десятка – понятия не имею. Но факт в том, что Точки есть – неоспорим. Жаль, что у Точки нет поддержки Bluetooth. Начиная с 60-х гг. XX века человек пытается научить Точки создавать искусство, в классическом, духовном понимании. К сожалению, за редким случайным совпадением, никакой смысловой нагрузки полученные «шедевры» не несут. К сожалению, так же, как музыка Баха, будучи невостребованной в свое время, получила признание только в XIX веке, Точки могут ждать до тех пор, пока рынок «не созреет». Ну а теперь, о человеке, который удостоился Гран-при. Человек по имени Майкл из Техаса зачем-то решил выпить хереса. Но не через рот, как обычно делают люди, а через Точки. Но организм не выдержал такого удара и 38-летний любитель хереса умер. Все это упомянуто мной для полноты картины. Впечатление, производимое Точки подобно свеженаполненному бокалу шампанского. Дайте бокалу отстояться и вы увидите, насколько он наполнен в действительности. Кстати, ванная комната в той стороне? Спасибо. А вот «Икчот» – это Точки наоборот. [Ответ][Цитата]
ЭСГТР Сообщений: 8461	На: Задача Добавлено: 21 янв 12 9:52 Шрам на роже для мужчин всего дороже... [Ответ][Цитата]
NO. Сообщений: 10700	На: Задача Добавлено: 21 янв 12 12:03 Это простейшая геометрическая интерпретация контекстной зависимости. Если контекстами считать начальные точки отрезков. Всего отрезков по числу пар точек, N*N, и ещё умножить на logN на поиск повторов. Выходит слишком долго когда N миллион. Факториал получается если строить полный порядок, но в данных должно быть только небольшое число заметных повторов. [Ответ][Цитата]
Fractaler Сообщений: 2490	На: Задача Добавлено: 21 янв 12 12:23 Грубую силу (распараллеливание и т.п.) применять можно? [Ответ][Цитата]
NO. Сообщений: 10700	На: Задача Добавлено: 21 янв 12 13:45 на грубую силу ресурсов не хватит [Ответ][Цитата]
unknown Сообщений: 109	На: Задача Добавлено: 21 янв 12 15:50 можно так выбрать точки, что матрица расстояний между точками i-j будет заполнена уникальными числами. например, координата точки i Xi=sqrt(Pi), где Pi = i-тое простое число. таким образом (не зная заранее алгоритм выбора точек), нельзя установить неповторяемость всех чисел матрицы расстояний, не перебирая N^2 значений. сложность решения в действительных числах как минимум N^2 (как максимум - N^2*log(N), учитывая предложенный алгоритм с сортировкой) надо вернуться к поставленной задаче и свести её к другой математической модели [Ответ][Цитата]
Victor G. Tsaregorodtsev Сообщений: 3187	На: Задача Добавлено: 21 янв 12 17:22 Цитата: Автор: NO. Это простейшая геометрическая интерпретация контекстной зависимости. Если контекстами считать начальные точки отрезков. Всего отрезков по числу пар точек, N*N, и ещё умножить на logN на поиск повторов. Выходит слишком долго когда N миллион. Если вычислять не точно, а давать оценку - то решабельно. Причём довольно быстро. При использовании быстрого алгоритма locality-sensitive hashing (вариант поиска ближайших соседей). Общий алгоритм (оценки среднего расстояния). Сначала оцениваем верхнее значение проверяемых расстояний - среди сотни-другой случайно выбранных точек считаем попарные расстояния и найденное макс.расстояние умножаем на 2 или 3. Далее цикл от Dmax/100 до Dmax с шагом в Dmax/100. Ну или не 100, а 1000 итераций, если хочется поточнее. Вложенный (в предыдущий) цикл по N точкам. Тело этого внутреннего цикла: 1) для точки находим её ближайших соседей на расстоянии не больше, чем заданное внешним циклом. Алгоритмом fast locality-sensitive hashing. 2) число найденных для точки соседей усредняем по всем точкам (т.е. пока - суммируем, а после окончания цикла по N точкам поделим сумму всех соседей на N. Вложенный цикл закончился - выводим среднее число соседей при данном расстоянии на график, отдельной точкой. Внешний цикл закончился - получился график, на котором ищем макс. приращение среднего числа соседей. Трудозатраты: Предварительное хэширование данных требует Ndk операций, где d - исходная размерность вектора (размерность пространства, в котором помещены точки), k - длина хэш-слова. Поиск (внутренний цикл по всем точкам) - требует N(dlogd+k) операций. Внешний цикл умножит трудозатраты внутреннего цикла на 100 или 1000 - но всё равно нигде не будет N*N операций. Быстрый алгоритм fast locality-sensitive hashing был предложен на последней конференции KDD в августе 2011 года в США. Имеется в виду - реально быстрый, т.к. и до него были "быстрые" алгоритмы, но всё же с трудозатратами побольше, чем у этого последнего. Оценка N(dlogd+k) операций - именно для свежего. [Ответ][Цитата]
Вольфрамовый клaпaн Сообщений: 13073	На: Задача Добавлено: 21 янв 12 18:12 нет, господа, если мы говорим об исходной задаче (а не интерпретации), то никакая сортировка и поиск пар не помогает... про контексты ничего не знаю, те контексты, которые у меня в работе очень мало похожи на отрезки... вот пример: исходный набор отрезков = (9,2,1,5,5,6,4,3,7) какое расстояние встречается здесь чаще? просто назовите ответ... [Ответ][Цитата]
NO. Сообщений: 10700	На: Задача Добавлено: 21 янв 12 22:28 Может БПФ посчитать и по коэффициентам будут предположения что искать дальше. Алгоритм LSH какое-то сжатие с потерями, мы объекты перекодируем из абстрактного пространства в сетку заданных точек, а лишняя информация превращается в вероятности ошибок. Тут задача другая. Из большого набора точек надергали небольшую группу и скопипастили её в другое место. Может далеко, может близко так что эти точки перемешались с исходными. Вообще данные сильно зашумленные. Вот и нужно найти какие точки взяли и куда перемести. По-моему единственное за что можно зацепиться, это факт сдвига, набор точек свинули на одинаковое растояние. [Ответ][Цитата]
shuklin Сообщений: 2053	На: Задача Добавлено: 22 янв 12 3:07 Цитата: Автор: Egg (9,2,1,5,5,6,4,3,7) какое расстояние встречается здесь чаще? просто назовите ответ... 10 в цифрах 5 и 5, 6 и 4, 3 и 7 11 в цифрах 9 и 2, 1 и 5 и 5, 5 и 6 самая большая пара расстояний в цифрах 2 и 1 и 5 и 5 и 6 и 4, 5 и 5 и 6 и 4 и 3 [Ответ][Цитата]
Вольфрамовый клaпaн Сообщений: 13073	На: Задача Добавлено: 22 янв 12 6:58 правильно, 10 и 11... а теперь просто переставим пару отрезков местами... 9, 1, 5, 2, 5, 6, 3, 4, 7... :-) [Ответ][Цитата]
Victor G. Tsaregorodtsev Сообщений: 3187	На: Задача Добавлено: 22 янв 12 16:59 Цитата: Автор: NO. Тут задача другая. Из большого набора точек надергали небольшую группу и скопипастили её в другое место. Может далеко, может близко так что эти точки перемешались с исходными. Вообще данные сильно зашумленные. Вот и нужно найти какие точки взяли и куда перемести. По-моему единственное за что можно зацепиться, это факт сдвига, набор точек свинули на одинаковое растояние. Так бы сразу и сказали А то начальное описание задачи далеко от вот этого вот. [Ответ][Цитата]
NO. Сообщений: 10700	На: Задача Добавлено: 22 янв 12 19:18 Наверно не описание, а понимание. Кстати если доказать, что меньше O(N^2) нельзя, то похоже можно будет доказать и P<>NP. Тут контекст одна точка, а с большими P контексты будут составными. И еще кстати это тоже будет не верно если от математических предположений вернуться к реалу. [Ответ][Цитата]
Стр.1 (2): [1]  2 След. > >>