Problema com algoritmo do caixeiro viajante

Programação Java
, , , ,
#1

Olá! Estou tentando fazer o algoritmo do caixeiro viajante em java para um trabalho da faculdade. Porém, estou preso na hora de fazer a matriz de adjacência! A idéia é pegar os valores dos jtextfield em que o usuário colocou os custos de cada aresta e passá-los para uma matriz de inteiro (esta é a matriz de adjacência). Segue o código:

public class CV extends JFrame {

private JPanel contentPane;
private JTextField BD;
private JTextField AB;
private JTextField AC;
private JTextField CD;
private JTextField BE;
private JTextField BF;
private JTextField CF;
private JTextField FG;
private JTextField DG;
private JTextField EG;
private JTextField CE;
private JPanel panel;
private JTextPane textPane;

private ArrayList<String> valores;
// Variavel global para definir o numero de cidades
public static int NUMERO_CIDADES = 7;


public static void main(String[] args) {
	EventQueue.invokeLater(new Runnable() {
		public void run() {
			try {
				CV frame = new CV();
				frame.setVisible(true);
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	});
}

public CV() {
	setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	setBounds(100, 100, 780, 553);
	contentPane = new JPanel();
	contentPane.setBorder(new EmptyBorder(5, 5, 5, 5));
	setContentPane(contentPane);
	setLocationRelativeTo(null);
	setResizable(false);

	panel = new JPanel();

	textPane = new JTextPane();
	textPane.setEditable(false);
	textPane.setBorder(new LineBorder(new Color(0, 0, 0), 2));

	JToggleButton btnCalcular = new JToggleButton("Calcular");
	btnCalcular.addItemListener(new ItemListener() {
		public void itemStateChanged(ItemEvent e) {
			if (btnCalcular.isSelected()) {
				Calcular();
			} else {
				Resetar();
			}
		}
	});

	JLabel lblCalcularMenorRota = new JLabel("Calcular Menor Rota!");
	lblCalcularMenorRota.setFont(new Font("Tahoma", Font.PLAIN, 12));
	GroupLayout gl_contentPane = new GroupLayout(contentPane);
	gl_contentPane.setHorizontalGroup(gl_contentPane.createParallelGroup(Alignment.LEADING).addGroup(gl_contentPane
			.createSequentialGroup().addContainerGap()
			.addGroup(gl_contentPane.createParallelGroup(Alignment.LEADING)
					.addComponent(textPane, GroupLayout.PREFERRED_SIZE, 612, GroupLayout.PREFERRED_SIZE)
					.addGroup(gl_contentPane.createSequentialGroup()
							.addComponent(panel, GroupLayout.PREFERRED_SIZE, 620, GroupLayout.PREFERRED_SIZE)
							.addPreferredGap(ComponentPlacement.RELATED)
							.addGroup(gl_contentPane.createParallelGroup(Alignment.LEADING)
									.addComponent(lblCalcularMenorRota, GroupLayout.PREFERRED_SIZE, 127,
											GroupLayout.PREFERRED_SIZE)
									.addComponent(btnCalcular, GroupLayout.PREFERRED_SIZE, 98,
											GroupLayout.PREFERRED_SIZE))))
			.addContainerGap(49, Short.MAX_VALUE)));
	gl_contentPane.setVerticalGroup(gl_contentPane.createParallelGroup(Alignment.LEADING)
			.addGroup(gl_contentPane.createSequentialGroup()
					.addComponent(panel, GroupLayout.PREFERRED_SIZE, 374, GroupLayout.PREFERRED_SIZE)
					.addPreferredGap(ComponentPlacement.UNRELATED)
					.addComponent(textPane, GroupLayout.DEFAULT_SIZE, 123, Short.MAX_VALUE))
			.addGroup(gl_contentPane.createSequentialGroup().addGap(10)
					.addComponent(btnCalcular, GroupLayout.PREFERRED_SIZE, 33, GroupLayout.PREFERRED_SIZE)
					.addPreferredGap(ComponentPlacement.RELATED)
					.addComponent(lblCalcularMenorRota, GroupLayout.PREFERRED_SIZE, 23, GroupLayout.PREFERRED_SIZE)
					.addGap(435)));

	JLabel label = new JLabel("");
	label.setBounds(0, 10, 614, 354);
	panel.setLayout(null);
	label.setIcon(new ImageIcon("src/CaixeiroViajante.png"));
	label.setBorder(new LineBorder(new Color(0, 0, 0), 2, true));
	panel.add(label);

	BD = new JTextField();
	BD.setForeground(Color.BLACK);
	BD.setBackground(Color.WHITE);
	BD.setBounds(259, 32, 27, 30);
	panel.add(BD);
	BD.setColumns(10);

	AB = new JTextField();
	AB.setColumns(10);
	AB.setBounds(88, 109, 27, 30);
	panel.add(AB);

	AC = new JTextField();
	AC.setColumns(10);
	AC.setBounds(88, 233, 27, 30);
	panel.add(AC);

	CD = new JTextField();
	CD.setColumns(10);
	CD.setBounds(320, 84, 27, 30);
	panel.add(CD);

	BE = new JTextField();
	BE.setColumns(10);
	BE.setBounds(307, 139, 27, 30);
	panel.add(BE);

	BF = new JTextField();
	BF.setColumns(10);
	BF.setBounds(295, 261, 27, 30);
	panel.add(BF);

	CF = new JTextField();
	CF.setColumns(10);
	CF.setBounds(247, 321, 27, 30);
	panel.add(CF);

	FG = new JTextField();
	FG.setColumns(10);
	FG.setBounds(468, 266, 27, 30);
	panel.add(FG);

	DG = new JTextField();
	DG.setColumns(10);
	DG.setBounds(468, 69, 27, 30);
	panel.add(DG);

	EG = new JTextField();
	EG.setColumns(10);
	EG.setBounds(445, 139, 27, 30);
	panel.add(EG);

	CE = new JTextField();
	CE.setColumns(10);
	CE.setBounds(285, 193, 27, 30);
	panel.add(CE);
	contentPane.setLayout(gl_contentPane);
}

protected void Resetar() {
	for (Component c : panel.getComponents()) {
		if (c instanceof JTextField) {
			((JTextField) c).setText(null);
			((JTextField) c).setEditable(true);
			textPane.setText(null);
		}
	}
}

private void Calcular() {

	valores = new ArrayList<String>();
	for (Component c : panel.getComponents()) {
		if (c instanceof JTextField) {
			JTextField textfield = JTextField.class.cast(c);
			textfield.setEditable(false);
			valores.add(textfield.getText());
		}
	}
	// Vetor para atribuir uma letra do alfabeto em ordem crescente as cidades
	String[] cidades = new String[NUMERO_CIDADES];

	// Vetor para atribuir letras do alfabeto as cidades em ordem crescente
	String[] alfabeto = { "A", "B", "C", "D", "E", "F", "G" };

	// Popula o vetor de cidades com as letras em ordem crescente
	for (int i = 0; i < NUMERO_CIDADES; i++) {
		cidades[i] = alfabeto[i];
	}

	// Cria a matriz de adjecencia do tamanho dos caminhos entre as cidades
	int mapa[][] = new int[11][11];

	// Inicializa a matriz de adjencia em 0
	for (int i = 0; i < 11; i++) {
		for (int j = 0; j < 11; j++) {
			mapa[i][j] = 0;
		}
	}
	// Popula a matriz de adjecencia com os valores informados pelo usuario
	// (replica o triangulo inferior de acordo com o triangulo superior)
	
	for (int i = 0; i < 11; i++) {
		for (int j = 0; j < 11; j++) {
			if (i == j) {
				mapa[i][j] = 0;
			} else if (mapa[i][j] == 0) {
				
				Iterator<String> it = valores.iterator();
				while (it.hasNext()) {
					mapa[i][j] = Integer.parseInt(it.next());
					mapa[j][i] = mapa[i][j];
				}
			}
		}
	}

	// Mostra a matriz no textPane
	for (int i = 0; i < 11; i++) {
		System.out.println();
		for (int j = 0; j < 11; j++) {
			System.out.printf("%d ", mapa[i][j]);
			textPane.setText(String.valueOf(mapa[i][j]));
		}
	}
}

}

Inserindo alguns valores assim:

Aplica%C3%A7%C3%A3o
Aplicação.jpg957×683 121 KB

A matriz resultante fica assim:

0 20 20 20 20 20 20 20 20 20 20
20 0 20 20 20 20 20 20 20 20 20
20 20 0 20 20 20 20 20 20 20 20
20 20 20 0 20 20 20 20 20 20 20
20 20 20 20 0 20 20 20 20 20 20
20 20 20 20 20 0 20 20 20 20 20
20 20 20 20 20 20 0 20 20 20 20
20 20 20 20 20 20 20 0 20 20 20
20 20 20 20 20 20 20 20 0 20 20
20 20 20 20 20 20 20 20 20 0 20
20 20 20 20 20 20 20 20 20 20 0

O que está errado!
Alguém pode me a ajudar a achar o erro e/ou entender como deveria funcionar esse algoritmo por favor?
Agradeço a atenção desde já!

#2

Vendo por cima:

Você esta resetando o iterador para cada par (i, j). Tenta só inicializar o iterador antes do for (int i

#3

Já fiz isso também. Não funciona, ele insere apenas o primeiro item do ArrayList na tabela e ainda insere no lugar errado…

#4

Enfim, mas o problema é claramente ai. Olha o que você ta fazendo:

Para um unico par (i, j) você está iterando sobre todos os elementos e sobre-escrevendo loucamente os valores no mesmo (i, j).

Ou seja, em todos os (i, j) sempre vai ter o último valor da lista do iterador it.

Acho que a questão é pensar como fazer melhor isso ai. Tenta entender bem o que ta acontecendo e re-escreve de uma forma mais lógica e fácil de entender.

#5

Eu tentei fazer utilizando o somente o while e duas variáveis contadoras para simular o for, porém, ele pegou os valores do ArrayList e os colocou na diagonal da matriz, também coloquei os 2 for dentro do while e nao funcionou também…

#6

Cara, é só não usar o while, se você está preenchendo uma matriz, é só percorrer as linhas e colunas:

Iterator<String> it = valores.iterator();
for (int i = 0; i < 11; i++) {
	for (int j = 0; j < 11 - i ; j++) {
		if (i == j) {
			mapa[i][j] = 0;
		} else {
            if (it.hasNext()) {
                mapa[i][j] = Integer.parseInt(it.next());
                mapa[j][i] = mapa[i][j];
            }
		}
	}
}
1 curtida
#7

Pois é, talvez do jeito que o @rmendes08 falou funcione mesmo. Mas pra mim tem coisas nebulosas ai, por exemplo a ordem dos componentes. Não ta claro que os componentes vão estar na lista na mesma ordem que ele quer que esteja.

Pra um grafo desse tamanho eu preencheria na mão:

mapa[0][1] = valorComponenteTal;
mapa[0][2] = valorComponenteFulano;

e talvez criar uma função pra fazer o espelhamento, já que o grafo tem os mesmos pesos em ambas direções.