Я изучаю кратчайшие пути в ориентированных графах в настоящее время. Существует много эффективных алгоритмов для поиска кратчайшего пути в сети, например, dijkstra или bellman-ford. Но что, если график является динамическим? Говоря динамически, я имею в виду, что мы можем вставлять или удалять...
Эти термины смущают меня. Насколько я понимаю SAT решатель: решить выполнимость логики высказываний (используя DPLL или локальный поиск). Процедура принятия решения - это процедура определения выполнимости некоторой разрешимой теории первого порядка. SMT-решатель - это SAT-решатель + процедура...
Есть ли какой-нибудь алгоритм, который очень трудно распараллелить, или исследование все еще активно? Я хотел знать о любом алгоритме или любой области исследований в параллельных вычислениях. Все, что я искал, имеет «параллельную» реализацию. Просто хочу изучить некоторые неизученные области...
У удивительного числа проблем есть довольно естественное сокращение к линейному программированию (LP). См. Главу 7 в [1] для примеров, таких как сетевые потоки, двустороннее сопоставление, игры с нулевой суммой, кратчайшие пути, форма линейной регрессии и даже оценка схемы! Поскольку оценка схемы...
В настоящее время я читаю и наблюдаю за генетическим алгоритмом, и я нахожу его очень интересным (у меня не было возможности изучить его, пока я учился в университете). Я понимаю, что мутации основаны на вероятности (случайность - корень эволюции), но я не понимаю, почему выживание. Из того, что я...
У меня есть два способа составить список предметов в случайном порядке, и я хотел бы определить, являются ли они одинаково справедливыми (беспристрастными). Первый метод, который я использую, состоит в том, чтобы создать весь список элементов, а затем выполнить случайное перемешивание (скажем,...
Первоначально матроиды были введены обобщать понятия линейной независимости совокупности подмножеств над некоторыми основаниями установить . Некоторые проблемы, которые содержат эту структуру, позволяют жадным алгоритмам находить оптимальные решения. Позднее понятие жадных текстов было введено для...
Этот вопрос был перенесен из Биржи стека разработки программного обеспечения, поскольку на него можно ответить в Бирже стеков информатики. Мигрировал 7 лет назад . Я пытаюсь реализовать распределенную хэш-таблицу для выпечки, но некоторые вещи ускользают от моего понимания. Я надеялся, что кто-то...
В радикальной сортировке мы сначала сортируем по наименьшей значащей цифре, затем сортируем по второй наименьшей значащей цифре и так далее и получаем отсортированный список. Теперь, если у нас есть список из чисел, нам нужно бит, чтобы различать эти числа. Таким образом, количество проходов...
Это похоже на вопрос, который должен иметь простой ответ, но у меня нет однозначного ответа: Если у меня есть два битных числа , какова сложность вычисления ?nnna,pa,pa, pamodpamodpa\bmod p Простое деление aaa на ppp заняло бы время O(M(n))O(M(n))O(M(n)) где M(n)M(n)M(n) - сложность умножения. Но...
Этот вопрос был перенесен из Математического стека Exchange, потому что на него можно ответить в Информатике стека Exchange. Мигрировал 3 года назад . Я пытался найти алгоритм, чтобы найти максимальное покрытие вершинных циклов ориентированного графа то есть набор непересекающихся циклов, которые...
Этот вопрос был перенесен из теоретического обмена стеков информатики, потому что на него можно ответить в обмене стеков информатики. Мигрировал 7 лет назад . Эта проблема взята из интервьюstreet.com Нам дан массив целых чисел который представляет линейных сегментов, так что конечными точками...
За столом человек. й человек должен платить долларов.nnniiipipip_i Некоторые люди не имеют правильных счетов для оплаты точно , поэтому они придумали следующий алгоритм.pipip_i Во-первых, каждый кладет часть своих денег на стол. Затем каждый человек забирает деньги, которые он переплатил. Счета...
Я изучаю C ++ и заметил, что время выполнения функции push_back для векторов постоянно «амортизируется». В документации также отмечается, что «если происходит перераспределение, само перераспределение будет линейным во всем размере». Разве это не означает, что функция push_back - это , где - длина...
Допустим, есть такая программа, которая, если вы дадите частично заполненную судоку любого размера, даст вам соответствующую заполненную судоку. Можете ли вы рассматривать эту программу как черный ящик и использовать это для решения TSP? Я имею в виду, есть ли способ представить проблему TSP как...
Пусть G=(V,E)G=(V,E)G=(V,E) некоторый полный взвешенный неориентированный граф. Построим второй граф G′=(V,E′)G′=(V,E′)G'=(V, E') , добавив ребра одно за другим из в . Добавим края дляEEEE′E′E'Θ(|V|)Θ(|V|)\Theta(|V|)G′G′G' всего. Каждый раз, когда мы добавляем одно ребро (u,v)(u,v)(u,v) к E′E′E' ,...
Согласно этой странице , алгоритм Дейкстры - это просто BFS с очередью приоритетов. Неужели это так просто? Думаю,
Рассмотрим следующую алгоритмическую задачу: Входные данные: натуральное число вместе с его простой факторизацией. Найти: натуральные числа которые минимизируют , с учетом ограничения, чтоNNnх , у, zИкс,Y,Zx,y,zх у+ уZ+ х зИксY+YZ+ИксZxy+yz+xzх уZ= nИксYZзнак равноNxyz=n В чем сложность этой...
То, что я хочу сделать, это превратить мою математическую задачу в булеву проблему удовлетворенности (SAT), а затем решить ее с помощью SAT Solver. Интересно, знает ли кто-нибудь руководство, руководство или что-нибудь, что поможет мне преобразовать мою проблему в экземпляр SAT. Кроме того, я хочу...
Когда дело доходит до разработки алгоритмов, часто используются следующие методы: Динамическое программирование Жадная стратегия Разделяй и властвуй Хотя для первых двух методов существуют хорошо известные теоретические основы, а именно принцип оптимальности Беллмана и теория матроидов...