Kas ir alkatīgs algoritms un kā tas tiek izmantots problēmu risināšanā?

Heuristiska pieeja, kas katrā solī pieņem vietēju optimālu lēmumu, cerot, ka tas novedīs pie globāli optimāla risinājuma.

Pielietojums:

1. Aktivitāšu izvēles uzdevums (Activity Selection Problem):

   • Uzdevums: Izvēlēties maksimālo nesakritīgo laika intervālu skaitu no dotā kopuma.
   • Heuristiskais risinājums: Sakārtot intervālus pēc aizvēršanas laika pieauguma. Katru soli izvēlēties intervālu ar mazāko aizvēršanas laiku, kas nesaskaras ar jau izvēlētajiem.

   # Piemērs — Aktivitāšu izvēle
   # activities = [(start_time, end_time)]
   
   activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
   activities.sort(key=lambda x: x[1]) # Sakārtot pēc aizvēršanas laika
   
   selected_activities = []
   last_finish_time = -1
   
   for activity in activities:
       if activity[0] >= last_finish_time:
           selected_activities.append(activity)
           last_finish_time = activity[1]
   
   print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]
   

2. Monētu maiņas uzdevums (Coin Change Problem) — kanoniskajām monētu kopām:

   • Uzdevums: Izdot norādīto summu ar minimālo monētu skaitu.
   • Heuristiskais risinājums: Maksimāli izmantojot lielākās nominālvērtības, kamēr summa tiek izsniegta. Strādā tikai noteiktās kopās (piemēram, 1, 5, 10, 25).

   # Piemērs — Coin Change (kanoniskās monētas)
   coins = [25, 10, 5, 1]
   amount = 67
   result = {}
   
   for coin in coins:
       while amount >= coin:
           result[coin] = result.get(coin, 0) + 1
           amount -= coin
   
   print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
   

3. Kraskala algoritms minimālam izplatības kokam (Minimum Spanning Tree):

   • Uzdevums: Atrast virsotņu apakškopu, kas savieno visas virsotnes ar minimālo kopējo svaru.
   • Heuristiskais risinājums: Sakārtot visas malas pēc svara pieauguma. Pakāpeniski pievienot malas, ja tās neveido ciklu ar jau izvēlētajām, līdz ir savienotas n-1 malas (kur n — virsotņu skaits).

Heuristiskie algoritmi ir vienkārši īstenojami, bet ne vienmēr atrod globāli optimālu risinājumu. Dažiem uzdevumiem (piemēram, monētu maiņas, mugursomas problēma) heuristiska pieeja nav optimāla. Lai nodrošinātu optimālitāti vai labāku tuvinājumu, var būt nepieciešama dinamiskā programmēšana vai citas metodes. Pirms heuristikas izmantošanas ir jāizpēta, vai tā ir piemērota konkrētajam uzdevumam.