Algorithmatic problem

[eigen]

Originally posted by: jman19

Originally posted by: bleeb
There are other more efficient methods than the Brute Force Method... You can try giving each node a weight and based on that come up with an algorithm... (don't remember the names off the top of my head)

If you remember the names of any of these post them here. Is there a way to try weights, and then based on some results, figure out how to properly readjust them to "move" towards the solution?

You may want to check out "tabu search" and "scattershot"

 

[jman19]

Originally posted by: eigen

Originally posted by: jman19

Originally posted by: bleeb
There are other more efficient methods than the Brute Force Method... You can try giving each node a weight and based on that come up with an algorithm... (don't remember the names off the top of my head)

If you remember the names of any of these post them here. Is there a way to try weights, and then based on some results, figure out how to properly readjust them to "move" towards the solution?

You may want to check out "tabu search" and "scattershot"

Thanks, I'll check them out. I've taken both Graph Theory and Operations Research, but that was 2 years ago... seems as if I've forgotten some of what I've learned 🙁

 

[RaynorWolfcastle]

Originally posted by: OulOat
This is a special case the Hamiliton graph cycles, and Hamiltion is NP-hard. Thus, by reduction, TSP is NP-hard.

Where is my cookie?

Originally posted by: rgwalt
This is the traveling salesman optimization problem, and is a tough cookie.

R

These gentlemen are correct. Brute-forcing this problem only works for small datasets since, this problem cannot be solved in polynomial time by any known algorithm.

Read up on the traveling salesman problem (TSP) if you're interested in knowing all the gory details. I'm pretty sure that solving the TSP in polynomial time is a prize problem.

 

[wfbberzerker]

isn't it algorithmic?

 

[eigen]

Originally posted by: RaynorWolfcastle

Originally posted by: OulOat
This is a special case the Hamiliton graph cycles, and Hamiltion is NP-hard. Thus, by reduction, TSP is NP-hard.

Where is my cookie?

Originally posted by: rgwalt
This is the traveling salesman optimization problem, and is a tough cookie.

R

These gentlemen are correct. Brute-forcing this problem only works for small datasets since, this problem cannot be solved in polynomial time by any known algorithm.

Read up on the traveling salesman problem (TSP) if you're interested in knowing all the gory details. I'm pretty sure that solving the TSP in polynomial time is a prize problem.

I sure solving it will get you some cash, but proving/disproving p=np gets you a cool miilion.

 

[RaynorWolfcastle]

Originally posted by: eigen
I sure solving it will get you some cash, but proving/disproving p=np gets you a cool miilion.

More specifically, I think that the million goes to someone that can prove/disprove that all NP-problems are actually P-problems. I think that by definition all P-problems are part of the set of NP-problems, no?

 

[KEV1N]

I once approximated the solution for a particular large dataset using PL/SQL in Oracle for a database class in college... basically do a reasonable number of paths (brute force) for as much storage space as you have and pick the shortest one. I remember on the night that it was due, somebody else in the class brought down the server we were all using because he filled up the disk with paths. Hehehe!

 

[gopunk]

Originally posted by: RaynorWolfcastle

Originally posted by: eigen
I sure solving it will get you some cash, but proving/disproving p=np gets you a cool miilion.

More specifically, I think that the million goes to someone that can prove/disprove that all NP-problems are actually P-problems. I think that by definition all P-problems are part of the set of NP-problems, no?

yea i think he meant that the set of p questions is equal to (not just a subset of) that of np questions.