Algorithms

Re: This is all about Decision Support System...

28-Dec-08 5:24

If it's a thesis project, you should really be consulting with your thesis supervisor. Soliciting help from the internet could end up with you using somebody else's work in your thesis and claiming it to be yours; a big no-no.

Unless you have a specific question or programming issue, I suggest you consult with your supervisor first as to the best method by which to proceed.

Alan Balkany28-Dec-08 7:09

Alan Balkany

28-Dec-08 7:09

For an incompletely-understood complex problem, I like to initially "push" the problem and see how it pushes back. This gives insights as to the issues the ultimate solution needs to address.

Since you're meeting goals while minimizing costs, one way to push the problem is to examine Linear Programming http://en.wikipedia.org/wiki/Linear_programming[^], which is a simple, effective, well-known approach to this type of problem.

Although Linear Programming probably won't meet your needs, the value here is in analyzing why it doesn't work for your problem. The answer to that will provide clues to coming up with a more sophisticated solution. Repeat as needed.

Crystal Report

dkkeyan25-Dec-08 22:24

dkkeyan

25-Dec-08 22:24

how to connect crystal report with ASP 2.0

A* & Genetic Algorithms

Mustafa Ismail Mustafa25-Dec-08 5:52

25-Dec-08 5:52

I've been tasked by my AI Professor to create a solution for the n-Queens problem, using A* and GA, and maintaining Constraint Satisfaction.

Basically, is this possible? If so, how's the mix? I know I should have asked the Professor these questions in class, but he was in a rush to leave because he his wife was delivering and it did not click at the time in my head.

Don't forget to vote if the response was helpful

Sig history

"dad" Ishmail-Samuel Mustafa

Unix is a Four Letter Word, and Vi is a Two Letter Abbreviation

"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib

⁷³Zeppelin28-Dec-08 5:21

28-Dec-08 5:21

Isn't A* a path finding algorithm? In that sense using both A* and GA seems a little redundant. Just to take a whack at it, I would suggest using A* to search a possible population of paths generated by the GA.

Alternatively, you could use the GA to position the queen and then A* to calculate the paths.

Like I said, either algorithm should be sufficient, I'm not sure why you need to use both. Any more recent developments since posting the original question?

(I've been absent from the forums as I was taking a Christmas break. Smile | :)

)

Mustafa Ismail Mustafa28-Dec-08 5:27

28-Dec-08 5:27

I called the Prof this morning and I explained to him that what I understood made the assignment a load of rubbish. It turns out I misunderstood. He wants two assignments, both solutions to the n-Queens problem, one using SM-A* (simplified memory bounded A*) and the other using GA.

Cheers.

Don't forget to vote if the response was helpful

Sig history

"dad" Ishmail-Samuel Mustafa

Unix is a Four Letter Word, and Vi is a Two Letter Abbreviation

"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib

⁷³Zeppelin28-Dec-08 5:31

28-Dec-08 5:31

Mustafa Ismail Mustafa wrote:
He wants two assignments, both solutions to the n-Queens problem, one using SM-A* (simplified memory bounded A*) and the other using GA.

Ah, that would make more sense. Seems unnecessary (and possibly difficult) to mix the two.

Mustafa Ismail Mustafa28-Dec-08 5:35

28-Dec-08 5:35

Precisely.

I couldn't understand how he wanted the mix. It does make a lot more sense.
Cursed MSc.

Don't forget to vote if the response was helpful

Sig history

"dad" Ishmail-Samuel Mustafa

Unix is a Four Letter Word, and Vi is a Two Letter Abbreviation

"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib

⁷³Zeppelin28-Dec-08 5:41

28-Dec-08 5:41

Mustafa Ismail Mustafa wrote:
Cursed MSc.

You have much to learn yet, young Masters Student.

Mustafa Ismail Mustafa28-Dec-08 5:46

28-Dec-08 5:46

Actually, I'm top of my class $Shucks | :-\$

It didn't register at the time but I got suspicious when I started reading for the assignment. Didn't make sense, so I posted here and then I called the Prof and he set the record straight.

I'm aiming for the PhD at Queens, I really hope it works out. Computational Biology or Financial Engineering.

Don't forget to vote if the response was helpful

Sig history

"dad" Ishmail-Samuel Mustafa

Unix is a Four Letter Word, and Vi is a Two Letter Abbreviation

"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib

⁷³Zeppelin28-Dec-08 6:00

28-Dec-08 6:00

Mustafa Ismail Mustafa wrote:
Financial Engineering

Interesting you brought that up - since I am a "financial engineer". I would counsel you not to go into it. There have been huge lay-offs (150,000+) in the wake of the financial crisis and investment banks are decreasing their activity in this area as most are being merged with their deposit side activities. Combine that with calls for increased regulation of the financial markets and derivatives and the number of jobs available for financial engineers will see a marked decrease.

I am trying to get out of the field myself and it is proving very difficult to find a job. The profession is currently very unpopular - nobody wants to be associated with those thought to be behind the credit crisis.

Mustafa Ismail Mustafa28-Dec-08 7:34

28-Dec-08 7:34

Really?

I'd have thought that it would pick up after the recession, besides, wouldn't that actually help the financial institutions get back on their feet faster?

I prefer going into Computational Biology, specifically into the modeling and forecasting of diseases and/or chemical reactions in biological entities systems.

You've given me food for thought.

In either case, because of the financial crisis, in the States, many universities have cut down the number of PhD students that they're willing to take on, but come this summer, I'm leaving Jordan to either carry on with the PhD or to get a better paying job in [western] Canada.

Don't forget to vote if the response was helpful

Sig history

"dad" Ishmail-Samuel Mustafa

Unix is a Four Letter Word, and Vi is a Two Letter Abbreviation

"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib

⁷³Zeppelin28-Dec-08 7:41

28-Dec-08 7:41

Yes. All investment banks are cutting back their quantitative positions. The increased regulation will mean more routine uses of derivative products and less need for people with quantitative backgrounds to invent new products.

It's already happening. In Zurich, for example, there are thousands with backgrounds in financial engineering on the job market. For each job posting they are getting so many applications they can't handle them all. Even the headhunter organizations are telling me not to expect anything until late next year at the soonest and, even then, there will be huge competition for limited positions - those with the most experience will be taken first. It's terrible. Most banks are waiting to see what the "new system" will mean for their risk management operations. That could be two years or more before there's a solid draft and implementation.

I'm trying to get into financial regulation so that when the banks start hiring I'll have some experience.

And it's worse in the U.S. The number of unemployed is in excess of 150,000.

Mustafa Ismail Mustafa28-Dec-08 8:16

28-Dec-08 8:16

Would you mind if I emailed you later on tonight when I get back home? I'd like to discuss this in greater detail if you don't mind. I would so totally appreciate it.

Don't forget to vote if the response was helpful

Sig history

"dad" Ishmail-Samuel Mustafa

Unix is a Four Letter Word, and Vi is a Two Letter Abbreviation

"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib

⁷³Zeppelin28-Dec-08 20:45

28-Dec-08 20:45

No problem. I'm GMT+1, so my response could be delayed due to time difference.

Mustafa Ismail Mustafa28-Dec-08 20:49

28-Dec-08 20:49

Great, I'm GMT +2 so we should be fine Smile | :)

Don't forget to vote if the response was helpful

Sig history

"dad" Ishmail-Samuel Mustafa

Unix is a Four Letter Word, and Vi is a Two Letter Abbreviation

"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib

urgent!

Mark Churchill24-Dec-08 23:25

Mark Churchill

24-Dec-08 23:25

how to calculate shortest path between houses. answer must take into account fully laden sleigh and naughty/nice rating of occupants. urgent!

CODE PLEASE!

Merry Christmas CodeProject Big Grin | :-D

Mark Churchill
Director, Dunn & Churchill Pty Ltd
Free Download: Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio.

Alpha release: Entanglar: Transparant multiplayer framework for .Net games.

Re: urgent!

⁷³Zeppelin28-Dec-08 5:29

mpeg 2 sync ( & a little hardware )

28-Dec-08 5:29

Mark Churchill wrote:
how to calculate shortest path between houses

Dijkstra's algorithm for the nice! The longest path algorithm for the naughty!

( Is this a homework question? Poke tongue | ;-P

)

It's a bit past Christmas, so Happy Holidays, Mark!

bulg24-Dec-08 8:20

bulg

24-Dec-08 8:20

modified on Monday, February 9, 2009 7:30 PM

Calculating the longest path

zenerguy3223-Dec-08 20:15

zenerguy32

23-Dec-08 20:15

I have a problem I can't seem to figure out. I'm trying to code an algorithm which calculates the longest path(s) from a given list of nodes and their neighbor nodes. I've learned a little bit about Djikstra's and the "traveling salesman" algorithms but those are both meant to calculate the shortest distance between two points. The problem statement would basically be "Given a list of nodes and their neighboring nodes (all one unit away), calculate the longest path(s) that can be taken using any given 'segment' only once in each path."

Here's an example. Given this list:

Node : Neighboring Node,Neighboring Node,Neighboring Node
0 : 1,2,9
1 : 0,5,6
2 : 0,3,-1
3 : 2,4,-1
4 : 3,5,-1
5 : 4,1,-1
6 : 1,7,-1
7 : 6,8,-1
8 : 7,9,-1
9 : 8,0,-1
('-1' means no neighboring node)

the algorithm should output:

"0-1-5-4-3-2-0-9-8-7-6-1"
"0-1-6-7-8-9-0-2-3-4-5-1"
"0-2-3-4-5-1-0-9-8-7-6-1"
"0-2-3-4-5-1-6-7-8-9-0-1"
"0-9-8-7-6-1-0-2-3-4-5-1"
"0-9-8-7-6-1-5-4-3-2-0-1"
"1-0-2-3-4-5-1-6-7-8-9-0"
"1-0-9-8-7-6-1-5-4-3-2-0"
"1-5-4-3-2-0-1-6-7-8-9-0"
"1-5-4-3-2-0-9-8-7-6-1-0"
"1-6-7-8-9-0-1-5-4-3-2-0"
"1-6-7-8-9-0-2-3-4-5-1-0"

I've been trying to code this in VB6 but it's gotten very messy and I think I'd like to try coding it in Python to get it working and then convert it to VB6.

My current method starts at a node and "jumps" to a neighbor node until it reaches a node that's already been used once in the current path, and then jumps backwards until it reaches a three-neighbor-node and takes the second "fork" of that node until it reaches that end. It does this until it's jumped all the way back to the starting node, and then it chooses another starting node and runs again until all three-neighbor nodes have been started from. I guess it's similar to a tree-searching algorithm except the branches can connect to each other.

I've spent a while Googling and haven't found much - most articles I've found deal with finding the shortest path. Any help would be appreciated!

⁷³Zeppelin28-Dec-08 5:13

28-Dec-08 5:13

Since you are using a sequence of nodes, you can use the constraint that no node in a potential path can be the same as the previous node. Then objective function is the length of the path.

I dug up some pseudocode:

Pseudocode for Longest Path
	Nodes of graph have integer names

Node Extensible( sequence s )
  Boolean found, Node endpoint
	p = EndOfPath(s)
        Set Inpath(x) = true for any x in s
	//LastUsed remembers last vertex used to extend s
	y = LastUsed(p)+1
        // now find first vertex which is :
        // not in use in s
        // adjacent to p
        // >= y
	found = false, q = y
        While q <= number of vertices And Not found
            found = Not InPath(q) And IsEdge(p, i)
            If Not found Then q = q + 1
        End While
        If Not found Then
            Extensible = -1
        Else
            Extensible = q
        End If

Sequence Truncate( sequence s )
        'Reset Lastused for EndofPath of s and remove EndofPath
         p = EndOfPath(s)
	 // p will be removed so reset Lastused
         Lastused(p) = 0
         If s.length = 1 then
		// choose new start vertex
		Truncate = s+1 // s is integer name for old start
        Else
                Truncate = all but last node of s
        End If

Sequence Extend( sequence s )
	 p = EndOfPath(s)
         q = Extensible(s)
            If q = -1 Then
                If s.Length > s*.Length Then s* = s
                // backtrack
                Extend = Truncate( s )
            Else
                Lastused(p) = q
                Extend = s + q
            End If
        End If

zenerguy3230-Dec-08 10:04

zenerguy32

30-Dec-08 10:04

In your pseudocode, when finding the next node to jump to, it says:

73Zeppelin wrote:
// now find first vertex which is :
// not in use in s
// adjacent to p
// >= y

If I'm reading that correctly it will only use nodes which have not already been used in the current path. However, it shouldn't matter how many times any particular node is used but rather how many times each "road" between nodes is used.

In my example, "0-1-5-4-3-2-0-9-8-7-6-1" was a valid path. Node '0' is used twice, but each "road" leading to each of its three neighbors is used only once (0-1,2-0,0-9). Am I understanding your pseudocode correctly?

One more question - what does

73Zeppelin wrote:
If s.Length > s*.Length Then s* = s

do? Thanks!

⁷³Zeppelin31-Dec-08 2:07

31-Dec-08 2:07

zenerguy32 wrote:
If I'm reading that correctly it will only use nodes which have not already been used in the current path. However, it shouldn't matter how many times any particular node is used but rather how many times each "road" between nodes is used.

In my example, "0-1-5-4-3-2-0-9-8-7-6-1" was a valid path. Node '0' is used twice, but each "road" leading to each of its three neighbors is used only once (0-1,2-0,0-9). Am I understanding your pseudocode correctly?

Ah, okay. Yes, the algorithm allows traversal through a vertex only one time. You are allowing multiple traversals?

zenerguy32 wrote:
73Zeppelin wrote:
If s.Length > s*.Length Then s* = s

do? Thanks!

This is just used for backtracking.