Какой самый эффективный способ написания системы учета курсов на PHP?

Question

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

Пример:

Для обязательных курсов:

• MAT101 - 1, 2, 5
• HIS102 - 2, 4, 6
• ENG105 - 3, 6, 7

И дополнительные курсы:

• LIT103 - 3, 4, 6
• CHE101 - 7, 1, 2
• BIO101 - 5, 4, 7
• MAT201 - 6, 5, 1
• ANT201 - 1

(не каждый факультативный курс должен быть включен в расписание)

Одним из возможных решений будет:

1. MAT101 [обязательно]
2. HIS102 [обязательно]
3. LIT103
4. BIO101
5. MAT201
6. ENG105 [обязательно]
7. CHE101

Какой самый эффективный способ написать это на PHP?

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

Answer 1

Проблема:

Проблема: учитывая набор обязательных и дополнительных курсов, каждый из которых доступно только в определенные временные интервалы (есть 7 временных интервалов) генерировать все возможные расписания.

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

Объект будет рекурсивным и будет принимать список пар, первая из которых будет временным интервалом, а второй элемент пары - списком возможных классов, которые могут заполнять временной интервал. Структура данных будет выглядеть так:

Для обязательных курсов:

• 1 - MAT101 , CHE101, MAT201, ANT201
• 2 - MAT101, HIS102 , CHE101
• 3 - ENG105, LIT103

и т.д.. где требуются полужирные курсы. Также потребуется список курсов, которые уже были выбраны предыдущими рекурсивными вызовами метода.

Функция будет

• проверьте, содержит ли список возможностей (описанных выше) вместе со списком уже выбранных курсов все необходимые курсы. Если нет, верните.
• выберите первый доступный временной интервал (назовите его myPick), а затем
• для каждого возможного класса, который заполнил бы этот временной интервал (назовите его currentClass),
  • Если этому методу был задан только 1 временной интервал в первом аргументе,
    • вывести список уже выбранных классов (заданных в качестве аргумента).
    • распечатать "$ currentClass $ myPick \ n",
    • распечатать дополнительный символ новой строки для разделения списков. вернуться.
  • иначе рекурсивно вызывайте метод, где вы передаете ему список временных интервалов, которые вы еще не выбрали (список временных интервалов, заданных в качестве аргумента, минус тот, который вы только что выбрали на шаге 2), за исключением того, что каждая возможность список для временных интервалов имеет класс, который вы напечатали, удален из него. вторым аргументом рекурсивного вызова должен быть список уже выбранных классов, данный этому экземпляру вызова с добавлением (<currentClass,myPick>) в список.

Это должно помочь вам начать.

Answer 2

Прежде всего, я согласен с Брайаном, что сначала вам нужно иметь полное представление о проблеме, а затем об алгоритме, который есть в Интернете.

Вы сказали, что не каждый необязательный курс должен быть включен, это означает, что этот шаблон является единственным принятым:

obc xxxxxx

где obcявляется обязательным уроком, а x является обязательным или необязательным.Порядок не имеет значения, конечно.

Если у вас есть N обязательных и M необязательных курсов (очевидно, N + M> 7 или N + M = 7), то вы можете иметь только N принятых шаблонов вышеуказанного вида.

Затем вы должны найти все различные расписания этого вида:

XXXXXX (6 курсов)

здесь порядок не имеет значения, и повторение не допускается, поэтому вам нужны комбинациииз 6 из (N + M), что составит:

(N+M)!/[6!(N+M-6)!] = K different such timetables.

Тогда все различные расписания 7 курсов будут:

K + K +... + K (N раз) = N * K

(Проверьте, правильно ли это, действительно ли вы устали сегодня, иначе предложите какой-нибудь код).

Я надеюсь, что этоможет помочь