Вопросы по теме 'approximation'
Приблизительный алгоритм нахождения леса Штейнера
Рассмотрим взвешенный граф G=(V,E,w). Нам дано семейство подмножеств вершин V_i.
Лес Штейнера — это лес, который для каждого подмножества вершин V_i соединяет все вершины в этом подмножестве с деревом.
Пример: только одно подмножество V_1 = V....
821 просмотров
schedule
31.08.2022
Быстрое приближенное решение линейных уравнений?
Мне нужно решить систему из N линейных уравнений в качестве промежуточного шага в числовом оптимизаторе. AFAIK достаточно простые алгоритмы для этого точно - O (N ^ 3) (хотя я видел ужасно сложный в какой-то математической статье, который мог бы...
2498 просмотров
schedule
16.05.2022
Как измерить сложность строки?
У меня есть несколько длинных строк (~ 1 000 000 символов). Каждая строка содержит символы только из определенного алфавита, например
A = {1,2,3}
Примеры строк
string S1 = "1111111111 ..."; //[meta complexity] = 0
string S2 = "1111222333...
1022 просмотров
schedule
26.10.2022
Простая аппроксимация обратной неполной гамма-функции
Как можно аппроксимировать обратную неполную гамма-функцию Г(s,x) некоторой простой аналитической функцией f( с, Г)? Это означает, что нужно написать что-то вроде x = f(s,Г) = 12*log(123,45*Г) + Г + 123,4^s.
(Мне нужны хотя бы идеи или ссылки.)
3622 просмотров
schedule
27.05.2022
Минимизация цветов: вариант алгоритма рюкзака?
Работая над проектом, я столкнулся с этой проблемой, которую я переформулирую здесь в терминах, выходящих за пределы реальной области проблемы (полагаю, я мог бы говорить о калибрах фейерверков и формах, но это еще больше усложнило бы понимание). Я...
494 просмотров
schedule
26.12.2022
В какой ситуации может понадобиться ряд Тейлора для полинома?
Мне трудно понять, почему было бы полезно использовать ряд Тейлора для функции, чтобы получить приближение функции, вместо того, чтобы просто использовать саму функцию при программировании. Если я могу сказать своему компьютеру вычислить e^(.1), и он...
1731 просмотров
schedule
11.09.2022
Приближение для поиска значения с использованием Python
Итак, у меня есть один вектор альфы, один вектор беты, и я пытаюсь найти тета, когда сумма всех оценок (для альфы от i до n и бета от i до n) равна 60.
math.exp(alpha[i] * (theta - beta[i])) / (1 + math.exp(alpha[i] * (theta - beta[i])
По...
978 просмотров
schedule
27.05.2022
Метод Герона в Python
Метод Герона генерирует последовательность чисел, которые представляют все более и более точные приближения для √ п . Первое число в последовательности является произвольным предположением; каждое второе число в последовательности получается из...
6893 просмотров
schedule
25.10.2022
Оптимальный алгоритм планирования смен
Некоторое время я пытался решить проблему с расписанием для пула, над которым я работал. Эта проблема заключается в следующем ...
В бассейне работают X многих спасателей, и у каждого есть определенное количество часов, которое они хотели бы...
16408 просмотров
schedule
23.01.2023
Центрированное конечно-разностное приближение 2-го порядка
Этот вопрос может показаться математическим, но это скорее вопрос программирования, связанный с дискретизацией, поэтому я решил задать его здесь.
Задача состоит в том, чтобы найти конечно-разностную аппроксимацию второго порядка частной производной...
2104 просмотров
schedule
10.10.2022
Ошибка цикла while с методом Netwon-Raphson
Я пытаюсь найти применение методу Ньютона-Рафсона, чтобы найти корни. Он делает это, делая предположение, а затем улучшая предположение после каждой итерации, пока вы не получите один из нулей.
Поскольку метод Ньютона-Рафсона быстро находит нули,...
764 просмотров
schedule
29.08.2022
Реализация населения методом Монте-Карло
Я пытаюсь реализовать алгоритм Монте-Карло для населения, как описано в этой статье (см. стр. 78 Рис.3) для простой модели (см. функцию model() ) с одним параметром с использованием Python. К сожалению, алгоритм не работает, и я не могу понять,...
542 просмотров
schedule
08.02.2023
Как аппроксимировать сумму числа делителей от 1 до n?
Проблема
Я хочу решить эту проблему:
Пусть количество делителей = d(n) (например, d(6)=4, потому что число 6 имеет 4 делителя, {1, 2, 3, 6}), я хочу вычислить d(1)+d(2 )+d(3)+...+d(n). Но я не могу рассчитать для больших n, таких как 10 ^ 20...
721 просмотров
schedule
10.05.2023
Смешанное целочисленное ближайшее оптимальное решение в Matlab
Можно ли найти решение, ближайшее к оптимальному для смешанно-целочисленной задачи? Например, я бы хотел, чтобы упрощенная проблема была ниже:
f = [1;1;1];
intcon = 1:3;
Aeq = [0.99,0.97,0.15];
beq = 0.16;
lb = zeros(3,1);
ub = [1;1;1];
x =...
599 просмотров
schedule
06.11.2022
Как аппроксимировать x-й процентиль для большого неизвестного количества чисел
Недавно наткнулся на этот вопрос о том, как найти x-й процентиль для данного потока чисел. У меня есть базовое понимание того, как этого можно было бы достичь, если бы поток был относительно небольшим (можно сохранить в памяти, отсортировать и найти...
383 просмотров
schedule
27.06.2023
Многомерное приближение в Python
Мне нужно аппроксимировать (по функции Гаусса) 2-х или 3-х мерные наборы данных с помощью Python, но я нашел только методы интерполяции. Кто-нибудь слышал о какой-то библиотеке, которая может это сделать?
79 просмотров
schedule
25.06.2023
Проверить правильность раскраски случайного графа (Python)
Итак, я пробую другой подход к раскраске графа, то, что я делал, в основном, назначал случайным образом цвета узлам графа, и что я хочу сделать, это после назначения этих цветов проверить правильность этой раскраски (нет соседних узлов, имеющих того...
535 просмотров
schedule
02.05.2024
Как использовать MIPGap и TimeLimit от Gurobi в Python?
Я работаю над крупным планом MILP. Поэтому я должен установить разумное значение времени или установить MIPGap на разумный уровень. Я уже знаю документацию от gurobi.
MIPGap: https://www.gurobi.com/documentation/6.5/refman/mipgap.html...
1237 просмотров
schedule
22.04.2022
Для заданного набора точек в двумерном пространстве, каждая из которых имеет некоторый штраф, найдите выпуклую область, покрывающую ровно N точек, минимизирующую штраф.
Есть ли алгоритм для этого? Ничего страшного, если это приближение или дополнительные ограничения для упрощения. Вот более подробное заявление
У меня есть K точек в каком-то низкоразмерном пространстве (скажем, 2d). У каждого есть штраф (может...
60 просмотров
schedule
23.05.2022
Как обосновать коэффициент аппроксимации этого детерминированного алгоритма (взвешенный MAX-k-Cut)
Взвешенная задача MAX-k-CUT требует максимального взвешенного разреза во взвешенном неориентированном графе. Предположим теперь, что каждая вершина одна за другой жадно приписывается группе, которая может максимизировать общий вес новых разрезов....
57 просмотров
schedule
21.03.2023
