Skip to main content
Share Your Experience: Take the 2024 Developer Survey
11 votes

Why are search problems assumed to have the structure of "find a path in a graph"?

You are completely right: The problems we call search problems are typically problems that can be modeled as a graph problem. The general gist of it is that there are "states", "...
Pål GD's user avatar
  • 16.4k
9 votes

Why are search problems assumed to have the structure of "find a path in a graph"?

There are at least two meanings of the word "search problem". In one context, we use the phrase "search problem" to refer to searching for paths in a graph, or making a sequence of ...
D.W.'s user avatar
  • 160k
7 votes
Accepted

Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Reduction from 3-SAT: a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word. e.g. 3 SAT: (a,b,-c) && (-b,c) => pairs: (a,-a), (...
Albert Hendriks's user avatar
4 votes
Accepted

What is a search problem?

A problem is a search problem if there's an algorithmic way to verify the answer. In particular, let $V$ be any algorithm that takes two inputs and always terminates. Then the following is a search ...
D.W.'s user avatar
  • 160k
4 votes

Does White never lose in Chess if Chess is solved?

Let's take alternative chess. The rules are identical to chess, except that White can pass in it's very first move (but Black can't, even if White passed). Now it's obvious that White has a strategy ...
gnasher729's user avatar
  • 30.4k
4 votes
Accepted

Difference between cost and the heuristic function in A* search

Necessary heuristic function is needed for 2nd image, I can't tell why it's so in that image. But for the common A star algorithm, heuristic is an "Oracle" that guide algorithm to make "...
LighT's user avatar
  • 103
3 votes
Accepted

Does White never lose in Chess if Chess is solved?

This is unknown at the time of writing. Further, according to solving chess on Wikipedia, no resolution is expected in the near future.
Juho's user avatar
  • 22.6k
3 votes

Non-quadratic search for specific difference between elements in sorted array

I know of two. Sort the numbers, then walk 2 pointers from opposite ends towards each other, moving the left pointer rightward whenever the difference of the pointed-to elements is too small, and the ...
j_random_hacker's user avatar
3 votes
Accepted

How come Google search never gets slower? Doesn't it have to go through the ever increasing amount of data on the internet and then rank?

The google indexing and search is run in parallel using a map-reduce algorithm. As the number of pages to index expands, so does the number of computers that google uses for the task. Currently ...
Johan's user avatar
  • 1,080
3 votes

Extend binary search

Your problem is known as group testing. An essentially optimal algorithm for your problem is Generalized binary splitting. There are also pretty good non-adaptive algorithms (such algorithms fix all ...
Yuval Filmus's user avatar
2 votes

Better algorithm for aggregating data from various LDAP systems

Your algorithms seem fine. I don't think you need better algorithms; I suspect what would help most is more on the engineering and implementation side. At a high level, I would say that your design ...
D.W.'s user avatar
  • 160k
2 votes

Black-box combinatorial optimization problem over permutations

In general if you know nothing about f and it can be totally arbitrary, then there is nothing you can do: you cannot do better than brute-force. If f has no structure, no properties, no regularities, ...
D.W.'s user avatar
  • 160k
2 votes
Accepted

Is graph search of shortest (optimal) path an instance of optimisation?

Although I'm not sure what you're calling 'optimisation', I can tell you that both Dijkstra's algorithm and BFS are not some form of searching a solution space. If they were, they would start with an ...
Discrete lizard's user avatar
  • 8,248
2 votes
Accepted

Search vs planning in artificial intelligence

Short answer is "Yes". Long answer is "No": As far as I am concerned the difference is limited to a specific author/lecture: (to the best of my understanding of the slides) The author of the linked ...
Fleeep's user avatar
  • 151
2 votes

Does White never lose in Chess if Chess is solved?

Maybe it is worth mentioning why some kind of reasoning like White has a winning strategy because everything black does, white could have done before. does not work. You might already be familiar ...
ttnick's user avatar
  • 1,623
2 votes

$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right

A two-stage binary search works. First, for the purposes of this search define $0$ to be greater than any positive integer. Then, let $l = 1$ and $h = 2$ and: While $A_h \leq x$ let $l \leftarrow h$ ...
orlp's user avatar
  • 13.6k
2 votes

Can all types of computational problems be modeled as decision problems?

Yes. Every computation problem can be viewed as computing a function $f:\{0,1\}^ \to \{0,1\}^*$: on input $x$, the algorithm outputs $f(x)$. Here is a corresponding decision problem: given $x$ and $...
D.W.'s user avatar
  • 160k
2 votes

How to find long trails in a multidigraph

Here's a suggestion for a simple greedy heuristic to apply to the big SCC. It's based on the observation that a cycle of edges can be traversed a number of times equal to the minimum multiplicity of ...
j_random_hacker's user avatar
2 votes
Accepted

Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Graph canonization is well-studied, and there are sophisticated algorithms for it; see https://en.wikipedia.org/wiki/Graph_canonization. The standard answer is to use existing, well-tuned software, ...
D.W.'s user avatar
  • 160k
2 votes

How to find time complexity of Breadth First Search for this tree?

It's true, time complexity for a single tree doesn't make sense. Aysmptotic notations are used to get bounds of how the algorithm scales in terms of its input size. The usual time complexity for BFS ...
Rinkesh P's user avatar
  • 1,024
1 vote

Why is a regex search less efficient than a normal search?

"Linear scan" probably means the search can't backtrack. This guarantuees an O(n) complexity for the search. With backtracking it's possibly to get cases of exponential complexity. You might ...
kutschkem's user avatar
  • 462
1 vote

Question regarding the assumptions of the No-Free-Lunch-Theorem for Search

I think that I was indeed misunderstanding something. Any search algorithm that wants to evaluate any point $x \in \mathcal{X}$ through $f$ would implicitly add $(x,f(x))$ to the histogram $d$. For ...
asdfsolider's user avatar
1 vote

The best approach to search for closest object in hash map holding arraylist without changing data structure

If it is for some reason important to use hashing, there is a concept called locality sensitive hashing, however it is somewhat complicated. Typically, nearest neighbor search is done with tree ...
TilmannZ's user avatar
  • 764
1 vote

Need help with adding elements to hashtable with linear probing

It is the hash function h(k) that determines the position. They don't specify the hash function, but instead they give the value to which h(k) evaluates for both tables. The hash function is usually a ...
Paul Schutte's user avatar
1 vote
Accepted

Is Google search personalized?

I asked Google about that, and the second result was: Google personalizes search results even when you’re logged out, new study claims From there: Google says it still personalizes for location ...
ljleb's user avatar
  • 138
1 vote

Fastest algorithm to find whether a list contains a word?

If you are given an unordered list and asked to test whether just one item is in the list then a sequential check of each item in the list is the best you can do. If you want to carry out multiple ...
gandalf61's user avatar
  • 1,589
1 vote

Finding $k$-th element in prefix of size $i$

I misunderstood the original premise that A does not need to change. If you want a solution for that, a good one is to just apply the worst-case linear time ...
hLk's user avatar
  • 235
1 vote
Accepted

Kth smallest element in an arra

You can use quickselect with median of medians to find a good pivot so that the total running time is linear in the worst case.
Juho's user avatar
  • 22.6k
1 vote

Heuristics vs meta-heuristics vs hyper-heuristics?

Defining meta-heuristics as "heuristics designed to find, generate, or select a heuristic" seems too broad. A meta-heuristic is commonly understood as an algorithmic template that defines how ...
Marcus Ritt's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible