Сцэна з 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 з інтэрвалаў у радку.

Вынік: Якое самае вялікае мноства інтэрвалаў узаемна не перакрываюцца, якія можна выбраць з I?

Я ўпэўнены, што будзе шмат ідэй для распрацоўкі гэтага алгарытму. Можна пачынаць працаваць кожны раз, калі ёсць першая праца, то ёсць пачынаць працу трэба з самай ранняй даты, пасля таго, як вы не хочаце сядзець без справы.

Алгарытм выбару задач ранняй даты пачатку

Цяпер, чаму гэта не выдатная ідэя, каб ісці наперад. Падумайце пра першую працу, якая доўжыцца вельмі доўга, і, у сваю чаргу, забівае ўсе перспектывы, якія маюць больш кароткі тэрмін. Гэты сцэнар прадстаўлены ніжэй-

Няправільная ідэя з алгарытмам выбару заданняў найбольш ранняй даты пачатку

Такім чынам, натуральным развіццём думкі было б пачаць выбіраць самую кароткую працу і працягваць шукаць самую кароткую працу на кожным кроку. Максімізацыя гэтай колькасці максімальна павялічыць прыбытак. Давайце вызначым гэта эўрыстычна -

Самы кароткі выбар працы

Цяпер такі падыход выглядае добра, але прымаць кароткія задачы можа абмежаваць нас да паловы выплат. Давайце разгледзім ніжэй малюнак гэтага выпадку.

Абмяжуйце выплату, выбраўшы самую кароткую працу

Такім чынам, давайце пашукаем правільны і эфектыўны алгарытм -

Правільны і эфектыўны алгарытм для праблемы планавання фільмаў

Такім чынам, у нашым выпадку, глядзіце малюнак -3, каб даведацца, як выбудоўваюцца праекты. На малюнку ніжэй паказана, як мастак прымае фільмы-

Рашэнне праблемы планавання фільмаў

Забярыце

  1. Існуе прынцыповая розніца паміж алгарытмамі, якія заўсёды даюць правільны вынік, і эўрыстыкай, якая звычайна можа зрабіць добрую працу, але без прадастаўлення якіх-небудзь гарантый.
  2. Правільнасць алгарытму - гэта ўласцівасць, якую неабходна ўважліва прадэманстраваць.

Заўвага аўтара

Гэта першы артыкул з серыі "Алгарытмы і структуры дадзеных". У наступным артыкуле мы пабудуем матэматычную аснову, якая б прадэманстравала правільнасць алгарытмаў. Сачыце за абнаўленнямі …

Шчаслівае навучанне :)

Крыніцы

  1. Кіраўніцтва па алгарытме - Стывен Скіена Скіена, кафедра камп'ютэрных навук, SUNY Stony Brook, ЗША.
  2. Уводзіны ў алгарытмы - Cormen, Leiserson, Rivest & Stein
  3. Алгарытмы і структуры дадзеных з выкарыстаннем Python - Брэд Мілер і Дэвід Ранум, Лютэраўскі каледж