Problém výběru aktivit

Postupný výběr aktivit a ukázka, že je jedno, kterou aktivitu vybereme splňující princip algoritmu.
All activities: seřazené aktivity podle finálního času.
Step 1: zvolení první aktivity (zeleně označené) v seznamu
Step 2: zvolení jedné z aktivit, která splňuje podmínku nepřekrývání s předešlou aktivitou. Zde lze vybrat obě aktivity, následně se zde provede nedeterministický výběr nebo paralelizace úlohy (zbytečné, ale je zde nadále demonstrováno), případně se vezme první nalezenec.
Step 3: zvolení jedné z aktivit, která splňuje podmínku nepřekrývání s předešlou aktivitou. Zde lze vybrat pouze jedna aktivita.
Step 4: zvolení jedné z aktivit, která splňuje podmínku nepřekrývání s předešlou aktivitou. Zde žádná taková aktivita nesplňuje podmínky
Done: výsledný seznam (černě označené) výstupních aktivit

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 s_i (start) a koncovým f_i (final) časem, přičemž musí splňovat: s_i < f_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):

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

A_SORT2 = {(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:

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

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

Poznámka: A_SORT1 a A_OPTIMAL1 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. A_SORT2 a A_OPTIMAL2 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(nlog(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!")
			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.intervals = 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] <= activity[0]:
				self.optimal_list_of_activities.append(activity)
				print(activity)
				break
			activity = self._pop()
		else:
			print("END LIST")

	def _pop(self):
		if len(self.intervals) == 0:
			return None
		activity = self.intervals[0]
		self.intervals = self.intervals[1:]
		return activity

def main():
	ASP = ActivitySelectionProblem()
	activities = [(9, 10), (7, 10), (7, 8), (7, 9), (9, 12), (8, 10), (11, 12), (11, 13), (12, 13), (13, 15), (13, 16), (17, 18)]
	ASP.setActivities(activities).do()

if __name__ == "__main__":
	main()

Důkaz

Když se zvolí první aktivita ze seřazeného seznamu A, pak se jedná o triviální výběr.

Následně se hledá další aktivita s nejnižším, ale zároveň vyšším finálním časem než má poslední evidovaná aktivita. Přičemž se vyloučí veškeré překrývající se aktivity s již zvolenou aktivitou. V tomto kroku lze vzít i jinou aktivitu splňující podmínky, ale vždy bude ve výstupní množině stejný počet aktivit (viz Ilustrace), čímž lze říci, že se jedná o nejvýhodnější výběr(y). Tento krok se může opakovat, protože je splněná indukce.

Následující aktivita může byt:

• s totožným finálním časem – přeskakuje se
• s pozdějším finálním časem než vybraná aktivita (nutné další ověření)
  • počáteční čas je menší než finální čas vybrané aktivity – přeskakuje se
  • počáteční čas je stejný jako finální čas vybrané aktivity – vybírá se (pokud nemusí byt mezi jednotlivými aktivitami pauzy/přestávky)
  • počáteční čas je vyšší než finální čas vybrané aktivity – vybírá se (splňuje-li případný minimální časový rozestup mezi aktivitami)