|
Hi there, I have an algorithm which searches a graph for Hamiltonian cycles. A graph is a bunch of nodes, with edges (connected with probability p each). A Hamiltonian cycle is a path along the edges from one node back to itself- passing through each node precisely once.
My algorithm currently does the following procedure:
starts at node 1
tries to increase the path to 2 vertices, call it 1,final node.
Algorithm:
if final node in path has a neighbour not already in the path, extend it by going to the first neigbhour it has in a list
if final node has no neighbours then remove final node and search the list of (final node - 1) for other potential neighbours.
(output if Path has length n and final node is connected to node 1)
This algorithm has a worst case complexity of n!. I.e if there n nodes and it visits everypath but can't find a hamiltonian cycle.
But what would be the average case running time given n and p?
|
|
|
|
|
Try your code using my Big O Algorithm Analyzer.
Big O Algorithm Analyzer for .NET[^]
It will show you the running time verses the n, you might have to create a Big O function to calculate p, I can't understand why this would be n! though.
Let me know if you need some help using the tool.
|
|
|
|
|
This can't be a new problem, but I don't see any code out there for it. An application I'm working on accepts input in Unicode, so most things work with Japanese characters, but there are a couple of names that I need to generate in ASCII. I have a base name to work from in Japanese (Hiragana or Katakana) and would like to use Hepburn or ISO_3602 romanization to convert into ASCII. There are various tables out there that I could use for this purpose, but I thought I'd check here first.
Has anyone out there solved this problem who's willing to share?
Thanks
|
|
|
|
|
Well, I have no knowledge on the language, but couldn't you just create a look-up method?
|
|
|
|
|
So far i have made the snake move about, eat randomly generated food pieces and the peices attach to the end of the snake, i need help on figuring out how to move the "segments" attached to the head of the snake.
For example a snake moving right works fine,
----->
But when i press down this happens:
|
|
|
V
When it should be:
-----
.....|
.....V (dots represent a space as this WYSIWYG doesn't allow me to have spaces)
Any ideas? Thanks
|
|
|
|
|
Hi,
1.
when you use PRE tags, you get a non-proportional font, and spaces work as you would expect.
2.
you need to hold the playground in memory, maybe as a 2-dimensional array of integers.
you could initialize it at all zero (=empty cells); then set one or a few cells to consecutive numbers (1,2,3,..N) where the highest number is the head and the lowest non-zero is the tail of the snake.
Moving it means adding the next number to the right/left/top/down position of the head, depending on current direction; and probably also removing the lowest non-zero, unless you want the snake to grow.
[CLARIFICATION ADDED]: in one dimension the snake could move
from 0 0 1 2 3 4 0 0 0
to 0 0 0 2 3 4 5 0 0
, so the head was 4 and now moved to 5, while the tail was 1 and moved to 2. You keep a pointer to the head and adjust it in the right direction; and you keep a pointer to the tail, search the neighbour that is one higher, and that becomes the tail.[/ADDED]
3.
and then you should visualize all this in the Paint handler, as I explained here[^].
modified on Wednesday, January 13, 2010 8:41 PM
|
|
|
|
|
I would actually store the snake's head index, tail index, and current direction. Then, store a 2D grid such that each cell can have one of three values: empty, snake, or new_segment, based on the contents of that cell. At each time step, move the head in the current direction by updating the head index, and test the value of that cell. If the value is "snake", there is a collision. If the value is "new_segment", draw the head, change the value to "snake", and continue to the next time step. Finally, if the value at the head index is "empty", erase the tail, search the four adjacent cells to find the one with a "snake" value (that isn't the head index), and set the tail index appropriately.
This approach has the following complexities:
Memory usage: O(grid_size)
Moving the snake: O(1) (assuming you use arrays with constant access time)
Redrawing the snake: O(1) (you only have to update at most two cells)
Testing for collisions: O(1) Hope this helps,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
I'm not sure that is good enough, if zero-gap meandering is allowed (it seems it is in such games), then the tail would not know where to go, as in:
0 0 0 0 0 0 0
0 1 4 5 6 7 0
0 2 3 0 0 0 0
where 7 is the head, 1 is the tail, and the problem is which square to vacate after 1 is vacated.
|
|
|
|
|
Ah... then perhaps there are still three states: empty=int.MaxValue, new_section=int.MaxValue - 1, and other=moveCount % (int.MaxValue - 1) (if it is not possible to have a game where int.MaxValue - 1 moves are made, then forget the modulus to save time. Also be sure that grid_height * grid_width < int.MaxValue - 1). Basically, I was trying to suggest the possibility that the number assigned to each cell was not necessarily the location of that cell in the snake. This allows a move to be performed in O(1) time instead of having to iterate through each snake segment and decrement it to reflect the snake segment on that tile. I think you were suggesting the same thing, but after reading your post I didn't know if that was clear to the OP or not, so I tried to expound upon it even though I probably just added to the confusion with my buggy approach. Thanks for the catch!
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
I think you misunderstood my proposal; I'm not reworking the whole snake on each step of its journey: I add a head (like you do), and I replace the current tail by the cell that is numbered one higher, so if a snake is 1-2-3-4 at one point in time, it is 2-3-4-5 the next, etc. So it is as O(1) as yours, and has a similar limitation as I must end the game, or do something very special, when the head would overflow (an easy trick would be to use odd values only for the snake cells, i.e. increment by 2; that would work fine except for very complex paths on huge boards).
BTW:
Skippums wrote: there are still three states: empty=int.MaxValue, new_section=int.MaxValue - 1, and other=moveCount % (int.MaxValue - 1)
if the state variable can range from 0 to int.MaxValue, few people would call that three states 
|
|
|
|
|
Luc Pattyn wrote: I think you misunderstood my proposal
Exactly! When I first read your post, I thought, "Why would Luc suggest such an inneficient algorithm?" I knew you wouldn't suggest such a thing, so I reread your post. After a few reads, I finally comprehended what you meant, and thought that it could use some clarification. Unfortunately, I clarified it right into buggy software, but I think you get where I coming from .
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
Sorry about that; I now added some clarification to the original message.
Thanks.
|
|
|
|
|
Hi 'thebuzzwright',
> So far i have made the snake move about, eat randomly generated food pieces and the peices attach to the end of the snake, i need help on figuring out how to move the "segments" attached to the head of the snake.
I just wanted to add that I have a freeware open source version of the Snake game, written in Borland Delphi 5 (no longer owned by Borland any more. See: embarcadero.com for the latest trial versions of Delphi or google for 'free Delphi compiler download' to find older free versions of Delphi).
https://downloads.embarcadero.com/free/delphi[^]
... for M$ Windows (almost all versions). You should also be able to port it to other versions of Delphi or even convert in to Lazarus programming language (available for M$ Windows, Macs & Linux). Delphi and Lazarus are essential Object Oriented Pascal with a GUI (Graphical User Interface) RAD (Rapid Application Development) interface.
I would recommend Delphi 3 or 5 or 7. Standard is fine (named 'Personal' in later versions) however, with the later forms of the compiler e.g. Professional or Enterprise version (and later Architect)... they can be very expensive and also have a very large foot-print (e.g. size of installed files and folders) but they will also have the source code for it's units included with the compiler. This is handy if you need to re-compile it's own units (not usually necessarily) and also if you want to look at the code for one of Delphi's own unit or form files to see how they have implemented some of the code to achieve a particular task.
Alternatively, Lazarus compiler is very good... however, note also that the compiler is constantly being developed and re-programmed and tweaked and developed ... so you will need to find a 'repository' for the 'snapshots' of the compiler and download it and compile it... There are different versions for different OS's and also different versions of the compiler -- some of which are considered stable code and some contain experimental beta version of the compiler (RAD GUI). Just google for it.
My Snake Game
=============
Here is a link to my freeware open source version of the Snake game in Delphi 5. It is based on an earlier version of it by someone else, which I debugged and made some changes to. It was also written in Delphi (possibly ver 4 or 3... I forget, as this goes back years). There is also a link to the older ver in the code, and possibly also the code of the ealier version *may* be included.
http://sites.google.com/site/pewtas/delphitable2#SNAKEGAME[^]
Note that there are some nifty new features which I added, like being able to have the borders ON or OFF. When the border are OFF, you can move thro' the borders (or walls) and the window for the snake simply wraps around e.g. left and right borders join and so do the top and bottom borders. I also added numerous tweaks and debugged it quite a bit and re-wrote some of the code and declarations (e.g. type-declaration -- to make it more structured and/or more readable).
Regards,
PEW  ))
from Hobart, Tasmania, AustraliaPeter E Williams ))
|
|
|
|
|
Thanks for that very helpful !
|
|
|
|
|
I have a 2D scene defined as a series of segments (like a GL_LINES section from OpenGL or Line from Direct3D). Each segment have a starting and an ending point. These segments can be joined at one end or not.
I want to find inside this scene the rectangle which :
a) have the interior completely free (no segment can cross its boundaries - might touch them thou);
b) have his sides parallel to Ox and Oy axes;
c) have the biggest area;
d) have the center closest to a specific point (Xref,Yref);
e) have a certain aspect ratio H/W.
Conditions a) and b) are mandatory. Condition c) have priority over d) and d) over e) meaning it is more important to be bigger than to be closer to Xref/Yref which it is more important than having a specific aspect ratio (how to quantize "importance" - I'm open to suggestions).
I only need ideas/hints how to solve this problem (if it is solvable) - I'll manage the implementation regardless of complexity.
Thank you
|
|
|
|
|
Hi,
how about this:
1. start with "infinite" values for dLeft, dTop, dRight, dBottom;
2. consider the rectangle from (Xref-dLeft, Yref-dTop) to (Xref+dRight, Yref+dBottom);
3. now iterate over all segments and reduce dLeft, dTop, dRight, dBottom so they just match your criteria
this should meet a,b,d
you can amend 3 to try and get (c) and/or (e)
refinement: when you have a choice how to keep a segment outside your rectangle, provide either a recursion (might be too costly), or a backtracking algorithm to analyze different alternatives.
|
|
|
|
|
Yes, this was my first thought when I bump into this ugly problem.
Already tried it and does not work properly, that's why I came here for help.
Most of the times I have lines starting exactly from (Xref,Yref) or crosing that point or so close that the resulting rectangle is too small - the closesness thing : if I'd be just a little bit off (Xref,Yref) the rectagle might be bigger.
The second issue : granularity. All points coordinates are double precision - I did a "step up" based on (Xmax-Xmin)/somthing big - but looks very ugly when you zoom in the scene to fit the result.
And the third issue : performance - I have roughly 30K-40K lines per scene and I have to find ~700 enclosed rectangles. I've managed to break the scene into smaller pieces, but still it takes a lot of time.
I observed that selecting the "proper" Xref/Yref point makes all the difference - the more free space around it the better the result (actually this sounds like a problem in itself) ... but I cannot find a way to select it (now I'm fiddling manualy with the coordinates).
Edit: "inside" the scene means inside the culling polygon around the scene
modified on Sunday, December 27, 2009 9:54 AM
|
|
|
|
|
I have given it some thought, this is definitely no easy problem. I'm starting to think that there is no polynomial algorithm for this..
It would have been easy if your lines were lines rather than segments.. but they aren't.
But there might be shortcuts, what more is known about those line segments? Do they, on average, cross most of the scene or are they mostly tiny? Are they usually connected to each other or usually separated?
How much can we relax condition C?
|
|
|
|
|
I know this is a hard one ... I've been trying to find a workable solution for a week now.
So ... they are segments indeed - nothing to do about that. But any idea if they weren't is also welcome. (I've tried something where each polygon is just a intersection of semi-planes plus a lot of orientation vectors, but nothing has come yet ...)
What these segment represent ? Shapes - 2D slices through complex mechanical 3D objects or assemblies manually retouched (rightfully or not). Or in the worst case a series of slices one over the other in the same spot (actually this is more the case - I have very few simple shapes). There is nothing specific about them in the meaning they are either closed polygons or not, concave/convex or not or undefinable. They are somehow grouped (per initial object), but doesn't follow any logic in the order of definition. I found simple rectangles defined by 4 segments in 1,2,3,4 counterclockwise order starting from the top as often as 1,3,2,4 (side - opposite side). Arcs/circles/curves are defined as a fragmented series of segments, but not necessarily in order. Don't start me on the more complex shapes. But I did managed to order them so they follow a logic order (ccw from Ox) and where they intersect I broke each of them in two so I can have only adjacent polygons and not crossing ones. (The actual definitions for these shapes comes from some dxf files - if it matters). But I still have single segments not connected to anything else.
As per condition c) ... that is the biggest problem : I need the biggest rectangle where I can fit something without touching anything else.
Where I can be a little malleable is the (Xref,Yref) point. This is now the geometric center of culling polygon that enclose the original object.
|
|
|
|
|
Hi,
here is another idea:
1. before drawing the segments, create an imaginary grid, where each cell has a certain height and width, say 64 pixels.
2. place the segments, and mark the grid cells that get (partially) covered by them.
3. search an unmarked grid cell, and now look for the largest rectangle of empty grid cells containing it
4. only then enlarge the rectangle using actual coordinates instead of grid indices.
|
|
|
|
|
If I would thinking in bitmaps/pixels this might work. But I don't have pixels, I don't have a moveto/lineto/floodfill algorithm, I only have coordinates ... a math approach is what I'm hoping for ... if exists ... however complicate that might be ... On performance I will think after that.
Think of this problem like a "inverse"/"reverse" convex hull problem. There you have to find the smallest polygon which enclose a scene, I need the biggest free one inside the scene (sort of anyway).
|
|
|
|
|
Hi,
third, partial and final attempt:
assume an unknown point px,py is inside the rectangle you want;
if you were to apply the conversion:
x' = 1/(x-px)
y' = 1/(y-py)
then (px,py) would map on infinity, and you would really be looking for a convex hull.
Maybe what you should do is try a couple of (px,py) points in the neighbourhood of your point of interest.
BTW: The problem of course now is your shapes look all different, so it may be more difficult to locate their extreme points.
|
|
|
|
|
I've tested this just now using memory-mapped bitmaps. It works in the meaning that it finds the biggest rectangle (actually all the rectangles, then I chose the fittest) ... But this walking pixel by pixel on a segment (grid cell is 1x1) ... arghh . I still hope there is a math solution to this.
|
|
|
|
|
Hmm,
I am having a problem visualizing the problem. I'm looking at some examples of problems of this type on Wolfram|Alpha:
Pappus graph[^]
The problem in the example seems to have the same characteristics as your problem and it is pure mathematical solution. My conclusion is that you need some sort of graph algorithm.
Can you give a simple example using geometric terms? So I can visualize the problem better? I would like to help...
|
|
|
|
|
Okay I have a veague idea of what you are trying to do. Here is how I would attack it.
Daniel.Sturza wrote: a) have the interior completely free (no segment can cross its boundaries - might touch them thou);
Use the 'Bentley–Ottmann algorithm':
Bentley–Ottmann algorithm[^]
Find the intersections of points, dump these into a point graph (tree graph, using an algorithm which indexes the roots and children, etc.), for each graph that does not cross a segment add to an 'exclusion graph'.
Next Find the max area of space occupied by exclusion graph (interior completely royalty free):
Distance transform[^]
-or-
Shoelace formula[^]
The input would be the exclusion graph's. For each graph in the stack find the largest area, add to an 'area graph'. Here you migh need to also jump to step #b first to find the correct rotation or merge this into one step.
Daniel.Sturza wrote: b) have his sides parallel to Ox and Oy axes;
Rotating calipers algorithm[^]
This algorithm does some rotating, so I'm not sure if it is good for your (Ox, Oy) points. What are Ox,Oy? The algorithm is good for any poly or hull.
Daniel.Sturza wrote: c) have the biggest area;
This should have been found in step a.
Daniel.Sturza wrote: d) have the center closest to a specific point (Xref,Yref);
Jump-and-Walk algorithm[^]
This is a triangulation algorithm, my guess is that it can be adopted to your needs.
Daniel.Sturza wrote: e) have a certain aspect ratio H/W.
No idea what aspect ratio would be. I would be using vector graphics of some sort, so the hull algorithm you are using should do this for you?!?!
Then again this is all brain storming and it might be more like 'day dreaming' Ha,ha,ha. Hope this gives you some ideas...
Another bazaar approach might be to create a Voronoi Diagram of all points, then for each segment connect the points, if the point moves through an area described by the Voronoi Diagram then remove the area from the diagram. After all points have been connected you will be left with areas excluded by the segments and then you can find the max rectangle.
Voronoi Diagram[^]
-And-
Largest empty rectangle[^]
A Fast Algorithm for Finding Maximal Empty Rectangles for Dynamic FPGA Placement[^]
~TheArch
modified on Monday, December 28, 2009 3:31 PM
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
