Mustaqil ishi Mavzu

To'lqin algoritmi-kenglikdagi qidiruvga asoslangan va ikki bosqichdan iborat: to'lqinning tarqalishi va teskari harakat.Eng qisqa yo'l-bu ustundagi yo'l, ya'ni ikki qo'shni tepalikda va uning uzunligi bilan bog'liq bo'lgan tepaliklar va qovurg'alar ketma-ketligi.

Floyd algoritmi grafning har qanday ikki uchi orasidagi eng qisqa yo'lni topish uchun algoritmdir.

Bulkhead algoritmi-grafikani chetlab o'tish algoritmi, bu mumkin bo'lgan yo'llarning ketma-ket izlanishiga asoslangan.

Deykstra 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.

Deykstra 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.

Foydalanilgan adabiyotlar:

1. 
   Абрамов С.А. Лекции о сложности алгоритмов.- М.: МЦНМО, 2009.- 256 с.
   
2. 
   Дональд Кнут Искусство программирования, том 1. Основные алгоритмы— 3-е изд. — М.: «Вильямс», 2006. — С. 720.
   
3. 
   Кнут В. Искусство программирования. Т.3. Сортировка и поиск. – 2-е изд. - Издательский дом “Вильямс”, 2000.
   
4. 
   Вирт Н. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 1989. – 360.
   
5. 
   Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.