|
I did my final year project on a scrabble game and i found that the best way to increase speed when matching words is by choosing an efficient data storage technique for your dictionary.
A tree structure is needed to solve this problem, a DAWG would probably be the best choice.
|
|
|
|
|
Hi everyone,
Could anyone kindly assist with some code (preferably Java) for the Travelling Salesman Problem that uses any of the following Heuristics
1. Tabu Search
2. Hill Climbing
3. GRASP (Greedy Randomized Adaptive Search Procedure)
4. Simulated Annealing
I need this to just text some problems.
Thanks
laremtj
Jesus Loves You, Give your Heart to Him Today
|
|
|
|
|
laremtj wrote: preferably Java
This is a Visual Studio/.NET Centric site, if in case you haven't noticed.
"Any sort of work in VB6 is bound to provide several WTF moments." - Christian Graus
|
|
|
|
|
I'm not sure this is the rigth place to post this question but it sounds like a math problem to me so...
Problem:
I need all the combinations of a set of numbers (to make it easy lets take 3 numbers, but eventualy it has to work for 15numbers and more)
the user will give in 3 number for example: 1 , 5 , 19
then the programme needs to give the following combinations:
1, 5, 19
1, 19, 5
5, 1, 19
5, 19, 1
19, 1, 5
19, 5, 1
I've been searching for some algoritme our other way to do this for several weeks now and just can't find it
any ideas on how I could achieve this??
If my help was helpfull let me know, if not let me know why.
The only way we learn is by making mistaks.
|
|
|
|
|
Hi,
if you want to list all combinations, recursion is what you need.
Build a method that takes a collection as an input, and let a for loop pick one element,
remove it, then call recursively with wath remains in the collection, until the collection
is empty; then return.
BTW: if your collection is ordered, and your method picks in that same order, the result will
be ordered too.
Warning: for n elements, the recursion depth will be n, the number of combinations n!
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Recursion is a bad thing. You can almost always remove recursion from an algorithm using a simple stack. Case in point, you can remove recursion from the suggested algorithm with a stack. Something like this:
1 on Stack
5 on Stack
19 on Stack
Start popping -> 1,5,19
19 on Stack
5 on Stack
Start popping -> 1,19,5
etc ...
HossFly
|
|
|
|
|
Hoss Fly wrote: Recursion is a bad thing
Nonsense! Recursion is simply one tool that any professional should consider. There may be performance issues in some applications, but often you can't beat it for simplicity and elegance. Recursive descent parsing is an excellent example.
Hoss Fly wrote: You can almost always remove recursion from an algorithm using a simple stack
So why not use the processor stack - i.e. recursion. If you use built-in support rather than roll your own stack the code may be cleaner and less error prone.
Unless the number of elements is large (in which case there is no point enumerating all n! permutations), recursion is a perfectly valid method of solution to consider.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
You made my point for me. You shouldn't use recursion if you do not know the recursion depth. Whereas with a stack it is never an issue. I can describe many a problem where one cannot KNOW the recursion depth in advance (Flood Fill, Point Insertion w/r to Triangulation, clipping, etc...)
I have fixed recurssion based algorithms in two commercial products. The crashes this type of logic causes is often very difficult to catch. Try finding it in millions of lines of code and you will have the same opinion.
It is probably ok for some text book or academic problems. problem is developers fail to realize the stack problem and take the easy approach. I advocate thinking stack first, and recursion second (or last resort, or never.)
HossFly
|
|
|
|
|
|
As Peter already told you, recursion has its merits; it is often abused, but in this case
it is the right approach. My last remark (the depth n and result count n!) was
intended to illustrate that: if you care to consume n! results, then a stack depth of n
would not be an obstacle.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
<br />
char[] harfler = new char[7];<br />
harfler[0] = tb1.Text.ToCharArray()[0];<br />
harfler[1] = tb2.Text.ToCharArray()[0];<br />
harfler[2] = tb3.Text.ToCharArray()[0];<br />
harfler[3] = tb4.Text.ToCharArray()[0];<br />
harfler[4] = tb5.Text.ToCharArray()[0];<br />
harfler[5] = tb6.Text.ToCharArray()[0];<br />
harfler[6] = tb7.Text.ToCharArray()[0];<br />
<br />
List<string> liste = new List<string>();<br />
<br />
for (int i = 0; i < harfler.Length; i++)<br />
{<br />
for (int j = (i + 1) % 7, x = 0; x < harfler.Length; x++)<br />
{<br />
if (i != j)<br />
{<br />
for (int k = (j + 1) % 7, y = 0; y < harfler.Length; y++)<br />
{<br />
if (k != i && k != j)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k]);<br />
for (int l = (k + 1) % 7, z = 0; z < harfler.Length; z++)<br />
{<br />
if (l != i && l != j && l != k)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l]);<br />
for (int m = (l + 1) % 7, t = 0; t < harfler.Length; t++)<br />
{<br />
if (m != i && m != j && m != k && m != l)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m]);<br />
for (int n = (m + 1) % 7, v = 0; v < harfler.Length; v++)<br />
{<br />
if (n != i && n != j && n != k && n != l && n != m)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m] + "" + harfler[n]);<br />
for (int o = (n + 1) % 7, q = 0; q < harfler.Length; q++)<br />
{<br />
if (o != i && o != j && o != k && o != l && o != m && o != n)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m] + "" + harfler[n] + "" + harfler[o]);<br />
<br />
}<br />
<br />
o = (++o) % 7;<br />
}<br />
}<br />
<br />
n = (++n) % 7;<br />
}<br />
}<br />
<br />
m = (++m) % 7;<br />
}<br />
}<br />
<br />
l = (++l) % 7;<br />
}<br />
}<br />
<br />
k = (++k) % 7;<br />
}<br />
}<br />
<br />
j = (++j) % 7;<br />
}<br />
}<br />
Surely it is not an efficient way but in a specisific project this has worked well for me. It combinates 7 letters and produce words at least with length 3 and at most length 7.
.:: Something is Wrong ::.
|
|
|
|
|
Hmmm... that looks like permutations to me, not combinations.
|
|
|
|
|
In C++ something like this is the way to go:
--------------------------------------------
// Console.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <iterator>
void main()
{
using namespace std;
int Numbers[] = {1, 5, 19};
int *pOnePastEnd = Numbers + sizeof(Numbers)/sizeof(Numbers[0]);
sort(Numbers, pOnePastEnd);
copy(Numbers, pOnePastEnd, ostream_iterator<int>(cout, " "));
cout << endl;
while (next_permutation(Numbers, pOnePastEnd))
{
copy(Numbers, pOnePastEnd, ostream_iterator<int>(cout, " "));
cout << endl;
}
}
Steve
|
|
|
|
|
I see I got 2ed. Well it works perfectly and the OP didn't mention a language. If he's got a C++ compiler he can look in the source code and adapt the algorithm used to another language. Alternatively he could download STLport and do the same.
Steve
|
|
|
|
|
This is pseudocode for your solution:
ListCombinatoricalOrder(List L)
if (L is empty)
return
int n = L.Count
if (n == 1)
Write L[0]
return
Write(L)
ListCombinatoricalOrder(empty, L, n)
Done
ListCombinatoricalOrder(List Prefix, List comb, int count)
for (int i = 0; i < count; ++i)
List newPre = Prefix append comb[i]
List newComb = comb subtract comb[i]
if (i != 0)
Write(newPre, newComb)
ListCombinatoricalOrder(newPre, newComb, count - 1)
Done
WHERE:
Write(L) will write the entire list
Write(newPre, NewComb) will Write the list newPre then append the list NewComb to it
Notice the is an output generating algorithm not suited well for a library. But I left the details to you to make it more generic. This is just an idea of how to go about solving the combinatorical problem.
I hope this helps.
--Avi
-- modified at 4:42 Sunday 14th October, 2007
|
|
|
|
|
I have a set of machines, let's call them A,B,C,...etc and a bunch of tasks let's call them 1,2,3,...an so on. Now my machines aren't terribly reliable and often it may be the case that say A can do tasks 1 & 3, but can't do task 2, so obviously I shouldn't have it do task 2. Also each machine can only be assigned one task, so A can do 1 or 3, but not both. So let's say for example I have this:
A can do 1 & 3
B can do 1, 2 & 3
C can only do 3
The solution is obvious, A does 1, B does 2 and C does 3. This is fairly trivial for the case of only 3 machines and 3 tasks, but my real problem has 30 machines and potentially 30 tasks.
Is there an algorithm that handles these types of problems that somebody can point me in the direction of. It would need to suggest a solution (it's not necessary the case that any one solution would be better than another) or let me know that there is no solution and I need to fix my machines.
All I need is a nudge in the right direction.
Cheers!
|
|
|
|
|
Hungarian algorithm[^] maybe?
---- I don't care what you consider witty, but at least I do not blather on posting nonsense like Jim Crafton.-- Stringcheese, humbled by Crafton's ability to string together multiple sentences
|
|
|
|
|
Thanks, I'll check it out.
|
|
|
|
|
Hello,
I work for a steel fabrication plant and am faced with a problem I cannot solve. Hopefully the gang over here at Code Project can help me out a little...
First, let me define the terms I will use (a crash course in steel purchasing):
-Mill Order: simply an order of material placed to the steel mill
-Beams: should be self explanatory, but I want to cover their dimensioning:
-a beam has three dimensions, they are as follows; nominal flange depth (aka width), pounds per foot (weight), and length.
Sample: 10x15x9'-0" ( I should note here that the length property for each beam in the program is defined as the number
of 1/16ths of an inch that make up the length. ->
For the sample, the length would be 1728 (1728/16)/12=9).)
-Hundred Weight (or CWT): is the price of the beam per 100lbs. This is usually around $40-$50
-Standard Size: any beam length 30ft-65ft in increments of 5ft.
-Non-Standard Size: any beam of any length in increments of 6in. There is an extra charge of $0.25/cwt for non-standard beams.
-Bundle Requirements: a standard size 10x15 beam is sold in bundles of 3. If you need 5, you must buy 2 bundles and inventory
the extra.
a non-standard size 10x15 must meet at least one bundle requirement. So, if you need 4, they will sell you
4. But if you need 2, you must buy 3 and inventory the extra.
The bundle requirements change with each flange depth and weight.
Ok. Now to the logic bit...
I am given a list of all the beams for a job to order from the mill. Obviously I do not want to order every beam as is. I need to nest the beams into the mill order to optimize the amount of money being spent. If you do not know what I mean by "nest", let me explain: If I have 6 beams whose dimesions are 10x15x20', instead of ordering the beams without nesting and incuring a charge of $0.25/cwt for the non-standard length, I want to nest those 6 beams into 1 40' bundle.
This is the part that is difficult. I cannot seem to find a logic process to optimize all standard sizes vs. non-standard sizes vs. bundle requiremnts vs. pricing. If I could see a step by step process, or just have an idea of where to start, I would probably be able to begin serious development on the program.
I want to make it VERY CLEAR at this point that I am NOT asking anyone to do this for me. All I am looking for is a point in the right direction or something of that nature. I DO NOT WANT SOURCE FROM ANY LANGUAGE.
Thank you in advance for your time and input,
-David
|
|
|
|
|
I think I might be able to help. Before we start, I have two observations:
[1] I take it that ordering the beams in a manner that is not suited to the design will result in someone at the site cutting / trimming / grinding each beam ordered to the beam design specs. If so, there are personnel charges, equipment usage, temporary storage locations, etc... that are costs to the company to make that happen. I do not see those costs in your description, and I wonder if sometimes the cost of buying a non-standard size/bundle is actually cheaper. I will ignore this complexity for now.
[2] Clearly, the problem is overwhelming you as it has too many parameters to jostle at once. A good problem solving strategy in such cases is to relax a few of the paramaters and get a solution for the relaxed problem. For example, I would start off assuming you are always ordering beams of the same nominal flange depth and the same pounds per foot. The examples discussed almost suggest you are indeed making this assumption, but I want to be clear. I would like to start here and steer you to a solution. Once we find a solution for this relaxed problem, we will add back one of the constraints and see what changes. We will then continue to iterativley add back in all the constraints until the original problem is solved. Is this approach ok?
HossFly
|
|
|
|
|
HossFly,
First of all, I cannot tell you how much I appreciate a timely and professional response. Such things are a rarity among most forums and message boards.
To address your first point raised; all cutting, grinding, welding, etc. is done by us in our shop. So the ammount of "shop hours" is billed seperately to the job. But that is a very good point I had not thought of.
As for your second point, yes, the problem is overwhelming me. I had thought of letting some of the parameters lie dormant for a short while, but it seems that every element of the problem is so closely related to the other - I am not quite sure of which parameters to drop. But I do like your recommendation of using the same beam size. I will try that and see if I can get a chunk of the problem diagrammed.
My biggest problem right now, is that I cannot seem to even write out on paper how this process works.
Thank you for your response,
-David
|
|
|
|
|
Alright, we can break the problem down even further. I do intend to honor your request and not provide source or solution, but rather help you attack the problem. Here is a suggested course.
Problem1:
[1] Assume nominal flange depth and pounds per foot are fixed.
[2] Assume there is only one standard size, and it is 30 ft.
Problem2:
[1] Assume Problem 1, but now allow for 30 ft or 35 ft standard sizes.
I think once you solve Problem1, and especially after you solve Problem2, you will understand how the 30-65 feet increments are impacting your solution. Let me know how that goes.
HossFly
|
|
|
|
|
I think you might be able to get a long way by using a multiple knapsack algorithm. The knapsack problem is to select a combination of N items with weights {Wi} to fill a knapsack with capacity K. The multiple knapsack problem tries to fill M knapsacks with capacities {Kj} from the N weights {Wi}. In your case the knapsacks are the available beamlengths. So if for one beam size the available beamlength is 20' and you need lengths {10', 6', 8', 12', 15', 2', 5', 7', 8'} then you need 73' of beam, so try to fill 4 knapsacks of 20'. If the algorithm fails, try to fill 5 etc...
One standard multiple knapsack code is http://www.netlib.org/toms/632[^].
Once you know how many beams you need you can then cope with bundling.
-- modified at 2:22 Saturday 22nd September, 2007
The multiple knapsack algorithm also allows you to include arbitrary beam lengths in your own inventory. So for the example given, if you had a 14' length of beam on hand, you could try to solve for 4 knapsacks {14, 20, 20, 20} and if this didn't work then add an additional 20' knapsack. This way you will continually use up your inventory
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
A request was made to give no source code, and it was requested in BOLD. Yet you gave a link to an algorithm and source. Incredible.
|
|
|
|
|
HossFly,
Thank you for helping me break down the problem like that. That was help much needed.
I think I have a good chunk figured out. I used one length and worked out how to nest the beams into that length with respect to bundling. It seems to be working very well, on paper. Right now, I input the beam(s) to be nested, and I nest them into lengths of 65', 60', 55', 50', 45', 40', 35', and 30' (all the standard lengths) one at a time. Each of the standard lengths is a function and returns two values; the total number of bundles (after making sure the beam meets the bundle requirements), and the amount of drop (unused portions of the beam(s) I am nesting into). Then I sort out which function returns the least amount of drop (as this will be the cheapest and most productive solution).
I think my next step is to do the same but for non-standard lengths (my only problem here is that I do not know how to round the lengths into even 6in. incriments). That way I can compare standard and non-standard prices. After that it's just a simple task of designing a report to output to the user.
But I still have questions about this method's efficency and/or actual optimization. Is there a test of some kind that you know of that can provide evidence for this? If not, don't worry about it.
Thank you again for breaking it down like that. I wish I had thought of that, but I guess that's why God didn't put me on the Earth by myself.
-David
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
