Zugg Software :: View topic

Posted: Wed Dec 03, 2003 2:24 pm

Hi,

I have the mapper working almost perfectly with Achea! It was a bit painfull to setup, and I had to put in lots of triggers with #NOMAP, #NODIR, and #TAG to get it stable.

Now I have a lot of zones mapped I want to put them to good use.

So. The question is this. I have several locations I wish to put into a bashing run. Being lazy I want to use the shortest route possible passing through all my location. So what I am after is a script that will look at the routes length from A to B, A to C, A to D, B to C, B to D etc. Then work out which is the fastest route (A B C and D are stop points where I will bash).

To make it clearer A would always be the start and end point. As the grid below shows. So I guess its a matter of covering all permutations. But I am stumped on how to tackle this right now

A B C D A
A B D C A
A C B D A
A C D B A
A D B C A
A D C B A

Note. I know this will make it more difficult, but I would like to have as many stop points in the run as I need. I am working on this now. and will try to post some script soon. But any help would be apreciated.

--------------------------------

I guess I should use the %walk() function and compare everything in my list.

Apprentice Joined: 16 Dec 2002 Posts: 103

Since shortest path algorithms come up all the time in comp. sci., I'm sure that there are many people here who could help you. However, I can not tell from your post what exactly you are asking. Your example graph could not be less clear to me. You are showing us a 6x6 matrix and saying that it is clear from that matrix that A (which occurs many times) is the start and end point?

I'm going to go out on a limb here and assume that you are asking what the best way is to visit each vertex in a graph exactly once. My advice to you is to eyeball your room arrangement and hardcode the script to work for your mud. If, however, you are serious about doing it the hard way, then I recommend that you find a good discrete math reference. The task in question is one of finding (directed) Hamiltonian Circuits, and it is a hard problem (in the same way that breaking unbreakable codes is hard). By that, I mean that nobody presently knows any "good" ways to reliably find these paths (or even to determine if they exist) and that you would become very famous if you were to find a way to do so. If, however, you can generate such paths (probably by just eyeballing your map), then finding the shortest one is a relatively simple matter. If the only criteria in selecting paths between two rooms is the number of steps, then you can use a breadth-first search. If some paths are somehow more costly than others (e.g. moving through a swamp eats movement points), then you need to look into Dijkstra's Algorithm.

Having said all of that, I would like to say that I think you are making this needlessly complex. I'd pick an order of visitation and use %walk to do it. Just that simple. If that isn't good enough, though, then you're probably going to have to either describe your problem in _much_ more detail, or learn the formalism of graph theory (which is unbelievably verbose for something that is generally very intuitive) in order to more effectively explain your problem.

GURU Joined: 10 Oct 2000 Posts: 873 Location: USA

quote:
Originally posted by hatespyware
You are showing us a 6x6 matrix and saying that it is clear from that matrix that A (which occurs many times) is the start and end point?

He's showing us the most obvious way to solve his problem: list all the routes and then find the best. Unless the total number of rooms is small, this isn't practical.

What algorithm is practical depends a lot on details he hasn't given us (number of nodes, etc).

quote:

The task in question is one of finding (directed) Hamiltonian Circuits,

I don't believe that it is. A Hamiltonian circuit visits each node _only_ once. For many graphs, the cheapest path to visit all nodes may involve visiting some nodes more than once (think situations like the hubs in many airline's routes). For some graphs that his problem might encompass, a Hamiltonian circuit may be impossible while a valid solution to his problem isn't (think a street with two buildings that have only one entrance node each but many rooms inside- you have to leave the first building after exploring it, thus visiting that node twice).

quote:

and it is a hard problem (in the same way that breaking unbreakable codes is hard). By that, I mean that nobody presently knows any "good" ways to reliably find these paths

The mathematical problem in the general sense is hard, but good answers can be found for many real-world instances of traveling salesman problems. An example of this is UPS/FedEx pathing- they have lots of streets and houses/businesses, and each day they want the shortest routes to visit each customer in a list.

quote:

Having said all of that, I would like to say that I think you are making this needlessly complex.

I agree. For Achaean bashing areas, which tend to be simple, the easiest way to solve the problem is most likely to just eyeball it out on a map.

If MartokShiva comes back with details of his problem that make a solver necessary (and the number of nodes involved isn't small), a plugin is probably the best way to go.

-Tarn

Apprentice Joined: 16 Dec 2002 Posts: 103

quote:
Originally posted by Tarn
He's showing us the most obvious way to solve his problem

There is no obvious way to solve his problem.

quote:
For many graphs, the cheapest path to visit all nodes may involve visiting some nodes more than once

Only in cases where there is no Hamiltonian cycle. In any case where a hamiltonian cycle exists, it would be optimal (or "most optimal" as a fav. prof. used to say).

quote:
quote:
The task in question is one of finding (directed) Hamiltonian Circuits,
I don't believe that it is.

Yes, it is. If he wants to know the "most optimal" path, then he needs a hamiltonian cycle (if it exists). Since there is no general-purpose way to know if one exists without finding it, then I believe I was correct that the problem is one of finding Hamiltonian Cycles.

quote:
For many graphs, the cheapest path to visit all nodes may involve visiting some nodes more than once (think situations like the hubs in many airline's routes). For some graphs that his problem might encompass, a Hamiltonian circuit may be impossible while a valid solution to his problem isn't (think a street with two buildings that have only one entrance node each but many rooms inside- you have to leave the first building after exploring it, thus visiting that node twice).

Yeah, those examples are pretty basic to the concept, since it can be shown that in any connected graph where a hamiltonian does not exist, one or more cyclic offshoots have been added to an existing hamiltonian cycle (although it is a lot easier to just tell you!).

quote:
The mathematical problem in the general sense is hard, but good answers can be found for many real-world instances of traveling salesman problems.

I will definately admit that I don't understand precisely what he's asking, but I'm pretty sure that it is more than just to find _a_ route. He already knows that _some_ route exists, else he'd think it impossible to go from one place to another. He wants the _best_ route. The best route is a hamiltonion cycle (if it exists).

quote:
An example of this is UPS/FedEx pathing- they have lots of streets and houses/businesses, and each day they want the shortest routes to visit each customer in a list.

Since I don't have to cross your lawn to get to my own, I'm not sure that this is the best example. We lay our streets out in such a way that finding hamiltonian cycles is always possible. Furthermore, even though I don't know how to find them (well, I can eyeball them), I _can_ say that any "sufficiently interconnected" graph will definitely have a hamiltonion cycle. Besides, we usually think of traffic-type problems in terms of the edges rather than the vertices (which is why the word “pathing” is so natural in this case, I’d think).

I also think it may be worth pointing out (for you, if not he), that any formal process of finding hamiltonian cycles would _include_ finding _all_ cycles, optimal or not. Therefore, the task of finding hamiltonian cycles will yield the best solution whether a hamiltonian cycle exists or not.

Apprentice Joined: 16 Dec 2002 Posts: 103

I’m not sure if anyone else would find this interesting, but it is pertinent. Here is a very evil Perl regular expression which finds Hamiltonian Circuits. Certainly lends credence to the belief that Perl is a write-only language :)

GURU Joined: 10 Oct 2000 Posts: 4379 Location: USA

How about instead of finding the length of all permutations, you just walk each time to the closest room. This will not necessarily give you the shortest route, but will give you a pretty good one.

Just put all the rooms that you need to go to into a list. Then, walk to room A, do what you have to do and find the closest room from those in the list. Remove this room from the list and walk to it. Repeat these steps until there are no more rooms in the list and then go back to A.

Posted: Thu Dec 04, 2003 3:05 pm

I have a solution coded, that is almost working. I will post it later today.

I had to resort to trying all permutations as the distance from A to B is not necessarily the same as the distance from B to A. It's not true in a lot of times in Achaea :)

My solution works through all the permutations, and uses %walk, %expandpath and %numitems, to determin the number of steps between every stop point and every other stop point. In short, it uses brute force to solve the problem. This of course means that it slows down dramatically the more stop points I include.

I already know routes to and between the stop points, but I wanted to see if I could work out the "best" route programmatically.

Anyway.. After I have tested some more, I will post the solution here. It was actually rather simple, so I was surprised to read the long complecated explanations posted in reply to my initial posting.

GURU Joined: 10 Oct 2000 Posts: 873 Location: USA

quote:
Originally posted by MartokShiva
Anyway.. After I have tested some more, I will post the solution here. It was actually rather simple, so I was surprised to read the long complecated explanations posted in reply to my initial posting.

It's simple if brute force is feasible, hence my question about how many nodes we were considering. Big difference between 10 and 10,000 :)

Did your solution work out for the problems you needed it to solve?

For very small numbers of nodes, brute force works. Unfortunately, doubling the number of nodes doesn't double the amount of computation, it increases it by a lot more than that.

If brute force isn't feasible, then finding good solutions in a reasonable amount of time is one of the more interesting continuing problems in comp sci.

Fortunately, it seems that you're dealing with fairly simple problems.

BTW, a lot of my post and hatespyware's is attempts to correct some misunderstandings. I just can't stand to let misleading information sit there :)

I continue to disagree with hatespyware. I put together a lengthy reply post, but in the interest of not getting TOO sidetracked I'll present just one example relating to his claim that a Hamiltonian cycle will be the best solution if one exists:

Airfare illustration follows with 4 cities, A, B, C, D. Airfares are symmetrical, so costs A-B = B-A.

A-B = $500
A-C = $500
B-C = $500
A-D = $100
B-D = $100
C-D = $100

A Hamiltonian cycle certainly exists: A-C-B-D with his trailing trip back to A tacked on, for a total cost of $1200
But it's possible to do the traveling much more cheaply:
A-D-B-D-C-D-A , for a total cost of $600, which is not a Hamiltonian cycle because D is visited more than once.

I'll also observe that FedEx delivers to houses located on deadend streets, forcing them to visit the intersection (node) that the deadend branches off from twice, making a Hamiltonian cycle not just expensive but impossible.

Kjata's suggestion is a very greedy approach, and fails very often by causing you to walk past a node and have to retrace your steps later. Example: 10 rooms lined up east to west, with travel costs 1 between them. One extra room to the south of the westernmost room, with a movement cost 2 in either direction. If you used Kjata's algorithm to visit all nodes starting at the westernmost one in the W-E chain, you would walk all the way to the eastern end, then all the way back to visit the final room with the 2 movement cost.

-Tarn

GURU Joined: 10 Oct 2000 Posts: 4379 Location: USA

quote:
Kjata's suggestion is a very greedy approach, and fails very often by causing you to walk past a node and have to retrace your steps later. Example: 10 rooms lined up east to west, with travel costs 1 between them. One extra room to the south of the westernmost room, with a movement cost 2 in either direction. If you used Kjata's algorithm to visit all nodes starting at the westernmost one in the W-E chain, you would walk all the way to the eastern end, then all the way back to visit the final room with the 2 movement cost.

Yes, you're right. I was looking for a realy bad-case scenario like this one, but at that moment I didn't have much time to think about it so I just posted the suggestion. Besides, I was considering that all movement would always have the same cost (as is the case with my map Smile

) and that typically stop points would not be arranged the way you describe them, but more spread out.