Kommivoyajer masalasini hal qilish usullari
![qanday baholash kerakligi haqida kelishib olishimiz kerak. f
B bo'lsin
real
minimum, f
A esa algoritm tomonidan olingan kvaziminimdir. Ma'lumki , f
A / f
B ≥1,
lekin bu xato bo'lishi mumkinligi haqidagi ahamiyatsiz bayonot. Uni baholash
uchun siz yuqoridagi taxmin bilan munosabatni mahkamlashingiz kerak:
f
A / f
B ≥1+ n e , (5
)
bu erda, odatdagidek, oliy matematikada, e≥0, lekin odatlardan farqli o'laroq, juda
katta bo'lishi mumkin. e qiymati xato o'lchovi bo'lib xizmat qiladi. Agar
minimallashtirish algoritmi tengsizlikni (5) qanoatlantirsa, unda e xatosi borligini
aytamiz.
Keling, masalani yechish uchun A algoritmi mavjud deb faraz qilaylik,
uning xatosini taxmin qilish kerak. Keling, ixtiyoriy G ( V , E ) grafigini olaylik va
undan ZK ning kirish matritsasini tuzishda foydalanamiz:
[i,j]= { bilan 1,agar chekka ( i , j ) E ga tegishli bo‘lsa
1+ n e aks holda
G grafigi Gamilton sikliga ega bo'lsa, u holda minimal tur shu sikl orqali o'tadi va f
B = n . Agar A algoritmi ham doim shu yo'lni topsa, algoritm natijalariga ko'ra
ixtiyoriy grafikda Gamilton sikli bor yoki yo'qligini aniqlash mumkin. Biroq,
ixtiyoriy grafikda Gamilton sikli bor-yo'qligiga javob bera oladigan qo'pol kuch
bo'lmagan algoritmni hali hech kim bilmaydi. Shunday qilib, bizning A
algoritmimiz ba'zan xatoga yo'l qo'yishi va turga kamida 1+ n e uzunlikdagi bir
chetini kiritishi kerak. Lekin u holda f
A ( n -1)+(1+ n e) shuning uchun f
A / f
B
=1+ n e ya’ni. e xatosidan tengsizlik (5) bilan belgilangan qiymatdan oshib ketadi.
Biz muhokamada e qiymati bo'yicha kelisha olmadik, shuning uchun e
o'zboshimchalik bilan katta bo'lishi mumkin.
Shunday qilib, quyidagi teorema isbotlangan.
Yoki A algoritmi Gamilton siklining ixtiyoriy grafikda mavjudligini yoki
masalani yechishdagi A xatosi ixtiyoriy katta bo‘lishi mumkinligini aniqlaydi.
Bu fikr birinchi marta 1980 yilda Sani va Gonsales tomonidan nashr etilgan.
Sani-Gonsales teoremasi qirralarning uzunligi bo'yicha hech qanday cheklovlar 7](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_7.png?v=1)
![bo'ladi; G ' bu komponentlardan biri bo'lsin . Dastlabki grafik G , G ' va G ''
bog'liqligi tufayli kamida bitta umumiy cho'qqi bor, deylik v . Agar G '' da ba'zi
qirralar olib tashlangan bo'lsa, u holda har bir tepadan juft raqam chiqariladi.
Shuning uchun G '' bog'langan va uning barcha uchlari juft darajaga ega. Keling, G
'' da halqa quramiz (balki butun G '' chizmasdan ) va v orqali G '' chizilgan qismini
G ' ga qo'shamiz. G' ning chizilgan qismini shu tarzda kattalashtirib, biz G ' ning
butun G ni qamrab olishini ta'minlaymiz .
Bu masalani bir paytlar Eyler hal qilgan va grafikning barcha chetlarini
qoplaydigan yopiq chiziq endi Eyler sikli deb ataladi. Asosan quyidagi teorema
isbotlangan.
Grafikdagi Eyler sikli, agar (1) grafik ulangan va (2) uning barcha uchlari
juft darajaga ega bo‘lsagina mavjud bo‘ladi.
1.2.2. Yog'och algoritm .
Endi biz eng qisqa daraxtni qurish orqali muammoni hal qilish algoritmini
muhokama qilishimiz mumkin. Qisqartirish uchun biz ushbu algoritmni yog'och
deb ataymiz.
Birinchidan, tuzatish xususiyatini muhokama qilaylik. Misol uchun, 5-
rasmda qandaydir sxemani ko'rib chiqaylik. Agar uchburchak tengsizligi to‘g‘ri
bo‘lsa, d [1,3] d [1,2]+ d [2,3] va d [3,5] d [3,4]+ d [4,5] Bu ikkisini qo‘shish
tengsizliklar, biz d [1,3]+ d [3,5] d [1,2]+ d [2,3]+ d [3,4]+ d [4,5] ni olamiz .
Uchburchak tengsizligidan foydalanib, biz quyidagilarni olamiz: d [1,5] d [1,3]+
d [3,5]. Nihoyat
d [1.5] d [1,2]+ d [2,3]+ d [3,4]+ d [4,5]
Shunday qilib, agar uchburchak tengsizligi to'g'ri bo'lsa, unda har bir zanjir
uchun zanjirning boshidan oxirigacha bo'lgan masofa zanjirning barcha
qirralarining umumiy uzunligidan kichik (yoki teng) bo'lishi haqiqatdir. Bu to'g'ri
chiziq egri chiziqdan qisqaroq degan umumiy e'tiqodning umumlashtirilishi. 9](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_9.png?v=1)
![(1,2) o'z ichiga olmaydi barcha turlar sinf. Doiralar ustidagi raqamlar pastki
taxminlardir.
Keling, ijobiy yo'nalishda dallanishni davom ettiramiz: chapga - pastga.
Buning uchun jadvaldagi kichraytirilgan C [1,2] matritsadagi nollarni baholaymiz .
7. Hujayradagi maksimal ball (3,1) 3. Shunday qilib, shakldagi pastki
o'ng cho'qqi uchun ball. 7 - 35+3=38. Shaklda pastki chap
burchakni baholash uchun. 7, jadvaldagi C [(1,2), (3,1)]
matritsasini olgan holda C [1,2] matritsasidan boshqa 3-qator va 1-
ustunni o chirishingiz kerak . 8. Ushbu matritsada siz (2,3)ʻ katakchaga
taqiq qo'yishingiz kerak, chunki turning bir qismi allaqachon qirralardan (1,2) va
(3,1) qurilgan, ya'ni. [3,1,2] va muddatidan oldin yopish (2,3) taqiqlanishi kerak.
Ushbu matritsa 1-ustun bo'yicha berilgan (9-jadval), shuning uchun tegishli
sinfdagi har bir tur (ya'ni, qirralarning (1,2) va (3,1) o'z ichiga olgan tur) 36 yoki
undan ortiq turadi.
3 4 5 6
2 1 3 1 0
4 0
1 - 1 3
5 0 0
2 - 0
6 3 2 0
3 -
stol 9
3 4 6
2 1 3 0
3
4 0
3 - 3 20](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_20.png?v=1)
![5 0 0
3 0
stol 10
3 4
4 0 -
5 0 0
stol o'n bir
C matritsadagi nollarni baholaymiz [(1,2),(3,1)] maksimal ball 3 bo'lgan nol (6,5)
katakchada. Salbiy variant 38+3=41 ballga ega. Ijobiy variantni baholash uchun 6-
qator va 5-ustunni olib tashlang, (5,6) katakchaga taqiq qo'ying, jadvalga qarang.
10. Bu matritsa qaytarilmas. Binobarin, ijobiy variantni baholash ko'paymaydi (8-
rasm).
Jadvaldagi matritsadagi nollarni baholash. 10, biz chekka (2,6) tanlovi
asosida shoxlanamiz, manfiy variant 36+3=39 ball oladi va ijobiy variant uchun
ball olish uchun ikkinchi qator va oltinchi ustunni kesib tashlaymiz, jadvaldagi
matritsani olish. o'n bir.
(5,3) katakchadagi matritsaga taqiq qo'shilishi kerak, chunki turning bir
qismi [3,1,2,6,5] allaqachon qurilgan va muddatidan oldin qaytishni taqiqlash
kerak (5,3). Endi bizda diagonal cheklovlar bilan 2x2 matritsa qolgan, biz turni
qirralar bilan yakunlaymiz (4,3) va (5,4). Ijobiy variantlarga shoxlanganimiz bejiz
emas edi. Endi biz ekskursiya oldik: 1 → 2 → 6 → 5 → 4 → 3 → 1, narxi 36.
Qidiruv daraxtining pastki qismiga etib borgach, turlar sinfi bitta turga qisqartirildi
va smeta quyida aniq xarajat aylandi.
Shunday qilib, 36 va undan yuqori ball to'plagan barcha sinflar eng yaxshi
turni o'z ichiga olmaydi. Shuning uchun mos keladigan uchlari kesib tashlanadi.
Ikkala avlodi ham o'chirilgan cho'qqilar ham o'chiriladi. Biz umumiy qidiruvni
juda kamaytirdik. C[ Not (1,2)] matritsasiga mos keladigan sinf yaxshiroq turni o'z
ichiga oladimi yoki yo'qligini tekshirish qoladi , ya'ni. 1,2 katakchada taqiqlangan
C matritsasi berilgan, ustunda 1 ga qisqartirilgan (bu 34+1=35 ball bergan).
Nollarni baholash katakchadagi nol uchun 3 ni beradi (1,3), shuning uchun 35+3 21](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_21.png?v=1)
![tomonidan taklif qilingan Dijkstra algoritmidir. Ushbu algoritm umumiy
muammoni hal qiladi:
Yo'naltirilgan, yo'naltirilmagan yoki aralash (ya'ni, ba'zi yo'llar bir
tomonlama bo'lgan) tarmoqda ikkita berilgan cho'qqilar orasidagi eng qisqa
yo'lni toping.
Algoritm har birida n (= tarmoq uchlari soni) sonli uchta massivdan
foydalanadi. Birinchi a massivida ikkita qiymatga ega teglar mavjud: 0 (cho'qqi
hali ko'rib chiqilmagan) va 1 (cho'qqi allaqachon ko'rib chiqilgan ); ikkinchi
massiv b masofalarni o'z ichiga oladi - v
i dan mos keladigan cho'qqigacha bo'lgan
joriy eng qisqa masofalar ; uchinchi massiv c cho'qqilar raqamlarini o'z ichiga
oladi - k- element c
k joriy eng qisqa yo'lda v
i dan v
k gacha bo'lgan oxirgi cho'qqining soni . D
ik masofa matritsasi yoylarning uzunliklarini belgilaydi d
ik ; agar bunday yoy
bo'lmasa, u holda d
ik ga "mashina cheksizligi" ga teng bo'lgan katta B raqami
beriladi.
Endi biz tavsiflashimiz mumkin:
Dijkstra algoritmi
1 (boshlash).
n gacha bo'lgan tsiklda a massivni nol bilan to'ldiring; c massivni i raqami
bilan to'ldiring : D matritsaning i - qatorini b massivga o'tkazing ;
a [ i ]:=1; c [ i ]:=0; { i - boshlang'ich cho'qqi soni}
2 (umumiy qadam).
Belgilanmaganlar orasidan minimalni toping (ya'ni, a [ k ]=0 bo'lgan k ); j
indeksida minimumga erishilsin , ya'ni b
j b
k ; a [ j ]:=1;
0 2
3 1
2 ∞ ∞ ∞ ∞ ∞
2
3 0 2
5 ∞ 2
2 ∞ ∞ 3
5
1
2 2
5 0 1
8 ∞ ∞ ∞ ∞
∞ ∞ 1 0 ∞ 2 ∞ ∞ 23](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_23.png?v=1)
![8 0
∞ 2
2 ∞ ∞ 0 2
3 1
4 ∞
∞ ∞ ∞ 2
0 2
3 0 2
4 ∞
∞ ∞ ∞ ∞ 1
4 2
4 0 1
6
∞ 3
5 ∞ ∞ ∞ ∞ 1
6 0
stol 12
agar b
k > b
j + d
jk bo'lsa ( b
k := b
j + d
jk ; c
k := j ) {Shart v
i .. v
k yo'lning v
i .. v
yo'lidan uzunroq ekanligini bildiradi.
j , vk . Agar barcha a [ k ] belgilangan
bo'lsa, u holda yo'lning uzunligi v
i .. v
k b [ k ] ga teng . Endi biz eng qisqa
yo'lga kiritilgan cho'qqilarni sanab o'tishimiz kerak}
3 (javob berish).
{ v
i .. v
k yo'li quyidagi protsedura bo'yicha teskari tartibda qaytariladi: }
3.1. z:=c[k];
3.2. z soni ;
3.3. z := c [ z ]; Agar z = 0 bo'lsa, u holda tugating, aks holda 3.2 ga o'ting.
n ta elementdan iborat b massivini n marta ko'rib chiqish kerak , ya'ni
Dijkstra algoritmi kvadratik murakkablikka ega. Dijkstra algoritmining ishini
raqamli misol bilan ko'rsatamiz (kattaroq murakkablik uchun ba'zi shaharlar
(cho'qqilar) i , j bir-biri bilan bog'lanmagan deb hisoblaymiz, ya'ni D [ i , j ]= ∞ ).
Masalan, i =3 bo'lsin. 3 cho'qqidan eng qisqa yo'llarni topishingiz kerak. Birinchi
bosqichni bajargandan so'ng a , b , c massivlarining mazmuni jadvalda ko'rsatilgan.
12:
1 2 3 4 5 6 7 8
a 0 0 1 0 0 0 0 0
b 12 25 0 18 ∞ ∞ ∞ ∞
c 3 3 0 3 3 3 3 3 24](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_24.png?v=1)
![Shunday qilib, masalani hal qilish uchun siz Dijkstra algoritmini n marta
quyidagicha qo'llashingiz kerak.
Keling, ixtiyoriy juft cho'qqilarni olaylik
j , k . C [ j , k ] bevosita chetini istisno qilaylik . Deykstra algoritmidan foydalanib,
j .. k shaharlar orasidagi eng qisqa masofani topamiz . Bu masofaga ba'zi shahar m
kiradi . Bizda turning bir qismi j , m , k . Endi qo'shni shaharlarning har bir juftligi
uchun (bu misolda, j , m va m , k uchun ) biz mos keladigan chetni olib tashlaymiz
va eng qisqa masofani topamiz. Bunday holda, eng qisqa masofa allaqachon
ishlatilgan shaharni o'z ichiga olmaydi.
Keyinchalik, xuddi shunday tarzda, Dijkstra algoritmidan foydalanib, barcha
cho'qqilar ishtirok etgunga qadar cho'qqilar juftligi orasidagi eng qisqa masofani
topamiz. Keling, oxirgi cho'qqini birinchisiga bog'laymiz va ekskursiya qilamiz.
Ko'pincha, bu oxirgi chekka juda katta bo'lib chiqadi va tur xato bilan olinadi,
ammo Dijkstra algoritmini taxminiy algoritm sifatida tasniflash mumkin. 26](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_26.png?v=1)
![1.2.5. Sayohatchi sotuvchi muammosini hal qilish uchun mening usulim
(Anishchenko usuli).
Men sayohatchi sotuvchi muammosini hal qilish uchun o'z usulimni taklif
qilaman.
Keling, rasmga qaraylik. 9-10 va ulardagi eng qisqa turlarni topishga harakat
qiling. Shubhasiz, eng qisqa tur kesishuvchi qirralarni o'z ichiga olmaydi (aks
holda, cho'qqilarni kesishgan qirralar bilan almashtirish orqali biz qisqaroq turga
ega bo'lamiz). Birinchi holatda eng qisqa tur 1-2-4-5-3-1, ikkinchi holatda esa eng
qisqa tur 1-2-3-4-5-1. Besh yoki undan ortiq shaharlarning boshqa
ko'plab shunga o'xshash joylarini tahlil qilib,
quyidagi umumiy taxminni amalga oshirish mumkin:
1. Agar perimetri bo'ylab barcha shaharlar yotadigan
qavariq ko'pburchak qurish mumkin bo'lsa, unda
bunday qavariq ko'pburchak eng qisqa tur .
barcha shaharlar yotadigan qavariq ko'pburchakni qurish har doim ham
mumkin emas. Ba'zi shaharlar qavariq ko'pburchakka kiritilmasligi ehtimoli
yuqori. Biz bunday shaharlarni "markaziy" deb ataymiz. Qavariq ko'pburchakni
qurish juda oson bo'lganligi sababli, vazifa barcha markaziy shaharlarni minimal
yo'qotishlar bilan qavariq ko'pburchak shaklida turga kiritishdan iborat. Sayyor
sotuvchi tashrif buyurishi kerak bo'lgan shaharlar raqamlarini o'z ichiga olgan T [ n
+1] massivi bo'lsin , ya'ni birinchi navbatda sayohatchi sotuvchi T [1], keyin T [2],
keyin T [3] shahriga tashrif buyurishi kerak. , va hokazo d, va T [ n +1]= T [1]
(sayyor sotuvchi boshlang'ich shaharga qaytishi kerak). U holda i ∈ [1,2..n] tenglik
bajarilsa; C [ T [ i ], p ]+ C [ p , T [ i +1]] – C [ T [ I ], T [ i +1]]= min , keyin p
raqamli markaziy shaharni kiritish kerak. T [ i ] va T [ i +1] shaharlari orasidagi
sayohat . Ushbu operatsiyani barcha markaziy shaharlar uchun amalga oshirgandan
so'ng, natija eng qisqa turdir. Bu algoritm Paskalda amalga oshirilib, 1-taxminning
to'g'riligini tekshirib ko'rish mumkin. Tarmoq va bog'lanish usuli yordamida hal
qilgan muammomiz uchun mening algoritmim to'g'ri yechimni beradi. 27](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_27.png?v=1)
![1.3 Sayohatchi sotuvchi muammosini amaliy qo'llash
LC ning amalda aniq qo'llanilishidan tashqari, LC ni hal qilish uchun
qisqartirilishi mumkin bo'lgan bir qator boshqa vazifalar mavjud.
Bo'yoq ishlab chiqarish muammosi . Turli rangdagi n bo'yoq ishlab
chiqarish uchun ishlab chiqarish liniyasi mavjud ; Bu ranglarni 1,2... n raqamlari
bilan belgilaymiz . Biz butun ishlab chiqarish liniyasini bitta protsessor deb
hisoblaymiz.. Shuningdek, protsessor bir vaqtning o'zida faqat bitta bo'yoq ishlab
chiqaradi, shuning uchun bo'yoqlar qandaydir tartibda ishlab chiqarilishi kerak,
chunki ishlab chiqarish tsiklik bo'lgani uchun, bo'yoqlar ishlab chiqarilishi kerak
siklik tartib =( j
1 , j
2 ,.., jn , j1
) . Bo'yoq i ishlab chiqarishni tugatgandan so'ng va
bo'yoq j ishlab chiqarishni boshlashdan oldin jihozlarni bo'yoq i dan yuvish kerak .
Bu C [ i , j ] vaqtini talab qiladi. Ko'rinib turibdiki, C [ i , j ] ham i , ham j ga
bog'liq va umuman olganda, C [ i , j ]≠ C [ j , i ]. Muayyan tanlangan buyurtma
bilan siz bo'yoq ishlab chiqarish tsikliga vaqt sarflashingiz kerak bo'ladi
Qayerda tk
- k . bo'yoqning aniq ishlab chiqarish vaqti (o'zgarishlarni hisobga
olmaganda). Shu bilan birga, o'ng tomondagi ikkinchi yig'indi doimiydir, shuning
uchun umumiy ishlab chiqarish davri vaqti umumiy o'zgarish vaqti bilan birga
minimallashtiriladi.
Shunday qilib, ZK va almashtirish vaqtini minimallashtirish muammosi
faqat bitta muammodir, faqat uning variantlari turli so'zlar bilan tavsiflanadi.
Matbuotni bosish muammosi . Teshik pressi ko'p sonli bir xil panellar -
metall plitalar ishlab chiqaradi, ularda turli shakl va o'lchamdagi teshiklar birma-
bir teshiladi. Sxematik ravishda matbuotni x , y koordinatalari bo'ylab mustaqil
ravishda harakatlanadigan stol va stol ustida aylanadigan disk sifatida tasvirlash
mumkin, uning perimetri bo'ylab turli shakl va o'lchamdagi teshik ochuvchi
asboblar mavjud. Har bir asbob bitta nusxada mavjud. Disk ikki yo'nalishda teng
ravishda aylanishi mumkin (aylanish koordinatasi z ). Haqiqatan ham, varaqning 30](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_30.png?v=1)
![kerakli nuqtasi asbob ostiga olib kelinganida, uning ostida osilgan asbobni
bosadigan press mavjud.
j- teshikni teshish operatsiyasi raqamlarning to'rt barobari bilan tavsiflanadi (
x
j , y
j , z
j , t
j ), bu erda x
j , y
j - jadvalning kerakli pozitsiyasining koordinatalari, z
j
- koordinata. diskning kerakli joylashuvi va t
j - j- teshikni teshish vaqti .
Panellarni ishlab chiqarish tsiklik xarakterga ega: har bir varaqni qayta
ishlashning boshida va oxirida stol ( x
0 , y
0 ) va disk z
0 holatida bo'lishi kerak va bu holatda
hech qanday teshik bo'lmaydi. qilingan. Tizimning bu boshlang'ich holatini xayoliy
nol teshikning teshilishi deb hisoblash mumkin. Parametrlar bilan ( x
0 , y
0 , z
0 ,0 ).
J -chi teshikni i -chi teshikdan keyin darhol teshish uchun siz quyidagi
amallarni bajarishingiz kerak:
1. Jadvalni x o'qi bo'ylab x
i holatidan x
j holatiga o'tkazing , vaqtni t ( x )
(| x
i - x
j
|)= t
i , j ( x ) o'tkazing.
2. y o'qi bo'ylab xuddi shunday qiling , t
i , j ( y )
vaqtini sarflang.
3. Boshni ikkita yoyning eng qisqasi bo'ylab z
i holatidan z
j holatiga aylantirib, t
i , j (
z )
vaqtini sarflang .
4. t
j vaqtini sarflab, j -chi teshikni teshib qo'ying .
t ( x )
, t ( y )
, t ( z )
funktsiyalarining o'ziga xos shakli pressning mexanik
xususiyatlariga bog'liq va juda og'ir. Bu funktsiyalarni aniq yozishning hojati yo'q
1-3 amallar ( i -teshikdan j -thga o'tish) bir vaqtning o'zida sodir bo'ladi va
zımbalama bu harakatlarning eng uzuni bajarilgandan so'ng darhol sodir bo'ladi.
Shunung uchun
S[ i , j ] = maks ( t ( x )
, t ( y )
, t ( z )
)
Endi, oldingi holatda bo'lgani kabi, teshikli press uchun optimal dasturni
tuzish vazifasi ZK ga tushadi (bu erda, nosimmetrik). 31](https://docx.uz/documents/142da6d7-0af6-4db1-bb0a-fb3aaf2cfabe/page_31.png?v=1)
Kommivoyajer masalasini hal qilish usullari