Когда я посмотрел « Динамический программный подход к решению задач секвенирования » Майкла Хелда и Ричарда М. Карпа, у меня возник следующий вопрос: почему сложность их алгоритма для TSP равна (∑n−1k=2k(k−1)(n−1k))+(n−1)(∑k=2n−1k(k−1)(n−1k))+(n−1)(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1) (стр....
Для проекта, над которым я работаю, я должен генерировать случайные остовные деревья с ограниченной высотой. В основном я делаю следующее: 1) Создаю связующее дерево. 2) Проверяю осуществимость, если возможно, сохраняю его. 1) Начиная с минимального связующего дерева (Прима или Крускала), я...
Мне было трудно найти алгоритм или опубликовать статьи о триангуляции самопересекающегося многоугольника (также многоугольника со структурой дырок). Может, кто-нибудь поможет мне найти опубликованную статью / алгоритм, пожалуйста? PS: кто-то пометит этот вопрос соответствующим образом, пожалуйста,...
Я имею в виду вопрос здесь: мощные алгоритмы слишком сложны для реализации . Если алгоритм является мощным, но слишком сложным для реализации, как вы можете быть уверены, что алгоритм правильный? Без реализации вы не сможете протестировать алгоритм в реальном сценарии, и такой сложный алгоритм...
Вот проблема, которая беспокоила меня некоторое время. Допустим, строка представляет собой последовательность из 1 и 0, а строка с подстановочными символами - это последовательность из 1, 0 и? S. Все строки и строки шаблона имеют одинаковую длину. Это стандартные подстановочные знаки UNIX; 10 ?? 1...
Поскольку это пятница, пришло время для CW вопроса. Я ищу эвристики, которые широко используются в задачах оптимизации. Чтобы ограничить область применения более «дружественной теории» эвристики, вот правила (некоторые произвольные, некоторые нет) Это должен быть четко определенный метод без...
У нас есть набор, LLLсписков элементов из множества N= { 1 , 2 , 3 , . , , , n }N={1,2,3,...,n}N = \{ 1, 2, 3, ..., n \}, Каждый элемент изNNN появляется в одном списке в LLL, Я ищу структуру данных, которая может выполнять следующие обновления: с о п с в т ( х , у)concat(x,y)concat(x, y) :...
Определите сетку в 3D как связанную совокупность тетраэдров с непересекающимися внутренностями (поэтому тетраэдры имеют только k-грани, k ≤ 2К≤2k \le 2). Учитывая произвольный граф, есть ли эффективная процедура для проверки, если он может быть встроен в виде сетки? Здесь вложение - это отображение...
Я был бы признателен за любые указания или термины, которые могли бы привести меня в правильном направлении. У нас есть ориентированный граф и длины для каждого ребра которое можно считать положительным. Существует специальный начальный узел и конечный узел .G = ( V, E)гзнак равно(В,Е)G=(V,E)Lя...
В капаситированных Facility Местоположение задачи (CFLP) , нам дано множество клиентов и набор потенциальных объектов . У каждого клиента есть спрос который должен обслуживаться одним или несколькими открытыми средствами. Каждый объект имеет стоимость открытия и имеет емкость , что является...
Мне интересно узнать больше об забытых в кеше алгоритмах и структурах данных, но есть так много статей, что я, честно говоря, не знаю, с чего начать. Я нашел оригинальный тезис Прокупа по этому вопросу, который кажется хорошей отправной точкой, но если есть простое и доступное введение в предмет, я...
Мне интересно, существуют ли систематические исследования сумм квадратичных форм в квадрате, похожих на квадратичные формы, что практически отражается в разложении по собственным значениям (что имеет огромное практическое значение). Пара примеров связана с важностью вопроса. Анализ основных...
У меня есть семейство задач линейного программирования: максимизировать учетом , . Элементы , и являются неотрицательными целыми числами, строго положительными. ( также должен быть целым, но я буду беспокоиться об этом позже.)c′xc′xc' xAx≤bAx≤bA x\le bx≥0x≥0x\ge0AAAbbbccccccxxx В моем приложении...
Учитывая субмодульную функцию еff на Ω =Икс1∪Икс2Ω=X1∪X2\Omega=X_1\cup X_2 где Икс1X1X_1 а также Икс2X2X_2 не пересекаются и е( S) =е1( S∩Икс1) +е2( S∩Икс2)f(S)=f1(S∩X1)+f2(S∩X2)f(S)=f_1(S\cap X_1)+f_2(S\cap X_2), Воте1f1f_1 а также е2f2f_2 субмодульный на Икс1X1X_1 а также Икс2X2X_2...
Я читаю старую статью MC Golumbic о графиках EPT (пересечение ребер в дереве). В статье показано, что число максимальных кликов экземпляра графа EPT является полиномиальным. Он приходит к выводу, что если оракул сообщает, что графггG является графиком EPT, то можно найти максимальную клику с...
(Извинения, если это неуместно или слишком широко. Я открыт для предложений о том, как это переформулировать.) Я заинтересован в отслеживании "древней" истории алгоритмов максимального потока и алгоритмов дискретной оптимизации в целом. Форд-Фулкерсон мой соломенный стартовый пункт. Каковы были...
Предположим, у меня есть список подмножеств . Я могу сделать предварительную обработку в этом списке, если это необходимо. После этой предварительной обработки мне предоставляется другой набор . Я хочу , чтобы определить , какие - либо множества с .XX\cal X{1,...,n}{1,...,n}\{1, ...,...
На поисковые системы все чаще полагаются как на стражу информации, однако критерии, используемые поисковыми системами для ранжирования результатов, непрозрачны для пользователей. Как пользователи могут быть уверены в том, что их результаты не являются предвзятыми или подделаны каким-либо образом,...
Мой вопрос немного расплывчатый. Мне было интересно, если (и как), мы можем применить понятие ширины дерева для задач упаковки в графах. Я был бы счастлив с любым пониманием или ссылками прошлой исследовательской работы на этом (предполагая, что они - некоторая связь)....
Есть ли какие-либо известные результаты о сложности поиска разделителя (любого размера), удовлетворяющего заданному свойству? Я знаю, что разделитель кликов легко найти (за полиномиальное время), а также знаю, что во многих работах рассматривается проблема поиска небольших разделителей или...