Я провел некоторое тестирование различных начальных температур в своем имитирующем алгоритме отжига и заметил, что начальная температура влияет на производительность алгоритма. Есть ли способ расчета хорошей начальной...
Учитывая невзвешенный DAG (направленный ациклический граф) D=(V,A)D=(V,A)D = (V,A) и две вершины sss и ttt , возможно ли найти кратчайший и самый длинный путь от sss до ttt за полиномиальное время? Длина пути измеряется количеством ребер. Я заинтересован в поиске диапазона возможных длин пути за...
Предположим, что нам дано различных целых чисел , таких что для некоторой константы и для всех .a 1 , a 2 , … , a n 0 ≤ a i ≤ k n k > 0 innna1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n0≤ai≤kn0≤ai≤kn0 \le a_i \le knk>0k>0k \gt 0iяi Нас интересует нахождение отсчетов всех возможных попарных сумм...
Мне нужно построить d-регулярный граф экспандера для некоторого небольшого фиксированного d (например, 3 или 4) из n вершин. Какой самый простой способ сделать это на практике? Построение случайного d-регулярного графа, который оказался расширителем? Я также читал о конструкциях Маргулиса и графах...
Мне было интересно, когда языки, которые содержат одинаковое количество экземпляров двух подстрок, будут регулярными. Я знаю, что язык, содержащий равное количество единиц и нулей, не является регулярным, но является языком, таким как , где = число экземпляров подстроки "001" равно числу...
Существует жадный алгоритм поиска минимального покрытия вершин дерева, который использует обход DFS. Для каждого листа дерева выберите его родителя (т.е. его родитель находится в минимальном покрытии вершин). Для каждого внутреннего узла: если ни один из его дочерних элементов не выбран, выберите...
Задача Дана машина Тьюринга которая знает время выполнения O ( g ( n ) ) относительно длины ввода n , является временем выполнения M ∈ O ( f ( n ) )MMMO (г( н ) )О(грамм(N)){O}(g(n))NNnM∈ O ( f( н ) )M∈О(е(N))M \in {O}(f(n)) ? Разрешима ли указанная выше проблема для некоторых нетривиальных пар...
Я знаю, что мы можем минимизировать DFA, находя и объединяя эквивалентные состояния, но почему мы не можем сделать то же самое с NFA? Я не ищу доказательств или чего-то в этом роде - если только доказательство не проще для понимания. Я просто хочу интуитивно понять, почему минимизация NFA так...
Известно, что язык слов, содержащих одинаковые числа 0 и 1, не является регулярным, а язык слов, содержащих одинаковые числа 001 и 100, является регулярным ( см. Здесь ). Учитывая два слова , разрешимо ли, если язык слов, содержащий равное количество и является...
Может ли кто-нибудь отослать меня к рецензируемым статьям, изучающим преимущества или недостатки написания кода в функциональном стиле? Существуют ли документы, в которых обсуждается применение лямбда-исчисления в таких областях, как машинное обучение, языковой дизайн и т....
Я понимаю, что недетерминированные автоматы нажатия могут быть улучшением по сравнению с детерминированными, поскольку они могут «выбирать» из нескольких состояний, и есть некоторые контекстно-свободные языки, которые не могут быть приняты детерминированным выпуском. Все-таки я не понимаю, как...
Я просматривал этот сайт, и там говорится, что люди нашли решения для туров TSP, которые на 0,031% выше, чем оптимальный тур. Не найдя оптимального тура, откуда они знают, какой длины он должен...
Итак, как известно, проблема решения ILP 0-1 является NP-полной. Показать его в NP легко, а оригинальное сокращение было от SAT; с тех пор было доказано, что многие другие проблемы NP-Complete имеют составы ILP (которые функционируют как сокращение от этих проблем до ILP), потому что ILP очень...
ЧАСЧАСHч : U→ { 0 , … , M- 1 }час:U→{0,...,M-1}h: U \rightarrow \{0,\ldots,M-1\}∀ х , у∈ U, х ≠ у⇒ Prh ∈ H[ ч ( х ) = ч ( у) ] ≤ 1M∀Икс,Y∈U,Икс≠Y⇒Prчас∈ЧАС[час(Икс)знак равночас(Y)]≤1M\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M} Вы можете узнать больше о...
Какой алгоритм вы бы использовали, чтобы найти кратчайший путь графа, который вложен в евклидову плоскость, чтобы путь не содержал каких-либо самопересечений (во вложении)? Например, на графике ниже вы хотите перейти от . Обычно такой алгоритм, как алгоритм Дейкстры, выдает такую...
Пусть GGG граф, и пусть sss и ttt две вершины GGG . Можем ли мы эффективно выбрать равномерно и независимо случайным образом кратчайший путь sss - ttt из множества всех кратчайших путей между sss и ttt ? Для простоты можно предположить, что GGG простая, ненаправленная и невзвешенная. Даже во многих...
У меня есть два больших наборов целых чисел AAA и . Каждый набор содержит около миллиона записей, и каждая запись представляет собой положительное целое число длиной не более 10 цифр. BBB Каков наилучший алгоритм для вычисления и ? Другими словами, как я могу эффективно вычислить список записей ,...
Это произошло, когда я пытался ответить на этот вопрос о минимизации длины проводки . Я собирался назвать это проблемой "полигамного брака", но интернет, так что котята. Ура! Предположим , что мы имеем MMM котят , которые должны быть приняты NNN человек, M>NM>NM > N . Для каждого котенка, iii...
Можно ли использовать алгоритм сортировки с нетранзитивным сравнением, и если да, почему транзитивность указана в качестве требования для сортировки компараторов? Фон: Алгоритм сортировки обычно сортирует элементы списка в соответствии с функцией сравнения C (x, y), с...
Определим язык LLL как L = { a , b } ∗ - { w w ∣ w ∈ { a , b } ∗ }L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\} . Другими словами, LLL содержит слова, которые не могут быть выражены как какое-то слово, повторенное дважды. Является ли LLL контекстно-свободный или нет? Я пытался...