Алгоритм оптимизации [закрыт]

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

Сначала предположим, что у нас есть следующие зависимости:

deps = [(11, 2), (11, 9), (8, 9), (11, 10), (3, 10),
        (5, 11), (7, 11), (7, 8), (3, 8)]

, который формирует следующий график:

[117]

чтобы найти курсы, которые ей нужно пройти в течение первого семестра:

semesters = []
sources = {start for start, end in deps}
sinks   = {end for start, end in deps}
semester = sources - sinks
semesters.append(semester)

т.е. найти все корни в графе (узлы без входящих стрелок).

Затем удалите корни:

deps = [(start, end) for start, end in deps if start not in semester]

и повторите ...

semesters = []
while deps:
    sources = {start for start, end in deps}
    sinks   = {end for start, end in deps}
    semester = sources - sinks
    semesters.append(semester)
    deps = [(start, end) for start, end in deps if start not in semester]

print("semesters needed:", 1 + len(semesters))

нам нужно добавить 1, так как при последнем удалении корней удаляются 2 уровня узлов.

Мы можем сравнить две версии, используя модуль timeit (я поместил ваш код в функцию и исправил несколько ошибок):

def semestercount():
    deps = [(11, 2), (11, 9), (8, 9), (11, 10), (3, 10),
            (5, 11), (7, 11), (7, 8), (3, 8)]
    count = 0
    while deps:
        sources = {start for start, end in deps}
        sinks   = {end for start, end in deps}
        semester = sources - sinks
        count += 1
        deps = [(start, end) for start, end in deps if start not in semester]
    return count + 1


def op_code():
    NM = [(11, 2), (11, 9), (8, 9), (11, 10), (3, 10),
          (5, 11), (7, 11), (7, 8), (3, 8)]
    nodes = list(set(sum(NM, ())))
    N = len(nodes)
    M = len(NM)
    remCourses = []
    courseRes = {}
    for i in range(N):
        courseRes[nodes[i]] = list()
        remCourses.append(nodes[i])

    for i in range(0,M):
        res = NM[i]
        courseRes[res[0]].append(res[1])

    semCount = 0
    while len(remCourses) > 0:
        newCourses = []
        for key in courseRes:
            if len(courseRes[key]) == 0:
                newCourses.append(key)


        for l in range(N):
            for course in newCourses:
                if course in courseRes[nodes[l]]:
                    courseRes[nodes[l]].remove(course)

        for course in newCourses:
            if course in remCourses:
                remCourses.remove(course)

        semCount += 1
    return semCount


import timeit
print timeit.timeit("semestercount()", "from __main__ import semestercount")
print timeit.timeit("op_code()", "from __main__ import op_code")

на моем компьютере он печатает: [1119 ]

5.85758427398
42.8849096743

так немного быстрее: -)