[Ottimizzazione] Matching di peso massimo (non perfetto) su grafi non bipartiti

[fabrinhood]

Salve a tutti, sono nuovo del forum e non so se questa è la sezione giusta in cui scrivere (nel caso non lo sia indirizzatemi voi). Sto svolgendo un progetto in ambito di intelligenza artificiale, e sostanzialmente il problema consiste nel trovare l'indice di Banzhaf su un input costituito da un grafo non orientato, non bipartito e pesato sugli archi. Se non sapete cos'è l'indice di Banzhaf poco male, non è importante; ad ogni modo, per il calcolo di questo valore è necessario calcolare i matching di peso massimo sul grafo intero e PER TUTTE LE COMBINAZIONI POSSIBILI DEI RAMI. Per esempio, avendo un grafo con nodi {1,2,3,4,5} e archi {(1,2, peso x),(1,3, peso y),(2,3, peso z),(2,4, peso m),(3,4, peso n),(3,5, peso o),(4,5, peso p)} mi occorre calcolare i matching (di peso massimo) relativi ai sottografi indotti dal grafo dato (tutti i sottografi possibili, ad esempio per S1 = <{1,2}; (1,2, peso x)>, per S2= <{1,2,3} ; (1,2, peso x),(1,3, peso y),(2,3, peso z)>, per S3 = <{3,4,5},(3,4, peso n),(3,5, peso o),(4,5, peso p)>, etc etc ....). Spulciando un po' di letteratura ho trovato l'algoritmo di Edmond (per il calcolo del matching di peso massimo) e molte varianti ad esso associate, tuttavia il problema è che per ogni nuovo sottografo l'algoritmo ricomincia da capo, portando così la complessità a livelli molto elevati. E' possibile avere un'ottimizzazione (non necessariamente basata sull'algoritmo di Edmond, anzi, sono ben accetti altri suggerimenti) che calcoli le soluzioni dei sottografi in maniera "incrementale", mentre viene caolcolato il matching per l'intero grafo?

Spero di essere stato chiaro nell'esporre il problema e mi auguro che qualcuno mi possa essere d'aiuto.

[banzhaf]

La soluzione è CalcuList. Spero di esserti stato di aiuto. Buon lavoro.

[fabrinhood]

Perdona la mia ignoranza, ma cos'è CalcuList? Dove posso trovare informazioni su questa "cosa" (dico cosa perché non so se si tratta di un algoritmo piuttosto che di un linguaggio) ?