Как этот предикат Пролога может стать быстрее, чем экспоненциальный?

Question

У меня есть предикат, который проверит, доступна ли комната в рамках данного расписания (состоящего из событий).

Проверка, доступна ли комната и не занята ли другим событием, в настоящее время работает экспоненциально. Я хотел бы оптимизировать это.

Что я сейчас делаю:

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

Я думал об этом, но единственный способ сделать это более эффективным - использовать утверждения.

Мне интересно, есть ли другой способ, кроме использования утверждений для повышения эффективности?

Answer 1

Оптимальное планирование - определенно экспоненциальная проблема. Это сродни оптимальной упаковке бункера. Это целая область исследований.

Мне кажется, что то, что вы делаете, это O (n²): вы сравниваете каждый элемент в списке с каждым другим элементом в списке. Но вы делаете это только один раз, потому что вы сравниваете каждый элемент после этого элемента в списке. Таким образом, элемент 1 сравнивается с N-1 другими элементами, а элемент N-1 сравнивается только с 1 другим элементом. Это не абсурдная временная сложность для вашей проблемы.

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

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

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

Чтобы пойти дальше, я думаю, нам нужно узнать больше о вашей проблеме.