Вопросы с тегом «optimization»

15
По заданному набору наборов найдите наименьший набор (ы), содержащий хотя бы один элемент из каждого набора.

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

14
Начальная температура в алгоритме имитации отжига

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

14
Нахождение максимального XOR двух чисел в интервале: можем ли мы сделать лучше, чем квадратичное?

Предположим, нам даны два числа и и мы хотим найти для .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Наивный алгоритм просто проверяет все возможные пары; например, в ruby ​​у нас будет: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if (i ^ j > max) max...

14
Какое свойство минусов позволяет устранить хвостовую рекурсию по модулю минусов?

Я знаком с идеей базового исключения хвостовой рекурсии, когда функции, которые возвращают прямой результат вызова для себя, могут быть переписаны как итерационные циклы. foo(...): # ... return foo(...) Я также понимаю, что в особом случае функция все еще может быть переписана, если рекурсивный...

14
Как найти максимальный набор элементов массива, такой, что каждый элемент в больше или равен количеству элементов в ?

У меня есть алгоритмическая проблема. Дан массив (или набор) из неотрицательных целых чисел. Найти максимальное множество из , что для всех ,,н STTTnNnSSSTTTa∈Sa∈Sa\in Sa⩾|S|a⩾|S|a\geqslant |S| Например: Если TTT = [1, 3, 4, 1, 3, 6], то SSS может быть [3, 3, 6] или [3, 4, 6] или [4, 3, 6]. В = [7,...

13
Каково оптимальное решение конкурса TSP Procter и Gamble 1962 года?

В 1962 году вы могли бы выиграть приз в размере 10 000 долларов (около 80 000 долларов в сегодняшних деньгах), если бы нашли решение евклидовой задачи коммивояжера, определенной в 33 городах. http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html Глядя на картинку, проблема кажется довольно...

13
Анализируя модифицированную версию карточной игры «Война»

Простая игра, в которую обычно играют дети, в игру «Война» играют два человека, используя стандартную колоду из 52 игральных карт. Сначала колода перемешивается, и все карты раздаются двум игрокам, так что у каждой по 26 случайных карт в случайном порядке. Предположим, что игрокам разрешено...

13
MIN-2-XOR-SAT и MAX-2-XOR-SAT: они NP-сложные?

Какова сложность MIN-2-XOR-СБMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} и MAX-2-XOR-СБMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Они в П? Они NP-хард? Чтобы формализовать это более точно, пусть Φ ( x ) = ∧NяСя,Φ(x)=∧inCi,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, где х =( х1, … , Хм)x=(x1,…,xm)\mathbf{x}...

13
Нахождение максимальной факторизации регулярных языков

Пусть язык L ⊆ Σ ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* регулярный. Факторизация LL\mathcal{L} - это максимальная пара ( X , Y )(X,Y)(X,Y) наборов слов с X ⋅ Y ⊆ LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X ≠ ∅ ≠ YX≠∅≠YX \neq \emptyset \neq Y , где X ⋅ Y = { x yX⋅Y={xyX \cdot Y = \{xy | x ∈ X , y ∈ Y...

13
Матрица цепочек умножения и возведения в степень

Если у меня есть две матрицы AAA и BВB с размерами 1000×21000×21000\times2 и 2×10002×10002\times1000 , соответственно, и я хочу вычислить (AB)5000(AВ)5000(AB)^{5000} , более эффективно сначала переписать выражение как A(BA)4999BA(ВA)4999ВA(BA)^{4999}B и только потом оценивать численно, потому что...

12
Выбор подмножества для максимизации минимального расстояния между точками

У меня есть набор точек , и у меня есть расстояние между каждой точкой . Эти расстояния евклидовы, но точки на самом деле находятся в пространстве признаков.CCCD(Pi,Pj)D(Pi,Pj)D(P_i,P_j) Из точек я хочу выбрать подмножество из точек. Назовите это подмножество . Я хочу выбрать это подмножество,...

12
Упаковать сумку подарков для Руперта легче, чем для Санты?

Или: нам нужен Руперт, чтобы вообще получать подарки? Помимо вопросов маршрутизации , Санта сталкивается со следующей проблемой (много-много раз): Имея сумку вместимостью ¹ CCC и набор подарков {p1,…,pn}{p1,…,pn}\{p_1, \dots, p_n\} , каждый размером sisis_i , он хочет сделать детей...

12
Оптимальная стратегия для абстрактной игры

Мне дали следующую проблему в интервью (которую я уже не смог решить, не пытаясь обмануть мой путь мимо): Игра начинается с положительного целого числа . (Например , 0 = 1234 ) . Это число преобразуется в двоичное представление, и N представляет собой количество битов в 1 . (Например, A 0 = b 100...

12
Является ли этот частный случай задачи планирования разрешимым за линейное время?

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

11
Вариант задачи о ранце

Как бы вы подошли к проблеме ранца в ситуации динамического программирования, если теперь вам нужно ограничить количество предметов в ранце константой ппp ? Это та же самая проблема (максимальный вес , каждый предмет имеет значение и вес ), но вы можете добавить только предмет (ы) в рюкзак и,...

11
Алгоритм сопоставления чисел с минимальным количеством ходов

Это своего рода вопрос о расстоянии редактирования, и он очень прост. У меня просто мозги на эту тему, и до сих пор не могу понять. Учитывая ряд чисел, например [3, 1, 1, 1] Как наиболее эффективно превратить все числа в одно и то же число с минимальным количеством «ходов»? Под «перемещением»...

11
Что такое алгоритм bicriteria приближение?

Что такое алгоритм bicriteria приближение? Это продолжает прибывать в случае потока данных кластеризации. Это связано с многоцелевой оптимизацией? Именно там я наткнулся на него: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. Статья посвящена потоковой версии алгоритма k-средних. В статье есть...

11
Как быстро мы можем вычислить размер максимального соответствия в невзвешенном двудольном графе?

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

11
Минимизировать максимальную составляющую суммы векторов

Я хотел бы кое-что узнать об этой задаче оптимизации: для заданных неотрицательных целых чисел aя , J , Kai,j,ka_{i,j,k} найдите функцию еff минимизирующую выражение МаксимумКΣяaя , ж( я ) , кmaxk∑iai,f(i),k\max_k \sum_i a_{i,f(i),k} Пример, использующий другую формулировку, может прояснить...

11
Непрерывная задача оптимизации, которая сводится к TSP

Предположим, мне дан конечный набор точек на плоскости, и меня просят нарисовать дважды дифференцируемую кривую через , чтобы ее периметр был как можно меньше. Предполагая, что и , я могу формализовать эту проблему следующим образом: С ( Р ) р я р я = ( х я , у я ) х I < х я +...