Massimo un terzo taglio

Question

Voglio risolvere il seguente problema (questo è un problema a casa. Non cercare risposte definite o complete):

Massimo un terzo taglio:

• Ingresso: Un grafico non diretto G = (v, e) dove V = {1,2, ..., n}, tale che | V | è divisibile per 3 e una funzione di peso integrale positivo W: E a n (sui bordi).
• Obiettivo: Fin un sottoinsieme di vertici U sottoinsieme di V tale che | U | = | v |/3.
• Obbiettivo: Massimizzare il peso totale dei bordi tra U e il suo complemento.

Certo, puoi farlo usando una ricerca completa di tutte le possibilità. Voglio però un algoritmo più efficiente.

Sto pensando a una specie di Ricerca locale Algoritmo, come l'arrampicata per la collina più ripida (Sahc) o una sua variazione (ricottura simulata, riavvio casuale ecc.).

• Stati:
  Potrebbe essere un vettore binario, dove il io-th elemento rappresenta se il vertice i è in u o no (0: non in u, 1: in u), dove il numero 1-S è | V |/3.
  
• Successori:
  Spegni un po ', accendi un altro.
• Funzione euristica:
  Somma di tutti i pesi dei bordi tra u e v u. Potrebbe essere calcolato quando si genera un successore, è necessario solo controllare il vertice rimosso e aggiunto. Forse gli stati possono contenere un elenco di bordi rilevanti.
• Altri parametri:
  Come la tempratura o la quantità di riavvio consentito potrebbe essere impostata testando l'algoritmo su grafici di dimensioni variabili, funzionalità di peso e bordi e scegliendo i valori migliori.

Stavo anche pensando Ricerca evolutiva.


Sono sulla strada giusta qui? Forse ci sono opzioni migliori? Qualsiasi suggerimento sarebbe molto apprezzato.

Grazie!