Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › UPDATED: Traveling salesman problem help - recursion- JAVA
New Posts  All Forums:Forum Nav:

# UPDATED: Traveling salesman problem help - recursion- JAVA

Hi guys,

Long story short, I'm working on a project for a math class at school, and I chose to do mine on the Traveling Salesman Problem, something I've always wanted to investigate more.
However, I'm having problems with my brute force solving algorithm.

SKIP THIS IF YOU KNOW WHAT THE TRAVELING SALESMAN PROBLEM IS:

To summarize as much as possible, the TSP goes like this: You are a salesman who wants to visit each city in a region (a city is essentially a point on a map). There are 'n' cities in the bounded x and y region, and each city is connected to each city (by assume a straight road). You need to find the shortest possible route among the cities that allows you to visit each city.One of the algorithms I want to use (and I will need to test other algorithms) is Brute Force, which checks every possible route and returns the shortest route. The reason this is not always used is because it requires us to check (n-1)! possible routes, and that number gets huge as 'n' increases- in fact, with just 50 cities, that would be 608281864034267560872252163321295376887552831379210240000000000 routes to check.

ASSUME THAT WE ARE GOING TO BE USING AN ARBITRARY REGION WITH 4 CITIES (we don't care about distances- we want to hit every possible route).

Here is a simple picture demoing what I'm talking about (4 cities is what I'm starting with to check if the process is working properly)

MEGA EDIT*

Code:
``````public void BruteForceFindBestRoute(Route r, ArrayList<City> citiesNotInRoute)
{
if(!citiesNotInRoute.isEmpty())
{
for(int i = 0; i<citiesNotInRoute.size(); i++)
{
City justRemoved = (City) citiesNotInRoute.remove(0).clone();
Route newRoute = (Route) r.clone();

BruteForceFindBestRoute(newRoute, citiesNotInRoute);
}
}
else //if(citiesNotInRoute.isEmpty())
{
if(IsBestRoute(r))
bestRoute = r;
}

}```
```

I cleaned up the post and simplified the code. The new code still doesn't work, but for a different reason.

The problem is that the variable i inside the for loop seems to lose it's meaning when we break out of the recursion, and the loop is not continued. Ideas? I'm getting desperate...
Edited by om3n - 7/28/12 at 4:49pm
 om3n rev. 2.8 (14 items)
CPUMotherboardGraphicsRAM
Intel Q6600 quad core @ 3.6 GHZ/ 3.2 GHZ constant eVGA 790i Ultra SLI BFG 9800 GTX @ 800/2000/1200 x2 SLI (2 x 4096MB) GSkill DDR3 Ripjaw @ 1511
RAMHard DriveOptical DriveOS
(2 x 1056MB) Corsair DDR3 XMS 1333 @ 1511 2x 150GB WD raptors RAID0; seagate 500GB & 1000GB ASUS 20x SATA Windows 8 professional x64
MonitorKeyboardPowerCase
Samsung 226BW 22" x2 CM Storm Quckfire Pro  Thermaltake 1200 watt toughpower Thermaltake Armor
Mouse
Logitech G700
 om3n rev. 2.8 (14 items)
CPUMotherboardGraphicsRAM
Intel Q6600 quad core @ 3.6 GHZ/ 3.2 GHZ constant eVGA 790i Ultra SLI BFG 9800 GTX @ 800/2000/1200 x2 SLI (2 x 4096MB) GSkill DDR3 Ripjaw @ 1511
RAMHard DriveOptical DriveOS
(2 x 1056MB) Corsair DDR3 XMS 1333 @ 1511 2x 150GB WD raptors RAID0; seagate 500GB & 1000GB ASUS 20x SATA Windows 8 professional x64
MonitorKeyboardPowerCase
Samsung 226BW 22" x2 CM Storm Quckfire Pro  Thermaltake 1200 watt toughpower Thermaltake Armor
Mouse
Logitech G700
My head asplode. I'd tell that salesman to go to hell.
Quote:
Originally Posted by Segovax

My head asplode. I'd tell that salesman to go to hell.

ha ha, yeah, my head asploded at like 3 pm yesterday, and I've been working on this problem ever since. I'm totally stuck.
 om3n rev. 2.8 (14 items)
CPUMotherboardGraphicsRAM
Intel Q6600 quad core @ 3.6 GHZ/ 3.2 GHZ constant eVGA 790i Ultra SLI BFG 9800 GTX @ 800/2000/1200 x2 SLI (2 x 4096MB) GSkill DDR3 Ripjaw @ 1511
RAMHard DriveOptical DriveOS
(2 x 1056MB) Corsair DDR3 XMS 1333 @ 1511 2x 150GB WD raptors RAID0; seagate 500GB & 1000GB ASUS 20x SATA Windows 8 professional x64
MonitorKeyboardPowerCase
Samsung 226BW 22" x2 CM Storm Quckfire Pro  Thermaltake 1200 watt toughpower Thermaltake Armor
Mouse
Logitech G700
 om3n rev. 2.8 (14 items)
CPUMotherboardGraphicsRAM
Intel Q6600 quad core @ 3.6 GHZ/ 3.2 GHZ constant eVGA 790i Ultra SLI BFG 9800 GTX @ 800/2000/1200 x2 SLI (2 x 4096MB) GSkill DDR3 Ripjaw @ 1511
RAMHard DriveOptical DriveOS
(2 x 1056MB) Corsair DDR3 XMS 1333 @ 1511 2x 150GB WD raptors RAID0; seagate 500GB & 1000GB ASUS 20x SATA Windows 8 professional x64
MonitorKeyboardPowerCase
Samsung 226BW 22" x2 CM Storm Quckfire Pro  Thermaltake 1200 watt toughpower Thermaltake Armor
Mouse
Logitech G700
I have updated the OP with new code that should hopefully be easier to read and understand. I could really use help guys
 om3n rev. 2.8 (14 items)
CPUMotherboardGraphicsRAM
Intel Q6600 quad core @ 3.6 GHZ/ 3.2 GHZ constant eVGA 790i Ultra SLI BFG 9800 GTX @ 800/2000/1200 x2 SLI (2 x 4096MB) GSkill DDR3 Ripjaw @ 1511
RAMHard DriveOptical DriveOS
(2 x 1056MB) Corsair DDR3 XMS 1333 @ 1511 2x 150GB WD raptors RAID0; seagate 500GB & 1000GB ASUS 20x SATA Windows 8 professional x64
MonitorKeyboardPowerCase
Samsung 226BW 22" x2 CM Storm Quckfire Pro  Thermaltake 1200 watt toughpower Thermaltake Armor
Mouse
Logitech G700
 om3n rev. 2.8 (14 items)
CPUMotherboardGraphicsRAM
Intel Q6600 quad core @ 3.6 GHZ/ 3.2 GHZ constant eVGA 790i Ultra SLI BFG 9800 GTX @ 800/2000/1200 x2 SLI (2 x 4096MB) GSkill DDR3 Ripjaw @ 1511
RAMHard DriveOptical DriveOS
(2 x 1056MB) Corsair DDR3 XMS 1333 @ 1511 2x 150GB WD raptors RAID0; seagate 500GB & 1000GB ASUS 20x SATA Windows 8 professional x64
MonitorKeyboardPowerCase
Samsung 226BW 22" x2 CM Storm Quckfire Pro  Thermaltake 1200 watt toughpower Thermaltake Armor
Mouse
Logitech G700
After really trying hard at your code, I think I finally understand what you're trying to do.

Just to confirm, what you're doing is creating a route using the recursion instruction from the citiesNotInRoute at first, then filling the array list back with all the removed cities to start again (using the for-loop) to create a new route in the same way. Right?

Well, assuming your algorithm is correct and assuming you're working with objects here (with the array list and the route being instance variables of that object), couldn't you just define i to be an instance variable of the object so that it keeps its value after the object is instantiated? I suppose you could but then again, I haven't read the rest of your code.
 Toshiba Satellite L655 (13 items) Desktop (13 items) MacBook Pro 13" (6 items)
CPUGraphicsRAMHard Drive
Intel i5 480m@2.67GHz AMD Radeon Mobility 5650 4GB DDR3 500GB
OSMonitor
Windows 7 64bit HP 15.6" 1366x768
CPUMotherboardGraphicsRAM
E7500 Intel...:( MSI GTS250 1GB 2GB
Hard DriveOSMonitorPower
250GB Windows XP 17" LG CRT 1280x768@85hz 400W
CPUGraphicsRAMHard Drive
Intel i5 @ 2.5 GHz Intel HD4000 4 GB DDR3 @ 1600 MHz 500 GB @ 5400 RPM
OSMonitor
OSX Lion 13.3" @ 1280 x 800
 Toshiba Satellite L655 (13 items) Desktop (13 items) MacBook Pro 13" (6 items)
CPUGraphicsRAMHard Drive
Intel i5 480m@2.67GHz AMD Radeon Mobility 5650 4GB DDR3 500GB
OSMonitor
Windows 7 64bit HP 15.6" 1366x768
CPUMotherboardGraphicsRAM
E7500 Intel...:( MSI GTS250 1GB 2GB
Hard DriveOSMonitorPower
250GB Windows XP 17" LG CRT 1280x768@85hz 400W
CPUGraphicsRAMHard Drive
Intel i5 @ 2.5 GHz Intel HD4000 4 GB DDR3 @ 1600 MHz 500 GB @ 5400 RPM
OSMonitor
OSX Lion 13.3" @ 1280 x 800
Brute force definitely stinks
Plenty of examples online using genetic algorithms to solve this problem!

I feel like there's some code missing here.... course there is...
 My System (30 items) "Zeus" (13 items)
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB)
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 7 Ultimate 64-bit Dell U2412M
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool
 My System (30 items) "Zeus" (13 items)
CPUMotherboardGraphicsRAM
Intel Core i5 2500K (4.5ghz @ 1.320v) Gigabyte Z68X-UD3R-B3 MSI R7970 Lightning Corsair 16GB (4x4GB)
Hard DriveHard DriveHard DriveHard Drive
Plextor PX-256M5S 256GB Crucial M4 128GB Hitachi HDS721010CLA332 Hitachi HDS723020BLA642
Hard DriveHard DriveHard DriveOptical Drive
Hitachi HDS723020BLA642 Hitachi HUA722010CLA330 WDC WD10EARS-00Z5B1 TSSTcorp CDDVDW SH-S223B
CoolingCoolingOSMonitor
Phanteks PH-TC14PE with TY-140's Lamptron FCv5 (x2) Windows 7 Ultimate 64-bit Dell U2412M
MonitorMonitorMonitorKeyboard
Dell U2412M Dell U2212HM Dell U2212HM Ducky DK9087 G2 Pro
Corsair AX-750 Corsair Obsidian 650D Microsoft IntelliMouse Optical  XTRAC Ripper XXL
AudioAudioAudioAudio
Westone W3 IEMs RE-272 IEMs Shure SE-215 IEMs Schiit Bifrost DAC
AudioAudio
Schiit Asgard 2 amp HiVi Swan M50W 2.1
CPUMotherboardGraphicsRAM
Intel Core i7 950 GA-X58-UD3R Radeon HD 5450  24GB Corsair @ 1333mhz
Hard DriveOSPowerCase
4x WD Cavair Red 1TB in RAID 0 Windows Server 2008 R2 x64 Corsair HX-520 LianLi LanCool
Quote:
Originally Posted by tompsonn

Brute force definitely stinks
Plenty of examples online using genetic algorithms to solve this problem!
I feel like there's some code missing here.... course there is...

Genetic algorithms are AWESOME, however they can (and often do) get stuck at a "local best" point instead of finding the ABSOLUTE best like a brute force algorithm would do.

ONTOPIC: If you want you can view the source code of my solution (meant to be readable instead of optimized), its in python but it shows you the core of the recursive algorithm; for your work, other than translating it to Java, you would have to change the way it calculates the shortest path (I did mine simply based on number of points in the path, you would have to sum the distances between all points, easy).
Warning: Spoiler! (Click to show)
Code:
``````def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest

graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D', 'F'],
'D': ['C'],
'E': ['F', 'Q'],
'F': ['C', 'A', 'E'],
'Q': ['Z'],
'Z': ['A']}

print find_shortest_path(graph, 'A', 'E')```
```

If you want to use my approach, I'm more than willing to help you port it to Java, it should be pretty straightforward, but perhaps dictionaries/hashes/tables are new to you.
 Back in Black (13 items)
CPUMotherboardGraphicsRAM
AMD Phenom II X4 965 BE (C3) Biostar TA790GX A3+ Sapphire HD 5770 (v2) CORSAIR XMS3 4GB DDR3
Hard DriveOptical DriveOSMonitor
WD Caviar Black 640GB Sony Optiarc CD/DVD RW Windows 7 Ultimate x64 NEC MultiSync LCD 1960NXi
KeyboardPowerCaseMouse
Microsoft Comfort Curve Keyboard 2000 Corsair 650TX Cooler Master Storm Scout Logitech MX 400 Laser
 Back in Black (13 items)
CPUMotherboardGraphicsRAM
AMD Phenom II X4 965 BE (C3) Biostar TA790GX A3+ Sapphire HD 5770 (v2) CORSAIR XMS3 4GB DDR3
Hard DriveOptical DriveOSMonitor
WD Caviar Black 640GB Sony Optiarc CD/DVD RW Windows 7 Ultimate x64 NEC MultiSync LCD 1960NXi
KeyboardPowerCaseMouse
Microsoft Comfort Curve Keyboard 2000 Corsair 650TX Cooler Master Storm Scout Logitech MX 400 Laser
New Posts  All Forums:Forum Nav:
Return Home
Back to Forum: Application Programming
• UPDATED: Traveling salesman problem help - recursion- JAVA
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › UPDATED: Traveling salesman problem help - recursion- JAVA