Сцена от Good Will Hunting, където Уил решава сложен проблем в MIT

Разлика между алгоритми и евристични

Нека изследваме основната структура на проектирането на алгоритъм чрез някои интересни проблеми и техните тънкости

мотивиране

Отнеха ми години, за да разбера, че компютърните науки не са за „Компютри“ или „Програмиране“. Ние попадаме в този капан, тъй като сме толкова закачени с думата „компютър“ и „програмиране“, които се използват толкова слабо с тази дисциплина. Компютърните науки са изучаването на проблемите. Имайки проблем, целта на компютърния учен е да разработи алгоритъм, стъпка по стъпка списък с инструкции за решаване на всеки случай на проблема, който може да възникне. Алгоритмите са ограничени процеси, които ако бъдат спазени, ще решат проблема. Алгоритмите са решения, разбира се с малки изключения като всичко останало на този свят. Компютрите и програмирането са само инструментите за постигане на това.

След като се убедих, че „Компютърните науки са изучаване на алгоритми“, бързо бих могъл да го свържа с математиката. Всъщност те са повече от братя и сестри. Сега това е красотата, когато можете грациозно да се ориентирате от една дисциплина в друга. Накратко, няма да сбъркам, ако кажа, че математиката е основата, върху която са изградени компютърните науки и освен това алгоритмите са друг начин за изразяване на математиката. Това е музиката на разума.

Това е решаване на проблеми, поглъщащо интелектуално и красиво - което е достатъчна мотивация за мен да започна с изучаването на алгоритми. Сигурен съм, че имате и ще го направите. Нека завърша този раздел с два цитата, което дава добра основа за нашето изследване и със сигурност храна за размисъл.

Трябва да се види алгоритъм, за да се вярва. - Доналд Кнут (математик и компютърен учен)
Джон Фон Нойман
Ако хората не вярват, че математиката е проста, то е само защото не осъзнават колко сложен е животът. - Джон фон Нойман (математика, физика, статистика, икономика и компютърни науки)

Въведение

Да започнем с проблем. Алгоритмичният проблем, известен като сортиране, се дефинира, както следва:

Разграничаването между проблем и случай на проблем е основно. Например в този случай може да бъде масив от имена като {Suvro, Bhavna, Jane, Mike, Ram, Richa} или списък с числа като {7, 12, 11, 101, 45}. Но алгоритъмът за "сортиране" е общ проблем и следователно се нуждае от общо решение, което може да предприеме всички възможни входни инстанции и да ви получи желания резултат. Има различни алгоритми за решаване на проблема със сортирането, от които единият се нарича „Сортиране на вмъкване“.

Анимация на логическия поток от сортиране на вмъкване в конкретен случай

Вмъкването сортиране е метод за сортиране, който започва с един елемент (като по този начин формира тривиално сортиран списък) и след това постепенно вмъква останалите елементи, така че списъкът да остане сортиран. Разгледайте представителството вляво.

Реализацията на Python на Insertion Sort е както следва:

Вътрешният процес на сортиране на вмъкване

Винаги търсим алгоритми, които са правилни, ефективни и лесни за изпълнение. В тази уводна глава ще се съсредоточим само върху въпроса за коректността на алгоритмите.

Правилните алгоритми обикновено идват с доказателство за коректност, т.е. трябва да отведе всеки случай на проблема до желания резултат, подобно на това, което видяхме в горния пример. Но, преди да продължим по-нататък, нека демонстрираме защо „това е очевидно“ никога не е достатъчно доказателство за коректност и обикновено е плоско грешно.

Моят алгоритъм ли е очевиден или правилен?

Нека разгледаме проблем, който често възниква при приложения за производство, транспорт и тестване. Кажете, имате робот, който е способен да запоява. Сега искате да спойкате платка, която се състои от чипове и други компоненти, които трябва да бъдат закрепени към платката. И така, очевидният въпрос е как роботът ще обикаля целия борд и ще свърши задачата. Това трябва да се направи ефективно, тъй като има много дъски, които трябва да бъдат произведени в даден момент и всяка дъска има много такива точки за запояване.

Официалното определение на проблема ще изглежда нещо подобно и трябва да програмираме рамото на робота.

Проблем: Оптимизация на роботи с обиколки

Вход: Набор S от „n“ точки в равнината

Резултат: Коя е най-кратката обиколка с цикъл, която посещава всяка точка от множеството S?

Показване-1: Евристиката на най-близкия съсед

Може би най-важната идея би била евристиката на най-близкия съсед. Започвайки от някаква случайна точка p0, ходим до първата си най-близка съседка p1. От p1, ние ходим до най-близкия си невидим съсед (по този начин изключваме p0 като кандидат). Продължаваме да го повтаряме, докато всички точки не бъдат посетени веднъж и след това се връщаме към първоначалната ни точка p0, за да завършим обиколката.

И така, основната идея тук е да посетим близките точки, преди да посетим отдалечени точки, за да намалим общото време за пътуване. Той работи перфектно върху изобразяването-1, дадено по-горе и също не много, но сравнително ефективно, когато разглежда два двойки точки (pi, pj) два пъти, веднъж при добавяне на pi и други, когато добавяте pj към обиколката. Но, съжалявам, че този алгоритъм е напълно НЕЗАВИСИМ.

Алгоритъмът разбира разбира се обиколка, но не е задължително да намери най-краткия възможен тур. Помислете за случая, когато всички точки са разположени по права линия, вижте изображение 2. След това, ако започнем от 0, продължаваме да хопскотираме ляво-дясно-ляво… през целия борд, докато оптимална обиколка може да е започнала от най-лявата точка и да посещаваме всяка точка, докато вървим надясно и накрая да се върнем обратно към първата точка.

Показване-2: Евристиката на най-близкия съсед

Може да е това, от което се нуждаем, е различен подход. Винаги ходенето до най-близката точка е твърде ограничително. Така че не можете да разберете само като ги погледнете дали алгоритмите са правилни или грешни.

На този етап може да се чудите какъв трябва да е правилният алгоритъм за решаване на този проблем. Е, един отговор може да бъде сигурен правилен, който е да се изброят всички възможни подреждания на всички точки и след това да изберете това подреждане, което свежда до минимум общата дължина. Така че, ние гарантирано ще завършим с възможно най-краткото турне.

Сега, нека да оценим допълнително тази възможност. Кажете, има общо 20 точки. Така че, за да изброим всички възможни пътеки с 20 точки, ще имаме 20! (20 факторни), който е с магнитуд 10 спрямо мощността 18 различни подреждания. Това е голям брой за един компютър, който да оцени и да каже, ако n = 1000 е напълно възможно, тогава може да се наложи да изчакаме да се случи друг голям взрив, преди компютърът да може да оцени всички възможности и да разбере кой път е най-кратък ,

Този проблем е по-известен като Проблемът с продавача на пътници (TSP) и определено ще положим усилия да намерим ефективен алгоритъм за решаване на този проблем, но засега основният изход от тази дискусия е, че има фундаментална разлика между алгоритмите и евристични методи. Алгоритмите винаги дават правилен резултат, но евристичният може да свърши чудесна работа, но никога не гарантира цялостно решение.

Още тънкости относно коректността на алгоритъма

Нека разгледаме друг проблем за разширяване на нашата мисъл относно точността на алгоритма. Това е проблем с планирането. Кажете, вие сте един от търсените актьори / актриси и имате списък с филмови проекти, за да влезете. Офертите идват с началната дата и крайната дата на проекта. Сега, за да се заемете с работата, не можете едновременно да приемате два проекта, чиито интервали се припокриват.

За художник като вас самата цел е много ясна, т.е. да направи възможно най-много пари от тези проекти. Всеки проект плаща една и съща такса, което означава, че търсите възможно най-голям набор от проекти, чиито интервали от време не се припокриват. Нека да разгледаме изобразителното изображение на този проблем с планирането.

Показване - 3: Проблем с планирането

Сега, както преди, нека официално да дефинираме проблемното изявление -

Проблем: Проблем с планирането на филми

Вход: набор от I от n интервала на линията.

Резултат: Кой е най-големият подмножество от взаимно не се припокриващи се интервали, които могат да бъдат избрани от I?

Сигурен съм, че ще има много идеи за проектиране на този алгоритъм. Човек може да започне да работи винаги, когато е налице първата работа, т.е. трябва да започнете с работата с най-ранната начална дата, след като всичко, което не искате да седите в бездействие.

Алгоритъм за избор на задание за най-ранна дата на стартиране

Сега защо това не е чудесна идея, за да продължите напред. Помислете за първата работа, която продължава много дълъг период от време и от своя страна убива всички перспективи за работа с по-кратък срок. Този сценарий е изобразен по-долу-

Лоша идея с алгоритъма за избор на задачи за най-ранна дата на стартиране

И така, естественият прогрес на мисълта би бил да започнете да избирате най-кратката работа и да продължавате да търсите най-кратката налична работа на всеки етап. Увеличаването на това число би увеличило печалбата. Нека определим това евристично формално -

Най-кратък избор на работа

Този подход изглежда добре, но заемането на най-кратки работни места може да ни ограничи до половината изплащане. Нека разгледаме по-долу изображението на този случай.

Ограничете изплащането, като изберете най-кратката работа

Така че, нека да потърсим алгоритъм, който е едновременно правилен и ефективен -

Правилен и ефективен алгоритъм за проблема с планирането на филма

Така че, в нашия случай, вижте Отдел -3, за да видите как са подредени проектите. По-долу изображението показва как художникът приема филмите-

Решение на нашия проблем с насрочването на филми

Отнеси

  1. Съществува фундаментална разлика между алгоритмите, които винаги дават правилен резултат, и евристиката, която обикновено може да свърши добра работа, но без да предоставя никаква гаранция.
  2. Коректността на алгоритъма е свойство, което трябва внимателно да се демонстрира.

Бележка на автора

Това е първата статия от поредицата „Алгоритми и структури от данни“. В следващата статия ще изградим математическа рамка, която ще демонстрира правилността на алгоритмите. Останете на линия ...

Честито учене :)

Източници

  1. Ръководството за дизайн на алгоритъма - Стивън С. Скиена, катедра по компютърни науки, SUNY Stony Brook, САЩ.
  2. Въведение в алгоритмите - Cormen, Leiserson, Rivest & Stein
  3. Алгоритми и структури от данни, използващи Python - Brad Miller и David Ranum, Luther College