|
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.
|
|
|
|
|
Hello everyone! I am a fourth year IT student and I am now currently making my thesis. By this time, I am in the process of building a mathematical model in helping to identify the right products to be purchased as well as its corresponding quantity to meet the desired goals like having an increase of sales and minimization of product purchasing costs. By the way, my study is all about Decision Support Sytem applying the goal-seeking analytical modeling technique. Is there anyone who can help me on how to build the model??? I really need your expertise on this matter. Please help me to deal with this...
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
