Iti0210lab42ex

Allikas: Lambda

Harjutusülesanne

Harjutustunnis lahendamiseks: meil on neli taksot (A-D) ja kolm klienti (1-3). Kõigile klientidele tuleb suunata takso, nii et keskmine ooteaeg oleks minimaalne. Kuna eesmärk on lokaalse otsingu harjutamine, kasuta mäeronimist (slaidid). Tee paberi ja pliiatsiga mäeronimisotsingu iteratsioone, kirjutades välja naaberolekud ning valides nendest optimaalseima, kuni otsing peatub (millal see juhtub?).

Algolek:

A -> 1
B -> 2
C -> 3
D -> vaba

Naaberolekud leiame nii, et vahetame kaks taksot omavahel ära (näiteks, A -> 3 ja C -> 1).

Keskmise ooteaja minimeerimine on sama mis summaarse ooteaja minimeerimine, kuna ükskõik mis lahenduse korral on 3 klienti.

Takso kohalejõudmise ajad iga kliendi juurde:

      1   2   3
A    17  25  10
B    14  12   8
C     8   7   6
D    12   2   7