Есть ли хорошо известный алгоритм оптимизации/сортировки комнат для гостиниц?
Задача состоит в том, чтобы перераспределить комнаты для максимального использования. Позвольте сказать, что у меня есть 10 номеров, дата начала и дата окончания каждой брони. Некоторые комнаты не могут быть использованы, а другие могут (флаг).
Любой намек в правильном направлении был бы велик. Спасибо.
Если у вас есть набор резервирований и фиксированное количество комнат, то вопрос заключается не в том, как максимизировать использование, а в том, чтобы проверить, действительно ли оговорки могут быть реализованы вообще или нет. Использование, очевидно, остается тем же, если все оговорки реализованы.
Еще один возможный случай использования заключается в том, что у вас есть набор зарезервированных номеров, которые, как вы знаете, могут быть реализованы, и затем вы пытаетесь установить новое резервирование, то есть новый клиент хочет сделать новое бронирование, и вы хотите проверить, может переместить некоторые из оговорок, чтобы создать место для нового.
В обоих случаях фактический вопрос заключается в том, как проверить, может ли реализоваться данный набор оговорок.
Для нереляционных оговорок это тривиально, поэтому предположим, что они могут быть реализованы, и вы хотите проверить, могут ли быть реализованы также перемещаемые оговорки.
Первая проверка - рассчитать на каждую ночь количество оговорок за ту ночь; если в любое время суток количество резервирований превышает количество доступных номеров после того, как фиксированные оговорки будут учтены, вы не сможете реализовать оговорки любыми трюками; ваш отель забронирован на ту ночь.
В противном случае вы можете использовать жадный алгоритм для попытки решения: обработать оговорки в порядке их дат начала и забронировать каждую резервацию в первую комнату (например, в порядке номеров), которая доступна. Если это дает вам решение, то вы поняли оговорки, и все готово.
Если это не сработает, вы можете использовать GRAPH COLORING для решения проблемы, и это универсальное решение. Постройте граф, где каждое резервирование является node, а два узла (резервирование) связаны тогда и только тогда, когда они перекрываются по времени. Включите фиксированные (не перемещаемые) оговорки на графике. Затем сделайте полную окраску графика с N цветами (N = общее количество комнат в вашем отеле), как только вы определили фиксированные оговорки с номерами номеров, к которым они относятся.
Вы можете обрабатывать также только частично гибкие резервирования таким образом, добавляя ссылку от резервирования r к специальному n-preolored node для комнаты n тогда и только тогда, когда резервирование НЕ может быть реализовано в комнате n (например, нижняя комната класс).
Этот же алгоритм раскраски графа успешно используется, например, в компиляторах для распределения регистров.
Конечно, вопрос заключается в том, как эффективно выполнять гравюру; для этого есть готовые реализации.
Удачи!
Вы хотите найти Drools-Planer: http://www.jboss.org/drools.
Backtracking работает очень хорошо для таких проблем, по моему опыту. Просто начните с присвоения первой оговорки типу комнаты. Продолжайте назначать резервирование до тех пор, пока не останется неназначенным. Затем возвращайтесь туда, где вы поступили не так, и соответствующим образом меняйте прежние решения.
Таким образом, вы либо найдете/все возможные решения (ы), либо вы докажете, что не существует.
Преимущество в том, что вы можете доказать нецелесообразность. Более того, обратное отслеживание позволяет вам найти "причину" невозможности.
Можно моделировать свою проблему с помощью математического программирования или программирования ограничений, используя множество готовых инструментов (попробуйте cplex или gurobi для MP и gecode или cp optimizer для CP, просто для того, чтобы назвать несколько) для моделирования и решения этих классов проблем. Обычно они имеют API, которые можно вызывать на большинстве языков программирования.
Я предполагаю, что этот ответ наступает после очень долгого времени, но я надеюсь, что он может помочь кому-то еще: -)