help для написания алгоритма

Question

Я занимаюсь разработкой алгоритма для назначения, и я не уверен, что написал правильный алгоритм, не могли бы вы направить меня? Вопрос: Есть n студент S1, S2, ..., Sn и и n класс: G1, G2, ... Gn. Каждому учащемуся должен быть присвоен ровно один класс, и ровно один студент назначается на один класс. Если Tij - значение присвоения Si в Gj, я должен найти Q-подмножество T, которое является максимальным. (Я должен назначить рабочих для наилучшей возможной работы) Пример для этого вопроса: если у меня есть два студента S1 и S2, а также у меня есть 2 Grad G1 и G2, у меня есть, например, T12 = 12, T21 = 7, T11 = 9, Т22 = 16 подмножество должно быть Q = {Т12, Т22} Я написал следующий алгоритм (в Java):

Algorithm studentG(J[],W[],V[][],x[][]) 
{ 
    // I use heap data structure for solving this problem 
    // initial all x[][] = 0 
     ArrayList<Heap> students = new ArrayList<Heap>(); 
     students = Heap(v[][]); // this method make a heap for each student, 

    for(int k = 0; k< J.length, k++) 
    { 
    Boolean test = false; 
    // this loop is for each student to assign each student to only one grade not more. 
    for(int m = 0; m< students.size(); m++) 
{ 
If(students.get[m].root.getGrade() ==k && test == false){ 
test = true; 
//I have assigned 1 to the feasible and 0 othrwise 
x[m][k] = 1; 
}else if(students.get[m].root. getGrade() != k){ 
Continue; 
}else if(students.get[m].root. getGrade() == k && test == true){ 
students.get[m].remove(root); 
students.get[m].heapify(); 
} 
} 
} 

делает эту работу хорошо? Благодарю.

Answer 1

Ваш пример неясен. Не выбирает T12 и T22 нарушать ваши условия (т. Е. Есть два ученика, назначенных на 2-й класс).

Answer 2

То, что вы пытаетесь решить, на самом деле является перефразированием travelling salesman problem, и Google предоставит вам множество возможных алгоритмов для его решения.

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

Перед реализацией алгоритма попробуйте выразить его в псевдоязычных терминах. Простейшая реализация алгоритма может выглядеть следующим образом:

foreach student S do 
    foreach unassigned grade G do 
    Add {G, S} to the solutions 
    Compute the solution score 
    If (this score > greater score so far) Then 
     Keep solution like this 
     Mark G as assigned 
    Else 
     Remove {G, S} from the solution 
    Next 
Next 

Насколько идут структуры данных, вы могли бы иметь в Java:

// The number of grades and students 
public static final int N = 10; 

// The students and grades are just a suite of numubers 
List<int> students = new ArrayList<int>(N); 
List<int> grades = new ArrayList<int>(N);  
for (int i=0; i<N; ++i) { 
    students.set(i, i); 
    grades.set(i, i); 
} 

// Each score for a possible pair of grade student is stored in a matrix 
int[][] scores = new int[N][N]; 
for (int s=0; s<N; ++s) { 
    for (int g=0; g<N; ++g) { 
    scores[s][g] = students.get(s) * grades.get(g); 
    } 
} 

// An association of student and grade 
class Association { 
    int student; 
    int grade; 
    int score; 
    public Association(int student, int grade, int score) { 
    this.student = student; 
    this.grade = grade; 
    this.score = score; 
    } 
} 

// The solution 
Stack<Association> solution = new Stack<Association>(N); 

Я дам вам попробовать реализовать вышеупомянутую с алгоритмом эти структуры данных, используя Stack.push и Stack.pop, чтобы добавить/удалить ассоциацию из решения и List.remove, чтобы отметить оценку, используемую в решении.

Не забудьте реализовать функцию, которая вычисляет сумму очков в текущем решении (может быть Somthing как: общественное ИНТ getSolutionScore (решение Stack))

Answer 3

@Samuel: «Каждый студент должен присвоенный ровно одному классу, и ровно один студент присваивается любому классу ».

Это означает наличие функции, которая отображает ученика в любой класс S-> G. Условие, кажется, не вводить ограничений в (т.е. все оценки должны быть назначены в наилучшим образом среди множества студентов, сохраняя при этом ограничение 1-к-1.)

---

Таким образом, в сущности (если проблема была действительно сформулированы правильно), это означает простое выполнение

Q = argmax_j (Tij) для всех i's.

Это просто Максимальное значение каждой строки матрицы затрат T.

---

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

Поскольку это кажется слишком простым, проблема может быть сформулирована неправильно.