Come abbinare i corsi con i requisiti

Dopo aver fatto un brainstorming su questo argomento per un po ', credo che un modo algoritmicamente efficiente per farlo sia quello di modellarlo come flusso massimo problema:

Inizia con un vertice di Origine e un vertice di Sink.

Ogni corso preso dallo studente è rappresentato da un vertice che è collegato al lavandino attraverso un bordo con capacità 1.

Ogni requisito è rappresentato da un vertice che è collegato alla Sorgente tramite un bordo con capacità C, dove C è il numero di corsi richiesti da tale requisito. Questo vertice è collegato da un bordo con capacità 1 a ciascun corso in grado di soddisfare tale requisito.

Si può quindi applicare Floyd-Fulkerson o un altro algoritmo Max-Flow. Se il flusso massimo attraverso il grafico è uguale alla somma del numero di corsi richiesti per ogni requisito, allora tutti i requisiti sono stati soddisfatti; ispezionare il flusso oltre i limiti dai requisiti ai corsi fornirà i dettagli dell'assegnazione dei corsi alle diverse esigenze.

Sulla base della complessità di Floyd-Fulkerson, penso che questo dovrebbe avere il tempo di esecuzione nel caso peggiore di O(r(R+S)) , dove r è il numero totale di corsi richiesti, R è la dimensione della specifica dei requisiti, e S è il numero di corsi effettuati dallo studente.

Ovviamente questo è tutto teorico adesso, dato che devo ancora implementarlo, e potrebbe essere eccessivo per la mia applicazione pratica.

(se solo come punto di partenza, verso una soluzione migliore)

quindi, ecco un ingenuo, backtracking di forza bruta (in ECMAScript 5) a cui stavo pensando, che dovrebbe sempre trovare una soluzione se ce n'è una, insieme alla traccia di essa.

Questo potrebbe certamente essere adattato, allo stesso modo, per esplorare e restituire tutte le possibili soluzioni (se più di una), insieme alle loro tracce:

link

function fulfilled(solution, requirements, attended, relaxer, index) {
  function newRequirement(original, isRelaxed) {
    if (isRelaxed) {
      var i = original.courses.indexOf(relaxer),
          // Exclude the relaxer course from
          // the courses of a relaxed requirement
          newCourses = original.courses.slice(0, i).
                       concat(original.courses.slice(i + 1)),
          // Decrement the weight of a relaxed requirement
          newWeight = original.weight - 1;
      return {
        id: original.id,
        weight: newWeight,
        courses: newCourses
      };
    }
    else {
      return original;
    }
  }
  function someUnfulfilled() {
    // True if any unfulfilled requirement,
    // false otherwise
    return requirements.find(function(requirement) {
      return requirement.weight > 0;
    }) != null;
  }
  // Are we trying to relax some requirement
  // by a given (relaxer) course, or are we
  // merely at the bottom of the call stack?
  if (typeof index !== "undefined") {
    // ... yes, we are relaxing a requirement; so make
    // a new requirement list differing only by it,
    // at index, relaxed by the relaxer course
    var relaxed = requirements[index];
    requirements = requirements.map(function(requirement) {
      return newRequirement(requirement, requirement.id === relaxed.id);
    });
  }
  // Is there any unfulfilled requirement?
  if (someUnfulfilled()) {
    // Is there any more courses being attended?
    if (attended.length > 0) {
      // Current course, head of the attended courses:
      var course = attended[0];
      for (var i = 0; i < requirements.length; i++) {
        var candidate;
        // Try to relax only the unfulfilled requirements:
        if ((candidate = requirements[i]).weight > 0) {
          // Remaining courses, after the current one:
          var remaining = attended.slice(1);
          // Can the current course contribute to the solution
          // by relaxing the candidate (i-th) requirement?
          if (
            (candidate.courses.indexOf(course) >= 0) &&
            (fulfilled(solution, requirements, remaining, course, i))
          ) {
            // Yes, it could; so, record its contribution,
            // and backtrack with a success signal
            solution.push({ course: course, requirement: candidate.id });
            return true;
          } else {
            // (Keep iterating through the requirements)
          }
        } else {
          // (Ignore the already fulfilled requirements)
        }
      }
      // The current course cannot relax any requirement,
      // and also contribute to the solution by doing so;
      // so, backtrack with a failure signal
      return false;
    } else {
      // Not enough of attended courses to fulfill the requirements;
      // so, backtrack with a failure signal
      return false;
    }
  } else {
    // All the requirements have been fulfilled by now,
    // so, backtrack with a success signal
    return true;
  }
}

per es.,

(come nell'esempio della tua domanda)

var allRequirements =
    [
      { id: "R1", weight: 2, courses: [ 'A', 'B', 'C', 'D' ] },
      { id: "R2", weight: 1, courses: [ 'A', 'B' ] }
    ],
    aSolution = [ ],
    input = [ 'A', 'B', 'C', 'D' ];

fulfilled(aSolution, allRequirements, input)
aSolution.reverse()

rendimenti:

aSolution === [
  {
    "course": "A",
    "requirement": "R1"
  },
  {
    "course": "B",
    "requirement": "R2"
  },
  {
    "course": "C",
    "requirement": "R1"
  }
]

mentre,

allRequirements =
    [
      { id: "R1", weight: 3, courses: [ 'A', 'B', 'C', 'D' ] },
      { id: "R2", weight: 2, courses: [ 'A', 'B', 'E' ] }
    ];
aSolution = [ ];
input = [ 'A', 'B', 'C', 'D', 'E' ];

fulfilled(aSolution, allRequirements, input)
aSolution.reverse()

rendimenti:

aSolution === [
  {
    "course": "A",
    "requirement": "R1"
  },
  {
    "course": "B",
    "requirement": "R2"
  },
  {
    "course": "C",
    "requirement": "R1"
  },
  {
    "course": "D",
    "requirement": "R1"
  },
  {
    "course": "E",
    "requirement": "R2"
  }
]

'HTH,