A* Search - TSP

[xThrash]

Hello,

For an assignment I have to implement some search algorithms in order to solve the travelling salesman problem, I understand the problem and I understand how the algorithm works, I simply don't know how to implement it (my Java isn't great) but this should really be the easy part but unfortunately my knowledge of Java isn't good enough to apply what I know about the algorithm.

I was therefore wondering if anyone could provide some hints or tips on how to get started with this or maybe even some good links to read up on, I also have to implement some other algorithms too if there's an easier one to start with id be happy to go with that one!

Any help is much appreciated! Thank you

[Taywin]

Before you attempt to implement, you need to formulate how your input and output data structure for the problem are going to be. The TSP problem itself is not too difficult to understand. You, however, need to be able to relate the problem with your search algorithm.

I cannot really explain to you in words but may be able to see how it goes with your code. I guess showing your code may enable others to understand what you are heading to as well. So first step, what is your data structure?

[xThrash]

Thanks for the reply, im not too sure what youre actually asking? Im assuming im going to have to use some sort of list in order to store the nodes, I have been given some test files to use as input which vary from 5 cities to about 500. I dont have any code yet as I simply dont know where to start, as I say my Java isnt great and is seriously rusty so I have no idea how to even approach this problem let alone putting it into code.

[rubberman]

That's why you are studing computer science, I presume, so you can learn how to do this stuff? You say you understand the traveling salesman problem? I suspect that if you really did understand it, you could formulate your solution in pseudo code, which could easily be converted into any suitable programmng language, including Java (C++ with training wheels in my opinion). Do that at the least - produce pseudo code to solve the problem, and then we may decide you should be assisted in formulating it in Java... :-(

[Taywin]

I guess I somewhat understood how you feel. You do not have problems understanding each concept, but you have a problem relating concepts to a problem. In other words, you have a problem applying concepts to a problem. I had this problem before in advanced AI class. I talked to my professor and he couldn't help me because he did not understand why I did not get it. As a result, he left me high and dry. It took me almost the whole semester to understand but it was too late by then (my mid term was so bad that I could not pull the grade up).

First, what is your input structure right now? You said it contains 5 up to 500 cities. Do you have city-to-city connection data? Do you have weight for each connection? Do you have a name or ID for each city? If you have all, you should start from implementing your own cities and routes data first. Do you have an idea how to create City and CityRoute (or whatever name you want) classes? This will be your own design and you will use them in your program later on. For now, start with input data structure first.