|
A directed graph is called a unique-path graph if given vertices v and w, there is at most one path from v to w. Now, I am given a graph G in which there exists a vertex x that has paths to all other vertices. (The vertex x is not known to us initially) How do I check that G is a unique path graph in O(|E| + |V|) time?
Using the concept of strongly connected components, I can find the vertex x in O(|E|+|V|) time. How do I proceed after that? How does x help us in checking multiple paths between a pair of vertices?
|
|
|
|
|
What data do you have about the graph ? got a example ?
Have you tried something ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Hi All,
I am trying to come up with an algorithm to get following three piece of information to plot a chart:
1. Start : Should be close to the minimum value of the dataset
2. Stop : Should be close to the maximum value of the dataset
3. Interval : Should be such that it will have "0" on the axis when interval traverses from minimum to maximum.
Example: dataset{-266,-17.6,0.5,2000,6000}
My final return values should be:
Start: 400
Stop: 6000
Interval:200
Note: Since start is 400 and interval is 200, we will have 0 as a point on the x-axis.
|
|
|
|
|
How did you choose 400 to be 'close' to -266? Plotting the values from 400 to 6000 in intervals of 200 is a simple straight line. Your question is not clear.
|
|
|
|
|
400 value is in example. I came up with those numbers to explain what I am trying to achieve.
Actually, I did figure this out.
Thanks.
|
|
|
|
|
Hi all!
when this impulse based equation can equal to zero:
w'=w+(j/I)*r*n;
n normal contact;j impulse;I inertia;
modified 1-Sep-15 19:43pm.
|
|
|
|
|
What is your question ?
And I guess more details will be welcomed.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
as you know: https://en.wikipedia.org/wiki/Collision_response[^]
just that w will never be zero, and need always two points of contact to be;(the eqation above is elastic collision with rotation no friction)!
__________ \/__________
a triangle can never stand like this!(in a real world or can it!?)
see here(http://i.stack.imgur.com/o9P7V.png[^]
what if the ball was heading the center of the bar, the bar won't spin right!
but we know that a force in a direction in a center of mass mmake angular velocity zero right!
but this equation from wiki never make it until there is two points of contact, is that is!?
modified 2-Sep-15 8:34am.
|
|
|
|
|
Ok, the wording is not obvious for not English native people.
A couple of sentences explaining what you are looking for will not arm.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
|
Good day,
I have a DB, that have a 3000 strings and 40 integer columns, each of them describe something about 1 piece of product, for example, cost, resource, etc.
User type end sum for each column.
I need a feedback, what stack of 5 types of instruments fits max by each column to the user number.
For example, 7 hammers, 2 presses, 3 crowbar, 4 gloves, 5 glasses all together cost 154000 money, user input 150000, have a resource of 923000 hours, user input 920000 etc.
I don't know, how to google that question or use search for it, but if you can help me with it's name or, more of it, with building, i will release my end program under Open Source. Thank you very much for your time, sorry, if my English bad.
|
|
|
|
|
Knapsack problem? Bin packing?
|
|
|
|
|
It is looking like HomeWork !
I think some details are missing in the problem to fully understand what is the request?
It look like a simple counting problem.
What have you tried ? What is your problem ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Good day,
You can solve this problem by integer linear programming.
|
|
|
|
|
It is more like counting things.
like making a list of all names, and counting each you see a name
and printing the top 5 names.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
What have you tried so far in solving this?
"I've seen more information on a frickin' sticky note!" - Dave Kreskowiak
|
|
|
|
|
Consider a warehouse with a number of shelves(Bins) that have number, length, width, height and limit Weight capacity.
The Items that place in this warehouse are a number of cubes that have number, length, width, height and weight.
The algorithm must find the right place for Items so Bins have the lowest waste of space. and sum of weight of Items in each bin must not be more than its weight capacity.
Items are placed at the edge of Bins. Namely, any Items can't be placed on Items, behind Items and in front of Items.
____________
I tried to write my problem as an integer linear programming model.
I can't Upload Image Of My Linear Model So I Insert This Link: Here Is the link
[Click Here]
______________
I tried this algorithm:
1_ Sort list of bins Smallest To Biggest.
2_ Sort list of items Biggest To Smallest.
3_ insert each item in first bin that have free space, by best fit algorithm.
It worked but can't swap bins when it's necessary. In other words it is not an optimized algorithm.
please help me
modified 19-Aug-15 5:34am.
|
|
|
|
|
Please don't repost the same message if it doesn't appear immediately.
All three of your posts went to moderation, and required a human to decide if they were or were not spam.
I have deleted the "spares".
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
|
|
|
|
|
The ILP model allows items to overlap inside a bin, is that supposed to be possible?
|
|
|
|
|
|
Make copies of every item, one copy per "way it could fit in the bin", then ban combinations that overlap (for ex. in a 2x2x2 bin if you have an 1x1x2 item and a 1x2x2 item, then the case where the 1x2x2 is flat on the ground and the 1x1x2 item is standing upright is illegal). Also have a constraint that says that in total you will take the item exactly once (sum of all copies is 1).
|
|
|
|
|
Hi,
Already seen this question somewhere
What about giving your actual code and explain where you have a problem ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Hi
This is about my "project course".
The project almost completed by c#.
[^]
______________
I used a greedy algorithm to placing items in bins so it is not a optimized algorithm.
here is my placing function:
public static string placeItemInBin(Item itemToPlacing)
{
sortBinList();
LinkedListNode<Bin> binNode;
bool isPlaced = false;
int allSideStates = 1;
while (allSideStates <= 2)
{
binNode = listOfBins.First;
while (isPlaced == false && binNode != null)
{
if (binNode.Value.RemainLength >= itemToPlacing.Length)
if (binNode.Value.RemainWeight >= itemToPlacing.Weight
&& binNode.Value.Width >= itemToPlacing.Width
&& binNode.Value.Height >= itemToPlacing.Height)
{
LinkedListNode<Partition> partitionNode;
LinkedListNode<Partition> Best;
Best=null;
partitionNode = binNode.Value.parts.First;
while (partitionNode != null)
{
if (partitionNode.Value.num == -1
&& partitionNode.Value.size >= itemToPlacing.Length
&& (Best == null || partitionNode.Value.size <= Best.Value.size))
{
Best = partitionNode;
if (Best.Value.size == itemToPlacing.Length)
break;
}
partitionNode = partitionNode.Next;
}
if (Best != null)
{
string placingDetail;
if (Best.Value.size == itemToPlacing.Length)
{
Best.Value.num = itemToPlacing.Number;
itemToPlacing.CmPlaceInBin = Best.Value.cmBegin;
}
else
{
Partition newPart = new Partition(itemToPlacing.Length, itemToPlacing.Number,
Best.Value.cmBegin);
Best.Value.cmBegin += itemToPlacing.Length;
Best.Value.size -= itemToPlacing.Length;
binNode.Value.parts.AddBefore(Best, newPart);
itemToPlacing.CmPlaceInBin = newPart.cmBegin;
}
itemToPlacing.BinNumber = binNode.Value.Number;
binNode.Value.RemainLength -= itemToPlacing.Length;
binNode.Value.RemainWeight -= itemToPlacing.Weight;
binNode.Value.RemainVolume -= itemToPlacing.Length
* binNode.Value.Width * binNode.Value.Height;
isPlaced = true;
if (itemToPlacing.IsRotate == true)
placingDetail = "Item: Number: " + itemToPlacing.Number +
" (Rotated), Placed In Bin Number: " + binNode.Value.Number;
else
placingDetail = "Item: Number: " + itemToPlacing.Number +
" (Not Rotated), Placed In Bin Number: " + binNode.Value.Number;
return placingDetail;
}
}
binNode = binNode.Next;
}
itemToPlacing.changeSideState();
allSideStates++;
}
itemToPlacing.BinNumber = -1;
itemToPlacing.CmPlaceInBin = -1;
return "Not Found";
}
|
|
|
|
|
You should update your question with the code, so everyone will see it.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
How do you define Best fit or Wasted space ?
your optimisation is combinational !
Which mean that to best fit a packet, you may need to move another one, and the move can cascade until you find a combination of placement that is better.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|