Մի տեսարան ՝ բարի կամքի որսից, որտեղ Ուիլը բարդ խնդիր է լուծում MIT- ում

Տարբերությունը ալգորիթմների և հեուրիստական ​​միջև

Եկեք ուսումնասիրենք ալգորիթմի ձևավորման հիմնական կառուցվածքը որոշ հետաքրքիր խնդիրների և դրանց նրբությունների միջոցով

Մոտիվացիա

Ինձ տարիներ տևեցին հասկանալու, որ համակարգչային գիտությունը ոչ թե «Համակարգիչներ» կամ «Ծրագրավորում» է: Մենք ընկնում ենք այս ծուղակի մեջ, քանի որ այդքան շատ ենք ընկնում «համակարգիչ» և «ծրագրավորում» բառերով, որոնք այդքան դյուրին են օգտագործվում այս կարգապահության հետ: Համակարգչային գիտությունը խնդիրների ուսումնասիրությունն է: Խնդիր ունենալով ՝ համակարգչային գիտնականի նպատակը ալգորիթմի մշակումն է, քայլ առ քայլ ցուցումների ցուցակը `խնդրի ցանկացած օրինակ լուծելու համար, որը կարող է առաջանալ: Ալգորիթմները վերջավոր գործընթացներ են, որոնք դրանց հետևելուց հետո կլուծեն խնդիրը: Ալգորիթմները լուծումներ են, իհարկե, քիչ բացառություններով, ինչպես այս աշխարհում ամեն ինչ: Համակարգիչները և Ծրագրավորումը դրան հասնելու գործիք են:

Այն բանից հետո, երբ համոզվեցի, որ «Համակարգչային գիտությունը ալգորիթմների ուսումնասիրությունն է», ես կարող էի արագորեն այն կապել մաթեմատիկայի հետ: Իրականում, նրանք ավելին են, քան երկվորյակ քույրեր: Այժմ այն ​​գեղեցկությունն է, երբ դուք կարող եք հեզորեն շարժվել մի կարգապահությունից մյուսը: Մի խոսքով, սխալ չեմ լինի, եթե ասեմ, որ մաթեմատիկան այն հիմքն է, որի վրա հիմնված է համակարգչային գիտությունը, և ավելին, ալգորիթմները մաթեմատիկան արտահայտելու ևս մեկ միջոց է: Դա բանականության երաժշտությունն է:

Դա խնդրի լուծում է, ինտելեկտուալորեն կլանող և գեղեցիկ, ինչը ինձ համար բավական է մոտիվացիայի համար `սկսելու ալգորիթմների ուսումնասիրությունը: Վստահ եմ, որ ունեք և կունենաք: Թույլ տվեք այս հատվածը վերջացնել երկու մեջբերումով, ինչը լավ հիմք է տալիս մեր ուսումնասիրությանը և, իհարկե, մտքի համար:

Պետք է հավատալ ալգորիթմին: - Դոնալդ Ննութ (մաթեմատիկոս և համակարգչային գիտություն)
Vոն Ֆոն Նեյմանը
Եթե ​​մարդիկ չեն հավատում, որ մաթեմատիկան պարզ է, դա միայն այն պատճառով է, որ նրանք չեն գիտակցում, թե որքան բարդ է կյանքը: - John von Neumann (մաթեմատիկա, ֆիզիկա, վիճակագրություն, տնտեսագիտություն և համակարգչային գիտություն)

Ներածություն

Եկեք սկսենք խնդրից: Տեսակավորում կոչված ալգորիթմական խնդիրը սահմանվում է հետևյալ կերպ.

Խնդրի և խնդրի օրինակն առանձնացնելը հիմնարար է: Այս դեպքում օրինակ կարող է լինել այնպիսի անունների շարքը, ինչպիսիք են `Սուվրո, Բավնա, Janeեյն, Մայք, Ռամ, Ռիչա} կամ թվերի ցուցակ, ինչպիսիք են 7, 12, 11, 101, 101, 45 {: Բայց «տեսակավորելու» ալգորիթմը ընդհանուր խնդիր է, ուստի անհրաժեշտ է ընդհանուր լուծում, որը կարող է վերցնել ցանկացած մուտքագրման հնարավոր դեպքեր և կստանա ձեզ ցանկալի արդյունքը: Տեսակավորման խնդիրը լուծելու համար կան տարբեր ալգորիթմներ, որոնցից մեկը կոչվում է «Տեղադրման տեսակ»:

Տեղադրման տրամաբանական հոսքի անիմացիա հատուկ դեպքի վրա

Տեղադրման տեսակավորումը տեսակավորման տեսակ է, որը սկսվում է մեկ տարրից (այդպիսով ձևավորելով աննշանորեն դասավորված ցուցակ) և այնուհետև աստիճանաբար տեղադրում մնացած տարրերը, որպեսզի ցուցակը մնա դասավորված: Նայեք ձախ կողմում ներկայացուցչությանը:

Ներդրման տեսակավորման Python- ի իրականացումը հետևյալն է.

Տեղադրումը Տեսակավորել ներքին գործընթացը

Մենք միշտ որոնում ենք ալգորիթմներ, որոնք ճիշտ են, արդյունավետ և հեշտ է իրականացնել: Այս ներածական գլխում մենք կանդրադառնանք միայն ալգորիթմների ճշգրտության խնդրին:

Alիշտ ալգորիթմները սովորաբար գալիս են կոռեկտության ապացույցով, այսինքն ՝ այն պետք է տանի խնդրի յուրաքանչյուր օրինակ դեպի ցանկալի արդյունքի, որը նման է վերը նշված օրինակում: Բայց նախքան անցնելը, եկեք ցույց տանք, թե ինչու է «ակնհայտ» երբեք չի բավարարում կոռեկտության ապացույց և սովորաբար սխալ է:

Իմ ալգորիթմն ակնհայտ է կամ ճիշտ:

Եկեք քննարկենք մի խնդիր, որը հաճախ ծագում է արտադրության, փոխադրման և փորձարկման ծրագրերի մեջ: Ասեք, դուք ունեք մի ռոբոտ, որը ունակ է զոդել: Այժմ դուք ուզում եք, որ միացնեք մի շրջանային տախտակ, որը բաղկացած է չիպսերից և այլ բաղադրիչներից, որոնք անհրաժեշտ է ամրացնել տախտակին: Այսպիսով, ակնհայտ հարցն այն է, թե ինչպես է ռոբոտը պատրաստվում շրջել տախտակով և կատարել առաջադրանքը: Դա պետք է անի արդյունավետորեն, քանի որ տվյալ տախտակում արտադրվելու են շատ տախտակներ, և յուրաքանչյուր տախտակ ունի այդպիսի միացման շատ կետեր:

Խնդրի պաշտոնական ձևակերպումը նման բան է լինելու, և մենք պետք է ծրագրավորենք ռոբոտի թևը:

Խնդիր. Ռոբոտների տուր օպտիմիզացում

Մուտքագրում. Ինքնաթիռում մի շարք S- ի կետեր

Արդյունք. Ո՞րն է ամենակարճ ցիկլի շրջագայությունը, որն այցելում է S խմբի յուրաքանչյուր կետ:

Նկար-1. Մոտակա հարևան բյուրո

Թերևս ամենակարևոր գաղափարը կլիներ ամենամոտ հարևան բյուրոյի կողմից: Սկսելով մի պատահական կետ p0, մենք քայլում ենք դեպի նրա առաջին ամենամոտ հարևանը p1: P1- ից մենք քայլում ենք դեպի նրա ամենամոտ անխնամ հարևանը (այսպիսով բացառվում է p0- ին որպես թեկնածու): Մենք անընդհատ կրկնում ենք այն, մինչև բոլոր կետերը մեկ անգամ այցելեն, հետո մենք վերադառնանք մեր նախնական կետ p0 ՝ շրջագայությունն ավարտելու համար:

Այսպիսով, այստեղ հիմնական գաղափարն է հեռավոր կետեր այցելելուց առաջ այցելել մոտակա կետեր ՝ ճանապարհորդության ընդհանուր ժամանակը կրճատելու համար: Այն հիանալի աշխատում է վերը տրված նկար 1-ի վրա, ինչպես նաև ոչ այնքան, բայց ողջամտորեն արդյունավետ, այն նայում է յուրաքանչյուր զույգ կետի (pi, pj) երկու անգամ, մեկ անգամ, երբ ավելացնում է pi և այլ, երբ հավելում է շրջագայությանը: Կներեք, որ ասում եմ, որ այս ալգորիթմը լրիվ սխալ է:

Ալգորիթմը, իհարկե, շրջայց է գտնում, բայց անպայման չէ, որ գտնի հնարավորինս կարճ ժամանակահատվածը: Դիտարկենք այն դեպքը, երբ բոլոր կետերը գտնվում են մի տողի երկայնքով, տե՛ս նկար 2-ը: Հետո եթե մենք սկսենք 0-ից, ապա մենք շարունակում ենք hopscotching ձախ-ձախ-ձախ ... տախտակի ողջ երկայնքով, մինչդեռ օպտիմալ շրջագայությունը կարող էր սկսվել ձախից և այցելել յուրաքանչյուր կետ, երբ մենք քայլում ենք աջ և վերջապես վերադառնում ենք առաջին կետին:

Նկար 2 – ը. «Մոտակա հարևան» հեթանոսական

Կարող է լինել այն, ինչ մեզ պետք է, այլ մոտեցում է: Միշտ քայլելը դեպի ամենամոտ կետը չափազանց սահմանափակիչ է: Այսպիսով, դուք չեք կարող ասել պարզապես նայելով դրանց, թե արդյոք ալգորիթմները ճիշտ են կամ սխալ:

Այս պահին գուցե մտածեք, թե որն է ճիշտ ալգորիթմը `այս խնդիրը լուծելու համար: Դե, մի պատասխան կարող է լինել, անշուշտ, ճիշտ, որը պետք է թվարկել բոլոր կետերի բոլոր հնարավոր պատվերը, ապա ընտրեք այն դասավորությունը, որը նվազագույնի է հասցնում ընդհանուր երկարությունը: Այսպիսով, մեզ երաշխավորված է, որ ավարտենք հնարավորինս կարճ շրջագայությունը:

Հիմա եկեք գնահատենք այս հնարավորությունը ևս: Ասենք ՝ ընդհանուր 20 միավոր կա: Այսպիսով, 20 հնարավոր միավորով թվարկելու բոլոր հնարավոր ուղիները մենք կունենանք 20: (20 ֆակտորիալ), որը 10 բալ ուժգնությունից 18 տարբեր պատվեր է: Այժմ դա մեծ թիվ է համակարգչի համար գնահատելու և ասելու համար, եթե n = 1000, ինչը միանգամայն հնարավոր է, ապա հնարավոր է, որ մենք ստիպված լինենք սպասել ևս մեկ մեծ պայթյունի, եթե համակարգիչը կարողանա գնահատել բոլոր հնարավորությունները և պարզել, թե որ ճանապարհն է ամենակարճը: .

Այս խնդիրը ավելի շատ հայտնի է որպես lingանապարհորդ վաճառողների խնդիր (TSP), և մենք անպայման ջանքեր կգործադրենք գտնել արդյունավետ ալգորիթմ ՝ այս խնդիրը լուծելու համար, բայց ներկայումս այս քննարկումից հիմնական խլումն այն է, որ կա ալգորիթմների և հեուրիստիկա: Ալգորիթմները միշտ բերում են ճիշտ արդյունքի, բայց ունիվերսալը կարող է մեծ աշխատանք կատարել, բայց երբեք լիարժեք լուծում չի երաշխավորում:

Ալգորիթմի ճշգրտության վերաբերյալ ավելի շատ նրբություններ

Եկեք նայենք մեկ այլ խնդրի ՝ ալգորիթմի ճշգրտության կետում մեր միտքը ընդլայնելու համար: Սա ժամանակացույցի խնդիր է: Ասացեք, դուք դերասան / դերասանուհի եք փնտրում և մուտք եք գործել կինոնախագծերի ցուցակ: Առաջարկները գալիս են ծրագրի մեկնարկի և ավարտի ամսաթվով: Այժմ աշխատանքը ստանձնելու համար չես կարող միաժամանակ ընդունել երկու նախագիծ, որոնց ընդմիջումները համընկնվում են:

Ձեր նման արվեստագետի համար նպատակը շատ պարզ է, այսինքն ՝ այս նախագծերից որքան հնարավոր է մեծ գումար վաստակել: Յուրաքանչյուր նախագիծ վճարում է նույն վճարը, ինչը նշանակում է, որ դուք փնտրում եք նախագծերի ամենամեծ հնարավոր փաթեթը, որոնց ժամանակային ընդմիջումները չեն համընկնում: Եկեք դիտարկենք այս պլանավորման խնդրի պատկերային պատկերումը:

Նկարագրություն - 3. Պլանավորման խնդիր

Հիմա, ինչպես նախկինում, պաշտոնապես պետք է սահմանենք խնդրի մասին հայտարարություն-

Խնդիր ՝ կինոնկարի պլանավորման խնդիր

Մուտքագրում. I- ի n ընդմիջումների շարքը գծի վրա:

Արդյունք. Ո՞րն է փոխադարձաբար չհամընկնող ընդմիջումների ամենամեծ ենթաբազմությունը, որը կարող է ընտրվել I- ից:

Վստահ եմ, որ այս ալգորիթմը նախագծելու համար շատ գաղափարներ կլինեն: Կարելի է սկսել աշխատել, երբ առաջին աշխատանքն առկա է, այսինքն, դուք պետք է սկսեք գործն սկսելու ամենավաղ սկզբից, այն բանից հետո, երբ դուք չեք ցանկանում պարապ նստել:

Ամենավաղ սկիզբը Աշխատանքի ընտրության ալգորիթմ

Հիմա ինչու սա հիանալի գաղափար չէ առաջ գնալու համար: Մտածեք առաջին գործի մասին, որը տևում է շատ երկար ժամանակահատված և իր հերթին սպանում է բոլոր այն հեռանկարները, որոնք ունեն ավելի կարճ տևողություններ: Այս սցենարը պատկերված է ստորև

Վատ գաղափար `ամենավաղ մեկնարկի ամսաթվով աշխատանքի ընտրության ալգորիթմի հետ

Այսպիսով, բնական մտքի առաջընթացը կլիներ ամենակարճ աշխատանքը ընտրելը և ամեն շրջանի ամենակարճ աշխատանքը փնտրելը: Այս թիվը առավելագույնի հասցնելը առավելագույն օգուտ կբերի: Եկեք ձևակերպենք այս ժառանգականությունը

Աշխատանքի ընտրության ամենակարճը

Այժմ այս մոտեցումը լավ է թվում, բայց ամենակարճ աշխատանքն ունենալը կարող է մեզ սահմանափակել մարումների վճարման կեսը: Եկեք դիտենք ստորև նկարազարդումը այս գործի վերաբերյալ:

Սահմանափակեք վճարումը `ընտրելով ամենակարճ աշխատանքը

Այնպես որ, եկեք փնտրենք ալգորիթմ, որը ինչպես ճիշտ է, այնպես էլ արդյունավետ -

Movieիշտ և արդյունավետ ալգորիթմ `կինոնկարի պլանավորման խնդրի համար

Այսպիսով, մեր դեպքում դիմեք «Կախվածություն -3» -ին ՝ տեսնելու, թե ինչպես են գծավորվում նախագծերը: Ստորև նկարազարդումը ցույց է տալիս, թե ինչպես է նկարիչն ընդունում կինոնկարները

Լուծում մեր կինոնկարների պլանավորման խնդրին

Մի՛ վերցրու

  1. Ալգորիթմների միջև գոյություն ունի հիմնարար տարբերություն, որը միշտ տալիս է ճիշտ արդյունք և ուրոլոգիստիկա, որը սովորաբար կարող է լավ աշխատանք կատարել, բայց առանց որևէ երաշխիք տրամադրելու:
  2. Ալգորիթմի ճշգրտությունը մի հատկություն է, որը պետք է ուշադիր ցուցադրվի:

Հեղինակային գրառում

Սա շարքի առաջին հոդվածն է ՝ «Ալգորիթմներ և տվյալների կառուցվածքներ»: Հաջորդ հոդվածում մենք կկառուցենք մաթեմատիկական շրջանակ, որը ցույց կտա ալգորիթմների ճիշտությունը: Մնացեք մեզ հետ …

Ուրախ սովորում :)

Աղբյուրները

  1. Ալգորիթմի դիզայնի ձեռնարկ - Սթիվեն Ս. Սիենա, համակարգչային գիտությունների ամբիոն, SUNY Stony Brook, ԱՄՆ:
  2. Ներածություն ալգորիթմների վերաբերյալ `Կորմեն, Լեյսերսոն, Ռիվես և Սթայն
  3. Ալգորիթմներ և տվյալների կառուցվածքներ `օգտագործելով Python - Brad Miller և David Ranum, Luther քոլեջ