Questions tagged [search-algorithms]
Algorithms for finding an element in some specified data-structure (most commonly, in a tree).
711 questions
0
votes
1
answer
15
views
Find coordinate in ordered-dithering matrix
The Bayer index matrix for ordered dithering can be computed as follows:
...
- 101
0
votes
1
answer
72
views
You are given two unsorted lists $R$ and $C$ of possibly different sizes containing elements from the same universe. Find a Balancing Split
For any value $v$, the list $L$ is split into two sublists $L_{low}$ and $L_{high}$.
$L_{low}$ has all values in $L$ which are less than or equal to $v$.
$L_{high}=L-L_{low}$.
The balancing split is ...
- 118
1
vote
1
answer
72
views
What do you call the two most common ways of selecting a random leaf node from a tree?
If you have a tree, there are two common ways to select a random leaf node from the tree:
You can "flatten" out the tree, so that each leaf node gets selected with the same probability.
...
- 11
3
votes
1
answer
147
views
Interesting pattern in $k$-ary search
I was playing around with $k$-ary searches, and found something interesting:
This is the $\log(\frac{\text{time}}{\text{binary time}})$ to find an element in an array of length $100$ averaged over ...
- 81
8
votes
1
answer
1k
views
Switching bodies to get everyone back to their correct body?
Yamada-kun can switch bodies with anyone he kisses. So first he kisses A, and switches into their body. Then, as A, he kisses B and switches into their body (and now B is in A's body). Then, as B, he ...
- 652
0
votes
0
answers
36
views
Shapez2 Shape Crafting Optimization Problem
This is an algorithmic challenge from the factory game Shapez2, essential for building what's known as a TMAM (True Make Anything Machine).
I’ve been researching this problem over the past month. ...
- 1
2
votes
0
answers
89
views
How to generate a minimal sequence of lazy pair swaps to cover all N! combinations of a list of N-elements?
I'm trying to find a method to quickly generate all index-pair sequences for the following problem:
Given a sequence of N elements, find the shortest sequence of lazy pair swaps (i, j) — where each (...
- 21
2
votes
1
answer
118
views
Z3 Exploration into Euler's Sum of Powers Conjecture Counterexample
I am trying to use z3 to come up with Ladner and Parkin's counterexample of Euler's Sum of Power's Conjecture which is a generalization of Fermat's Last Theorem.
Euler's Sum of Power's Conjecture :
...
- 103
1
vote
1
answer
155
views
Tree Search $A^*$ With an Admissible Heuristic Does Not Necessarily Return an Optimal Solution
I know that the title of this post is wrong, but I got stuck on an example. Consider the graph below, which I obtained from here.
To the best of my knowledge, the tree search version of $A^*$ fails ...
- 111
0
votes
1
answer
109
views
Complexity of peak finding algorithm for N dimensions
I am totally new in this area.
Lets say we have a list of random numbers and we have to find one peak value (only one is fine), and a peak is if $a \geq$ than its both neighbours (or one if it is in ...
- 103
0
votes
0
answers
56
views
Generating tuples with a range for average
I am trying to generate 67 distinct tuples with a certain avaerage but my method is not working (can't even find 1), is there are a way to do this that will be quicker? Here is my code:
...
- 1
0
votes
1
answer
62
views
Is there an A*/D* variant for graph where path to destination is unraveled based on whether it's closer to the destination?
I have a few constraints in my path finding application for source to destination routing on a map:
Server has a huge map and Client can only query a small chunk of it at a time because of data ...
- 101
1
vote
2
answers
94
views
Finding two disjont longest possible vertical or horizontal lines in 2D matrix with non-usable cells
The problem is to find two disjont longest possible (but with equal length) horizontal or vertical lines in given 2D matrix, where some cells are excluded from use. The disjont means that any cell ...
- 65
1
vote
2
answers
103
views
O(N log N) algorithm/implementation for maximum inner product search
I am in a situation where I have a query space Q and a key space K, both filled with N d-dimensional real vectors (N ≈ 10^6, d ≈ 50). For each query q, I want to find the k≈10 keys k_i that have the ...
1
vote
1
answer
58
views
Best Search Algorithim
In Microsoft Power Bi there are formulas that can be used in visualizations called measures. These measures can be used within the formulas of other measures.
As a result, a measure can have a complex ...
- 11