Ответы пользователя mayton2019 по тегу «Алгоритмы»

Алгоритм маршрута перевозчика?

mayton2019 @mayton2019

Bigdata Engineer

Это - задача коммивояжера. Но с дополнениями. В классической постановке например
коммивояжер должен объехать все 50 штатов и при этом его путь по дорогам должен быть минимален.

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

Плюс есть еще гараж А и Б но для нас это не важно. Просто все генерируемые маршруты будут А .... Б. По шаблону.

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

Методов решения много. Чаще всего я слышал про генетические алгортмы и отжиг.
Они - очень похожи. Учитывая что в примере очень мало пунктов развозки то задача за 1 секунду
может быть решена генетикой причем точныйм и наилучшим образом.

Ответ написан 16 окт.

Комментировать

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

mayton2019 @mayton2019

Bigdata Engineer

Задача по смыслу очень похожа на укладку рюкзака (Knapsack_problem)
https://en.wikipedia.org/wiki/Knapsack_problem

Ответ написан 29 авг.

Комментировать

Как сделать кэш динамики запасов?

mayton2019 @mayton2019

Bigdata Engineer

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

{ "tovar" : {
    "id" : "0001",
    "events" : [
         ......
         { "event" : 555, ......}
     ]
  }
}

Ответ написан 29 авг.

2 комментария

Есть идеи по алгоритму для авторизации по локации?

mayton2019 @mayton2019

Bigdata Engineer

Локации можно брать в расчет на глазок как приблизительную оценку. Как OSINT. И то с поправкой
на диапазоны IP проксей и ВПН и с учетом совершенно сбитого или отключенного GPS приемника.
Тоесть рассматривать это как рандомный шумящий фактор.

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

Я сильно сомневаюсь что результаты такого голосования будут иметь какой-то смысл. Да и зачем
вам делить локации?

Ответ написан 23 авг.

Комментировать

Как транспонировать биты числа максимально быстро?

mayton2019 @mayton2019 Куратор тега Java

Bigdata Engineer

Ищется функция вида

def transpose(matrix uint16) : uint16 = {}

Если она ДЕТЕРМИНИРОВАНА тоесть зависит от аргумента и все. То можно ее ускорить
путем МЕМОИЗАЦИИ тоесть создания просто таблицы расчитанных значений.
Это будет очень быстро.

Это удобно поскольку таблица получается не очень большая и влезает в разумные
рамки памяти. Если допустим мы говорим о 32х битах то можно изучать варианты.
В реальном мире линейного распределения аргументов не бывает. Распределение
всегда косит в какую-то сторону, и этим можно вользоваться, создавая кеши значений
типа LRU или дисковые базы данных как делают например, для
тяжелых расчетов или в вебе для медленных источников данных.

Ответ написан 06 авг.

Комментировать

Какая лучше нейросеть подходит под поиск нужных частей (подходящей части звонка)?

mayton2019 @mayton2019

Bigdata Engineer

1 коммутатор прислал часть А 8600100 Б 8700100 длительность 50сек время вызова 2024-08-03 12:51:00
2 коммутатор прислал часть А 8600100 Б 8700100 длительность 49сек время вызова 2024-08-03 12:51:00
3 коммутатор прислал часть А 8600100 Б 8700100 длительность 50сек время вызова 2024-08-03 12:51:01

Данная постановка для нейросетей выглядит достаточно ... натянутой что-ли.
Обычно НС мы внедряем тогда, когда у нас нет возможности описать логику на if-else.
В твоем-же случае если вектор параметров представить как { x1, x2, x3, x4 }, то
нам достаточно проверить что параметры x3, x4 попадают в окрестность некого времени "эпсилон"
(равной 1 секунда например) и после этого задача сведения трех записей в одну группу решается элементарно.

Для более обобщенных случаев почитай про метод кластеризации (машинное обучение ) https://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D...

Но он в свою очередь потребует для твоих векторов { x1,x2,x3,x4 } ввести некую меру дистанции
чтобы понимать насколько далеко один вектор убежал от другого (и не только по длительности звонка
но и возможно по номеру А и Б).

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

Ответ написан 03 авг.

1 комментарий

Как называется это свойство набора кодов (словаря)?

mayton2019 @mayton2019

Bigdata Engineer

Если твой парсер строк - это конечный автомат (Finite-State-Machine)
то твой вопрос звучит как существуют ли запрещенные переходы внутри этого
автомата.

Как в английском это звучит я не знаю. Prohibited? Disabled? Короче я учил теорию
автоматов по Совестким учебникам. Поищи сам.

Не стоит циклиться на названии.

Ответ написан 20 июл.

1 комментарий

Как правильно выстроить архитектуру игры-головоломки про спички?

mayton2019 @mayton2019

Bigdata Engineer

Плохо что ты не занимался радиотехникой. Цифры на экране - очень похожи на классический
7-сегментный индикатор. И его состояние может быть представлено 7 битами.
Например цифра 8 - горят все элементы можно представить как
1111111
Цифра 1 - горят соотвественно 2 и другие пять равны нулю. Отображение придумай сам.

Итого у тебя будет матрица 7 х 5 бит. Эта матрица и будет состоянием игры.

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

Что еще. В твоей игре будут запрещенные комбинации цифр которые надо отдельно проверить.

Ответ написан 19 июл.

1 комментарий

Как разбить треугольник в прямоугольной области на N треугольников?

mayton2019 @mayton2019

Bigdata Engineer

У тебя две задачи.

1) Первая - это пересечение треугольника и прямоугольника. Я не помню никаких
названий или реализаций этого алгоритма. Да. Сазерленд тебе будет полезен. Но он решает
только прямую и прямоугольник. Попробуй рассматривать треугольник - как многоугольник
и отрезай от него по одной стороне с 4 сторон.

2) Вторая называется - триангуляция. Она много где описана в инженерной графике. Книг
точно не помню но поищи. Шикин и Боресков. Эгрон. Павлидис. Они точно должны были
что-то писать про это.

Ответ написан 30 июн.

Комментировать

Какой правильный класс коллекции для хранения сортируемого списка?

mayton2019 @mayton2019 Куратор тега Java

Bigdata Engineer

Задача : сделать так, чтоб при принудительном обновлении в первую очередь обновлялись объекты, которые не обновлялись дольше всего.

Мне не очень понятно, что мешает их обновить сразу?

Стоимость операций с HashMap, TreeMap достаточно дешевая чтобы этим вопросом вообще не
беспокоиться.

Если бы у тебя было очень много объектов и они не влазали бы в heap, то тогда я-бы предложил
LRU Cache (Last Recently Used). Но у тебя 5000 объектов. Это мало для БД и кеша горячих объектов.

Ответ написан 14 июн.

Комментировать

Как найти решение для задачи?

mayton2019 @mayton2019

Bigdata Engineer

Мы ищем функцию select_camera следующего вида. (На неком подобии Python/Scala)

case class Range(begin:Double,end:Double)

case class CameraProps(distance_range : Range, luminosity_range : Range) 

def select_camera(distance : Double, luminosity : Double, cams : List[CameraProps]) : List[Int] = {
  ....
}

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

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

Быстрые алгоритмы и структура это QuadTree-s, R-Trees (Antonin Guttman).
И те и другие - подходят. Они по сути - вспомогательные структуры для ускорения поиска камер.

При условии что точка будет двигаться а камеры стоят стационарно а искать надо много.

Если двигаются и камеры и точки - то тогда надо искать другие структуры данных.

Ответ написан 07 июн.

Комментировать

Как составить список уникальных комплексных решений для уравнения? Как понять что число 0.999999 то же что 1.0000001?

mayton2019 @mayton2019

Bigdata Engineer

Можно методом Монте-Карло перебирать все случайные решения на всей области определения.
Потом - делать квантизацию (так чтобы такое значение 0.99999 равнялось такому 1.000001)
и квантизованные пары (ключи) складывать в какую-то хеш-табличку с подсчетом.
Триллион итераций ждать не будем. Может быть где-то через тысяч сто у нас будет
гистограмма. И бери из нее top 10 значений. Это и будут твои 10 уникальных.

Ответ написан 23 мая

1 комментарий

Как правильно реализовать структуру данных для упаковки многомерного(кол-во измерений не известно сразу)массива в JSON / любой другой формат данных?

mayton2019 @mayton2019

Bigdata Engineer

Если размерности известны. Например 120 на 30 на 200 на 40 то такой гипер-кубик
можно упаковать в обычный линейный массив. И он будет по длине равен 28800000 элементов.
Таким образом любой многомерный массив укладывается в одномерный.
Формула доступа будет достаточно простая. Почти тоже что и для матрицы.

Тоесть задача хранения - решена.

Ответ написан 30 апр.

9 комментариев

Какие существуют методы сравнения качества изображения?

mayton2019 @mayton2019

Bigdata Engineer

Я помню что в умных статьях, которые сравнивают алгоритмы сжатия типа JPEG/J2k/Lurawave
часто приводили параметр PSNR (Peak signal-to-noise ratio) и на базе него пытались
построить какие-то выводы. Период этих революций сжатия приходился примерно на 2000-е годы.

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

В случае когда картинок много и мы не можем определить где оригинал то я-бы предложил
смотреть спектры высоких частот. Где их больше - там и предположительно оригинал.
Если с изображением работали (scale, фильтры) то обычно метрика высоких частот будет
слабее выражена.

Вобщем сравнивать вам придется не по 1 параметру а по вектору. Увы-увы... в наше современное
время маш-обучения сравнение векторов это нормально. Так и должно быть.

Ответ написан 21 апр.

3 комментария

Как правильно удалять элементы хэш таблицы?

mayton2019 @mayton2019

Bigdata Engineer

Судя по всему метод открытой адресации - это проосто нехороший метод для решения проблем хеширования. Я не знаю, толи преподаватели пошли очень душные. Толи студенты любопытные, но всех
тянет как магнитом к open addressing (OA), хотя многие продуктовые библиотеки коллекций C++/C#/Java
просто не используют OA по дефолту. Они берут Separate Chaining и это работает всегда хорошо.

Я-бы сделал следующую рекомендацию. Поскольку удаление элемента при OA - тяжелая операция,
которая требует перепроверки всех элементов цепочки ключа, то лучше вообще не удалять а
пере-создавать новую таблицу или отказаться от OA в пользу Separate Chaining.

Ответ написан 10 мар.

2 комментария

Какая структура с лимитом памяти позволит ускорить поиск по огромному файлу с набором бинарных данных?

mayton2019 @mayton2019

Bigdata Engineer

Коробочным решенеим задачи может быть префиксное дерево (Trie) с лимитом в 100Мб
которое в листовых узлах должно хранить списки искомых записей.

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

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

Ответ написан 06 мар.

Комментировать

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

mayton2019 @mayton2019

Bigdata Engineer

Так-же как и в индексировании документов. Строится некое векторное представление документа.
И потом похожие векторы - указывают на одинаковые (99.9%) документы. Методик векторизации
много. В основном это токенизация слов и свертывание их к хешу.

Ответ написан 28 дек. 2023

2 комментария

В чем проблема в коде работы с графом?

mayton2019 @mayton2019

Bigdata Engineer

Зачем делать безсмысленный makeStep? Пускай он возвращает булево значение.

boolean makeStep(Graph &graph, ValuesTable &table) { .... }

Не было отрицательных свойств среди вершин - значит пускай вернет true.
Тогда будет стоп алгоритма. И не надо будет
делать дополнительных пере-расчетов.

Ответ написан 24 нояб. 2023

7 комментариев

Через какой алгоритм решать эту задачу?

mayton2019 @mayton2019

Bigdata Engineer

Стоя на 12 этаже можно за 1 ход попасть на 23 этах (Вверх) или на 6 этаж (Вниз).
Стоя на 6 этаже можно за 1 ход попасть на 11 этаж (ВВ) или на 3 этах.
(и так далее)

Вот такой граф получается. Немного напоминает Гипотезу Коллатца. За счет минус единички
адрес меняется четность и есть надежда что мы не зациклимся а все таки куда-то двигаемся.
Значит можно упорным баловством с кнопками куда-то приехать.

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

Ответ написан более года назад

4 комментария

Как написать свой матричный фильтр (например размытие по Гауссу)?

mayton2019 @mayton2019

Bigdata Engineer

Фильтр Гаусса ничего не знает о цвете. Он просто применяется к матрице вещесвтенных чисел.
Поэтому обычно картинку в формате RGB переводят в трех-слойную вещественную матрицу { double, double, double }
и фильтр Гаусса применяют трижды для каждого слоя. И результат потом снова сводят в RGB.

Есть миллиард хитростей как делать это в целых или в вещественных числах или как использовать SIMD, Parallel
computing e.t.c. но ты сделай сначала самый простой и работающий вариант а потом уже оптимизация.

С оптимизацией неизбежно сталкиваются все новички на цифровых фильтрах. Потому-что без нее фильры
работают на порядки медленнее чем в Photoshop например.

Ответ написан более года назад

Комментировать

Войдите на сайт