Является ли этот алгоритм хорошим способом определить, имеют ли два массива одинаковое содержимое в одинаковом порядке?

Question

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

Array A would be like this [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6, pnt1]
Array B would be like this [pnt2, pnt3, pnt4, pnt5, pnt6, pnt1, pnt2]
Array C would be like this [pnt2, pnt1, pnt6, pnt5, pnt4, pnt3, pnt2]
Array D would be like this [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4, pnt1]

Массивы A и B равны, потому что точки находятся в одном и том же порядке и одинаковых точках.Массивы A и C равны, потому что точки находятся в одном и том же порядке (но обращены), как и B и C. По той же причине.

Массив D не равен ни одному из других массивов, потому чтообход точки не в порядке.

Так что мой алгоритм выглядит следующим образом:

1) сравнивать длины массивов, должно содержать одинаковое количество элементов - постоянное время

2)найти A [0] в B, заданном как K - линейный поиск, линейное время

3) посмотреть, будет ли A [1] = B [K + 1] и так далее до A [n], линейное время

Естественно, индексы будут обтекать конец массива, возможно, с помощью оператора модов.

Есть ли алгоритм, который может работать лучше, чем этот?

Answer 1

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

Прежде всего, удалите повторяющиеся элементы, как указал ElKamino. Затем, в основном, вы хотите знать, можно ли получить A, вращая элементы B.

Когда A=[x1, x2, ..., xk], B будет иметь такое же содержимое в том же порядке, что и A, если и только если B=[x3, x4, ..., xk, x1, x2] или что-то подобное. В таком случае B можно назвать rotation of A. Однако этого недостаточно, так как вы также хотите проверить, является ли порядок таким же, но обратным. Затем вы можете применить ту же процедуру для обратного B или обратного A.

псевдокод

def isSamePolygon(A, B):
    remove the last element of A and last element of B
    return isRotation(A, B) or isRotation(A, reverse(B))

def isRotation(A, B): // returns true if A is a rotation of B
    // create an array which has two copies of A.
    // e.g [a1, a2, ..., ai, a1, a2, ..., ai]
    if (size(A) != size(B))
        return false
    temp_array = concat(A, A)
    return true if temp_array contains the elements of B in the exact same order,
        false otherwise

Анализ

Время выполнения и пространственные сложности isRotation являются линейными по размеру max (размер (A), размер (B)). Это связано с тем, что для создания temp_array требуется линейное время и линейное пространство размером A. Точно так же проверка наличия B в A также требует линейного времени для запуска.

Поправьте меня, если я ошибаюсь, но используя этот алгоритм, вы не сможете уменьшить асимптотические сложности. Однако, вы можете оптимизировать его, чтобы он работал быстрее. Вы можете поменять местами A и B, если size(A)>size(B). Более того; вы можете проверить обратное одновременно, вместо этого сделав два звонка.

Answer 2

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

Так что не намного лучшечем ваш алгоритм, который работает в оптимальное время O (N).[Вставьте шаг между 2 и 3, чтобы определить порядок обхода.]

Если разрешена предварительная обработка, для каждого многоугольника вы можете идентифицировать первую вершину в лексикографическом порядке (X, Y).Назовем это главной вершиной.Сделав это, вы сделаете шаг 1 вашего алгоритма бесполезным, поскольку два равных многоугольника имеют одну и ту же основную вершину и избавят от необходимости линейного поиска.

Еще лучше, если вы могли бы связать подпись с многоугольниками, вычисливCRC по координатам, начиная с главной вершины.Затем вы могли бы обнаружить различные полигоны с высокой вероятностью во времени O (1), просто сравнив сигнатуры.

Answer 3

Сводка:

1. Удалить повторную точку
2. Найти местоположение i минимального значения
3. Если значение в i-1 ниже, чем значение в i+1 перевернуть строку (нужно принять крайние случаи, т.е. i = 0 или i = n-1)
4. Повернуть массив так, чтобы минимальное значение находилось в заголовке

Общая сложность: O (n)

ПРИМЕЧАНИЕ: шаги 3 и 4 не являются абсолютно необходимыми.На шаге 2 вы можете получить местоположение минимума, а на шаге 3 - ориентация .При сравнении двух разных массивов, просто начните со сравнения * местоположений * с минимумов и двигайтесь в соответствии с ориентацией .

Например:

[pnt1, pnt2,pnt3, pnt4, pnt5, pnt6, pnt1] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6]

[pnt2, pnt3, pnt4, pnt5, pnt6, pnt1, pnt2] -> [pnt2, pnt3, pnt4, pnt5, pnt6, pnt1] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6]

[pnt2,pnt1, pnt6, pnt5, pnt4, pnt3, pnt2] -> [pnt2, pnt1, pnt6, pnt5, pnt4, pnt3] -> [pnt3, pnt4, pnt5, pnt6, pnt1, pnt2] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6]

[pnt1, pnt2, pnt3, pnt5, pnt6, pnt4, pnt1] -> [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4] -> [pnt1, pnt2,pnt3, pnt5, pnt6, pnt4]

Answer 4

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

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

В этом случае эти два многоугольника должны сравниваться равными:

P = ABCADEAFGAHIAJKA
Q = FGAHIAJKABCADEAF

Некоторые из приведенных алгоритмов могут игнорировать это, потому что первая (и лексикографически минимальная) вершина A в P повторяется. Однако, пока мы знаем, что edge не повторяется, мы можем без особых проблем адаптировать алгоритм:

1. Поиск P[0] в Q.
2. Найдя совпадение в Q[i], сравните P[1] с Q[i-1] и Q[i+1] (с соответствующей упаковкой).
3. Если ни одно из них не совпадает, вернитесь к 1 и продолжите поиск P[0] в Q, начиная с Q[i+1].
4. Как только совпадение найдено на шаге 2, продолжите сравнение, продвигаясь вперед через P и в том же направлении через Q. Либо будет найдено несоответствие, в этом случае полигоны будут разными, и вы сможете немедленно остановиться (нет необходимости продолжать поиск другого совпадения для P[0]), либо вы пройдете весь путь, и они будут идентичными.

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