Problém výběru aktivit

Technology

12 hours ago

Author

Základní myšlenka problému výběru aktivit je, aby se ve stanoveném časovém intervalu vměstnalo co největší počet nepřekrývajících se aktivit z (konečné) množiny aktivit. Vstupem je (konečná) množina aktivit patřící do daného časového intervalu. Výstupem algoritmu je nalezená optimální množina nepřekrývajících se aktivit. Cílem je využití takového algoritmu, který nevyužívá hrubou sílu. Pro tyto účely lze využit hltavého (greedy) algoritmu, který vede k optimálnímu řešení.

Každá aktivita má pevně určené časové intervaly s počátečním si (start) a koncovým fi (final) časem, přičemž musí splňovat: si i.

Řešení

Mějme seznam (množinu) aktivit s časovými intervaly:

A = {(9, 10), (7, 10), (7, 8), (7, 9), (9, 12), (8, 10), (11, 12), (11, 13), (12, 13), (13, 15), (13, 16), (17, 18)}

* První krok: Seřadit seznam aktivit primárně podle koncových časů a následně sekundárně (není však nutno) podle počátečních časů (například stabilním algoritmem řazení slučováním):

ASORT1 = {(7, 8), (7, 9), (7, 10), (8, 10), (9, 10), (9, 12), (11, 12), (11, 13), (12, 13), (13, 15), (13, 16), (17, 18)}

ASORT2 = {(7, 8), (7, 9), (9, 10), (7, 10), (8, 10), (9, 12), (11, 12), (11, 13), (12, 13), (13, 15), (13, 16), (17, 18)}

* Druhý krok: Následně se ze seřazeného seznamu vezme první aktivita.

* Třetí krok: Nalezení první aktivity v seřazeném seznamu, která splňuje podmínku, že její počáteční čas je větší případně rovný (pokud můžeme vynechat přestávky) koncovému času již vybrané (poslední) aktivity ⇒ hltavá volba. Nedojde-li k nalezení vhodné aktivity, algoritmus se ukončí.

* Čtvrtý krok: Nalezená aktivita se zaznamená a zopakuje se třetí krok, pokud je ještě v seřazeném seznamu ještě nějaký prvek, jinak se algoritmus ukončí.

Níže je uvedený Python skript, který řeší tuto problematiku.

Výsledek tohoto algoritmu:

AOPTIMAL1 = {(7, 8), (8, 10), (11, 12), (12, 13), (13, 15), (17, 18)}

AOPTIMAL2 = {(7, 8), (9, 10), (11, 12), (12, 13), (13, 15), (17, 18)}

Poznámka: ASORT1 a AOPTIMAL1 představuji možnost, kdy je seznam seřazen primárně podle finálního času a sekundárně podle počátečního času. ASORT2 a AOPTIMAL2 představuji možnost, kdy je seznam seřazen pouze podle finálního času.

Tento algoritmus má časovou složitost O(n) nepočítáme-li časovou náročnost třídění (která může byt například O(n log(n)) ).

class ActivitySelectionProblem: def __init__(self, list_of_intervals=None): self.setActivities(list_of_intervals) self.optimal_list_of_activities = []

def setActivities(self, list_of_intervals): if isinstance(list_of_intervals, list): self.intervals = list_of_intervals # must be list of tuples with two numbers return self

def do(self): if len(self. intervals) == 0: print("No data. +more") return self. _sort self. _takeFirst while len(self. intervals): self. _findSuitableActivity print("DONE, optimal list of activities:") print(self. optimal_list_of_activities).

def _sort(self): print("SORTING by final time. ") self. +moreintervals = sorted( self. intervals, key=lambda item: item[1] #key=lambda item: (item[1], item[0]) ) print("SORTING DONE, sorted data:") print(self. intervals).

def _takeFirst(self): print("TAKE FIRST") self.optimal_list_of_activities.append(self._pop) print(self.optimal_list_of_activities[0])

def _findSuitableActivity(self): print("FINDING NEXT SUITABLE ACTIVITY...") last_optimal_activity = self.optimal_list_of_activities[-1]

activity = self._pop while activity is not None: if last_optimal_activity[1]