Алгоритм рекурсивного планирования не работает правильно Python - PullRequest
Новая
       5

Алгоритм рекурсивного планирования не работает правильно Python

0 голосов
/ 31 октября 2018

Я создал рекурсивный алгоритм планирования, который принимает массив объектов Event, которые содержат время начала и время окончания. Эти времена генерируются случайным образом, и время начала всегда меньше времени окончания. Время это число от 0 до 24 (24 часа в сутки, 24 == 0)

Вот код генератора массива случайных событий: 

def randomEventArray(s):
    e = []
    rand1 = 0
    rand2 = 0
    for i in range(s):
        rand1 = random.randint(0,21)
        rand2 = random.randint(rand1+1,23)
        e.append(Event(rand1,rand2))
    return e

Вот код для объекта Event: 

class Event:
    def __init__(self, start, end):
        self.startTime = start
        self.endTime = end
    def __repr__(self):
        return str(self)
    def __str__(self):
        return (str([self.startTime,self.endTime]))

Теперь вот часть, которая вызывает проблему. Я создал фрагмент кода, который рекурсивно проходит через сгенерированный массив событий и перечисляет большинство событий, которые можно провести за 24 часа. Ни одно событие не должно перекрываться.

Вот созданный рекурсивный жадный алгоритм: 

def scheduleGD2(E):
    events = []
    scheduleRecGD2(E,0,0, events)

    return events[:]

def scheduleRecGD2(E, eventPos, startTime,events):

    while eventPos < len(E) and E[eventPos].startTime < startTime:

        eventPos += 1
    if eventPos == len(E):
        return []
    minEndPos = eventPos
    for i in range(eventPos+1, len(E)):
        if E[i].endTime < E[minEndPos].endTime:
            minEndPos = i
    events.append(E[minEndPos])
    return scheduleRecGD2(E, minEndPos+1, E[minEndPos].endTime, events)

E = randomEventArray(20)
print(scheduleGD2(E))

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

[[0, 1], [1, 3], [4, 8], [9, 17], [17, 24]]

Однако я получаю следующий вывод: 

[[0, 1], [12, 16], [12, 16], [5, 17], [21, 22]]

Что ясно показывает, что Arr [2] перекрывается с Arr [1] (Arr [2] .StartTime (12)

Что не так и почему это происходит?

1 Ответ

0 голосов
/ 31 октября 2018

Я дал ваш код для отладки, включая замену пакета Events на простые парные кортежи. 

def scheduleRecGD2(E, eventPos, startTime, events):
    print("ENTER Rec", "eventPos", eventPos, "\tstartTime", startTime, "\n\tevents", events)

    while eventPos < len(E) and E[eventPos][0] < startTime:
        eventPos += 1

    if eventPos == len(E):
        return []

    minEndPos = eventPos
    print("\tFIRST: minEndPos", minEndPos, E[minEndPos])

    for i in range(eventPos+1, len(E)):
        if E[i][1] < E[minEndPos][1]:
            minEndPos = i 

    events.append(E[minEndPos])
    print("\tTRACE: minEndPos", minEndPos, E[minEndPos])

    return scheduleRecGD2(E, minEndPos+1, E[minEndPos][1], events)

# Main program
E = randomEventArray(8)
print(E)
print(scheduleGD2(E))

Выход: 

[(15, 20), (4, 7), (17, 20), (18, 23), (2, 7), (8, 23), (15, 23), (18, 20)]
ENTER Rec eventPos 0    startTime 0 
    events []
    FIRST: minEndPos 0 (15, 20)
    TRACE: minEndPos 1 (4, 7)
ENTER Rec eventPos 2    startTime 7 
    events [(4, 7)]
    FIRST: minEndPos 2 (17, 20)
    TRACE: minEndPos 4 (2, 7)
ENTER Rec eventPos 5    startTime 7 
    events [(4, 7), (2, 7)]
    FIRST: minEndPos 5 (8, 23)
    TRACE: minEndPos 7 (18, 20)
ENTER Rec eventPos 8    startTime 20 
    events [(4, 7), (2, 7), (18, 20)]
[(4, 7), (2, 7), (18, 20)]

АНАЛИЗ

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

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

РЕМОНТ

Следуйте многочисленным решениям, доступным онлайн: сначала отсортируйте список по порядку времени окончания, затем время начала. Теперь очень просто пройтись по вашему списку и найти первое доступное время start , которое (а) находится в списке позже, чем последний добавленный кортеж; (б) не менее текущего времени окончания.

Учитывая наличие решений, я оставлю это в качестве упражнения для студента. Начните с простого изменения в процедуре рандомизации: 

return sorted(e)
...