Расчет всех битонных путей

Question

Я пытаюсь вычислить все битонные пути для данного набора точек.

Учитывая N баллов.

Я предполагаю, что есть O (n!) Возможных путей.

Рассуждение

У вас есть n баллов, из которых вы можете выбиратьВаше начальное местоположение.Оттуда у вас n-1 балл, затем n-2 балла ... который, кажется, равен n!.

Правильно ли это рассуждение?

Answer 1

Вы можете решить эту проблему с помощью старого доброго динамического программирования.

Пусть Count (верх, низ) будет числом незавершенных туров, так что top - это самая правая точка верхнего ряда, а bottom - самая правая точка, а всеточки слева вверху, внизу, уже в след.

Теперь, Count (i, j) = Count (k, j), где k = {i-1} U {l: l

Thisэто сложность O (n ^ 3).

Если вы хотите перечислить все битовые тропы, вместе с Count также отслеживайте все пути.На этапе обновления добавьте путь соответствующим образом.Это потребует много памяти, хотя.Если вы не хотите использовать много памяти, используйте рекурсию (та же идея. Сортируйте точки. В каждой точке рекурсии поместите новую точку - верхнюю или нижнюю и проверьте, есть ли пересечения)