Ագահ ալգորիթմ

[Varzor]

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

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

[Varzor]

Միգուցե գծային ծրագրավորման, ոչ թե ուղղակի ծրագրավորման խնդիրները?
Եթե այո, ապա որտեղից ենթադրեցիր որ այս խնդիրը բերվում է գծային ծրագրավորման խնդրի(ու ինչպես)?

Բառեր ենք խաղում ?

Ոնց ինքդ ես տեսնում իմ առաջարկած մոդելի մեջ նպատակային ֆունկցիան գծային է: Իսկ եթե պայմանների մեջ կան ոչ գծային պայմաններ, ապա դրանք հեշտությամբ ձևափոխվում են գծային պայմանների:
Նույնպես ստանդարտ տարբերակներ կան: Քառակուսային ծրագրավորման խնդիրները վերածվում են գծայինի, օրնակ Վոլֆի մեթոդով:
Բայց անկեղծ ասած հեչ հավես ու ժամանակ չունեմ ուսանող ժամանակվաս անցածները քրքրելու, մանավանդ որ հիմա գործնականում այլ կարգի խնդիրների վրա եմ աշխատում:
Այդ ամենը շատ լավ նկարագրված է գրականությունում, ինչպես նաև ուսանողներին բավականին լավ դասախոսություններ են կարդում: համենայն դեպս մեր ամբիոնում շատ լավ էլ նկարագրում ու բացատրում էին:

[soultaker]

Բառեր ենք խաղում ?

Ոնց ինքդ ես տեսնում իմ առաջարկած մոդելի մեջ նպատակային ֆունկցիան գծային է: Իսկ եթե պայմանների մեջ կան ոչ գծային պայմաններ, ապա դրանք հեշտությամբ ձևափոխվում են գծային պայմանների:
Նույնպես ստանդարտ տարբերակներ կան: Քառակուսային ծրագրավորման խնդիրները վերածվում են գծայինի, օրնակ Վոլֆի մեթոդով:
Բայց անկեղծ ասած հեչ հավես ու ժամանակ չունեմ ուսանող ժամանակվաս անցածները քրքրելու, մանավանդ որ հիմա գործնականում այլ կարգի խնդիրների վրա եմ աշխատում:
Այդ ամենը շատ լավ նկարագրված է գրականությունում, ինչպես նաև ուսանողներին բավականին լավ դասախոսություններ են կարդում: համենայն դեպս մեր ամբիոնում շատ լավ էլ նկարագրում ու բացատրում էին:

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

[soultaker]

Հնարավոր է, բայց սխալ է: 3x3-ը տրոհվում է 2x2+ 5x(1x1): Ոնց տեսնում ես պայմանը բավարարվում է
Ու դա ևս մեկ քայլն է դեպի ճիշտ լուծումը: Փաստացի 9 հատ 1 երկարության կողմով քառակուսիները չբավարարեցին պայմանին, հետևաբար չեն կարող հանդիսանալ օպտիմալ լուծում
Ու ասեմ, որ պայմանների քանակը մենակ այդ երկուսը չի, էլի կան

Դու կոնկրետ չէիր նշել որ այդ պայմանները վերաբերվում են միայն օպտիմալ տրոհումներին(9 հատ 1x1 օպտիմալ տրոհում չի, բայց ամեն դեպքում տրոհում է): Եթե միայն դրանց են վերաբերվում, ապա կարող եմ օրինակ բերել 2x8-ը, որտեղ օպտիմալ տարբերակով ստացվում է 4 հատ 2x2: Ըստ քո առաջադրած պայմաններից մեկի` Sum(X(i) *i) <= 2*M և նաև < = 2*N, բայց Sum-ը այս դեպքում կլինի 4 * 2 = 8, որը այդ պայմաններից մեկին չի բավարարում:

[MSGM]

Դինամիկ ծրագրավորումով կարելի ա ավելի օպտիմալ լուծել, քան Էվկլիդեսի ալգորթիմն ա լուծում:
F(M, N) = 1, եթե M = N
հակառակ դեպքում.
F(M, N) = min(min_i{F(i, N) + F(M - i, N)}, i = 1...(M - 1); min_i{F(M, i) + F(M, N - i)}, i = 1...(N - 1))

Բայց բացարձակ օպտիմալ բազմանդամային բարդության լուծում պիտի որ չլինի: Ստեղ էլ պատասխանի մի քանի սահմաններ ա ապացուցած մի քանի դեպքերի համար:

[soultaker]

Դինամիկ ծրագրավորումով կարելի ա ավելի օպտիմալ լուծել, քան Էվկլիդեսի ալգորթիմն ա լուծում:
F(M, N) = 1, եթե M = N
հակառակ դեպքում.
F(M, N) = min(min_i{F(i, N) + F(M - i, N)}, i = 1...(M - 1); min_i{F(M, i) + F(M, N - i)}, i = 1...(N - 1))

Բայց բացարձակ օպտիմալ բազմանդամային բարդության լուծում պիտի որ չլինի: Ստեղ էլ պատասխանի մի քանի սահմաններ ա ապացուցած մի քանի դեպքերի համար:

Հա, էտ հղումը ավելի համոզեց որ բազմանդամային բարդության լուծում չկա:
Դինամիկ ծրագրավորման բանաձևի հետ կապված դու վերցնում ես երկու մասի ես բաժանում ուղղանկյունը, բայց հնարավոր չի արդյոք որ տենց գիծ չլինի օպտիմալի ժամանակ?

[MSGM]

Հա, էտ հղումը ավելի համոզեց որ բազմանդամային բարդության լուծում չկա:
Դինամիկ ծրագրավորման բանաձևի հետ կապված դու վերցնում ես երկու մասի ես բաժանում ուղղանկյունը, բայց հնարավոր չի արդյոք որ տենց գիծ չլինի օպտիմալի ժամանակ?

Իհարկե հնարավոր ա, դրա համար էլ էտ լուծումն էլ բացարձակ օպտիմալ չի, բայց Էվկլիդեսի ալգորիթմից ավելի օպտիմալ ա (վատագույն դեպքում նույն արդյունքը պիտի տա):

[Varzor]

Դու կոնկրետ չէիր նշել որ այդ պայմանները վերաբերվում են միայն օպտիմալ տրոհումներին(9 հատ 1x1 օպտիմալ տրոհում չի, բայց ամեն դեպքում տրոհում է): Եթե միայն դրանց են վերաբերվում, ապա կարող եմ օրինակ բերել 2x8-ը, որտեղ օպտիմալ տարբերակով ստացվում է 4 հատ 2x2: Ըստ քո առաջադրած պայմաններից մեկի` Sum(X(i) *i) <= 2*M և նաև < = 2*N, բայց Sum-ը այս դեպքում կլինի 4 * 2 = 8, որը այդ պայմաններից մեկին չի բավարարում:

Բայց ինչ կարիք կար կոնկրետ նշելու եթե խնդրի դրվածքն էր այդպիսին?` հաշվել հնարավոր մինիմալ քառակուսիների քանակը, որոնց հնարավոր է բաժանել MxN ուղղանկյունը:
Ինչ խնդիր լուծում էինք, դրա համար եմ գրել, հո ուրիշ խնդիր չեմ լուծում?
Ընդամենը քառակուսիների բաժանելու խնդիրը մի բանաձևով լուծվում է ` MxN հատ 1 երկարությամբ կողմով քառակուսիներ

[Varzor]

Հա, էտ հղումը ավելի համոզեց որ բազմանդամային բարդության լուծում չկա:
Դինամիկ ծրագրավորման բանաձևի հետ կապված դու վերցնում ես երկու մասի ես բաժանում ուղղանկյունը, բայց հնարավոր չի արդյոք որ տենց գիծ չլինի օպտիմալի ժամանակ?

Բայց էդ հղումը հստակ ասում է, թե որն է այդ քառակուսիների վերին սահմանը:
Ճիշտ է միարժեք լուծում չկա: Կախված ուղղանկյան չափերից այդ լուծումները կարող են լինել մի քանիսը` բաժանման տեսանկյունից, բայց քանակի տեսանկյունից` միշտ էլ մինիմալ քանակը մեկ թիվ է ստացվում:

[Varzor]

Իհարկե հնարավոր ա, դրա համար էլ էտ լուծումն էլ բացարձակ օպտիմալ չի, բայց Էվկլիդեսի ալգորիթմից ավելի օպտիմալ ա (վատագույն դեպքում նույն արդյունքը պիտի տա):

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

Ստեղ հնչած խնդրի պարագայում ընդամենը պետք է հաշվել այդ քառակուսիների քանակը: Ու քո տված հղումից օգտվելով կարելի է դա կատարել:

[soultaker]

Բայց էդ հղումը հստակ ասում է, թե որն է այդ քառակուսիների վերին սահմանը:
Ճիշտ է միարժեք լուծում չկա: Կախված ուղղանկյան չափերից այդ լուծումները կարող են լինել մի քանիսը` բաժանման տեսանկյունից, բայց քանակի տեսանկյունից` միշտ էլ մինիմալ քանակը մեկ թիվ է ստացվում:

Այս դեպքում քո առաջարկած լուծումը որպես ինչ էիր ներկայացնում? ՈՐՈՇ դեպքերի համար լուծում?

Այդ պարագայում կարելի է կիրառել կոմպլեքս ալգորիթմեր` կողմերի տարբեր հարաբերակցությունների համար:

Հիմա գծային ծրագրավորումով լուծվումա թե չէ?

Համենայն դեպս այդ մինիմալ քանակը միշտ էլ գոյություն ունի, ուղղակի կախված մուտքային տվյալներից կարող են տարբերվել լուծման քայլերն ու ալգորիթմերը:

Եթե լուծում է առաջարկվում, պիտի առաջարկվի կոնկրետ ալգորիթմ, ոչ թե նենց, որ դեպքերի մի մասի վրա ճիշտ աշխատի, մնացած մասի համար էլ ասեն լավ, սրանց համար էլ մի ուրիշ ձևով կանենք, կանցնի կգնա:

[MSGM]

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

Ստեղ հնչած խնդրի պարագայում ընդամենը պետք է հաշվել այդ քառակուսիների քանակը: Ու քո տված հղումից օգտվելով կարելի է դա կատարել:

Խնդիրը հետևյալն ա.
մուտքային տվյալներ - M և N
ելքային թիվ - K, որը քառակուսիների մինիմալ քանակն ա, որով կարելի ա ծածկել M և N կողմերով ուղղանկյունը:
Ցանկացած M-ի և N-ի համար գոյություն ունի միակ ելքային թիվ:
Էս թեմայում նշված ալգորիթմներից ոչ մեկը խնդիրը չի լուծում: Ավելին, իմ ու soultaker-ի կարծիքով էտ խնդիրը էքսպոնենցիալից ավելի լավ բարդություն ունեցող լուծում չունի: Իհարկե կարելի ա էքսպոնենցիալ բարդությամբ լուծումը օպտիմիզացնել տարբեր սահմանների մասին ինֆորմացիայի, Էվկլիդեսի ու դինամիկ ծրագրավորման ալգորիթմերից ստացված ինֆորմացիայի միջոցով, բայց բարդությունը մեկ ա էքսպոնենցիալ ա մնում, ինչը նշանակում ա, որ էտ լուծումը պրակտիկ չի լինի ոչ փոքր մուտքային տվյալների համար (շատ ժամանակատար կլինի): Ուրիշ բան, եթե խնդիրը M-ի և N-ի համար ինչքան հնարավոր է քիչ (բայց ոչ բացարձակ մինիմալ) քառակուսիներով ծածկում գտնելն ա: Էտ դեպքում Էվկլիդեսի ալգորիթմն էլ կարա պետք գա, իմ նշածն ել:

[Varzor]

Խնդիրը հետևյալն ա.
մուտքային տվյալներ - M և N
ելքային թիվ - K, որը քառակուսիների մինիմալ քանակն ա, որով կարելի ա ծածկել M և N կողմերով ուղղանկյունը:
Ցանկացած M-ի և N-ի համար գոյություն ունի միակ ելքային թիվ:
Էս թեմայում նշված ալգորիթմներից ոչ մեկը խնդիրը չի լուծում: Ավելին, իմ ու soultaker-ի կարծիքով էտ խնդիրը էքսպոնենցիալից ավելի լավ բարդություն ունեցող լուծում չունի: Իհարկե կարելի ա էքսպոնենցիալ բարդությամբ լուծումը օպտիմիզացնել տարբեր սահմանների մասին ինֆորմացիայի, Էվկլիդեսի ու դինամիկ ծրագրավորման ալգորիթմերից ստացված ինֆորմացիայի միջոցով, բայց բարդությունը մեկ ա էքսպոնենցիալ ա մնում, ինչը նշանակում ա, որ էտ լուծումը պրակտիկ չի լինի ոչ փոքր մուտքային տվյալների համար (շատ ժամանակատար կլինի): Ուրիշ բան, եթե խնդիրը M-ի և N-ի համար ինչքան հնարավոր է քիչ (բայց ոչ բացարձակ մինիմալ) քառակուսիներով ծածկում գտնելն ա: Էտ դեպքում Էվկլիդեսի ալգորիթմն էլ կարա պետք գա, իմ նշածն ել:

Այ հիմա համամիտ եմ
Չկա այնպիսի "ռապիդ" ալգորիթմ, որը գծային, կամ գոներ պարզագույն քառակուսային բնույթի լինի: Ճշգրիտ լուծոը ստանալու համար, որքան մեծանում է ուղղանկյան չափսերը, այնքան մեծանում է իտերացիաների քանակը:
Ճիշտ է, մեծ կողմերի համար կարելի է մոտարկումների և ապրոքսիմացիաների միջոցով լոգարիթմական տեսը բերել գծայինի, բայց դա իրոք որ բավականին ռեսուրսատար է (համակարգչի համար) ու ժամանակի տեսանկյունից ոչ օպտիմալ:

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

Հ.Գ.
Բայց չեմ հասկանում, թե ինչի համար պիտի այդպիսի "աբստրակտ" խնդիր տային` առանց ուղղանկյան չափերի սահմանափակման

[Վահե-91]

Բայց չեմ հասկանում, թե ինչի համար պիտի այդպիսի "աբստրակտ" խնդիր տային` առանց ուղղանկյան չափերի սահմանափակման

տարօրինակ մարդա sonechka-ն, էսքան խոսում ենք, իրա խնդիրն ենք լուծում կամ քննարկում, մի անգամ չարձագանքեց կարողա էլ պետք չի ՞ ինչի ենք հավայի տանջվում ՞ մի հատ պետքա հարցնել ինքը որերորդ կուրսա, կարողա դասախոսն էլ չգիտի ինչ բարդության խնդիրա տվել
1 կուրսում դասախոսներիցս մեկը կուրսային էր տվել, համարյա վերջացնում էի, պարզվեց տվյալներից մեկի սխալ լինելու պատճառով այլևս հնարավոր չէր շարունակել, նորից սկսեցի ուրիշ տվյալով

[Varzor]

տարօրինակ մարդա sonechka-ն, էսքան խոսում ենք, իրա խնդիրն ենք լուծում կամ քննարկում, մի անգամ չարձագանքեց կարողա էլ պետք չի ՞ ինչի ենք հավայի տանջվում ՞ մի հատ պետքա հարցնել ինքը որերորդ կուրսա, կարողա դասախոսն էլ չգիտի ինչ բարդության խնդիրա տվել
1 կուրսում դասախոսներիցս մեկը կուրսային էր տվել, համարյա վերջացնում էի, պարզվեց տվյալներից մեկի սխալ լինելու պատճառով այլևս հնարավոր չէր շարունակել, նորից սկսեցի ուրիշ տվյալով

Չի բացառվում Պոլիտեխնիկում ամեն ինչ հնարավոր է