Algoritmo problema

Laba,

Niekaip nepavyksta sugalvoti algoritmo. Ne viena diena apie ji skaitinejau ir bandziau kazkaip persilauzti, bet niekaip nepavyko, todel kreipiuos pagalbos cia. Tuo paciu, manau, kad tai bus daliai is jusu idomu. :)

Esme: Turiu N neneigiamu skaiciu. Man juos reikia padalinti i dvi dalis, kad tos dalys sumos atzvilgiu butu kiek begalima lygesnes. Nariu skaicius neprivalo buti lygus.

Pavyzdziui:

Skaiciai = 1,2,3

1Dalis = 1,2

2Dalis = 3

Taigi, pasirasiau algoritma, kuris veike ganetinai paprastu principu:

1. Rikiuodavo seka Mazejimo tvarka
   
2. Sukuriu dvi sekas ir jiems po viena numeri pridedu (2 didziausi)
   
3. Ziuriu, kuri seka mazesne sumos atzvilgiu ir i ta pridedu sekanti nari
   

Su pavyzdine seka butu taip:

skaiciai = (3,2,1)
seka1 = 3
seka2 = 2

while ciklas nesibaige
   do if suma(seka1) > suma(seka2) seka2=2,1
         else seka1 = 3,1

Visgi sis algoritmas, grazina teisingus atsakymus ne visada.

Seka = 5, 5, 4, 3, 3

seka1 = 5,4

seka2 = 5,3,3

kuomet turetu grazinti:

5,5

4,3,3

Taigi narsiau internete ir susiradau, kad tai visai nemenka uzduotis, ir kad ja isspresti nebus taip paprasta

http://en.wikipedia.org/wiki/Partition_problem

Ieskojau internete sprendimu, juk kazko griebtis reikia ir radau stai toki atsakyma:

http://stackoverflow.com/questions/7938809/dynamic-programming-linear-partitioning-please-help-grok

Atsakyme radau koda, pythono kalba, taciau sugebejau tik isistatyti parametrus - jis veikia, taciau visiskai nesuprantu kaip. Skaiciau daug medziagos apie sia "problema", taciau kazkaip viskas kiaurai pro akis eina, ir nieko nesuprantu (galbut del sudetingu terminu).

from operator import itemgetter

def linear_partition(seq, k):
   if k <= 0:
       return []
   n = len(seq) - 1
   if k > n:
       return map(lambda x: [x], seq)
   table, solution = linear_partition_table(seq, k)
   k, ans = k-2, []
   while k >= 0:
       ans = [[seq[i] for i in xrange(solution[n-1][k]+1, n+1)]] + ans
       n, k = solution[n-1][k], k-1
   return [[seq[i] for i in xrange(0, n+1)]] + ans

def linear_partition_table(seq, k):
   n = len(seq)
   table = [[0] * k for x in xrange(n)]
   solution = [[0] * (k-1) for x in xrange(n-1)]
   for i in xrange(n):
       table[i][0] = seq[i] + (table[i-1][0] if i else 0)
   for j in xrange(k):
       table[0][j] = seq[0]
   for i in xrange(1, n):
       for j in xrange(1, k):
           table[i][j], solution[i-1][j-1] = min(
               ((max(table[x][j-1], table[i][0]-table[x][0]), x) for x in xrange(i)),
               key=itemgetter(0))
   return (table, solution)

Taigi butu gerai gauti betkokios pagalbos t.y algoritmo paaiskinimu, pasiulymu, pseudo kodu, nuoroda ar dar kuonors.

Na, iš bėdos, galima būtų bruteforce'inti visą reikalą jei N nėra per didelis kiekis.

Pradedi nuo 1 nario vienoje pusėje ir N-1 kitoje, randi skirtumą. Ir taip +1 narį vis pridedi ir žiūri koks skirtumas, lygini su praėjusiomis eilutėmis.

Visas galimybes praėjęs žinai indeksą, ties kuriuo geriausia kirsti masyvą.

Na, iš bėdos, galima būtų bruteforce'inti visą reikalą jei N nėra per didelis kiekis.

Pradedi nuo 1 nario vienoje pusėje ir N-1 kitoje, randi skirtumą. Ir taip +1 narį vis pridedi ir žiūri koks skirtumas, lygini su praėjusiomis eilutėmis.

Visas galimybes praėjęs žinai indeksą, ties kuriuo geriausia kirsti masyvą.

Klausimas kiek tai optimalu ir ar tai tikrai veikia, nes daznai vien kirsti masyvo neuztenka. Reikia rikiuoti. Pavyzdiuzi, masyve is 1000 elementu pirmas bus 1000, paskutinis-1 visu kitu suma 1001, taigi pagal ideja reiktu pirma su paskutiniu vienam masyve laikyt, visus kitus - kitam. Resursu visas visu variantu perrinkimas kainuotu nezmoniskai ;)

Na, bruteforce'inimas niekada nebus optimaliausias sprendimas programos veikimo atžvilgiu. Bet dažnai tai būna optimaliausias sprendimas sprendžiant problemą.

Be abejonės, vykdymo greičiai gali labai skirtingi būti, bet kartais priimtini.

Nesu tikras kaip tamsta gali atlikti rikiavimą jei yra reikalingas originalaus masyvo dalinimas. Nebent visai ne taip supratau uždavinį.

Svarstant labai abstrakčiai, ir bruteforce'inimo būdą galima optimizuoti. Vienas iš būdų būtų, tarkim... Skaičiaus, kuris yra toli nuo standartinio nuokrypio ir imtis atitinkamų veiksmų (gauti indeks'ą, dalinti tik tam tikromis dalimis, o ne visas).

Dėl resursų suvartojimo - apie kokius resursus mes šnekame? Apie kokio dydžio masyvus?

Greitai susukau dalinimo algoritmą. Kiekvienas sukasi 100 kartų su pseudorandom skaičiais:

Masyvo dydis | Masyvo elementų sklaida | Masyvo dalinimo vidutinė trukmė
50 | 0-500 | 53 us (praktiškai niekinis rezultatas nes per mažai veiksmų)
500 | - | 200 us
500 | 0-10000 | 205 us (skirtumo tarp praeito nėra, nes sudėjimo operacijos vis tiek vykdomos aproksimatliai tokiu pačiu greičiu, o iteracijų skaičius toks pat)
1000 | - | 455 us
2000 | - | 1440 us
3000 | - | 3355 us
4000 | - | 5850 us

Ir porą apskritai bepročių su skaičiais nuo 0 iki 10000:

20000 - 130284 us (vidurkis iš 100 bandymų)
50000 - 798429 us (vidurkis iš 20 bandymų)
100000 - 3194658 us (vidurkis iš 5 bandymų)  

EDIT: Reikia nepamiršti, kad bruteforce'inimui visai nesvarbu kaip elementai bus sudėti, kokie jų dydžiai (na, proto ribose, be abejo). Jis vis tiek kodą vykdys worst case atveju ir vykdymo greitis bus beveik toks pat visada. Viskas priklauso tik nuo elementų kiekio.

Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "The Easiest Hard Problem".

 

http://en.wikipedia.org/wiki/Partition_problem

NP-pilnas uždavinys, nieko geriau už perrinkimą nėra žinoma. Nors mažiems duomenims kažkoks dinaminis algoritmas ten yra paminėtas, bet čia jau reikia duomenų apribojimų.

Tai taip gaunasi, kad turiu visus imanomus variantus perrinkt? Kaip mazdaug tai turetu atrodyti? Darytis kazkokia lentele masyvu?

Susiskaičiuoji visą sumą ir ją padalini iš 2 – tai bus programos tikslas. Taip pat susirikiuok duomenis didėjimo tvarka.

Tada turbūt paprasčiausia daryti paiešką gilyn, pasinaudojant rekursija. Tikiuosi žinai paiešką gilyn (jei ne, truputis pasiskaityti). Pradedi nuo pirmo elemento, jį prisumuoji prie dalinės sumos, eini prie antro elemento, vėl prisumuoji. Kai dalinė suma tampa didesnė už tikslą (pusę visos sumos), išsisaugai gautą rezultatą.

Toliau algoritmą tęsi taip pat, tik kad prieš tai grįžti prie kokio nors ankstesnio nario ir šįkart jo neprisumuoji, ir vėl lendi gilyn. Jei šįkart, kai peržengi tikslą, gauta suma yra arčiau nei prieš tai rasta, tai tą naujają ir išsisaugai.

Jei nelabai aišku, sakyk, pateiksiu algoritmo veikimo pavyzdžių.

Susiskaičiuoji visą sumą ir ją padalini iš 2 – tai bus programos tikslas. Taip pat susirikiuok duomenis didėjimo tvarka.

 

Tada turbūt paprasčiausia daryti paiešką gilyn, pasinaudojant rekursija. Tikiuosi žinai paiešką gilyn (jei ne, truputis pasiskaityti). Pradedi nuo pirmo elemento, jį prisumuoji prie dalinės sumos, eini prie antro elemento, vėl prisumuoji. Kai dalinė suma tampa didesnė už tikslą (pusę visos sumos), išsisaugai gautą rezultatą.

 

Toliau algoritmą tęsi taip pat, tik kad prieš tai grįžti prie kokio nors ankstesnio nario ir šįkart jo neprisumuoji, ir vėl lendi gilyn. Jei šįkart, kai peržengi tikslą, gauta suma yra arčiau nei prieš tai rasta, tai tą naujają ir išsisaugai.

 

Jei nelabai aišku, sakyk, pateiksiu algoritmo veikimo pavyzdžių.

Principas aiskus, bandysiu igyvendint. Dekui

Pradžiai užmiršk viską, ką čia perskaitei su "geriau už perrinkimą nerasi". :)

Na, o dabar galim pradėti. Tavo uždavinys yra vienas iš standartinių dinaminio programavimo problemų. Čia gali rasti paaiškinimą (vadinasi "balanced partition").

Trumpai apie dinaminį programavimą (DP)

Pirmiausia DP nėra koks tai mandrus algoritmas, tai grynai matematikos sritis (priklauso diskrečiąjai optimizacijai) ir su tokiu programavimu, kurį visi (išskyrus matematikus) turi galvoje, turi tik tai bendro, jog dažnai taikomas įvairiose situacijose.

DP veikimą gali interpretuot įvairiai - pasirink kaip tau pačiam paprasčiau pavyksta įsivaizduoti. Keletas pavyzdžių:

• Šokinėjimas per būsenas
  
• Kelių dimensijų lentelės pildymas
  
• Rekursijos medis, skaičiuojamas nuo priešingos pusės
  
• Perrinkimas su netinkamų (nelogiškų) variantų išmetimu vykdymo metu
  

Tačiau, kad ir kokią interpretaciją pasiimtum, rezultatas tas pats - jis tiesiog didelę problemą skaido į mažesnes tokias pat problemas ir pagal tų mažesnių problemų rezultatą paskaičiuoja savo reikšmę.

Dažniausiai DP problema sprendžiama tokiu eiliškumu:

1. Sudarant vieną (arba kelias) rekurentinę formulę (ją paprastai gali apsirašyti daugiamačiu masyvu).
   
2. Apsibrėžiant pradines ir kraštines sąlygas
   
3. Skaičiuojant pagrindinį uždavinį, aprašytą ta pačia rekurentine formule.
   
4. Išskiriant problemos sprendinį iš praeitame etape užpildytos lentelės (daugiamačio masyvo, pildomo pagal rek. formulę)
   

Kartais (priklauso nuo problemos) gali išsirinkti daugiau sprendinių (keisdamas įeinamus problemos duomenis) neperskaičiuodamas pagrindinio uždavinio etapo. Čia aprašiau gan siaurą problemų tipą, pasitaiko ir kurkas sudėtingesnių atvejų.

Grįžkim prie tavo problemos.

Ją galime perfrazuoti:

Reikia rasti 2 krūvas, kurias įvardinsime jų narių sumomis - pavadinkim krūva (k) ir krūva (s-k), čia s - visų aibės narių suma. Tuomet mums reikia nustatyti sumą k taip, jog:

• Ji būtų išreiškiama duotos multi-aibės nariais (čia bus reikalingas DP)
  
• Skirtumas abs( (s-k) - (k) ) būtų minimalus
  

Sprendimas.

Pažymėkim duotą multi-aibę raide d ir jos narių skaičių raide n.

Absibrėškime rek. formulę f_x(y) = max{ f_x-1(y), f_x-1(y-d(x)) }

Čia x - koordinatės kintamasis multi-aibėje, o y - būsenos kintamasis.

Jos veikimą gali interpretuoti, kaip "imti-neimti". Nors tokia interpretacija ne visai teisinga, tačiau padės įsivaizduoti veikimą susiejant su paprastesne problema (knapsack).

Toliau mums reikės pradinės salygos - visiems x, priklausantiems [0,n-1], nustatome f_x(0) = 1

Rezultatu galime laikyti f_n-1(k) reikšmes, kurios nurodys ar krūvą (k) galime išreikšti multi-aibės d elementais.

Galiausiai, mums beliko rasti tokį k, kuris tenkina sąlygą f_n-1(k) ir su kuriuo krūvų skirtumas yra minimalus.

Programos kodas

Programoje specialiai pasirinkau ekvivalentų rekurentinės funkcijos bool vaizdavimą, vietoje {1,0}. Gal taip paprasčiau bus suvokti.

#include <stdio.h>

using namespace std;

int main()
{
int sum, min_diff, min_k,
    d[] = { 5, 9, 8, 3 },
    n = 4;

//aibes nariu suma
sum = 0;
for(int i = 0; i < n; i++)
{
	sum += d[i];
}

//apsibreziame ir nuresetiname lentele
bool **f = new bool*[n];
for(int i = 0; i < n; i++)
{
	f[i] = new bool[sum+1];
	for(int j = 0; j <= sum; j++)
	{
		f[i][j] = false;
	}
}

//pradine salyga
for(int x = 0; x < n; x++)
{
	f[x][0] = true;
}

//pagrindinis skaiciavimas
for(int x = 1; x < n; x++)
{
	for(int y = 1; y <= sum; y++)
	{
		f[x][y] = ( f[x-1][y] || (y-d[x] >= 0 && f[x-1][y-d[x]]) );
	}
}

//ieskome maziausio skirtumo tarp kruvos (k) ir kruvos (s-k), kuris tenkina salyga f[n-1][k]
min_diff = sum;
min_k = 0;
for(int k = 1; k <= sum/2; k++)
{
	if(f[n-1][k] && min_diff > sum - 2*k)
	{
		min_diff = sum - 2*k;
		min_k = k;
	}
}

printf("%d %d\n", min_k, sum - min_k);

return 0;
}

Dabar krūvų sumos yra žinomos, beliko tik rasti būtent kurie nariai jas gali sudaryti. Čia turėtum be vargo susitvarkyti. :)

Pradžiai užmiršk viską, ką čia perskaitei su "geriau už perrinkimą nerasi". :)

 

Na, o dabar galim pradėti. Tavo uždavinys yra vienas iš standartinių dinaminio programavimo problemų. Čia gali rasti paaiškinimą (vadinasi "balanced partition").

 

Trumpai apie dinaminį programavimą (DP)

 

Pirmiausia DP nėra koks tai mandrus algoritmas, tai grynai matematikos sritis (priklauso diskrečiąjai optimizacijai) ir su tokiu programavimu, kurį visi (išskyrus matematikus) turi galvoje, turi tik tai bendro, jog dažnai taikomas įvairiose situacijose.

 

DP veikimą gali interpretuot įvairiai - pasirink kaip tau pačiam paprasčiau pavyksta įsivaizduoti. Keletas pavyzdžių:

• Šokinėjimas per būsenas
  
• Kelių dimensijų lentelės pildymas
  
• Rekursijos medis, skaičiuojamas nuo priešingos pusės
  
• Perrinkimas su netinkamų (nelogiškų) variantų išmetimu vykdymo metu
  

Tačiau, kad ir kokią interpretaciją pasiimtum, rezultatas tas pats - jis tiesiog didelę problemą skaido į mažesnes tokias pat problemas ir pagal tų mažesnių problemų rezultatą paskaičiuoja savo reikšmę.

 

Dažniausiai DP problema sprendžiama tokiu eiliškumu:

1. Sudarant vieną (arba kelias) rekurentinę formulę (ją paprastai gali apsirašyti daugiamačiu masyvu).
   
2. Apsibrėžiant pradines ir kraštines sąlygas
   
3. Skaičiuojant pagrindinį uždavinį, aprašytą ta pačia rekurentine formule.
   
4. Išskiriant problemos sprendinį iš praeitame etape užpildytos lentelės (daugiamačio masyvo, pildomo pagal rek. formulę)
   

Kartais (priklauso nuo problemos) gali išsirinkti daugiau sprendinių (keisdamas įeinamus problemos duomenis) neperskaičiuodamas pagrindinio uždavinio etapo. Čia aprašiau gan siaurą problemų tipą, pasitaiko ir kurkas sudėtingesnių atvejų.

 

Grįžkim prie tavo problemos.

 

Ją galime perfrazuoti:

 

 

Sprendimas.

 

Pažymėkim duotą multi-aibę raide d ir jos narių skaičių raide n.

 

Absibrėškime rek. formulę f_x(y) = max{ f_x-1(y), f_x-1(y-d(x)) }

Čia x - koordinatės kintamasis multi-aibėje, o y - būsenos kintamasis.

 

Jos veikimą gali interpretuoti, kaip "imti-neimti". Nors tokia interpretacija ne visai teisinga, tačiau padės įsivaizduoti veikimą susiejant su paprastesne problema (knapsack).

 

Toliau mums reikės pradinės salygos - visiems x, priklausantiems [0,n-1], nustatome f_x(0) = 1

 

Rezultatu galime laikyti f_n-1(k) reikšmes, kurios nurodys ar krūvą (k) galime išreikšti multi-aibės d elementais.

 

Galiausiai, mums beliko rasti tokį k, kuris tenkina sąlygą f_n-1(k) ir su kuriuo krūvų skirtumas yra minimalus.

 

Programos kodas

 

Programoje specialiai pasirinkau ekvivalentų rekurentinės funkcijos bool vaizdavimą, vietoje {1,0}. Gal taip paprasčiau bus suvokti.

 

#include <stdio.h>

using namespace std;

int main()
{
int sum, min_diff, min_k,
    d[] = { 5, 9, 8, 3 },
    n = 4;

//aibes nariu suma
sum = 0;
for(int i = 0; i < n; i++)
{
	sum += d[i];
}

//apsibreziame ir nuresetiname lentele
bool **f = new bool*[n];
for(int i = 0; i < n; i++)
{
	f[i] = new bool[sum+1];
	for(int j = 0; j <= sum; j++)
	{
		f[i][j] = false;
	}
}

//pradine salyga
for(int x = 0; x < n; x++)
{
	f[x][0] = true;
}

//pagrindinis skaiciavimas
for(int x = 1; x < n; x++)
{
	for(int y = 1; y <= sum; y++)
	{
		f[x][y] = ( f[x-1][y] || (y-d[x] >= 0 && f[x-1][y-d[x]]) );
	}
}

//ieskome maziausio skirtumo tarp kruvos (k) ir kruvos (s-k), kuris tenkina salyga f[n-1][k]
min_diff = sum;
min_k = 0;
for(int k = 1; k <= sum/2; k++)
{
	if(f[n-1][k] && min_diff > sum - 2*k)
	{
		min_diff = sum - 2*k;
		min_k = k;
	}
}

printf("%d %d\n", min_k, sum - min_k);

return 0;
}

 

Dabar krūvų sumos yra žinomos, beliko tik rasti būtent kurie nariai jas gali sudaryti. Čia turėtum be vargo susitvarkyti. :)

Labai tau ačiū, bandysiu aiškintis. Neštis žadu du programos variantus - vienas minėtas tavo, kitas su perrinkimu, kadangi skyrius iš kurio atsiskaitom ir vadinasi PERRINIKMAS :)

Mano kodas Haskell kalba. Gražina List'ą padalintą į dvi dalis su -1. Nes dar nežinau kaip padaryt, kad gražintų 2 list'us. :D

{- UZDARBIS.LT UZDUOTYS -}

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort (filter (< p) xs)) ++ [p] ++ (quicksort (filter (>= p) xs))

halfSum :: Int -> Int
halfSum n = n `div` 2

uzdProcess :: [int] -> [int] -> [int]
uzdProcess [] ys = []
uzdProcess (x:xs) ys = if halfSum (sum ys) < sum xs
               then x : (uzdProcess xs ys)
               else x : (-1) : xs

uzd :: [int] -> [int]
uzd xs = uzdProcess (quicksort xs) xs

Visi varintai, kurius radau veikia.

P.S. Beveik visi :D

Mano kodas Haskell kalba. Gražina List'ą padalintą į dvi dalis su -1. Nes dar nežinau kaip padaryt, kad gražintų 2 list'us. :D

 

{- UZDARBIS.LT UZDUOTYS -}

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort (filter (< p) xs)) ++ [p] ++ (quicksort (filter (>= p) xs))

halfSum :: Int -> Int
halfSum n = n `div` 2

uzdProcess :: [int] -> [int] -> [int]
uzdProcess [] ys = []
uzdProcess (x:xs) ys = if halfSum (sum ys) < sum xs
               then x : (uzdProcess xs ys)
               else x : (-1) : xs

uzd :: [int] -> [int]
uzd xs = uzdProcess (quicksort xs) xs

 

Visi varintai, kurius radau veikia.

Sunkiai suprantama kalba :)

[...]

Pamiršai paminėti, kad šis algortimas tinka, kai skaičiai maži ir jų ne itin daug, nes atminties sanaudos n*S baitų (čia n – elementų skaičius, S – jų suma). Kitu atveju atminties sąnaudos išauga nežmoniškai. Pavyzdžiui, turint vien tik {2147483647} (maksimalus skaičius, telpantis į signed int) programa surytų beveik 2GB! atminties. Žinoma, taip nebus, nes tiek atminties kompiuteris nesugebės alokuoti ir programa nebaigs vykdymo.

Kaip buvo minėta, problema NP-pilna. Dinaminis algoritmas tinkamas tik uždavinio sąlygai su atitinkamais apribojimais.

Pamiršai paminėti, kad šis algortimas tinka, kai skaičiai maži ir jų ne itin daug, nes atminties sanaudos n*S baitų (čia n – elementų skaičius, S – jų suma). Kitu atveju atminties sąnaudos išauga nežmoniškai. Pavyzdžiui, turint vien tik {2147483647} (maksimalus skaičius, telpantis į signed int) programa surytų beveik 2GB! atminties. Žinoma, taip nebus, nes tiek atminties kompiuteris nesugebės alokuoti ir programa nebaigs vykdymo.

 

Kaip buvo minėta, problema NP-pilna. Dinaminis algoritmas tinkamas tik uždavinio sąlygai su atitinkamais apribojimais.

Taip, to nepaminėjau. :) Greitis atminties sąskaita. Na bent kol suma labai neišaugs programa tvarkysis gerai. Beje, lentelę palikau dvimatę tik vardan aiškumo, tai dimensijos, susijusios su elementų skaičiumi, galime nepaisyti ir tuomet gauname S baitų.