Problemi s funkcijo "Merge"

[VidicL13]

Pri iskanju optimalne rešitve problema, se mi je zataknilo pri algoritmu. V pseudo-kodi je navedeno, da moram izvesti Merge na nizu delnih rešitev, vendar si ne znam predstavljati kako naj to zgleda.

Originalna koda se nahaja v MCMKP.rmd vrstica 213-289 prilagam tudi algoritem.

```{r}
Resi <- function(N, C){
  z_st <- c()
  X_st <- c()
  z_st[1] <- 0
  for(k in c(2:C+1)){
    z_st[k] <- Inf
    if(length(N$w)==1){
      X_st[k] <- c()
    }
  }
  if(length(N$w)==1){
    X_st[1] <- c()
    X_st[N$w[1]+1] <- N
  }
  for(i in c(length(N$w):1)){
    if((C)>=N$w[i]){
      for(k in c((C+1):(N$w[i]+1))){
      z_st[k] <- min(c(z_st[k], z_st[k-N$w[i]] + N$p[i]))
      }
    }
  }
  if(length(N$w)==1){
    result <- list(X_st = X_st, z_st = z_st)
    return(result)
  }
  result <- c(z_st = z_st)
  return(result)
}

Rekurziven_DP <- function(N, C, z_st){
  N_st <- c()
  C_st <- 0
  X_st <- c()
  particija <- trunc(length(N$w)/2)
  N_1 <- N[1:particija,]
  N_2 <- N[(particija+1):nrow(N$w),]
  z_st_1 <- Resi(N_1, C)
  z_st_2 <- Resi(N_2, C)
  if(length(N_1$w) != 1 && length(N_2$w) != 1){
    z <- sapply(c(1:(C+1)), function(ind){
      z_st_1[ind] + z_st_2[(C+1)-ind]
    })
    C_1 <- which(z == z_st) %>% head(1)
    C_1 <- C_1 - 1
    C_2 <- C - C_1
  }
  if(length(N_1$w) == 1 && length(N_2$w) != 1){
    z <- sapply(c(1:(C+1)), function(ind){
      z_st_1[2][ind] + z_st_2[(C+1)-ind]
    })
    C_1 <- which(z == z_st) %>% head(1)
    C_1 <- C_1 - 1
    C_2 <- C - C_1
  }
  if(length(N_1$w) != 1 && length(N_2$w) == 1){
    z <- sapply(c(1:(C+1)), function(ind){
      z_st_1[ind] + z_st_2[2][(C+1)-ind]
    })
    C_1 <- which(z == z_st) %>% head(1)
    C_1 <- C_1 - 1
    C_2 <- C - C_1
  }
  if(length(N_1$w) == 1 && length(N_2$w) == 1){
    z <- sapply(c(1:(C+1)), function(ind){
      z_st_1[2][ind] + z_st_2[2][(C+1)-ind]
    })
    C_1 <- which(z == z_st) %>% head(1)
    C_1 <- C_1 - 1
    C_2 <- C - C_1
  }
  if(length(N_1$w) == 1){
    # tukaj naletim natežavo, saj ne vem kako naj bi izgledal Merge...
    }
  }

[VidicL13]

Poleg tega pa, ko sva zagnala kodo, ki jo imava v sage-u, je le ta v hipu vrnila vse rešitve, R pa je potreboval veliko časa za EN sam ne preveč obsežen primer. To nekako spodbija celoten članek, ki trdi da je dinamični program hitrejši. Znate morda to pojasniti?

[NabergojV]

Pa izpustila sva algoritme pri dinamičnem algoritmu, ki izračunajo seznam predmetov ki so v nahrbtniku pri OPT.. Ali je to krivo za tako odstopanje?

[jaanos]

Če prav razumem, Merge združi rešitev za podproblem (N₁, C₁) velikosti 1 z rešitvijo splošnega podproblema (N*, C*) v rešitev za podproblem (N₁ ∪ N*, C₁ + C*). Vse, kar je potrebno narediti, je unija obeh rešitev, saj je na tem mestu cena za to delno rešitev že predpisana (in tako ne obstaja "boljša" rešitev).

Če je Sage vrnil rešitev v hipu, sklepam, da je bil podani primer majhen. Poskusita z večjim primerom - morda lahko poskusita bolj povečati število elementov kot pa samo kapaciteto nahrbtnika (na kar zna biti ILP bolj občutljiv). Samo računanje rešitve kot seznama elementov iz izhoda linearnega programa se opravi v linearnem času in tako ne bi smelo bistveno vplivati na odstopanje.

[NabergojV]

Problem je v tem, da sva v sageu naredila zanko ki gre čez vse podatke.. torej tudi čez primere ki so večji.. pa še vedno izračuna v prb 0.1 s. Tudi vsakič ko zaženeva zanko ki gre čez primere vrne vsakič drugačen čas, odstopanja so približno na 10^(-4)

[NabergojV]

Zanko lahko vidite na githubu... ta prebere csv datoteke in vrne čas trajanja ter optimum.

[jaanos]

Problem bi znal biti tukaj:

https://github.com/VidicL13/MinCost-MaxKnapsackPacking/blob/de9f5c835e8ea203da0223ce690948d565689211/MCMKP.Rmd#L152-L159

V vsakem obhodu glavne zanke se torej (večkrat) izračuna delna vsota, zaradi česar je časovna zahtevnost algoritma O(n² + nC) namesto samo O(nC). Delne vsote lahko vnaprej izračunata s funkcijo cumsum, npr.

W <- cumsum(I$w)
P <- cumsum(I$p)

Vseeno svetujem še, da poskusita z večjimi primeri. Kolikor vidim, imata na repozitoriju primere z največ 100 predmeti - lahko poskusita z npr. 1000 predmeti (ali pa to nekoliko zmanjšata, če bi trajalo predolgo).

[VidicL13]

Sedaj sem popravil vsote in je zgodba popolnoma drugačna 👍 imam pa še vedno težavo pri interpretaciji X(N,C).

Ali je X(N,C) = [x₁ ... x _len(N) ]^T vektor ali gre za seznam oziroma matriko...

[NabergojV]

Sedaj želiva dodati še kapaciteto algoritmu v Sageu, vendar ne veva kako pretvoriti list v vector. Posodobljen algoritem je na Githubu. Kako izvoziva rezultat?

[NabergojV]

*** WARNING: Code contains non-ascii characters    ***

Error in lines 26-33
Traceback (most recent call last):
  File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 4, in <module>
ValueError: need more than 0 values to unpack

​Tole napako mi vrže, ko skušam zagnati algoritem na sagu, brez dodanegakoncniC

[jaanos]

X*(N, C) je v osnovi množica izbranih elementov za dana N in C - kako ga predstavita (npr. kot seznam elementov, ali kot logični vektor), je vajina izbira (in tudi ne bo težko prehajati iz enega načina v drugega).

Za računanje končne kapacitete lahko naredita tako:

    resitev = program.get_values(vzamemo)
    koncniC = sum(resitev[i] * w for i, w in enumerate(W))

Meni sicer ni vrnilo zgornje napake - z nepopravljenim algoritmom sem dobil le napako, da ni mogoče množiti slovarja in seznama. Poskusil sem s podatki iz #4 in s Korelirani_R10_N10.csv.