Жасалған алгоритмдердің тиімділігін зерттеу. Тиімді алгоритмдерді құрудың негізгі принциптері Алгоритмге қарағанда тиімділік

Жасалған алгоритмдердің тиімділігін зерттеу. Тиімді алгоритмдерді құрудың негізгі принциптері Алгоритмге қарағанда тиімділік

14.02.2022 Жара

Бір мәселені шешу үшін бірнеше түрлі алгоритмдер жасауға болады. Сондықтан ең тиімді алгоритмдерді таңдау міндеті туындайды. Алгоритмдердің тиімділігін дәл бағалау өте қиын міндет екенін және әрбір нақты жағдайда арнайы зерттеулерді қажет ететінін ескеріңіз.

Алгоритмдер теориясының алгоритмдердің сипаттамаларын бағалаумен айналысатын бөлігі метрикалық деп аталады. Оны сипаттамалық (сапалық) және метрикалық (сандық) деп бөлуге болады. Біріншісі алгоритмдерді кіріс деректер мен нәтижелер арасында орнатқан сәйкестік тұрғысынан қарастырады. Екіншісі алгоритмдерді алгоритмдердің өздерінің де, олар көрсеткен «есептеулердің» де күрделілігі тұрғысынан қарастырады, яғни құрылымдық объектілерді дәйекті түрлендіру процестері. Алгоритмдер мен есептеулердің күрделілігін әр түрлі тәсілдермен анықтауға болатынын және бір әдіспен алгоритм болатынын атап өту маңызды. Ақиынырақ болады IN, ал басқа әдіспен бәрі керісінше.

Көбінесе алгоритмдер қажетті жадымен, орындалатын операциялардың санымен, шешу уақытымен немесе есептеу қателігімен бағаланады. Бұл сипаттамалар көбінесе есептің параметрлеріне (өлшемдеріне) тәуелді және сызықты емес. Сондықтан алгоритмдер теориясында функциялардың асимптотикалық бағалаулары арқылы алгоритмдердің тиімділігін бағалау бағыты бар: қажетті жады, есептеу уақыты және т.б. Бұл жағдайда функцияның ең маңызды параметрі анықталады және параметр мәндерінің өсуіне қарай функцияның әрекеті зерттеледі. Зерттеу барысында олар қарастырылатын алгоритм сипаттамалары мәндерінің параметрге тәуелділік сипатын анықтауға тырысады. Ол сызықтық (яғни n параметріне пропорционал), логарифмдік (яғни log n-ге пропорционал), квадраттық (яғни n 2-ге пропорционал) және т.б. Бір есепті шешетін алгоритмдердің асимптотикалық бағалауларын салыстыра отырып, тиімдірек алгоритмді таңдауға болады. Олар барлық n³n o үшін T(n) ≤ k n x теңсіздігі орындалатындай k және n o оң константалары болса, кейбір T(n) параметрінің мәні n x ретті екенін айтады.

n – секундына 1000 операцияны бірдей жылдамдықпен – есептеулерді орындайтын, бірақ әр түрлі бірнеше алгоритмдерді (A 1, A 2, A 3, A 4, A 5) енгізу кезінде алынған сандық деректердің көлемі делік. асимптотикалық бағалаулар. 1.8-кестеде бұл алгоритмдер 1 секундта, 1 минутта және 1 сағатта өңдей алатын n мәндері көрсетілген (мәндер ең жақын бүтін санға дейін дөңгелектенеді). 1.3-кестедегі деректер алгоритмнің өнімділігі (яғни, уақыт бірлігінде өңделген деректер саны) асимптотикалық бағалау функциясының сипатына айтарлықтай тәуелді екенін анық көрсетеді.

Жасалған алгоритмдерді тестілеу әдетте n параметрінің шағын мәндерінде жүргізіледі. Мұндай тестілеу алгоритмнің орындалуына сенімділікті арттыруға мүмкіндік береді, бірақ n-дің үлкен мәндері үшін тапсырманың орындалуына мүлдем кепілдік бермейді. Бізде нақты мәселені шешу үшін компьютер жады немесе уақыт жеткіліксіз болуы мүмкін. Асимптотикалық бағалаулар n параметрінің белгілі шектеулері бар практикалық есептеулер үшін компьютерлік ресурстардың жеткіліктілігін бағалауға мүмкіндік беретін мағынада маңызды.

Алгоритмнің тиімділігіалгоритм қолданатын есептеу ресурстарымен байланысты алгоритм қасиеті болып табылады. Алгоритмге қажетті ресурстарды анықтау үшін алгоритмді талдау қажет. Алгоритм тиімділігін қайталанатын немесе үздіксіз процестердің өндіріс өнімділігіне ұқсас деп санауға болады.

Максималды тиімділікке қол жеткізу үшін біз ресурстарды пайдалануды азайтқымыз келеді. Дегенмен, әртүрлі ресурстарды (мысалы, уақыт пен жадты) тікелей салыстыруға болмайды, сондықтан екі алгоритмнің қайсысы тиімдірек деп есептелетіні көбінесе жоғары жылдамдықты талап ету, жадты минималды пайдалану немесе басқа өлшем сияқты қай фактордың маңыздылығына байланысты болады. тиімділігі.

Назар аударыңыз, бұл мақала ЖОҚБағдарламаны оңтайландыру, компиляторды оңтайландыру мақалаларында талқыланатын алгоритмді оңтайландыру туралы, циклды оңтайландыру, объект кодын оңтайландырушы, тағыда басқа. «Оңтайландыру» терминінің өзі жаңылыстырады, өйткені жасауға болатын барлық нәрсе «жетілдіру» қолшатырына жатады.

Фон

Орындау уақытына баса назар аудара отырып, тиімділіктің маңыздылығын 1843 жылы Ада Лавлейс Чарльз Бэббидждің механикалық аналитикалық қозғалтқышына қатысты атап өтті:

«Барлық дерлік есептеулерде процесті сәтті аяқтауға болатын конфигурациялардың үлкен таңдауы бар және әртүрлі конвенциялар есептеуді орындау мақсатында таңдауға әсер етуі керек. Ең бастысы - есептеуді орындауға қажетті уақытты азайтуға әкелетін конфигурацияны таңдау».

Ертедегі электронды компьютерлер жылдамдығы да, жадысы да өте шектеулі болды. Кейбір жағдайларда уақыт-жадты айырбастау бар екені анықталды, онда тапсырма жоғары жылдамдыққа жету үшін жадтың үлкен көлемін пайдалануы керек немесе жұмыс жадының аз көлемін пайдаланатын баяуырақ алгоритмді пайдалану керек. Бұл жағдайда қол жетімді жады жеткілікті болатын ең жылдам алгоритм пайдаланылды.

Қазіргі компьютерлер бұрынғы компьютерлерге қарағанда әлдеқайда жылдам және жады әлдеқайда көп (килобайттың орнына гигабайт). Дегенмен, Дональд Кнут тиімділік маңызды фактор болып қала беретінін атап көрсетеді:

«Бекітілген инженерлік пәндерде 12% жақсартуға оңай қол жеткізуге болады және ешқашан тыйым салынған деп саналмаған және мен бағдарламалауда да солай болуы керек деп ойлаймын».

Қарау

Алгоритм, егер оның ресурстарды тұтынуы (немесе ресурс құны) белгілі бір қолайлы деңгейде немесе одан төмен болса, тиімді болып саналады. Дөрекі түрде айтқанда, бұл жерде «қолайлы» «алгоритм қолжетімді компьютерде ақылға қонымды уақыт ішінде жұмыс істейді» дегенді білдіреді. Өйткені 1950 жылдардан бастап компьютерлердің өңдеу қуаты мен қолжетімді жадының айтарлықтай өсуі байқалды, қазіргі «қолайлы деңгей» тіпті 10 жыл бұрын да қабылданбады.

Компьютер өндірушілері мезгіл-мезгіл жаңа, көбінесе қуаттырақ үлгілерді шығарады. Бағасы бағдарламалық қамтамасыз етуайтарлықтай үлкен болуы мүмкін, сондықтан кейбір жағдайларда бар компьютермен үйлесімді жылдамырақ компьютерді сатып алу арқылы жақсы өнімділікке қол жеткізу оңайырақ және арзанырақ.

Алгоритм пайдаланатын ресурстарды өлшеудің көптеген жолдары бар. Ең көп қолданылатын екі өлшем – жылдамдық пен қолданылатын жад. Басқа өлшемдерге тасымалдау жылдамдығы, дискіні уақытша пайдалану, ұзақ мерзімді диск пайдалану, қуат тұтыну, иеленудің жалпы құны, сыртқы сигналдарға жауап беру уақыты және т.б. кіруі мүмкін. Бұл өлшемдердің көпшілігі алгоритмнің кіріс деректерінің өлшеміне (яғни, деректерді өңдеуді қажет ететін шамалар) байланысты. Өлшемдер деректердің ұсынылу жолына да байланысты болуы мүмкін (мысалы, кейбір сұрыптау алгоритмдері сұрыпталған деректерде немесе деректер кері ретпен сұрыпталғанда нашар жұмыс істейді).

Іс жүзінде алгоритмнің тиімділігіне қажетті дәлдік және/немесе сенімділік сияқты басқа факторлар әсер етеді. Төменде түсіндірілгендей, алгоритмді іске асыру тәсілі де нақты өнімділікке айтарлықтай әсер етуі мүмкін, бірақ іске асырудың көптеген аспектілері оңтайландыру мәселелері болып табылады.

Теориялық талдау

IN теориялық талдауАлгоритмдерде алгоритмнің күрделілігін оның асимптотикалық мінез-құлқында бағалау, яғни кіріс өлшемі функциясы ретінде алгоритмнің күрделілігін көрсету әдеттегі тәжірибе. n Big O белгісі қолданылады. Бұл бағалау, әдетте, үлкендер үшін өте дәл n, бірақ шағын мәндерде қате тұжырымдарға әкелуі мүмкін n(Осылайша, баяу деп саналатын көпіршікті сұрыптау, тек бірнеше элементтерді сұрыптау қажет болса, жылдам сұрыптаудан жылдамырақ болуы мүмкін).

Белгі	Аты	Мысалдар
O(1) (\displaystyle O(1)\,)	тұрақты	Санның жұп немесе тақ екенін анықтау. Тұрақты өлшемді іздеу кестесін пайдалану. Элементті таңдау үшін сәйкес хэш функциясын пайдалану.
O (лог ⁡ n) (\displaystyle O(\log n)\,)	логарифмдік	Екілік іздеу немесе теңестірілген ағаш арқылы сұрыпталған массивте элементті табу, биномдық үймедегі әрекеттерге ұқсас.
O(n) (\displaystyle O(n)\,)	сызықтық	Сұрыпталмаған тізімде немесе теңгерілмеген ағашта элементті табу (ең нашар жағдай). Екі қосу n- end-toend тасымалдауды қолданатын биттік сандар.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	квазисызықты, логарифмдік сызықты	Жылдам Фурье түрлендіру, үйінді сұрыптау, жылдам сұрыптау (ең жақсы және орташа регистр), біріктіру сұрыптауын есептеңіз
O (n 2) (\displaystyle O(n^(2))\,)	шаршы	Екі көбейту n-қарапайым алгоритмді қолданатын таңбалы сандар, көпіршікті сұрыптау (ең нашар жағдай), қабықша сұрыптау, жылдам сұрыптау (ең нашар жағдай), таңдау сұрыптау, кірістіру сұрыптау
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	экспоненциалды	Динамикалық бағдарламалау арқылы саяхатшы сатушы мәселесінің (нақты) шешімін табу. Толық іздеу арқылы екі логикалық мәлімдеменің баламалы екенін анықтау

Тексеру сынақтары: өнімділікті өлшеу

Бағдарламалық құралдың жаңа нұсқалары үшін немесе бәсекелес жүйелермен салыстыруды қамтамасыз ету үшін кейде алгоритмдердің салыстырмалы өнімділігін салыстыру үшін эталондар пайдаланылады. Егер, мысалы, жаңа сұрыптау алгоритмі шығарылса, алгоритмнің басқалары сияқты белгілі деректерде тиімді болуын қамтамасыз ету үшін оны алдыңғылармен салыстыруға болады. Пайдаланушылар өнімділік сынақтарын әртүрлі өндірушілердің өнімдерін салыстыру үшін функционалдық және өнімділік тұрғысынан олардың талаптарына сәйкес келетін өнімнің қайсысын бағалау үшін пайдалана алады.

Кейбір эталондық сынақтар Рой Лонгботтомның PC Benchmark Collection сияқты әр түрлі құрастыру және интерпретациялау тілдерінің салыстырмалы талдауын қамтамасыз етеді. «Компьютер тілінің өлшемдері» ойыныкейбір программалау тілдеріндегі типтік тапсырмалардың орындалуын салыстырады.

Іске асыру мәселелері

Іске асыру мәселелері нақты өнімділікке де әсер етуі мүмкін. Бұл бағдарламалау тілін таңдауды және алгоритмді нақты кодтау тәсілін, таңдалған тіл үшін аудармашыны таңдауды немесе пайдаланылатын компилятор опцияларын, тіпті түрін қамтиды. операциялық жүйе. Кейбір жағдайларда аудармашы ретінде іске асырылған тіл компилятор ретінде іске асырылған тілге қарағанда айтарлықтай баяу болуы мүмкін.

Бағдарламалаушының бақылауынан тыс уақытқа немесе жадты пайдалануға әсер ететін басқа факторлар бар. Бұған деректерді теңестіру, егжей-тегжейлі, қоқыс жинау, нұсқаулық деңгейіндегі параллелизм және қосалқы бағдарламаны шақыру.

Кейбір процессорлардың векторлық операцияларды орындау мүмкіндігі бар, бұл бір операцияға бірнеше операндтарды өңдеуге мүмкіндік береді. Бағдарламалау немесе жинақтау деңгейінде мұндай мүмкіндіктерді пайдалану оңай немесе оңай болмауы мүмкін. Тізбектелген есептеулерге арналған алгоритмдерді параллельді есептеулерді пайдалану үшін толығымен қайта құру қажет болуы мүмкін.

Процессордың үйлесімділігіне қатысты басқа мәселе туындауы мүмкін, мұнда нұсқаулар басқаша орындалуы мүмкін, сондықтан кейбір үлгілердегі нұсқаулар басқа үлгілерде салыстырмалы түрде баяу болуы мүмкін. Бұл оңтайландырушы компилятор үшін мәселе болуы мүмкін.

Ресурстарды пайдалануды өлшеу

Өлшемдер әдетте кіреберіс өлшемінің функциясы ретінде көрсетіледі n.

Ең маңызды екі өлшем:

Уақыт: Алгоритм процессорға қанша уақыт алады.
Жад: Алгоритм үшін қанша жұмыс жады (әдетте жедел жады) қажет. Мұның екі аспектісі бар: кодқа арналған жад көлемі және код жұмыс істейтін деректерге арналған жад көлемі.

Батареямен жұмыс істейтін компьютерлер (ноутбуктар сияқты) немесе өте ұзақ/үлкен есептеулер үшін (мысалы, суперкомпьютерлер) өлшеудің басқа түрі қызықтырады:

Тікелей энергия тұтыну: Компьютерді іске қосу үшін қажетті қуат.
Жанама энергия тұтыну: Салқындату, жарықтандыру және т.б. үшін қажетті энергия.

Кейбір жағдайларда басқа, сирек кездесетін өлшемдер қажет:

Беріліс өлшемі: Өткізу қабілеті шектеуші фактор болуы мүмкін. Тасымалданатын деректер көлемін азайту үшін қысуды пайдалануға болады. Графикалық немесе кескінді көрсету (мысалы, Google логотипі) ондаған мың байттың тасымалдануына әкелуі мүмкін (бұл жағдайда 48K). Мұны «Google» сөзіндегі алты байтты тасымалдаумен салыстырыңыз.
Сыртқы жады: Дискіде немесе басқа сыртқы жад құрылғысында қажет жад. Бұл жадты уақытша сақтау немесе болашақта пайдалану үшін пайдалануға болады.
Жауап беру уақыты: Бұл параметр компьютер сыртқы оқиғаларға жылдам жауап беруі қажет нақты уақыттағы қолданбалар үшін өте маңызды.
Меншіктің жалпы құны: Параметр бір алгоритмді орындауға арналған кезде маңызды.

Уақыт

Теория

Тесттің бұл түрі бағдарламалау тілін, компиляторды және оның опцияларын таңдауға да айтарлықтай тәуелді, сондықтан салыстырылған алгоритмдер бірдей шарттарда орындалуы керек.

Жад

Бұл бөлім алгоритмге қажет негізгі жадты (көбінесе ЖЖҚ) пайдаланумен айналысады. Жоғарыдағы уақыттық талдау сияқты, әдетте алгоритмді талдау қолданылады алгоритмнің кеңістіктік күрделілігікіріс өлшемі функциясы ретінде қажетті орындалу жадын бағалау. Нәтиже әдетте үлкен «O» арқылы көрсетіледі.

Жадты пайдаланудың төрт аспектісі бар:

Алгоритм кодын сақтауға қажетті жад көлемі.
Енгізілетін деректерге қажетті жад көлемі.
Кез келген шығысқа қажетті жад көлемі (сұрыптау сияқты кейбір алгоритмдер кірісті жиі қайта реттейді және шығыс үшін қосымша жадты қажет етпейді).
Есептеу кезінде есептеу процесіне қажет жад көлемі (бұл аталған айнымалы мәндерді және рекурсияны пайдалану кезінде маңызды болуы мүмкін ішкі бағдарлама шақыруларына қажет кез келген стек кеңістігін қамтиды).

Ертедегі электронды компьютерлер мен үй компьютерлерінің жұмыс жадысы салыстырмалы түрде аз болды. Осылайша, 1949 жылы EDSAC максималды жұмыс жадысы 17 разрядты 1024 сөз болды, ал 1980 жылы Sinclair ZX80 1024 байт жұмыс жадымен шығарылды.

Қазіргі компьютерлерде жадының салыстырмалы түрде үлкен көлемі болуы мүмкін (мүмкін гигабайт), сондықтан алгоритм қолданатын жадты белгілі бір жад көлеміне қысу бұрынғыға қарағанда азырақ қажет. Дегенмен, есте сақтаудың үш түрлі категориясының болуы маңызды:

Кэш (көбінесе статикалық жедел жад) - процессормен салыстырылатын жылдамдықта жұмыс істейді
Негізгі физикалық жады (көбінесе динамикалық жедел жады) - процессорға қарағанда біршама баяу жұмыс істейді
Виртуалды жад (көбінесе дискіде) - үлкен жад елесін береді, бірақ жедел жадқа қарағанда мыңдаған есе баяу жұмыс істейді.

Қажетті жады компьютердің кэшіне сәйкес келетін алгоритм негізгі жадқа сәйкес келетін алгоритмге қарағанда әлдеқайда жылдам, ол өз кезегінде виртуалды кеңістікті пайдаланатын алгоритмге қарағанда әлдеқайда жылдамырақ болады. Кейбір жүйелерде кэштің үш деңгейіне дейін болуы мәселені қиындатады. Әртүрлі жүйелерде бұл жад түрлерінің әртүрлі көлемдері болады, сондықтан алгоритмдегі жадының әсері бір жүйеден екіншісіне айтарлықтай өзгеруі мүмкін.

Электронды есептеулердің алғашқы күндерінде алгоритм және оның деректері жедел жадыға сыймаса, оны пайдалану мүмкін болмады. Бұл күндері виртуалды жадты пайдалану үлкен жадты қамтамасыз етеді, бірақ өнімділік құны. Алгоритм және оның деректері кэшке сәйкес келсе, өте жоғары жылдамдыққа қол жеткізуге болады, сондықтан қажетті жадты азайту уақытты азайтуға көмектеседі. Кэшке толығымен сәйкес келмейтін, бірақ қамтамасыз ететін алгоритм сілтемелердің орналасуы, салыстырмалы түрде жылдам жұмыс істей алады.

Тиімді алгоритмдердің мысалдары

Бағдарламалаудың қазіргі жағдайына сын

Бағдарламалар компьютерлерге қарағанда тезірек баяулауда.

Мэй былай дейді:

Кең таралған жүйелерде нұсқауларды орындауды екі есе қысқарту батареяның қызмет ету мерзімін екі есеге ұзартады, ал үлкен деректер жақсырақ алгоритмдерге мүмкіндік береді: N x N-ден N x log(N) дейін операциялар санын азайту үлкен N үшін күшті әсер етеді... N үшін =30 млрд, бұл өзгерістер 50 жылдық технологиялық жетілдіруге ұқсас.

Үздік алгоритм үшін байқау

Келесі конкурстар сапа критерийлерін төрешілер анықтайтын үздік алгоритмдерді әзірлеуге қатысуға шақырады:

да қараңыз

Арифметикалық кодтау – энтропияны кодтаудың бір түрі айнымалы код ұзындығымендеректерді тиімді қысу үшін
Ассоциативті массив – пайдаланылған кезде тиімдірек болатын деректер құрылымы ағаштар PATRICIAнемесе Джуди массивтері
Өнімділік сынағы – белгілі бір жағдайларда салыстырмалы орындау уақытын өлшеу әдісі
Ең жақсы, ең нашар және орташа жағдай- үш сценарий үшін орындалу уақытын бағалауға арналған конвенциялар
Екілік іздеу сұрыпталған тізімді іздеудің қарапайым және тиімді әдісі болып табылады
Филиал кестесі

Жақсы жұмысыңызды білім қорына жіберу оңай. Төмендегі пішінді пайдаланыңыз

Білім қорын оқу мен жұмыста пайдаланатын студенттер, аспиранттар, жас ғалымдар сізге алғыстары шексіз.

Жұмыстың HTML нұсқасы әлі жоқ.
Жұмыстың мұрағатын төмендегі сілтемені басу арқылы жүктей аласыз.

Ұқсас құжаттар

Рекурсивті функцияларға негізделген алгоритмнің формальды моделінің сипаттамасы. Тьюринг тану машинасының алгоритмінің аналитикалық және бағдарламалық моделін жасау. Қалыпты Марков алгоритмдерін қолдану арқылы алгоритмнің аналитикалық моделін құру.

курстық жұмыс, 07.07.2013 қосылған

Алгоритм түсінігі және матрицалық көбейту алгоритмдерінің уақыттық күрделілігін теориялық бағалауды талдау. Кәдімгі бағдарламалау және Open MP технологиясын қолдану арқылы бағдарламалау арқылы алгоритмдердің кейбір кластарының уақыт күрделілігін бағалаудың салыстырмалы талдауы.

диссертация, 12.08.2017 қосылды

Жалпы түсінікалгоритм және оның күрделілік өлшемдері. Алгоритмдердің уақыт және сыйымдылық күрделілігі. Күрделілікті талдаудың негізгі әдістері мен тәсілдері. Оңтайландыру алгоритмді құру әдісін таңдаумен және бағдарламада деректерді ұсыну әдістерін таңдаумен байланысты.

аннотация, 27.11.2012 қосылған

Биометриялық аутентификация алгоритмдерінің тиімділігін арттыру мақсатында саусақ іздерінің сапасын жақсарту мәселесі. Саусақ ізі кескінін өңдеу алгоритмдеріне шолу. Габор түрлендіруін қолдануға негізделген алгоритмді талдау.

диссертация, 16.07.2014 қосылған

Бірнеше процессоры бар жүйелерде есептеу процесін ұйымдастыру әдістері. Тапсырмаларды пакеттік өңдеуге арналған көппроцессорлық жүйелердің алгоритмдері негізінде бағдарлама құру. Әрбір алгоритм бойынша негізгі өнімділік көрсеткіштерін есептеу.

курстық жұмыс, 21.06.2013 қосылған

Бағдарламаның есептеу күрделілігін бағалау. Хаффман ақпаратты кодтау алгоритмін енгізу. Тестті екілік және Хаффман ағаштарында кодтау. Екілік символдық код. Оның мәтінде пайда болу символы және жиілігі. Алгоритмнің күрделілігін есептеу.

сынақ, 12/16/2012 қосылды

Бұл мәселені вербалды бейресми тұжырымнан математикалық тұжырымға көшу. Ең тиімді деректер құрылымдарын және өңдеу алгоритмдерін таңдау үшін әртүрлі опцияларды бағалаңыз. Алгоритмдерді программалау тілдерінің бірінде жүзеге асыру.

курстық жұмыс, 25.06.2013 қосылған

Тиімді алгоритмдерді құрудың негізгі принциптері

Алгоритмдерді жасайтын кез келген адам кейбір негізгі әдістер мен түсініктерді меңгеруі керек. Қиын тапсырманы басынан өткерген кез келген адам «Неден бастау керек?» Деген сұраққа тап болды. Ықтимал әдістердің бірі - жаңа мәселенің шешімін тұжырымдау үшін олардың біреуін қолдануға болатынын білу үшін жалпы алгоритмдік әдістер қорын қарап шығу. Егер мұндай резерв жоқ болса, онда сіз әлі де жақсы алгоритмді қалай жасай аласыз? Неден бастау керек? Тапсырмаға қарап, не істерімізді білмей, бәрімізде көңілсіз тәжірибе болды. Алгоритмдерді жасау үшін пайдалы үш жалпы есептерді шешу әдістерін қарастырайық.

Бірінші әдісқиын тапсырманы қарапайым тапсырмалар тізбегіне келтірумен байланысты. Әрине, бастапқы есептерге қарағанда қарапайым есептерді өңдеу оңайырақ, сонымен қатар бастапқы есептің шешімін осы қарапайым есептердің шешімдерінен алуға болады деген үміт бар. Бұл процедура деп аталады жеке мақсаттар әдісі.Бұл әдіс өте орынды көрінеді. Бірақ есептерді шешудің немесе алгоритмдерді жобалаудың көптеген жалпы әдістері сияқты, белгілі бір мәселеге көшу әрқашан оңай бола бермейді. Жеңіл мәселелер бойынша ақылды таңдау жасау ғылымнан гөрі өнер немесе интуиция болып табылады. Бұл тәсілді қолдану арқылы шешуге болатын есептер класын анықтау үшін жалпы ережелер жиынтығы жоқ. Кез келген нақты мәселе туралы ойлау сұрақ қоюдан басталады. Нақты мақсаттарды келесі сұрақтарға жауап бергенде белгілеуге болады:

1. Есептің бір бөлігін шешуге болады ма? Кейбір шарттарды елемеу арқылы қалған мәселені шешуге бола ма?
2. Ерекше жағдайлар үшін мәселені шешу мүмкін бе? Есептің барлық шарттарын қанағаттандыратын шешім шығаратын, бірақ кіріс деректері барлық кіріс деректерінің кейбір ішкі жиынымен шектелетін алгоритмді әзірлеу мүмкін бе?
3. Мәселеге қатысты жақсы түсінілмеген нәрсе бар ма? Егер біз мәселенің кейбір ерекшеліктеріне тереңірек үңілуге тырыссақ, шешімге жақындауға көмектесетін нәрсені үйрене аламыз ба?
4. Ұқсас есептің белгілі шешімі бар ма? Қарастырылып отырған мәселені шешу үшін оның шешімін өзгертуге болады ма? Бұл мәселе белгілі шешілмеген мәселеге тең болуы мүмкін бе?

Екінші әдісалгоритмді әзірлеу деп аталады көтеру әдісі.Көтеру алгоритмі бастапқы болжам жасаудан немесе мәселенің бастапқы шешімін есептеуден басталады. Содан кейін ең жылдам жоғары қозғалыс бастапқы шешімнен жақсырақ шешімдерге қарай басталады. Алгоритм жоғары қарай жылжу мүмкін болмайтын нүктеге жеткенде, алгоритм тоқтайды. Өкінішке орай, көтеру алгоритмі арқылы алынған соңғы шешімнің оңтайлы екеніне кепілдік беру әрқашан мүмкін емес. Бұл жағдай көбінесе көтеру әдісін қолдануды шектейді.

Жалпы алғанда, көтеру әдістері «дөрекі» деп жіктеледі. Олар қандай да бір мақсатты есте сақтайды және мақсатқа жақындау үшін қолдарынан келгеннің бәрін жасауға тырысады. Бұл оларды біршама «көргіш» етеді. Көтеру әдісінің алысты көрмеуі келесі мысалда жақсы көрсетілген. Функцияның максимумын табу керек делік сағ =/(X),графикпен берілген (2.15-сурет). Аргументтің бастапқы мәні болса x = a,онда өрлеу әдісі ең жақын мақсатқа ұмтылыс береді, яғни. нүктедегі функцияның мәніне x = b,ал бұл функцияның шын максимумы = c шамасында. Бұл жағдайда

Күріш. 2.15. Көтеру әдісінің суреті Көтеру әдісі жергілікті максимумды табады, бірақ ғаламдық емес. Бұл көтеру әдісінің «кедір-бұдыры».

Үшінші әдісретінде белгілі қайта жұмыс істеу,анау. Бұл алгоритмнің жұмысы мақсат қоюдан немесе мәселені шешуден басталады, содан кейін есептің бастапқы тұжырымына қарай жылжиды. Содан кейін, егер бұл әрекеттер қайтымды болса, проблемалық мәлімдемеден шешімге қарай қозғалыс жасалады.

Барлық үш әдісті қарастырайық джип мәселесі.Сізге ең аз отынды пайдаланып, джиппен 1000 шақырымдық шөлді кесіп өту керек делік. Джиптің жанармай багының көлемі 500 литр, отын біркелкі жұмсалады, 1 км-ге 1 литр. Сонымен қатар, бастапқы нүктеде жанармайдың шексіз цистернасы бар. Шөлде жанармай қоймалары болмағандықтан, сіз өзіңіздің сақтау қоймаларыңызды орнатып, оларды көліктің бакындағы жанармаймен толтыруыңыз керек. Сонымен, тапсырманың идеясы түсінікті: сіз бастапқы нүктеден біраз қашықтыққа толық резервуармен жүруіңіз керек, сонда бірінші қойма орнатуыңыз керек, цистернадан белгілі бір мөлшерде жанармай қалдыруыңыз керек, бірақ жеткілікті. қайта оралу. Бастапқыда толық жанармай құю қайтадан жүзеге асырылады және екінші қойманы одан әрі шөлге жылжыту әрекеті жасалады. Бірақ бұл қоймаларды қайда орнату керек және олардың әрқайсысында қанша жанармай сақтау керек?

Бұл мәселені кері жұмыс әдісі арқылы қарастырайық. Дәл осындай мөлшердегі отынмен шөлді ұшынан қандай қашықтықта кесіп өтуге болады? Кімгетанктер? Бұл сұрақты қарастырайық Кімге= 1,2, 3,... осындай бүтін санды тапқанша P,Не Птолық танктер 1000 шақырымдық шөлді басып өтуге мүмкіндік береді. Үшін Кімге= 1 жауап 500 км = 500 л (нүкте IN),суретте көрсетілгендей. 2.16.

Күріш. 2.16.

Сіз көлікке жанармай құюға болады INжәне қалған 500 км шөлді кесіп өтеді. Белгілі бір мақсат қойылды, себебі бастапқы мәселені бірден шешу мүмкін емес.

Солай етейік Кімге= 2, яғни. екі толық резервуар (1000 л) бар. Бұл жағдай суретте көрсетілген. 2.16. (500 - Xj) нүктесінен 1000 л жанармайдан бастап, жолды аяқтау үшін жеткілікті жанармайды нүктеге дейін тасымалдауға болатындай jCj максималды мәні қандай болуы керек. Кімге= 1. Қолайлы мәнді анықтаудың бір жолы X (келесідей. Біз нүктеде жанармай құйамыз (500 - Xj), біз барамыз X (нүктеге дейін километр INжәне нүктеге (500 - Xj) оралу үшін қажетті бөліктен басқа барлық отынды қоймаға құйыңыз. Бұл кезде резервуар бос болады. Енді біз екінші резервуарды толтырамыз, Xj километрге дейін барамыз IN, мына жерден алыңыз INжанармай сол жерде қалды және одан INБіз С-ға толық резервуармен барамыз. Жалпы жүріп өткен қашықтық үш сегменттен тұрады X (километр және бір сегмент КүнҰзындығы 500 км. Демек, 3x t + 500 = 1000 теңдеуінен оның шешімін Xj = 500/3 табамыз. Осылайша, екі резервуар (1000 л) Z> 2 = 500 жүруге мүмкіндік береді +x ( = 500(1 + 1/3) км.

қарастырайық k = 3. Джип 1000 литрді (500 - х)) нүктеге жеткізе алатындай етіп 1500 литр отынмен қай нүктеден кетуге болады? (500 - Xj - x 2) нүктеден 1500 литр отынмен қалдырып, нүктеге (500 - Xj) 1000 литр жеткізе алатындай x 2-нің ең үлкен мәнін табайық. Біз нүктеден (500 - Xj - x 2) шығып, (500 - x) дейін жүріп, х 2 литрден басқа барлық отынды жібереміз және бос резервуармен (500 - Xj - x 2) нүктеге ораламыз. Бұл процедураны қайталай отырып, біз саяхатқа 4x 2 литр жұмсаймыз және нүктеде (1000 - 4x 2) литр қалдырамыз (500 - x L). Енді нүктеде (500 - Xj - x 2) тура 500 литр қалды. Біз соңғы 500 литрді толтырып, оған x 2 литр жұмсап, нүктеге (500 - Xj) барамыз.

(500 - Xj) нүктесінде болғандықтан, біз саяхатқа 5х 2 литр отын жұмсаймыз. Мұнда барлығы (1500 - 5х 2) литр қалды. Бұл сома 1000 л тең болуы керек, яғни. x 2 = 500/5. Осыдан 1500 литр көлік жүргізуге мүмкіндік береді деген қорытындыға келеміз

Кері индуктивті жұмыс процесін жалғастыра отырып, біз оны аламыз Пжанармай цистерналары бізге өтуге мүмкіндік береді Днкилометр, қайда Дн = 500(1 +1/3 + 1/5 + ... + 1/(2П - 1)).

Біз ең кіші мәнді табуымыз керек P,қай жерде Дн> 1000. Қарапайым есептеулер мынаны көрсетеді n = 7 бізде D?= 997,5 км, яғни. жеті цистерна немесе 3500 литр жанармай сізге саяхаттауға мүмкіндік береді

977,5 км. Толық сегізінші резервуар - бұл нүктеден 3500 литр тасымалдау үшін қажет болғаннан көп болады Аорналасқан нүктеге дейін
А-дан 22,5 км (1000 - 977,5) Оқырманға 22,5 км белгісіне 3500 литр жанармай жеткізу үшін 337,5 литр жеткілікті екенін өз бетінше тексеруге мүмкіндік беріледі. Осылайша, шөлді I-ден С-ға көлікпен өту үшін 3837,5 литр жанармай қажет.

Енді отынды тасымалдау алгоритмін келесідей ұсынуға болады. -ден бастаймыз А, 3837,5 литр. Мұнда бірте-бірте белгіге дейін 3500 литрді тасымалдауға жеткілікті жанармай бар

22,5 км, бұл жерде джип ақыры бос цистернамен және 7 рет толық толтыру үшін жеткілікті отынмен аяқталады. Бұл отын 3000 литрді 22,5 + 500/13 км қашықтықтағы нүктеге жеткізуге жеткілікті. А,машинаның цистернасы қай жерде қайтадан бос болады. Кейінгі тасымалдау джипті 22,5 + 500/13 + 500/11 км қашықтықта орналасқан нүктеге әкеледі. А,вагонның бос цистернасымен және қоймада 2500 л.

Осылай жалғастыра отырып, біз кері жұмыс жасау арқылы жүргізілген талдаудың арқасында алға жылжып келеміз. Жақында джип 1000 литр жанармаймен 500 (1 - 1/3) шақырымға жетеді. Содан кейін пунктке 500 литр жанармай тасымалдаймыз IN,соларды машинаның цистернасына құйып, тоқтамай нүктеге жетейік МЕН(2.17-сурет).

Күріш. 2.17.

Шексіз қатарлармен таныстар үшін мынаны ескеріңіз DСонда бар П-тақ гармоникалық қатардың жартылай қосындысы. Бұл қатар әртүрлі болғандықтан, алгоритм кез келген шөлді кесіп өтуге мүмкіндік береді. Нүктеге оралу үшін шөлдегі әртүрлі нүктелерде жеткілікті отын қалдыру үшін осы алгоритмді өзгертіп көріңіз А.

3837,5 литрден аз отынмен 1000 шақырым жүруге бола ма деген сұрақ туындайды. Сіз алмайсыз. Бұл мәлімдеменің дәлелі өте күрделі. Дегенмен, келесі, өте орынды, дәлел келтіруге болады. Біз әрекет етіп жатқанымыз анық ең жақсы жолҮшін Кімге= 1. Қашан Кімге= 2 жоспар үшін пайдаланылады Кімге= 1, содан кейін нүктеден мүмкіндігінше алыс болу үшін жанармайдың екінші багы іске қосылады IN.үшін бастапқы алғышарт Кімгетанктер - бұл жағдайда біз қалай жақсы әрекет ету керектігін білеміз (- 1) цистерналарды алып, көмекпен мүмкіндігінше артқа жылжытыңыз ДДСҰтанк.

Сонымен, қарастырылып отырған мәселеде кері жұмыс істеу әдісі – мәселенің соңынан бастап шешілгендей; ішінара мақсаттар әдісі - олар барлық мәселені бірден емес, бөліктерге бөледі; және, сайып келгенде, көтерілу әдісі шешім бірден табылмай, оған жақындағандай рет-ретімен көрінеді.