Қоидаи ғалаба чӣ гуна аст ва дар ҳалли масъалаҳо чӣ…

Равиштиҳии heuristic, ки дар ҳар қадам қароргоҳи маҳаллӣ қабул мекунад, умедвор аст, ки ин ба қароргоҳи глобалӣ мусоидат мекунад.

Барнома:

Масъалаи интихоби фаъолият (Activity Selection Problem):

Вазифа: Беҳтарин миқдори интервалҳои беҳамоҳангро аз маҷмӯъ интихоб кунед.
Ҳалқаи heuristic: Интервалҳоро ба таври рӯйхати баробар ба вақти анҷом додани онҳо. Дар ҳар қадам интервал бо вақти анҷом додани хурдтаринро интихоб кунед, ки бо интервалҳои аллакай интихобшуда мувофиқат намекунад.

# Мисоли интихоби фаъолият
# 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]) # Тартиб додани бар асоси вақти анҷом додан

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) ]

Масъалаи иваз кардани пули нақд (Coin Change Problem) барои маҷмӯи монетҳои канонӣ:
- Вазифа: Суммаи муайянро бо камтарин шумораи монетҳо баровардан.
- Ҳалқаи heuristic: Беҳтарин истифодаи миқдори максималии номиналҳои калонтарин, то ки сумма бароварда шавад. Ин танҳо барои маҷмӯъҳои муайян кор мекунад (масалан, 1, 5, 10, 25).
```
# Мисоли иваз кардани монетҳо (барои монетҳои канонӣ)
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}
```
Алгоритми Краскал барои ёфтани дарахти минималии пайвастшавӣ (Minimum Spanning Tree):
- Вазифа: Ёфтани зермаҷмӯъаи сегҳо, ки ҳамаи нуқтаҳоро бо вазни минималӣ пайваст мекунад.
- Ҳалқаи heuristic: Ҳама сегҳоро ба тартиби афзоишӣ баррасӣ кунед. Ба сегҳо илова кунед, агар онҳо циклиро бо сегҳои аллакай интихобшуда набароранд, то ки n-1 сегро пайваст кунанд (ки n шумораи нуқтаҳо аст).

Алгоритмҳои heuristic оддӣ мебошанд, аммо ҳамеша наметавонанд қароргоҳи глобалӣ оптималӣ барои ҳама гуна вазифаҳо ёбанд. Барои баъзе вазифаҳо (масалан, масъалаи иваз кардани пули нақд бо маҷмӯи монетҳои ҳархела, масъалаи рюкзак дар умум) равиши heuristic оптималӣ нест. Барои кафолат додани оптималӣ ё наздиктарин беҳтар, метавонанд истифодаи барномасозии динамикӣ ё дигар усулҳо заруранд. Пеш аз истифодаи heuristic, бояд муайян кард, ки он барои вазифаи муайян мувофиқ аст.

Қоидаи ғалаба чӣ гуна аст ва дар ҳалли масъалаҳо чӣ гуна истифода мешавад?