Представьте, что у нас есть ресторан с n столами. Клиент может запросить резервирование (за любой таблицей) для некоторого начального временного интервала в будущем. Мы не можем ни изменить начальный-конечный интервал, ни разбить его среди и назначить его другому ресурсу (таблице), но мы можем выбрать любую таблицу, которую мы хотим разместить, до прибытия клиента. Мы хотим разместить как можно больше бронирований , учитывая, что таблицы ограничены. Алгоритм жадной оптимизации (сортировка по дате начала) может найти очень быстрое решение проблемы, если мы не введем клиентские заблокированные таблицы . Некоторые клиенты предпочитают указанную таблицу c (из-за представления или из-за того, что им просто нравится место), и поэтому их резервирование нельзя перенести на другой ресурс (что делает ресурс недоступным для этого периода времени). До сих пор я пробовал: жадная оптимизация (не может найти решение), алгоритм geneti c (в большинстве случаев находит решение, но он очень медленный, например, когда есть много резервирований), некоторый пользовательский алгоритм, который пытается жадный переход от фиксированного к фиксированному резервированию (чаще всего происходит сбой)
Учитывая всю эту информацию, у меня есть 2 вопроса:
- Существует ли алгоритм, который решает подобные проблемы или подобные? (Я видел, что Branch and Bound может решить эту проблему, но если в нашем случае нет фиксированного резервирования, мы не сможем удалить ответвление решения. Редактировать: возможно, откат назад мог бы подойти для этой проблемы лучше?)
- Каково дерево состояний пространства для этой проблемы? Сейчас я использую только номера ресурсов (номера таблиц). Это правильно?
Мне также известен этот вопрос . Это та же проблема, но без фиксированных запросов на резервирование.