Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымда, егер мәселенің оңтайлы шешімін оның ішкі мәселелерінің оңтайлы шешімдерінен құрастыруға болады, онда мәселенің оңтайлы құрылымы бар деп айтылады. Бұл қасиет мәселе үшін ашкөз алгоритмдердің тиімділігін анықтау үшін пайдаланылады. Әдетте, ашкөз алгоритм оңтайлы құрылымы бар мәселені шешу үшін қолданылады, егер индукция арқылы әр қадамда оның оңтайлы екендігі дәлелденсе. Әйтпесе, егер мәселеде үстемелі ішкі мәселелер болса, «бөліп талқандау» әдістерін немесе динамикалық бағдарламалау қолданылуы мүмкін. Егер тиімді ашкөз алгоритмдер болмаса және мәселеде үстемелі ішкі мәселелер болмаса, шешім кеңістігін ұзақ, бірақ түзу іздеу – ең жақсы балама болып табылады. Динамикалық бағдарламалауды математикалық оптимизацияға қолданғанда, Ричард Беллманның Оптималдық Принципі динамикалық оптимизация мәселесін белгілі бір бастапқы кезеңнен белгілі бір аяқталу кезеңіне дейін шешу үшін, кейінірек s кезеңінен басталатын ішкі мәселелерді шешу қажеттігіне негізделген, мұнда t < s < T. Бұл оңтайлы құрылымның мысалы. Оптималдық Принципі Беллман теңдеуін туындату үшін қолданылады, ол t кезеңінен басталатын мәселенің мәнінің s кезеңінен басталатын мәселенің мәнімен қалай байланысты екенін көрсетеді.
In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem. Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step. Otherwise, provided the problem exhibits overlapping subproblems as well, divide and conquer methods or dynamic programming may be used. If there are no appropriate greedy algorithms and the problem fails to exhibit overlapping subproblems, often a lengthy but straightforward search of the solution space is the best alternative. In the application of dynamic programming to mathematical optimization, Richard Bellman's Principle of Optimality is based on the idea that in order to solve a dynamic optimization problem from some starting period t to some ending period T, one implicitly has to solve subproblems starting from later dates s, where t<s<T. This is an example of optimal substructure. The Principle of Optimality is used to derive the Bellman equation, which shows how the value of the problem starting from t is related to the value of the problem starting from s.
Мысал
1-суретте көрсетілгендей, екі қала арасында көлікпен саяхаттау үшін ең қысқа жолды табуды қарастырайық. Мұндай мысал оңтайлы тармақтылықты (optimal substructure) көрсетуі мүмкін. Яғни, егер Сиэтлден Лос-Анджелеске дейінгі ең қысқа бағыт Портлендтен, содан кейін Сакраментодан өтетін болса, онда Портлендтен Лос-Анджелеске дейінгі ең қысқа бағыт та Сакраментодан өтуі керек. Демек, Портлендтен Лос-Анджелеске қалай жету мәселесі Сиэтлден Лос-Анджелеске қалай жету мәселесінің ішінде орналасқан. (Графиктегі толқынды сызықтар кіші мәселелердің шешімдерін көрсетеді.) Оңтайлы тармақтылықты көрсетуі күмәнді мәселенің мысалы ретінде Буэнос-Айрестен Мәскеуге ең арзан әуе билетін табу мәселесін қарастырайық. Егер бұл билет Маями мен Лондон арқылы жасалса да, Маямиден Мәскеуге ең арзан билеттің Лондон арқылы болатынына сенімді тұжырым жасауға болмайды, себебі әуе компаниясы бірнеше рейстен тұратын сапарды сату бағасы көбінесе сапардағы жеке рейстердің бағаларының қосындысына тең болмайды.
Consider finding a shortest path for traveling between two cities by car, as illustrated in Figure 1. Such an example is likely to exhibit optimal substructure. That is, if the shortest route from Seattle to Los Angeles passes through Portland and then Sacramento, then the shortest route from Portland to Los Angeles must pass through Sacramento too. That is, the problem of how to get from Portland to Los Angeles is nested inside the problem of how to get from Seattle to Los Angeles. (The wavy lines in the graph represent solutions to the subproblems.) As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to Moscow. Even if that ticket involves stops in Miami and then London, we can't conclude that the cheapest ticket from Miami to Moscow stops in London, because the price at which an airline sells a multi flight trip is usually not the sum of the prices at which it would sell the individual flights in the trip.
Анықтама
Оптималды субструктураның сәл формалды анықтамасын беруге болады. "Проблема" – "баламалардың" жиынтығы болсын, және әр баламаға c(a) шығыны сәйкес келсін. Міндет – c(a) шығынын ең төмендетуге мүмкіндік беретін баламалар жиынтығын табу. Баламаларды кіші топтарға бөлуге болады, яғни әр балама тек бір кіші топқа жатады. Әр топтың өзіндік шығын функциясы бар делік. Осы шығын функцияларының әрқайсысының ең төменгі мәнін, сондай-ақ сол кіші топтармен шектелген жаһандық шығын функциясының ең төменгі мәнін табуға болады. Егер осы ең төменгі мәндер әр кіші топ үшін сәйкес келсе, онда жаһандық ең төменгі мәнді барлық баламалар жиынтығынан емес, біз анықтаған кіші, жергілікті шығын функцияларының ең төменгі мәндерінен тұратын жиынтықтан таңдауға болады. Егер жергілікті функцияларды ең төмендету "төменгі дәрежелі" проблема болса және (нақтырақ айтқанда) осы азайтулардың шекті санынан кейін проблема тривиальды болса, онда проблеманың оптималды субструктурасы бар.
A slightly more formal definition of optimal substructure can be given. Let a "problem" be a collection of "alternatives", and let each alternative have an associated cost, c(a). The task is to find a set of alternatives that minimizes c(a). Suppose that the alternatives can be partitioned into subsets, i. e. each alternative belongs to only one subset. Suppose each subset has its own cost function. The minima of each of these cost functions can be found, as can the minima of the global cost function, restricted to the same subsets. If these minima match for each subset, then it's almost obvious that a global minimum can be picked not out of the full set of alternatives, but out of only the set that consists of the minima of the smaller, local cost functions we have defined. If minimizing the local functions is a problem of "lower order", and (specifically) if, after a finite number of these reductions, the problem becomes trivial, then the problem has an optimal substructure.