[Algoritmi - DIFFICILE] Problema teorico

[Malcolm1]

Ciao a tutti (ne è passato di tempo, eh?)!
Sto sviluppando un progetto alquanto complesso e mi sono trovato di fronte a questo problema; molte teste funzionano meglio di una (della mia di certo); ogni opinione è gradita.

Sia $G(V,E)$ un grafo completo; si vuole risolvere il problema del commesso viaggiatore tenendo in considerazione anche il peso dei nodi (che possono essere etichettati con valori discreti 1, 2 o 3) che indica la priorità con cui quel nodo deve essere visitato (da 1=bassa a 3=alta).
Si sa che TSP è un problema NP-hard, ma esistono soluzioni accettabilmente efficienti che si basano sull'utilizzo della disuguaglianza triangolare (per ogni vertice $u$, $v$ e $w$, si ha sempre che la funzione di costo $c$ soddisfa $c(u,w)< c(u,v) + c(v,w)$) che lo approssimano in tempo polinomiale.
Come si potrebbe aumentare una soluzione preesistente per tenere conto della priorità? La prima idea che avevo avuto era di effettivamente raggruppare i vertici in base alla priorità e applicare l'algoritmo ad ognuno di essi, ottenendo in effetti, tre problemi diversi; tuttavia mi sembra una soluzione un po' troppo rozza.
Idee anyone?

[marx1]

potresti aggiungere alla funzione di costo un valore addizionale dato dalla priorità del nodo corrispondente, facendo cosi una specie di funzione di fitness di un algoritmo genetico, in questo modo aumenta il costo della visita di un nodo con piorita più alta scegliendo quelli a prioritò più bassa.Dovresti però valutare bene il valore dell'elemento addizionale a seconda di quanto pesa effettivamente la priorità.Non so quanto sia buona come soluzione è solo un idea mia.