Комбинаторика, ықтималдық және статистика
жүктеу/скачать 2,02 Mb.
|
Комбинаторика, ы тималды ж не статистика
| 3. Қысқа жолды табу.
4-мысал: Саудагердің жүрген жолы сызба түрінде көрсетілген. Бір пунктен екінші пунктке көрсетілген бағыт бойынша ғана жүру керек. Саудагер әрбір пункте бір рет ғана бола алады. Оның жүрген жолын «бұтақтар» әдісі арқылы көрсету керек. Бірінші пунктен оныншы пунктке дейінгі ең ұзақ және ең қысқа жолдарды табу керек. Бағыттың бойында пунктер арасындағы ара қашықтықтар көрсетілген. Шешуі: Көрнекілік үшін бірінші пунктен оныншы пунктке дейінгі барлық мүмкін болатын жолдардың «бұтақтарын» құрайық. «Бұтақтар» бойынша 1- пунктен 10 - пунктке дейінгі барлық мүмкін болатын жолдар 11. Енді барлық жолдардың ұзындықтарын табайық, мұнда соңғы пунктен бастаған ыңғайлы. Мысалы, бірінші жол 10 – 8 – 4 – 2 – 1. Бұл жолдың ұзындығы 2+8+5+2 = 17 км. Сонымен, ең қысқа жолдың ұзындығы 13 км, ал ең ұзын жол 26км тең. «Бұтақтар» әдісінің тиімділігі, барлық мүмкін болатын жол санын санауға мүмкіндік береді және барлық жолдарды бірден көре отырып, оларды салыстыруға болады. Бұл әдісті торлық графикте ең қиын жолды табуда қолданамыз. (3) (6)
жүктеу/скачать 2,02 Mb. Достарыңызбен бөлісу:
|