Depois de pesquisar esse problema NP-Completo (que, portanto, não tem uma solução eficiente conhecida), chegamos a um algorítmo "ganansioso", que não promete a melhor resposta possível, mas é de O(n^2*m), onde n é o número de vértices e m, o número de arestas.
Segue o código de tal algorítmo, comentado.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | package greedyDSPcustom; /* Esse código procura o vértice com maior número de cidades vizinhas sem auxílio e o torna em ponto de emergência * O algoritmo continua criando pontos de emergência até não existirem mais cidades sem auxílio */ public class algorithm { public static int[][] g = { {0, 1, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 1, 0, 0}, {0, 1, 1, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0},}; public static int[] state = {0,0,0,0,0,0,0,0,0}; public static void main(String[] args) { int vertexMaxOrder = -1; while(!done()) { vertexMaxOrder = maxOrder(); state[vertexMaxOrder] = 2; //É ponto de emergência! Recebe auxílio por ser ponto de emergência for(int i=0; i<g[vertexMaxOrder].length; i++) { if(g[vertexMaxOrder][i] == 1 && state[i]==0) state[i] = 1;//É vizinho a um ponto de emergência, portanto recebe auxílio } } for(int i=0; i<state.length;i++) if(state[i]==2) System.out.println(i+1); } //Retorna o número de vizinhos sem auxílio para o vértice pedido public static int getOrder(int vertex) { int counter=0; for(int i=0; i<g[vertex].length;i++) if(g[vertex][i]==1 && state[i] == 0) counter++; return counter; } //Retorna o maior getOrder(vertex) dentre todos os vértices public static int maxOrder() { int max=-1; int vertex=-1; for(int i=0; i<g[0].length;i++) { if(getOrder(i)>max) { max = getOrder(i); vertex = i; } } return vertex; } //Retorna se o algoritmo deve acabar. A condição é não existir mais vértices sem auxílio (isto é, não serem pontos de emergência NEM vizinhos a um ponto de emergência) public static boolean done() { boolean done = true; for(int i=0; i<state.length;i++) if(state[i] == 0) done = false; return done; } } |
O trabalho completo pode ser visto em https://goo.gl/Bg3HQf, inclusive com um método de força bruta desenvolvido pelo genial aluno Matheus Mattos Moller.
