Я хочу создать систему, в которой вы можете ввести курсы (3-7 курсов), которые вы хотите взять в колледже, а затем выбрать предпочтения («Утро», «День», «Вечер», «Ночь / М», «T», «W», «TR», «F») ,
Мне нужен способ, чтобы, когда программа запрашивает базу данных (MySQL), она возвращает наилучшее возможное расписание, которое было сделано в соответствии с этими параметрами. Я пишу это в php.
Кто-нибудь знает лучший способ сделать это? Или ссылку на какой-то образец кода, от которого я мог это понять?
Это NP-полный.
Если вы хотите что-то простое и быстрое, напишите эвристику конструкции, как First Fit Decreasing . Проще говоря, он заказывает курсы в соответствии с трудностями (размер ученика, …) и назначает их по одному в лучшем оставшемся слоте времени и комнате. Вы можете легко сделать это на PHP.
Если вы хотите сделать это правильно, как сказал @malejpavouk, используйте библиотеку CP. Сначала он использует эвристику конструкции, а затем выполняет метаэвристику, такую как поиск табу, имитированный отжиг, … Вот расписание разработки исходного кода на Java. Ищите хорошую библиотеку PHP PHP.
Возможно, вы захотите попробовать библиотеку программирования ограничений (CSP) …. В CSP вы указываете проблему (обычно NP Hard), и библиотека решает ее с помощью некоторых эвристик (имитированный отжиг, табу-поиск) или исчерпывающей DFS с некоторыми трюками ( согласованность дуги, бритвенное пространство для поиска) … Он может решить проблемы NPC с тысячами переменных … но его как-то сложно установить «прекрасные» параметры системы черного ящика …
Это сложная проблема оптимизации. Вот предлагаемая эвристика (со случайными прыжками).