Определение : Многоугольник PPP на плоскости называется монотонным относительно прямой LLL , если каждая прямая, ортогональная LLL пересекает PпP не более двух раз. Для данного многоугольника PPP возможно ли определить, существует ли какая-либо прямая LLL такая, что многоугольник PPP является...
Я пытался придумать систему, которая оценивала бы устав организации для определения их базовой логики. Я думаю, что система предикатов первого порядка будет работать для представления правил, которые могут быть переведены из текста с помощью тегов части речи и других методов НЛП. Существует ли...
В книге Марка де Берга и др. «Вычислительная геометрия: алгоритмы и приложения» описан очень простой алгоритм грубой силы для вычисления триангуляций Делоне. Алгоритм использует понятие недопустимых ребер - ребер, которые могут отсутствовать в допустимой триангуляции Делоне и должны быть заменены...
Указанные языки и , скажем , что их конкатенация является однозначной , если для всех слов , существует ровно один разложение с и , и неоднозначном иначе. (Я не знаю, есть ли установленный термин для этого свойства - трудная вещь для поиска!) В качестве тривиального примера, конкатенация с самим...
Этот вопрос касается подхода к компьютерным оппонентам, который я создал и который в настоящее время используется или планируется использовать в нескольких компьютерных играх. Фон В прошлом году, когда я пытался улучшить компьютерного противника для игры под названием «Флаги Сапер» (краткое...
Я изучал эти три, и я излагаю свои выводы из них ниже. Может ли кто-нибудь сказать мне, достаточно ли я их понял, или нет? Спасибо. Дейкстры алгоритм используется только тогда , когда у вас есть один источник , и вы хотите знать , наименьший путь от одного узла к другому, но не может в таких...
При использовании A * (или любого другого лучшего алгоритма поиска пути) мы говорим, что используемая эвристика должна быть допустимой , то есть она никогда не должна переоценивать фактическую длину пути решения (или перемещения). Как допустимая эвристика обеспечивает оптимальное решение? Я...
Я понимаю, что использование DFS «как есть» не найдет кратчайшего пути в невзвешенном графе. Но почему настройка DFS позволяет ему находить кратчайшие пути в невзвешенных графах с такой безнадежной перспективой? Все тексты на эту тему просто утверждают, что это невозможно сделать. Я не уверен (не...
Обычный вопрос интервью - дать алгоритм для определения того, является ли данное двоичное дерево сбалансированным по высоте (определение дерева AVL). Мне было интересно, можем ли мы сделать что-то подобное с красно-черными деревьями. Учитывая произвольное неокрашенное двоичное дерево (с узлами...
Я задал этот вопрос на StackOverflow , но я думаю, что это более подходящее место. Это проблема из курса Введение в алгоритмы : У вас есть массив с положительными целыми числами (массив не нужно сортировать или элементы уникальны). Предложите алгоритм , чтобы найти наибольшую сумму элементов,...
Во многих обсуждениях двоичной кучи в качестве поддерживаемой операции для минимальной кучи обычно указывается только ключ уменьшения. Например, глава 6.1 CLR и эта страница википедии . Почему ключ увеличения обычно не указывается для min-heap? Я полагаю, что это можно сделать в O (высота),...
Дан плоский план G=(V,E)G=(V,E)G=(V,E) и пусть GG\mathcal{G} обозначает его вложение в плоскость st, каждое ребро которого имеет длину . Кроме того, у меня есть множество точек в которых каждая точка содержится в . Кроме того, для любой точки в верно, что существует с геодезическим расстоянием до...
Скорее всего, этот вопрос задавался раньше. Это из CLRS (2-е изд) проблема 6.5-8 - Задайте алгоритм времени для объединения k отсортированных списков в один отсортированный список, где n - общее количество элементов во всех входных списках. (Подсказка: используйте минимальную кучу для слияния k-...
Предположим, два списка сопоставимых предметов: и и с. Пусть INV (u) будет числом инверсий в u. Я ищу эффективный алгоритм для вставки элементов s в вас с минимальным увеличением INV (u). По сути, я хотел бы вставлять объекты в список, сохраняя его «как можно более отсортированным», сохраняя...
По крайней мере, на Java, если я напишу этот код: float a = 1000.0F; float b = 0.00004F; float c = a + b + b; float d = b + b + a; boolean e = c == d; значение будет . Я полагаю, что это связано с тем, что поплавки очень ограничены в способе точного представления чисел. Но я не понимаю , почему...
Каковы некоторые примеры сложных проблем решения, которые могут быть решены за полиномиальное время? Я ищу проблемы, для которых оптимальный алгоритм является «медленным», или проблемы, для которых самый быстрый известный алгоритм является «медленным». Вот два примера: Распознавание совершенных...
Я пытаюсь построить все неэквивалентные матрицы (или если хотите) с элементами 0 или 1. Операция, которая дает эквивалентные матрицы, - это одновременный обмен строк i и j И столбцов i и j , например. для8×88×88\times 8n×nn×nn\times n1↔21↔21\leftrightarrow2...
У меня есть тетраэдр и многогранник . ограничен так, что он всегда разделяет все свои вершины с . Я хочу определить, находится ли внутри .п т п т пttt ppptttpppttt ppp Я хотел бы добавить одну деталь к проблеме в случае, если она может внести вклад в решение: - тетраэдр Делоне, а грани p...
Недавнее сообщение в блоге о поиске трех равномерно распределенных приводит меня к вопросу о стековом потоке с главным ответом, который утверждает, что сделал это за O (n lg n) время. Интересная часть состоит в том, что решение включает возведение в квадрат полинома, ссылаясь на статью, которая...
После того, как я узнал, как построить массив суффиксов в сложности O(N)O(N)O(N) , я заинтересовался открытием приложений массивов суффиксов. Одним из них является нахождение самой длинной общей подстроки между двумя строками за O(N)O(N)O(N) времени. Я нашел в интернете следующий алгоритм:...