Расписание курсов с использованием php / mysql - PullRequest
Новая
       1

Расписание курсов с использованием php / mysql

0 голосов
/ 19 февраля 2011

Задача состоит в планировщике курса (для университета / колледжа). Если я не использую SQL: у меня есть один массив массивов и один 2-мерный массив. Каждый массив в первом массиве содержит уникальные идентификаторы различных курсов i, которые нужно пройти (каждый курс имеет разное время и дни, представленные этими уникальными идентификаторами). Второй массив содержит совместимый курс (то есть, который не создает временного конфликта). Если я выберу «n» количество курсов, я хочу найти все возможные комбинации курсов без временного конфликта. 

+++++++array 1+++++++++   ++++array 2+++++
course1 course2 course3   (compatible ids)
  122     235     654         122  235
  123     456     876         122  456
  124     190     943         122  654
  145     456     321         122  321
                              235  654...

В приведенном выше примере следующие идентификаторы могут составлять расписание: 122 235 654.
Единственное решение, которое я придумал, - это грубое форсирование (вложенный цикл). Есть ли более эффективный способ решения этой проблемы? Может быть, с помощью MySQL?

Ответы [ 2 ]

0 голосов
/ 19 февраля 2011 
create table course1 ( id INTEGER );
create table course2 ( id INTEGER );
create table course3 ( id INTEGER );
create table compatible ( id1 INTEGER, id2 INTEGER );

select distinct c1.id, c2.id, c3.id
from course1 c1
  INNER JOIN compatible p1 on p1.id1 = c1.id
  INNER JOIN course2 c2 on p1.id2 = c2.id
  INNER JOIN compatible p2 on p2.id1 = c2.id
  INNER JOIN course3 c3 on p2.id2 = c3.id
where exists ( select * from compatible p3 where p3.id1 = c1.id and p3.id2 = c3.id )

Это действительно не так гибко, и хотя оно должно быть быстрее, чем полное сканирование (пока индексируются идентификаторы), это потребует 2 ^ n ограничений, поэтому не подходит для большого количества курсов,Обратите внимание, что важен попарный порядок совместимой таблицы.

Вы можете повысить производительность своего решения php, используя хеш-таблицы и вложенные списки.Измените структуру вашего второго массива на 

array (
    122 => array( 235, 456, 654, 321),
    235 => array( 654...

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

0 голосов
/ 19 февраля 2011

Если это вариант, я бы определенно использовал MySQL и таким образом поддерживал бы большинство ваших реляционных данных.

...