“Dag’al kuch” usuli bilan tartiblashtirish. Kommivoyajer haqida masala Rеja

bu yerda c(i) – for siklining dastlabki i ta o‘tish oralig‘idagi taqqoslashlar soni. Bunga nechta taqqoslash talab etiladi? c(i) ning qiymati quyidagi tenglikda ko‘rsatilgan:

• bu yerda c(i) – for siklining dastlabki i ta o‘tish oralig‘idagi taqqoslashlar soni. Bunga nechta taqqoslash talab etiladi? c(i) ning qiymati quyidagi tenglikda ko‘rsatilgan:
• Yoki

Oxirgi tenglikni A(N) ifodaga qo‘yib quyidagini hosil qilamiz:

• Oxirgi tenglikni A(N) ifodaga qo‘yib quyidagini hosil qilamiz:
• N i ga bog‘liq bo‘lmaganligi uchun:

Natijada:

• Natijada:

Kommivoyajer haqida masala.

• Kommivoyajer haqida masala.
• Har bir shaharni grafning cho‘qqisi, shaharlar orasidagi yo‘lni qirralar, ular orasidagi sayohat bahosini shu qirraning og‘irligi deb tasavvur qilishi mumkin. Bundan shunday xulosa chiqarish mumkinki, qisqa yo‘lni qidirish algoritmi kommivoyajer masalasini hal qiladi, biroq bu unday emas. Kommivoyajer haqidagi masalaning qanday ikki sharti uni qisqa yo‘l haqidagi masaladan farqlaydi? Birinchidan biz hamma shaharlarga tashrif buyurishimiz kerak, qisqa yo‘lni izlash algoritmi esa berilgan ikki shaharlar orasidagi yo‘lni beradi. Agar qisqa yo‘lni tanlash algoritmi bergan qisqa bo‘lakli yo‘lni yig‘sak, bu yo‘l ba’zi shaharlardan bir necha marta o‘tadi. Ikkinchi farq qisqa yo‘lni izlashda dastlabki nuqtaga qaytishni talab qilishdan iborat.

Misol

Shahar	1	2	3	4
1	M	5	11	9
2	10	M	8	7
3	7	14	M	8
4	12	6	15	M