Questions tagged [heuristics]
Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.
189
questions
4
votes
1answer
61 views
Algorithm to create dense style crossword puzzles
I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of ...
0
votes
0answers
17 views
Least Constraining Value heuristic for graph coloring problem
The graph coloring problem involves assigning colors to vertices in a graph, such that no pair of adjacent vertices have the same color. I was given the problem to use least constraining value ...
1
vote
1answer
22 views
Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular)
Gradient descent sometimes works better than simulated annealing and vice versa.
Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one ...
1
vote
0answers
22 views
Is this a valid heuristic for Dots and Boxes to reduce the branching factor of the search tree?
I am implementing an AI based on the MiniMax algorithm that plays the game Dots and Boxes. I would like to reduce the branching factor of the search tree, by introducing a heuristic rule that limits ...
0
votes
0answers
17 views
What does the gradient mean in evolutionary algorithm?
I have been reading about evolutionary algorithms and I often find the concept of gradient that is used as "to follow a gradient"...
0
votes
0answers
31 views
A heuristic for finding an edge cycle cover
I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph.
In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
3
votes
0answers
26 views
Rearrange items in order reduce fragmentation and reduce wasted space
I have a segment with some offsets at irregular intervals
There are items of various length inside. Items cannot be placed randomly. Instead, their left side must match some offset.
Items are free ...
2
votes
0answers
36 views
Reaching local optimality in simulated annealing
I am currently reading about local search techniques. I understand that local search algorithms tend to get stuck in local optima and therefore usually do not find globally optimal solutions. Thus, ...
3
votes
1answer
107 views
Greedy Heuristics with an Altered Subset Sum/Partition Problem
Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, ...
0
votes
0answers
54 views
How do evaluation functions influence the optimal sequence of moves?
Assume you have a game tree and the features $(f_1, f_2, f_3,\ldots,f_n )$ that describe the state of the game at any node. Also assume that you are using depth-limited minimax and always expand up to ...
0
votes
0answers
139 views
What is the difference between nearest and cheapest insertion algorithms for a Traveling salesman problem?
I know that in the cheapest insertion algorithm we include the node which is not in the "base group" that has smaller cost given all possible combinations, and for the nearest we include the node with ...
1
vote
1answer
74 views
What is meant by a preemptive algorithm?
The definition on Google says 'serving or intended to pre-empt or forestall something, especially to prevent attack by disabling the enemy.'
So, how does this relate to an algorithm, especially the ...
0
votes
1answer
22 views
Comparison of constructive and local-search heuristics for TSP
In my high school class, we are currently looking at evaluating heuristic methods for intractable problems - especially TSP.
My question is what is the advantages or disadvantages of using a ...
2
votes
0answers
59 views
Matching of two weighted graphs allowing one-to-many mapping
I am looking for a heuristic for a graph matching problem as follows.
Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
2
votes
2answers
270 views
A* without heuristic more efficient than Dijkstra
I am using the module networkx to operate on graphs made from OpenStreetMap.
I wanted to compare the shortest path algorithm to ...
-1
votes
2answers
53 views
Can data be compressed through this hash function technique?
I'd like to know if this data compression scheme would work or not, and why:
Suppose we have a file. If we treat the bits that make up the file as the binary representation of a number n, we have n (...
4
votes
2answers
416 views
How do you prove a heuristic is admissible?
How does one prove that a suggested heuristic is admissible? Is this even possible?
For Example: Let's say I have the game Free Cell.
Rules: https://en.wikipedia.org/wiki/FreeCell
How can I ...
2
votes
1answer
67 views
Why is the usual simulated annealing algorithm using a Boltzmann probability?
I've coded a personal version for the simulated annealing problem, and I was wondering why, (other than by analogy to the physics), the probability is
$$ p = e^{-\dfrac{\Delta \text{length}}{T}}$$ (...
0
votes
0answers
45 views
What kind of standard deviation must be used in optimization algorithms?
I would like to ask about the standard deviation of objective function value.
There are two types of standard deviations:
Population standard deviation
Sample standard deviation
In metaheuristic ...
1
vote
0answers
172 views
Morphing Hypercubes, Token Sliding and Odd Permutations
A month ago, I asked the following question math.exchange (https://math.stackexchange.com/questions/3127874/morphing-hypercubes-and-odd-permutations), but for completeness, I will include the details ...
0
votes
0answers
252 views
How can an A* algorithm visit all nodes?
Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
0
votes
1answer
21 views
Term for an A*-like pathfinding strategy where only the heuristic goal distance matters
I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance ...
0
votes
1answer
72 views
Ant Colony optimisation for finding subsets with ~0 sum
I have a set A = [x1, x2...xn] where xi in R (real). I need to find all non intersecting subsets with subset sum ~0 (approximately equal to zero).
Since the set can have non zero real numbers, I have ...
2
votes
2answers
110 views
Does an optimal path imply the heuristic is admissible?
If we are given an A$^*$ path search with some heuristic $h$ that yields an optimal path, without knowing that the heuristic is admissible beforehand, would this imply that $h$ is admissible?
1
vote
1answer
131 views
Overall time complexity of Heuristical Algorithm for travelling salesman problem [TSP]
I am trying to figure out the time complexity of a heuristical algorithm used to solve the Travelling Salesman Problem in a more efficient way than by brute force, ($\theta(n!)$ or similar)
The ...
3
votes
1answer
31 views
Longest simple walk below a certain weight
Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight < $w$ that visits as many nodes as possible. Currently, I have a recursive ...
1
vote
0answers
172 views
Travelling Salesman problem using Guided Local Search
I am doing Week_4 of https://www.coursera.org/learn/discrete-optimization/
stuck in solving TSP.
As there are a lot of methods to solve this problem, I am currently coding
Guided Local Search as ...
0
votes
1answer
30 views
Defining Local Search stopping criteria
When performing a local search, for example, a 2-node exchange in a metaheuristic (like GRASP), what is the usual stopping criteria for that procedure?
Some bibliography says that the local search ...
0
votes
0answers
273 views
How MAC-3(maintaining arc consistency-3) algorithm works?
I am studying CSP problems in artificial intelligence. I don't understand the MAC-3 algorithm especially line number 10. Could you tell me with step by step?
...
6
votes
1answer
135 views
Optimal partitioning of n-tuples
Motivation
Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
1
vote
2answers
120 views
Choosing heuristic for A* algorithm where cost is less than absolute distance
Looking for information on choosing a heuristic for instances where the cost of traversing an edge can be less than one.
For example, say movement is allowed in the cardinal directions. Should all ...
0
votes
0answers
30 views
Relevance of the ZeroSum game to Heuristic search?
A question was posed to me as to the relevance of the ZeroSum game to Heuristic search algorithms.
I know that the zero sun game is a theory in which one persons gain is exactly balanced to another ...
1
vote
1answer
49 views
How to perform local search to find maximal induced subgraphs?
I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example.
What I mean by local ...
4
votes
1answer
165 views
Heuristics vs meta-heuristics vs hyper-heuristics?
The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic".
The wikipedia page on hyper-heuristics states that they are "heuristic ...
0
votes
0answers
47 views
can someone provide a good resource for understanding 2 opt heuristic?
I have looked into wikipedia and this MIT slide. A step by step iteration of the algorithm with a clear example would be appreciated.
0
votes
0answers
429 views
8 puzzle admissible heuristic where tiles are in correct position
For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once.
But ...
0
votes
0answers
32 views
How many states are examined in the most wins heuristic for tic-tac-toe (9-grid)?
I'm new to AI, and have a hard time to understanding how to count the total states are examined in the most wins heuristic for tic-tac-toe two plys deeper(9-grid)? Need help
-1
votes
1answer
157 views
How to prove if a heuristic function is admissible or not
Can somebody tell me how to solve this problem?
1
vote
1answer
503 views
Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?
I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first.
For example, should I start with one node; calculate ...
1
vote
1answer
658 views
A* Search Algorithm Implementation with Priority Queue
I've got a question regarding the A* search algorithm's implementation.
According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to ...
3
votes
1answer
176 views
Does domination rule apply for inadmissible heuristics?
Let's say $h_1(n) \geq h_2(n)$ so that dominance is established even if $h_1$ and $h_2$ are both inadmissible/non-optimal heuristics -in whichever given search space.
Is $h_1$ still faster/better ...
3
votes
2answers
52 views
Optimization Problem when calculating fitness is expensive
I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...
4
votes
1answer
2k views
Aren’t most constraining variable and least constraining value the exact opposite?
So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on
remaining variables but LCV is opposite: it tries to rule out as least values for other variables ...
0
votes
1answer
68 views
Steps to create a heuristic for solving a problem
I am completely new to AI and doing self-learning to acquire this knowledge.
I went through the different available search algorithm like BFS, DFS and A* but something that I can't understand is a ...
1
vote
1answer
39 views
What is the peak in fitness landscape
I have just started reading about fitness landscapes and I couldn't understand what the peak means. What does the peak mean?
2
votes
1answer
257 views
SAT Solving + Turing Machines
I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:
Randomness
Heuristics
Backtracking
SAT is just one example ...
1
vote
1answer
23 views
Justification behind this heuristic in SMA*+
I'm reading the paper Enhanced Simplified Memory-bounded A Star (SMA*+). In short, the authors propose a limited-memory version of A* where we cull nodes if we are out of memory, to re-expand them ...
0
votes
1answer
327 views
Consistent heuristic and A*
The following graph has consistent heuristic.
An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be ...
1
vote
1answer
20 views
How to get initial flow for TSP with missing edges
I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing.
How do I generate a valid initial path effectively?
I would use a greedy ...
1
vote
0answers
84 views
Comparison of time-dependent traveling salesman heuristics
I'm looking into implementing a heuristic for the time-dependent traveling traveling salesman problem (TDTSP) that completes in a certain amount of time.
There are a wide range of possible ways to ...
