|
By definition, a path is not a path if there is an "obstacle" (that cannot be overcome).
(Unless one considers / programs a "dead-end" as a "branch" / u-turn).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
It is a normal behaviour as RBFS is heuristic, so it discards some branches of the solution tree which may contain the solution. There are some heuristic algorithms, also for some graph problems, that find a solution which is not optimal but they at least find something close to the solution, which is satisfactory, whereas the other heuristic algorithms, when they miss the solution path, they will give you no results.
For finding paths in graphs, heuristic algorithms should be used only if you do not have enough memory for a regular BFS. They usually provide no solution if they miss them. I am now writing solving diamond peg solitaire with BFS, which should be ready within a couple of days on my site
informatyka-delphi.blogspot.com
If I am lucky, the graph will have up to 15 GB, compressed graph 4GB, so I shall find the solution with BFS.
|
|
|
|
|
I am trying to develop an algorithm which will be able to find minimum spanning tree from a graph.I know there are already many existing algorithms for it.However I am trying to eliminate the sorting of edges required in Kruskal's Algorithm.The algorithm I have developed so far has a part where counting of disjoint sets is needed and I need a efficient method for it.After a lot of study I came to know that the only possible way is using BFS or DFS which has a complexity of O(V+E) whereas Kruskal's algorithms has a complexity of O(ElogE).Now my question is which one is better,O(V+E) or O(ElogE)?
|
|
|
|
|
It seems reasonable to simply test both options instead of depending on hearsay.
Unlesss it's not that important; then just flip a coin.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Depends on how dense the graph is.
|
|
|
|
|
Hello,
Last week I studied aes gcm in lectures. But I fail to understand. Can anyone help to make me understand? Perhaps with explanations or schematic drawings. Thank you
|
|
|
|
|
|
On the link which you have shown all the explanations just discuss aes. Is aes gcm same with aes?
|
|
|
|
|
Don't you realize you could have Googled "Is aes gcm same with aes? - Google Search
Do you know how many lives your are impacting and how much life energy you are wasting?
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
|
<hi,
i am="" using="" sub-pixel="" edge="" detection="" algorithm="" implementing="" according="" to="" carsten="" steger's="" method.="" the="" output="" is="" a="" struct="" as="" following
struct="" contour="" {="" std::vector<cv::point2f=""> points; // edge location
std::vector<float> direction; // direction of the gradient in edge point,
// starting from y axis, counter-clockwise
std::vector<float> response; // amptitude of the gradient in edge point };
How do i use the data of direction and response parameters for drawing and what is the meaning of these parameters?
Thanks
|
|
|
|
|
I have a problem where I travel from point A to B and there is distance defined as `l`. In my car, I have a tank which can let me go only `b` kilometers. In `n` places there are gas stations and its cost for filling up my tank (I can only refill it fully). I start with a full tank.
What is the most efficient algorithm to get from the start of the highway to the end with the least cost?
My recent ideas:
Go with window sliding minimum algorithm to find (length is `b`) those stations where the cost is minimal. Code:
int n, range, targetDist;
scanf("%d %d %d", &n, &targetDist, &range);
int di, ci;
for (int k = 1; k <= n; k++)
{
scanf("%d %d", &di, &ci);
D[k] = di;
C[k] = ci;
}
D[0] = C[0] = bestcost[0] = 0;
for (int i = 1; i < n+1; ++i)
{
bestcost[i] = 1 << 30;
for (int j = 0; j < i; ++j)
{
int xx = bestcost[j] + C[i];
if (D[i] - D[j] <= range && xx < bestcost[i])
{
bestcost[i] = xx;
printf("(%d, %d)\n", i, bestcost[i]);
}
}
}
Input is:
3 8 4
2 1
4 2
6 3
Output is:
(1, 1)
(2, 2)
(3, 4)
So it corresponds to the cost to (i, cost(i)) - to get at i-th station, I have to pay cost(i).
How to find a minimal cost for whole distance with that information?
|
|
|
|
|
I found a way:
#include <vector>
#include <algorithm>
#include <deque>
#include <stdio.h>
typedef unsigned long long int ulli;
using namespace std;
void sliding_window_minimum(vector<pair<ulli, ulli>> st, ulli n, ulli targetDist, ulli range)
{
deque<pair<ulli, ulli>> minimize;
ulli j = 0;
for (ulli i = 0; i < n; i++)
{
if (st[i].first <= range)
{
while (!(minimize.empty()) && (minimize.back().second > st[i].second))
{
minimize.pop_back();
}
minimize.push_back(st[i]);
j++;
}
else
{
break;
}
}
for (ulli k = j; k < n; k++)
{
while (!(minimize.empty()) && ((st[k].first - minimize.front().first) > range))
{
minimize.pop_front();
}
if (minimize.empty()) {
break;
}
ulli tempCost = st[k].second + minimize.front().second;
while (!(minimize.empty()) && (minimize.back().second > tempCost))
{
minimize.pop_back();
}
minimize.push_back(make_pair(st[k].first, tempCost));
}
while (!(minimize.empty()) && ((targetDist - minimize.front().first) > range))
{
minimize.pop_front();
}
if (minimize.empty())
{
printf("NIE\n");
}
else
{
printf("%llu", minimize.front().second);
}
}
int main()
{
ulli n, d, b;
scanf("%llu %llu %llu", &n, &d, &b);
if (b >= d)
{
printf("%d", 0);
return 0;
}
int temp = n;
ulli d1, c1;
vector<pair<ulli, ulli>> st;
st.reserve(n+1);
while (temp--)
{
scanf("%llu %llu", &d1, &c1);
st.push_back(make_pair(d1, c1));
}
sliding_window_minimum(st, n, d, b);
}
|
|
|
|
|
|
Hello!
So I have this algorithm that outputs the highest value of an array:
Input: A[1,..,n], n>=1
Output: Highest value of an array
Maximum (A)
1. m = A[1]
2. i = 1
3. while i < n
4. if A[i+1] > A[i]
5. m = A[i+1]
6. i = i+1
7. return m
I have to prove this algorithm wrong and I'm confused how to do that, because to me the algorithm seems correct. Any advice on how to do this are very much appreciated.
Thanks!
|
|
|
|
|
What's wrong is lines 4 and 5. When i is one less than n , then you try to dereference A[i+1] , which is the same as A[n] , you will receive an access violation because arrays are indexed beginning from zero, not from one.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I was going to ask if his array was "zero-based", but his "spec" threw me off:
Quote: Input: A[1,..,n], n>=1
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Oh I see what you mean. You thought that he was specifying that HIS arrays were one-based. I guess it could be interpreted that way.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
But, if you take it that it is a 1 based array it will work, as demonstrated by the following bit of Python:
def maxi(A):
m = A[1]
i = 1
n = len(A) - 1
while i < n:
if A[i+1] > A[i]:
m = A[i+1]
i += 1
return m
modified 16-Apr-18 5:15am.
|
|
|
|
|
The error is in the line
if A[i+1] > A[i] It must be
if A[i+1] > m
|
|
|
|
|
Ha ha, the rest of us missed that.
|
|
|
|
|
<pre>import timeit
start = timeit.default_timer()
import math
def fequals(a, b):
return abs(a-b) < 0.0000001
def matmult(a,b):
zip_b = list(zip(*b))
return [[sum(ele_a*ele_b for ele_a, ele_b in zip(row_a, col_b))
for col_b in zip_b] for row_a in a]
def area(theta):
r = [[math.cos(theta), -math.sin(theta), 0.0],
[math.sin(theta), math.cos(theta), 0.0],
[0.0, 0.0, 1.0]]
v = [[1], [-1], [1]]
point = matmult(r, v)
return abs(point[0][0]*point[2][0])
def position(theta):
r = [[math.cos(theta), -math.sin(theta), 0.0],
[math.sin(theta), math.cos(theta), 0.0],
[0.0, 0.0, 1.0]]
c_o= [[0.5, 0.0, 0.0],
[0.0, 0.5, 0.0],
[0.0, 0.0, 0.5]]
result = matmult(r, c_o)
return(result)
def OptimizeTheta(A):
if fequals(A, 1.0):
return position(0.0)
elif fequals(A, 1.414213):
return position(math.pi / 4.0)
l = 0.0
m = math.pi / 4.0
while True:
mid = (l + m)/2.0
a = area(mid)
if fequals(A, a):
return position(mid)
if a < A:
l = mid
else:
m = mid
t =int(input())
for i in range(t):
A = float(input())
cube = OptimizeTheta(A)
print("Case #{}:".format(i+1))
print(cube[0][0], cube[1][0], cube[2][0])
print(cube[0][1], cube[1][1], cube[2][1])
print(cube[0][2], cube[1][2], cube[2][2])
#GHOST999
stop = timeit.default_timer()
execution_time = stop - start
Beyond value 1.41...
it becomes extremely inefficient..
appreciate any help..
|
|
|
|
|
and this algorithm is ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
In what language was the code written?
|
|
|
|
|
|