|
Thanks for the suggestion. If I'm following correctly then what I have is this:
1) Pick a random point
2) For each possible pair of other points calculate a value (I actually used area - it seemed to work better than total distance) and keep track of the highest scoring pair so far
3) Once I've checked every pair I now have three points that cover a maximum area of the space
The only thing I'm not sure of is the best way to expand this into more points (it's not critical that I do this right now, but I'd like to know). It seems that it would quickly get out-if-hand to do the same thing with all possible triples and/or quadruples, etc.
|
|
|
|
|
If you want the maximum area, you need to look at all triples instead of starting with a random point.
If there are a lot of points and/or you expand this into more points, it may be slow. Here's a possible shortcut: Determine the convex hull of your point set, and look through combinations of those (fewer) points.
The convex hull is roughly the outline / most extreme points in your set, so will probably have the points that enclose the maximum area.
There are many pages of convex-hull algorithms (e.g. http://en.wikipedia.org/wiki/Convex_hull_algorithms[^]) Try to find a simple one that can be easily implemented.
|
|
|
|
|
Hi,
Wjousts wrote: find two other points that are as far away as possible from the original point, but also as far apart from each other as possible.
That is two requirements, and they may or may not contradict each other.
Assume the same problem in one dimension; our example has 5 points at coordinate 0, 1, 2, 99, 100.
Now what are the points that meet your requirements with respect to the point at 0: is it 99 and 100 (maximizing requirement 1) or is it 1 and 100 (maximizing requirement 2), or something else?
You should first give an accurate requirement; if it is really unambiguous, you can then write a mathematical equation (a "cost function") or a software method that calculates how suitable a candidate solution is.
Once that is done, a suitable algorithm can be searched. For small problems, a brute force algorithm can be sufficient (i.e. just consider all possibilities, calculate all costs, and pick the lowest one).
For some cost functions, a smarter algorithm could be found, e.g. alpha-beta pruning might reduce the solution space.
|
|
|
|
|
Looking for the opposite of Djikstra's algorithm -- which finds shortest path between two points.
modified 29-Aug-18 21:01pm.
|
|
|
|
|
Firstly I'm sorry for writing this question here,because I didn't find the Java forum.Anyway I need to help for java code of DX-Ball.(Also I have to use Eclipse editor to do it).Is there anyone can help me about it? if there is please contact with me with meagle87@hotmail.com.
|
|
|
|
|
If you are looking for people to code for you that forum is located here[^]. Otherwise people generally only reply on the forums so posting your email is generally frowned upon.
Best of luck.
|
|
|
|
|
The Java forum is here[^].
|
|
|
|
|
To sum it up, I'm stuck trying to figure out how to implement a sample OPT cache replacement policy algorithm.
Its based on look ahead, I just can't figure out how to implement it in code.
I'm supposed to remove the item that will be called the farthest away from the currently called item.
Ideas?
TIA
[edit]
This had been previously posted in the C++ forum and then this morning I realized it was in the wrong place. My apologies. I have removed the original posting so as not to double post.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
modified on Monday, January 5, 2009 5:01 AM
|
|
|
|
|
Some more detail would be helpful. E.g. what's an "OPT" cache? (Google doesn't give any insight on this term.) What are you trying to accomplish? What distance metric is implied by "...the farthest away"?
|
|
|
|
|
This is the best description I can find[^]
Basically, the metric is the farthest memory location (or page if we're dealing with pages) is the one that gets victimized and evicted because other "nearer" locations will not cause a cache miss if they already exist.
I know exactly how the algorithm is supposed to go, I'm just having a problem translating that into code.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
|
The OPT algorithm as described in the link swaps out the page that's going to be needed the farthest in the future.
This is highly task dependent. You must have knowledge of your task's memory-use pattern in order to implement OPT. If you can describe this pattern, maybe someone can suggest an algorithm.
|
|
|
|
|
That's precisely it.
I'm building a simulator for a trace file that I have, so that the OPT can be compared to the other policies.
Its based on look ahead and that's what I've done and ended up with a cache's cache so to speak. I'm just not sure if I've done it right.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
|
Something in this[^] list might help. One thought would be to implement a BST as a base for this.
|
|
|
|
|
Extremely promising, thank you Pete.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
|
 Can you tell me how can i make more efficient algorithm for this problems?
We have a directed graph and a function of weight w we know that there is only one edge with a negative weight and that there is no cycle in the graph with negative weight we have s a vertex
We have to find an algorithm that find the length of all the shortest paths from s to every vertex of G
|
|
|
|
|
|
Lol I didnt realize that all the threads next to this one are also linked with A* ;o
You might take a look at those too.
|
|
|
|
|
The following is the C codes ,you can refer to it if needed.
#include<stdio.h>
#include<malloc.h>
#define MAXV 20
#define INF 32767
typedef struct
{
int edges[MAXV][MAXV];
int n;
} MGraph;
void Ppath(int path[],int i,int v)
{
int k;
k=path[i];
if(k==v) return;
Ppath(path,k,v);
printf("%d,",k);
}
void PRINTF(int dist[],int path[],int s[],int n,int v)
{
int i;
for(i=0;i<n;i++)
{
if(i==v) continue;
if(s[i]==1)
{
printf("from%dto%d,the shortestpath is：%d\t：",v,i,dist[i]);
printf("%d,",v);
Ppath(path,i,v);
printf("%d\n",i);
}
else printf("from%dto%ddoesn't exits a path\n",v,i);
}
}
void Dijkstra(MGraph p,int v)
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for(i=0;i<p.n;i++)
{
dist[i]=p.edges[v][i];
s[i]=0;
if(p.edges[v][i]<INF) path[i]=v;
else path[i]=-1;
}
s[v]=1;path[v]=0;
for(i=0;i<p.n;i++)
{
mindis=INF;
for(j=0;j<p.n;j++)
{
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for(j=0;j<p.n;j++)
{
if(s[j]==0)
{
if(p.edges[u][j]<INF&&dist[u]+p.edges[u][j]<dist[j])
{
dist[j]=dist[u]+p.edges[u][j];
path[j]=u;
}
}
}
}
PRINTF(dist,path,s,p.n,v);
}
int main()
{
int i,j,n,x;
MGraph p;
printf("please input the number of the vertex of the directed graph：");
scanf("%d",&n);
while(n!=0)
{
printf("please input the adjacency matrix of the directed graph：\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&p.edges[i][j]);
}
}
p.n=n;
printf("which vertex you want to search?(0--%d):\n end inputing with%d\n",n-1,n);
scanf("%d",&x);
while(x!=n)
{
Dijkstra(p,x);printf("\n");
printf("which vertex you want to search?(0--%d):\n end searching with %d:\n",n-1,n);
scanf("%d",&x);
}
printf("over!\n");
printf("please input the number of the vertex of the directed graph,
input 0 if you want to quit:\n");
scanf("%d",&n);
}
return 0;
}
|
|
|
|
|
|
I'm trying to figure out how to minimize the size of the search space for the A* algorithm.
I'm trying to solve the n-Queens problem using A*, and so, given a root and a goal, I create the intervening graph to be searched. That's fine, but the state space grows exponentially since its size in n^n (making n = 10 have a space of 10 billion items).
How could we deal with this?
Serialize and de-serialize?
The object is I'm trying to see how to build the SM-A* (Simplified Memory bounded A*).
Cheers
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
|
The simplest way to restrict a search space is to introduce appropriate constraints.
Alternatively, you could minimize some kind of heuristic function (defined on a per node basis) to pick the best possible search direction from any given node. The heuristic function will therefore only pursue searches from nodes at which it is minimized.
I don't know if some kind of Rapidly Exploring Random Tree might also be of interest.
|
|
|
|
|
73Zeppelin wrote: The simplest way to restrict a search space is to introduce appropriate constraints.
You mean like a maximum height for example? Or should I be thinking about generating them on the fly?
Like for example, where n == 4, if say the heuristics included that any queen should be in a column by itself, then the current node can generate 4 other nodes only if we follow the heuristic that one and one queen only will be moved up and down the column. This can be aided by the cost function, specifying a node with a greater number of constraints satisfied costing less.
Maybe the diagram expresses it better:
0 = empty
X = queen
when n == 4
A B C D
0 0 0 X 0
1 X 0 0 0
2 0 0 0 0
3 0 X 0 X
(1303 in compressed form)
Can generate any of 16 states (4 queens * 4 potential locations) or 12 states (4 queens * 3 potential locations if we decide that if a queen is chosen it must be moved to a location other than its present one)
So if we chose file D, the generated states to chose from are (generated states = n-1 heuristic):
(original)
A B C D A B C D | A B C D A B C D
0 0 0 X 0 | 0 0 0 X X | 0 0 0 X 0 | 0 0 0 X 0
1 X 0 0 0 | 1 X 0 0 0 | 1 X 0 0 X | 0 X 0 0 0
2 0 0 0 0 | 2 0 0 0 0 | 2 0 0 0 0 | 0 0 0 0 X
3 0 X 0 X | 3 0 X 0 0 | 3 0 X 0 0 | 0 0 X 0 0
(1303) (1300) (1301) (1302)
1302, the last one would have the smallest cost because it has the least number of conflicts, i.e. greatest number of constraints satisfied and it happens that it actually is a solution.
The closed queue's size can be maintained so that the search won't run to infinity.
Am I making sense? To me it seems like a viable solution.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
|
Generating on the fly using current available information about the state space is quite efficient (may or may not be "optimal", I'm not sure), in my opinion.
And it seems viable. It will, of course, require a bit of testing to make sure but offhand, it looks good.
|
|
|
|
|
Hello all.
I'm working on program decoding mpeg streams, decoding itself is performed on hardware - my code passes frames read from a file.
The problem is that I need recongnize i-frames. Is that information
contained in every frame or the frequency of i-frames in the stream is
in file header? I would appreciate any suggestions, links etc. (complete solution too).
|
|
|
|
|
that information is in the header of each Group Of Pictures,
MPEG TS {
Packet Elementary Stream (Video){
GOP {
### start code
header information <--- your mission, should you choose to accept it.
...
}
}
}
sorry for the late reply.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
