Кіріспе
Жергілікті жақсы нұсқаулардың тізбегі
Ашкөз алгоритм – бұл әр қадамда жергілікті жақсы нұсқау жасауға негізделген, проблеманы шешу эвристикасын қолданатын кез келген алгоритм. Көптеген жағдайларда ашкөз стратегия оңтайлы шешім бермейді, бірақ ашкөз эвристикасы жаһандық оңтайлы шешімге жуық, жергілікті жақсы шешімдерді қол жетімді уақыт ішінде табуға мүмкіндік береді. Мысалы, саяхатшы сатушысының мәселесі үшін (өте күрделі есептеу мәселесі) ашкөз стратегиясы мына эвристиканы ұсынады: «Саяхаттың әр қадамында, сапарламаған ең жақын қалаға барыңыз». Бұл эвристика ең жақсы шешімді табуға бағытталмайды, бірақ оны ақылға қонымды қадамдар санымен аяқтауға болады. Мұндай күрделі мәселенің оңтайлы шешімін табу үшін көбінесе өте көп қадамдар қажет болады. Математикалық оптимизацияда ашкөз алгоритмдер матроид қасиеттеріне ие комбинаторлық мәселелерді оңтайлы шешеді және субмодульдік құрылымы бар оптимизациялық мәселелерге тұрақты факторлық жуықтауды қамтамасыз етеді.
Ерекшеліктер
Ашкөз алгоритмдер кейбір математикалық мәселелерді жақсы шешеді, бірақ басқаларын шеше алмайды. Олардың жұмыс істейтін көптеген мәселелер екі қасиетке ие:
Greedy choice property We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution. Optimal substructure "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub problems."
Ашкөз таңдау қасиеті: Біз сол сәтте ең жақсы көрінетін кез келген таңдауды жасай аламыз, содан кейін туындайтын кіші мәселелерді шешеміз. Ашкөз алгоритм жасаған таңдау бұрынғы таңдауларға байланысты болуы мүмкін, бірақ болашақ таңдауларға немесе кіші мәселенің барлық шешімдеріне байланысты емес. Ол қайта-қайта бір ашкөз таңдаудан кейін бірін жасап, әр берілген мәселені кішірейтіп отырады. Яғни, ашкөз алгоритм ешқашан өзінің таңдауларын қайта қарамайды. Бұл динамикалық бағдарламалаудан басты айырмашылық, ол толыққанды болып, шешімді табуға кепілдік береді. Әр кезеңнен кейін динамикалық бағдарламалау алдыңғы кезеңде жасалған барлық шешімдерге негізделген шешімдер қабылдайды және шешімге дейінгі алгоритмдік жолды қайта қарауы мүмкін.
Greedy choice property We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution. Optimal substructure "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub problems."
Оптималды құрылым: "Егер мәселенің оңтайлы шешімі кіші мәселелердің оңтайлы шешімдерін қамтитын болса, онда мәселе оңтайлы құрылымға ие."
Greedy choice property We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution. Optimal substructure "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub problems."
Жарамсыздық жағдайлары
Ашкөз алгоритмдер көптеген басқа да проблемалар үшін ең оңтайлы шешімді беруге қабілетсіз, тіпті ең нашар мүмкін шешімді де шығаруы мүмкін. Мысалы, жоғарыда айтылған саяхатшы сатушысының мәселесін қарастырайық: қалалардың әр саны үшін қалалар арасындағы қашықтықтарды осындай етіп белгілеуге болады, онда ең жақын көрші эвристикасы ең нашар мүмкін болатын бірегей маршрутты құрастырады. Басқа мысалдар үшін, көкжиек эффектісіне жүгініңіз.
Матроидтар
Матроид – векторлық кеңістіктерден кез келген жиынға сызықтық тәуелсіздік ұғымын жалпылайтын математикалық құрылым. Егер оңтайландыру мәселесі матроид құрылымын қабылдаса, онда сәйкес ашкөз алгоритм оны ең жақсы шешеді.
Субмодульдік функциялар
Жинақтың кіші жиындарында анықталған функция, егер әрбір үшін мына теңсіздік орындалса, субмодульді деп аталады: . Егер біреу максималдық жиынтықты тапқысы келсе, ашкөз алгоритм, әрбір қадамда функцияны ең көп арттыратын элементті қосып, жиынтықты құрастырады. Бұл алгоритмнің нәтижесінде алынған жиынтық кем дегенде, яғни ашкөз алгоритм оңтайлы шешімге қарағанда тұрақты фактормен жақын нәтиже береді. Шығысқа кардиналдық сияқты қосымша шектеулер қойылған жағдайда да осындай кепілдіктерді дәлелдеуге болады, бірақ көбінесе ашкөз алгоритмге шағын өзгерістер енгізу қажет. Толық шолу үшін қараңыз.
Suppose one wants to find a set which maximizes The greedy algorithm, which builds up a set by incrementally adding the element which increases the most at each step, produces as output a set that is at least That is, greedy performs within a constant factor of as good as the optimal solution. Similar guarantees are provable when additional constraints, such as cardinality constraints, are imposed on the output, though often slight variations on the greedy algorithm are required. See for an overview.
Қолданбалар
Ашкөз алгоритмдер әдетте (бірақ әрдайым емес) жаһандық оңтайлы шешімді таба алмайды, себебі олар көбінесе барлық деректерді толыққанды қарастырмайды. Олар кейбір шешімдерге тым ерте бекініп, кейіннен ең жақсы жалпы шешімді табуға кедергі келтіруі мүмкін. Мысалы, графтарды бояу мәселесі үшін белгілі барлық ашкөз бояу алгоритмдері және басқа да NP-толық проблемалар тұрақты түрде оңтайлы шешімдерді таба алмайды. Дегенмен, олар пайдалы, өйткені оларды ойлап табу оңай және олар көбінесе оңтайлы мәнге жақын жуықтап алады. Егер ашкөз алгоритмнің белгілі бір проблема класы үшін жаһандық оңтайлы нәтиже беретіні дәлелденсе, ол әдетте басым әдіс болады, өйткені ол динамикалық бағдарламалау сияқты басқа оңтайландыру әдістерінен жылдам. Мұндай ашкөз алгоритмдердің мысалдары – Крускал алгоритмі және Прим алгоритмі ең аз қамтитын ағаштарды табу үшін, сондай-ақ оңтайлы Хаффман ағашын табу алгоритмі. Ашкөз алгоритмдер желілік маршрутизацияда да қолданылады. Ашкөз маршрутизацияны пайдалана отырып, хабарлама мақсатқа "ең жақын" көрші түйінге жіберіледі. Түйіннің орналасуы (сонымен қатар "жақындығы") оның физикалық орналасуымен анықталуы мүмкін, мысалы, ad hoc желілерінде қолданылатын географиялық маршрутизацияда. Орналасу шағын әлемдік маршрутизация және таратылған хэш-кестелердегідей толыққанды жасанды құрылым болуы мүмкін.
Мысалдар
Іс-әрекеттерді таңдау мәселесі осы мәселелер класына тән, онда мақсат бір-бірімен қақтырыспайтын іс-әрекеттердің максималды санын таңдау болып табылады. Macintosh компьютерлік ойыны Crystal Quest-тің мақсаты – саяхатшы сатушы мәселесіне ұқсас, кристаллдарды жинау. Ойынның демонстрациялық режимі бар, онда ойын әрбір кристаллға бару үшін ашкөз алгоритмді қолданады. Жасанды интеллект кедергілерді ескермейді, сондықтан демонстрациялық режим көбінесе тез аяқталады. Сәйкестік іздеу – сигналды жуықтау үшін қолданылатын ашкөз алгоритмнің мысалы. Ашкөз алгоритм Мальфатти мәселесіне оңтайлы шешімді табады, яғни берілген үшбұрыш ішінде үш ажыратылған шеңберді табу, олар шеңберлердің жалпы ауданын барынша арттырады; осы ашкөз алгоритм кез келген сандағы шеңберлер үшін де оңтайлы деп есептеледі. Huffman кодтау кезінде Huffman ағашын құру үшін ашкөз алгоритм қолданылады, ол оңтайлы шешімді табады. Шешім ағаштарын құруда ашкөз алгоритмдер жиі қолданылады, бірақ олар оңтайлы шешімді табуға кепілдік бермейді. Мұндай танымал алгоритмдердің бірі – шешім ағашын құру үшін ID3 алгоритмі. Дикстра алгоритмі және оған байланысты A* іздеу алгоритмі – графты іздеу және ең қысқа жолды табу үшін расталатын оңтайлы ашкөз алгоритмдер. A* іздеу шартты түрде оңтайлы, ол жол құнын асыра бағаламау үшін «қабылданатын эвристиканы» қажет етеді. Крускал алгоритмі және Прим алгоритмі – берілген байланысты графтың ең аз қамтитын ағаштарын құруға арналған ашкөз алгоритмдер. Олар әрқашан оңтайлы шешімді табады, ол жалпы жағдайда бірегей болмауы мүмкін. Sequitur және Lempel Ziv Welch алгоритмдері – грамматикалық индукция үшін ашкөз алгоритмдер болып табылады.