D - General Weighted Max Matching

Altre gare
1

stavo provando a capire la soluzione dell’editoriale del problema sopra menzionato con la programmazione dinamica, ma ci sono alcune cose che non mi sono proprio chiare.
questo è il codice completo della soluzione:

#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for(int i = 0; i < (x); i++)
int main() {
	int n;
	cin >> n;
	vector d(n, vector(n, 0));
	rep(i, n) {
		for(int j = i + 1; j < n; j++) cin >> d[i][j];
	}
	vector dp(1 << n, 0ll);
	rep(b, (1 << n) - 1) {
		int l = -1;
		rep(i, n) if(!(b >> i & 1)) {
			l = i;
			break;
		}
		rep(i, n) if(!(b >> i & 1)) {
			int nb = b | (1 << l) | (1 << i);
			dp[nb] = max(dp[nb], dp[b] + d[l][i]);
		}
	}
	cout << dp.back() << endl;
}

a me sembra che in questo modo vengano tralasciati molti indici dell’array dp, per esempio gli indici che in codice binario equivalgono a 0110 1010 1100 in un testcase con n=4, vengono utilizzati ma mai sovrascritti, il loro valore a fine programma è sempre 0.
Ringrazio in anticipo chiunque voglia provare a darmi una mano

2

Ciao, questa soluzione utilizza un particolare tipo di dp, in cui la rappresentazione binaria dell’indice di ciascuno stato ti indica quali nodi sono già stati presi e quali no.

Per maggiore chiarezza, riscrivo il codice della soluzione ufficiale (solo il ciclo principale):

  for (int mask=0;mask<(1<<n)-1;mask++) {
      int left=-1;
      for (int i=0;i<n;i++) {
          if (!(mask & 1<<i)) {
              left=i;
              break;
          }
      }
      for (int i=left;i<n;i++) {
          if (!(mask & 1<<i)) {
              int right=i;
              int new_mask=mask | (1<<left) | (1<<right);
              dp[new_mask]=max(dp[new_mask],dp[mask]+d[left][right]);
          }
      }
  }

Quando si processa uno stato mask, si accede a stati il cui indice ha uno o due bit in più accesi (che si traduce in indici strettamente maggiori); questo garantisce che nel momento in cui si utilizza dp[mask] il suo valore è quello definitivo, visto che tutti gli stati da cui si “raggiunge” mask hanno indice minore.

Ciò detto, la transizione consiste nel trovare il primo nodo non ancora preso in quello stato ( left ) e provare ad accoppiarlo con ciascun nodo non ancora utilizzato ( right ). Siccome il grafo è completo (in particolare esiste sempre un arco da i a j con i<j, mendre l’arco da i a i ha ovviamente peso 0) sarà possibile provare ad aggiungere ciascun arco left → right (ricordando che left è il nodo non preso con minor indice).

Considerando di aggiungere l’arco left → right, possiamo provare a migliorare il risultato per lo stato mask | 2^{left} | 2^{right} (dove | è l’operatore bitwise or).
Quando right è uguale a left stiamo semplicemente considerando il caso in cui un nodo non viene utilizzato, cosa che succede se N è dispari.

Gli stati 0110 non vengono mai raggiunti dalla transizione di altri stati per il semplice fatto che si può accendere una coppia di bit se uno dei due è il primo non acceso. Questo non è un problema perché si ha uno stato equivalente con 0111, ovvero quando il primo nodo non è stato considerato, mentre sono stati presi il secondo è il terzo, oppure quando è stato preso l’arco dal primo al terzo e ignorato il secondo o se è stato preso l’arco dal primo al secondo e ignorato il terzo.

Spero di avere risposto alla tua domanda, scusa se mi sono dilungato sul funzinamento di questa dp, ma penso sia importante per capire la soluzione.

3 Mi Piace
3

Immagina non scrivere la soluzione polinomiale a Max Weighted Matching. :new_moon_with_face:

4

non mi è ancora del tutto chiara una cosa, perché c’è un break; nel primo ciclo, perché il codice non è qualcosa del genere?

  for (int mask=0;mask<(1<<n)-1;mask++) {
      int left=-1;
      for (int i=0;i<n;i++) {
          if (!(mask & 1<<i)) {
              left=i;
              for (int i=left;i<n;i++) {
                  if (!(mask & 1<<i)) {
                      int right=i;
                      int new_mask=mask | (1<<left) | (1<<right);
                      dp[new_mask]=max(dp[new_mask],dp[mask]+d[left][right]);
                  }
              }
          }
      }
  }

cosí anche dp[6] dovrebbe essere usato, perché altrimenti quando si raggiunge mask = 6 che in codice binario è …00110 si calcolano nuovi valori di alcuni indici maggiori di 6 utilizzando dp[6] che equivale a 0, quindi in questo modo dp[mask] + d[left][right] equivale solo al peso dell’arco che viene aggiunto. Mettiamo il caso in cui left sia 3 e right sia 4, il valore per l’indice …011110 viene aggiornato solo con il valore del peso dell’arco che porta 3 a 4.

5

Ho capito cosa intendi ed é corretto. Alcuni stati non vengono calcolati. Questo perché non ti servono cioè questi stati non faranno parte in nessun caso della soluzione ottimale.

Se ci pensi, nella soluzione finale tutti i nodi sono stati associati ad un altro nodo, ad eccezione del caso in cui N sia dispari. Quindi processando uno stato tu stai provando ad associare il primo nodo libero con un altro nodo libero (o sé stesso), quindi non vuoi considerare tutte le coppie nella transizione di ciascuno stato.

Nell’esempio che fai te, l’indice 6 viene trascurato per il motivo che avevo spiegato nella prima risposta.

Se non mi sono spiegato bene chiedi pure

2 Mi Piace
6

non mi è chiario questo paragrafo, è vero che 0111 è uguale a max(0110,0101,0011) ma quello che non mi è chiaro è perchè questo dovrebbe servire, in questo caso sono 3 i bit scelti, e questa se N è pari non potrà mai arrivare ad essere una soluzione ottimale, perchè aggiungendo due bit alla volta arriverà ad aver preso N-1 bit, oppure N bit ma ne avrà trascurati 2, perchè una volta calcolata la soluzione ottimale di 0111, non sappiamo quale tra questi nodi sono stati scelti e quale non.

Forse però ho capito qualcosa, il fatto se non sbaglio è che si raggiungerà sempre la soluzione ottimale per mask[b] dove b è un numero composto in codice binario solo da 1, si può scegliere di prendere sempre una coppia di nodi di cui uno ha il minore indice possibile perchè tanto nella soluzione ottimale ci sarà un arco che va da quel nodo a indice minore a uno degli altri.

Dimmi se è sbagliato l’ultimo ragionamento che ho fatto. In ogni caso mi piacerebbe leggere la dimostrazione di questo, per caso conosci qualche sito dove hanno fatto la dimostrazione di un problema simile, e del perchè si possono scegliere coppie (i,j) dove i è il più piccolo possibile tra i bit non occupati?

1 Mi Piace
7

Il tuo ragionamento é corretto.
La dimostrazione di correttezza é facile da capire visto che si tratta di una ricerca completa. Di fatto qualunque sia la soluzione ottimale, una delle sequenze di tentativi corrisponde a questa visto che le provi tutte. Prendendo quella massima sai di prendere quella ottimale.
Ad esempio se con 4 nodi, se la soluzione ottimale fosse 0-2, 1-3 proverai all’inizio tutti gli archi da 0, incluso quello a 2 e quando arrivi allo stato 0101 saprai già il risultato migliore avendo a disposizione ancora 1 e 3. A questo punto proverai anche l’arco 1-3 che porta ad aggiornare il valore massimo dello stato 1111, che corrisponde alla soluzione.

3 Mi Piace