Routing algorithm - Algorithms Discussion Boards

Richard MacCutchan wrote:
=IF(X>0,-X,X)

Wow, that's sweet. Thumbs Up | :thumbsup:

Excel functions generally are.

Another option would be to use the ABS function:

=-ABS(X)

ABS function - Office Support[^]

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

Terrific.

Okay, so I know the table generation algorithms are slightly different in that LALR merges entries and a canonical LR parser will not.

My question is, is about the actual *use* of those entries - the final parse table.

Is there a difference between how a LALR parser parses and an LR parser *parses*?

Specifically, can I use the same parser code regardless of where I got the parse table? (whether from an LR algo or the LALR ago)

Real programmers use butterflies

shift/reduce parsing: the difference between LALR (1) and LR (1) is that LALR is based
on an LR (0) automaton.
Operationally they are the same: shift when you have to shift, reduce when you have to
reduce and give an error message when there is a mismatch between the set of expected tokens
and the received token

anyway thanks for your answer, i figured it out eventually the day i asked it but i didn't think to close the question (and i don't know if that's expected)

Real programmers use butterflies

Hi all, just seeking some advice please on how to approach this problem.

I need to create an algorithm for a small courier company.

The basic parameters would be x amount of drivers and a list of deliveries, pickup and drop-off postcodes with delivery time slots.

My thinking is to first create a matrix of all the pick up and delivery job postcodes and populate it with distance and journey times using Google’s API, then somehow loop through the jobs and match journey time’s with the delivery slots but not really sure where to start or even if this is a viable approach.

Any suggestions much appreciated !!!

Many thanks in advance 😊

Sounds like a nightmare version of the "travelling salesman" problem to me. Smile | :)

Traveling Salesman Problem | Solve the Traveling Salesman Problem[^]

All I can offer is that you should check whether the API returns the actual driving distance, or the "as the crow flies" straight-line distance. Once you start taking things like rivers and one-way systems into account, someone who is geographically closer to a destination might take considerably longer to reach it than someone who is technically further away.

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

Hey, yep definitely is that, the journey time’s returned are actual driving times based on Google’s distance API 😊

Looks like the OR Tools solution is very close to what I need, although need to allow for the different pick up locations as its not from a single depot...

Vehicle Routing Problem with Time Windows | OR-Tools[^]

Get a UPS, USPS or FedEx account and use their costing algorithms (and maybe their services, all told).

It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food

Kindly help me out to solve this question fro the book "Foundation of Algorithm"

There are two algorithms called Alg1 and Alg2 for a problem of size n. Alg1 runs in n2 microseconds and Alg2 runs in 100n log n microseconds. Alg1 can be implemented using 4 hours of programmer time and needs 2 minutes of CPU time. On the other hand, Alg2 requires 15 hours of programmer time and 6 minutes of CPU time. If programmers are paid 20 dollars per hour and CPU time costs 50 dollars per minute, how many times must a problem instance of size 500 be solved using Alg2 in order to justify its development cost?

thanks

This is a mathematics question, nothing really to do with algorithms.

If we would do this exercise for you, it would defeat its purpose which is to teach you how to develop and apply your analytical/mathematical skills.

"Five fruits and vegetables a day? What a joke!
Personally, after the third watermelon, I'm full."

I've come very close a couple of times, but I just can't get it right.

I know one person on Code Project that knows how, but I don't think he's telling. Fair enough.

Does anyone know of any resources on this? Something not math heavy, or at least not math exclusive. I'd prefer sample code or a high level description at least. Any programming language, though I prefer C family languages except java. I'll take java though, as it's what most of academia uses, and this is an academic exercise primarily.

I really would like to solve this for the parser generators I've built.

When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.

I am looking for the stat-of-the-art solver for the 0-1 knapsack problem, Do any one know how to find such a solver? better if it will be written in python or matlab.

Do you know what is limitation of current solver?

Thanks Tomer

Here is the question requirement:
There is a map shown in below

WWWWWWWWWWDW
WWWW    S  W
WWWW WWWW  W
WWWWSWWWW  S
WWWW WWWW  W
B   ES  E  W
WWWWWWWWWWWW

W is the wall that the player cannot move to
S is the score can the player option
E is the energy can gain
B is beginning point
D is the ending point

First, player has 0 energy and they need to go to E to gain energy first. Then when they gain energy, they can go to S to gain score. However, every E and S contains different energies, energies required and scores. Here is the clear description of the map:

<5 0> is B (Begining point)
<5 4> is E (energy point, contain 20 energy)
<3 4> is S (Score, require 6 energy to gain and contain 30 scores)
<5 5> is S (Score, require 2 energy to gain and contain 230 scores)
<5 8> is E (energy, contain 30 energy)
<3 10> is S (Score, require 16 energy to gain and contain 30 scores)
<1 8> is S (Score, require 8 energy to gain and contain 10 scores)

The final score is in this formula:

energy + scores - steps*2

The best path is B -> <5 4> -> <3 4> -> <5 5> -> <5 8> -> <3 10> -> D

The key point is that how to let the program or algorithm detect the optimal path (With the minimum steps and know which score should get as in the above example, the <1 8> Score is ignored.)

I am now figuring how can let the computer know going the <3 4> and go back the <5 4> and go to <5 5> is the best path instead of going to <5 5> -> <5 4> -> <3 4> -> <5 5>. I know the later one is a stupid path. But what I can think of is that to do the best path, we may need to search all path with factorial times loop which is not accepted in term of running time.

This kind of problem is basically solved by brute force because you have to check all paths.
But some techniques allow reducing the workload, like memorizing partial results to avoid recalculating them every time.
Memoization - Wikipedia[^]
For example, all path will start with 'B -> <5 4>' because of the map.

You must put some thinking to understand how the problem works and what simplifications can be done.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Performance shouldn't be a consideration when the problem is "small" to start with. "Optimum" is the same as exhaustive in this case.

It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food

how to set soft requirments in the input file ?

Looks like this question relates to an article[^]. It doesn't make sense outside of the context of that article.

I see you've also posted your question in the forum at the bottom of that article, which is the correct place for it.

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

Here is the question requirement:
There is a map shown in below

WWWWWWWWWWDW
WWWW    S  W
WWWW WWWW  W
WWWWSWWWW  S
WWWW WWWW  W
B   ES  E  W
WWWWWWWWWWWW

W is the wall that the player cannot move to
S is the score can the player option
E is the energy can gain
B is beginning point
D is the ending point

First, player has 0 energy and they need to go to E to gain energy first. Then when they gain energy, they can go to S to gain score. However, every E and S contains different energies, energies required and scores. Here is the clear description of the map:

<5 0> is B (Begining point)
<5 4> is E (energy point, contain 20 energy)
<3 4> is S (Score, require 6 energy to gain and contain 30 scores)
<5 5> is S (Score, require 2 energy to gain and contain 230 scores)
<5 8> is E (energy, contain 30 energy)
<3 10> is S (Score, require 16 energy to gain and contain 30 scores)
<1 8> is S (Score, require 8 energy to gain and contain 10 scores)

The final score is in this formula:

energy + scores - steps*2

The best path is B -> <5 4> -> <3 4> -> <5 5> -> <5 8> -> <3 10> -> D

The key point is that how to let the program or algorithm detect the optimal path (With the minimum steps and know which score should get as in the above example, the <1 8> Score is ignored.)

I am now figuring how can let the computer know going the <3 4> and go back the <5 4> and go to <5 5> is the best path instead of going to <5 5> -> <5 4> -> <3 4> -> <5 5>. I know the later one is a stupid path. But what I can think of is that to do the best path, we may need to search all path with factorial times loop which is not accepted in term of running time.

This requirement is incomplete, you only fave a vague description of what is the best path, how you compare 2 path op see which 1 is better.
and the map look weird.

We can't workout something from this.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Here is the refine question:
There is a map shown in below

<pre>WWWWWWWWWWDW
WWWW    S  W
WWWW WWWW  W
WWWWSWWWW  S
WWWW WWWW  W
B   ES  E  W
WWWWWWWWWWWW

W is the wall that the player cannot move to
S is the score can the player option
E is the energy can gain
B is beginning point
D is the ending point

First, player has 0 energy and they need to go to E to gain energy first. Then when they gain energy, they can go to S to gain score. However, every E and S contains different energies, energies required and scores. Here is the clear description of the map:

<5 0> is B (Begining point)
<5 4> is E (energy point, contain 20 energy)
<3 4> is S (Score, require 6 energy to gain and contain 30 scores)
<5 5> is S (Score, require 2 energy to gain and contain 230 scores)
<5 8> is E (energy, contain 30 energy)
<3 10> is S (Score, require 16 energy to gain and contain 30 scores)
<1 8> is S (Score, require 8 energy to gain and contain 10 scores)

The final score is in this formula:

energy + scores - steps*2

The best path is B -> <5 4> -> <3 4> -> <5 5> -> <5 8> -> <3 10> -> D

The key point is that how to let the program or algorithm detect the optimal path (With the minimum steps and know which score should get as in the above example, the <1 8> Score is ignored.)

I am now figuring how can let the computer know going the <3 4> and go back the <5 4> and go to <5 5> is the best path instead of going to <5 5> -> <5 4> -> <3 4> -> <5 5>. I know the later one is a stupid path. But what I can think of is that to do the best path, we may need to search all path with factorial times loop which is not accepted in term of running time.