Bulutli hisoblash nima? Agar biz kontseptsiya haqida gapiradigan bo'lsak

Bugungi kunda eng qisqa yo'lni topish dolzarb vazifadir.
Graflarda eng qisqa yo'lni topishning eng samarali algoritmlari Dijkstra algoritmi, Floyd algoritmi va Bulkhead algoritmlarini o'z ichiga oladi. Ushbu algoritmlar juda oz sonli vertikalar uchun samarali.
Dijkstra algoritmini amalga oshirishda dastlabki tepadan eng qisqa yo'llar allaqachon ma'lum bo'lgan ko'plab vertikalar qurilgan. Quyidagi qadamlar optimal yo'llarning uzunligini saqlab, mavjud bo'lgan to'siqlarga bir tepalikka qo'shilishga asoslangan.
Dijkstra algoritmining murakkabligi vertikani topish usuliga, shuningdek, ko'plab turg'un cho'qqilarni saqlash usuli va uzunliklarni yangilash usuliga bog'liq.
Floyd usuli, qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan eng qisqa yo'l boshqa eng qisqa yo'llardan iboratligiga asoslanadi.
Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, Floyd algoritmining ishlash vaqti o(n3) tartibiga ega.
Bulkhead algoritmlar optimal yechim topish uchun algoritmlar bor.
To'lqin algoritmi kenglikdagi qidiruvga asoslangan va ikki bosqichdan iborat: to'lqin tarqalishi va teskari harakat.
Keng qidirish usuli bilan qidirish, qaytib kelish bilan solishtirganda, ma'lumotni saqlash uchun ko'proq yordamchi xotira talab qiladi, biroq u tezroq ishlaydi, chunki bir xil tepalikka bir martadan ko'proq tashrif buyurilmaydi.


15. Dinamik dasturlash masalalarini yechish sxemasi.

Ko'p bosqichli qarorlarni qabul qilish jarayonlari turli xil vaziyatlarda uchrashi mumkin, masalan, zaxiralarni boshqarish, resurslarni taqsimlash yoki kosmik kemalarni boshqarish vazifalari. Har bir ko'p bosqichli qarorlarni qabul qilish jarayonini yo'naltirilgan tarmoqdagi eng qisqa yo'lni topishning eng tushunarli ko'p bosqichli jarayonini ishlab chiqish deb hisoblsh mumkin (10.1-rasm). Ushbu misoldan foydalanib, R. Bellmanning optimallashtirish tamoyili mohiyatini namoyish etish mumkin.

10.1-rasm. Yo'naltirilgan tarmoq

Yo'naltirilgan tarmoq N qaror bosqichlariga ega bo'lsin. 10.1-rasmdan ko’rinib turibdiki N = 5 ga teng. Quyidagi belgilashni kiritamiz:
n - bosqich raqami (n = 1, 2, 3, 4,5);
i - harakat amalga oshirilgan joy (i = 1, 2, ..., 8);
j - harakat yo'naltirilgan nuqta (j = 2, 3, ..., 9);
Sij - i nuqtadan j nuqtagacha bo'lgan masofa;
Sn (i) - bu masalani yechishning n-bosqichida i nuqtadan oxirgi nuqtagacha bo'lgan minimal masofa.
Nuqta n-bosqichga tegishli deb taxmin qilinadi, agar undan aniq n bosqichda yakuniy nuqtaga o'tish mumkin bo'lsa. Ko’rinib turibdiki, n-bosqichning biror nuqtasidan 9-nuqtagacha bo’lgan minimal yo’l shu bosqichning qaysi nuqtasida ekanligimizga bog'liq bo'ladi. N-bosqichga tegishli bo'lgan n-elementning raqami tizimning n-bosqich holat o'zgaruvchisi bo'ladi. Optimallashtirish odatda jarayon oxiridan boshlanadi, chunki n-bosqichning ba'zi nuqtalarida bo'lganligi sababli (n - 1) - bosqichning nuqtalaridan biriga o'tish to'g'risida qaror qabul qilinadi va keyingi harakat yo'nalishi oldingi bosqichlardan ma'lum bo’ladi. (N - 1) bosqichning j raqami n bosqichda boshqarish o'zgaruvchisi bo'ladi.
Birinchi bosqich (n = 1) uchun maqsad funktsiya (Bellman funktsiyasi) birinchi bosqich (6, 7, 8) nuqtalaridan 9 oxirgi nuqtaga qadar bo'lgan minimal yo'ldir, ya'ni S1 (i) = si9. Keyingi bosqichlar uchun yo'l uzunligi ikki yig’indidan iborat –n-bosqichning i nuqtasidan j (n - 1)-bosqichning j nuqtasigacha bo’lgan Sij yo’li va j nuqtadan oxirgi nuqtagacha bo'lgan yo'lning minimal uzunligi, ya'ni Sn - 1 (j). Shunday qilib, funktsional Bellman tenglamasi quyidagi shaklga ega bo'ladi:

Minimal uzunlik ma'lum bir qiymat j* da erishiladi, bu i nuqtadan oxirgi nuqtaga harakatning optimal yo'nalishidir. Beshinchi bosqichda biz boshlang'ich nuqtaga etib boramiz va tizimning holati i = 1 bo’lib aniqlangan bo’ladi. S5(1) funktsiyasi 1-chi nuqtadan 9-nuqtagacha bo’lgan minimal yo’lni ifodalaydi. Optimal yo'nalish barcha bosqichlarni teskari tartibda tahlil qilish orqali aniqlanadi.