Questions tagged [heuristics]
Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.
240
questions
1
vote
1
answer
339
views
Improvement Heuristics for Asymmetric TSP
i have been solving the Time-Dependent Traveling Salesman Problem using
an Ant Colony Optimization.
Upon reading the ACO papers, there are several reminders which state
that ACO performs best with ...
- 131
1
vote
1
answer
91
views
Movement on Labyrinth with Best First Search
I have the following labyrinth where R is the robot(the parent node), red blocks are the obstacles where the R cannot move and <...
- 119
1
vote
2
answers
261
views
What is the importance of disjoint edges in k-opt algorithms?
I'm trying to implement a k-opt algorithm and I'm bogged down on a detail: the importance of choosing disjoint edges.
My question: Is there any benefit to considering adjacent edges, or is the full ...
- 21
1
vote
1
answer
72
views
Distribution of beans in jars to k members
Here is the problem. We have N jars. Each jar can have any number of beans. These beans have to be distributed among C children. The resulting distribution should serve two goals Now
the number of ...
- 111
1
vote
1
answer
1k
views
How are the 1s and 0s derived by the minimax algorithm for the game called "nim"?
I'm having trouble figuring out why the 1s and 0s are where they are in this game tree for the game Nim:
There is a statement in the book that explains the numbers but it's still not clear to me,
In ...
- 113
1
vote
1
answer
315
views
Solving an ordered knapsack problem exactly with a non linear (blackbox) evaluation function
Thanks in advance for the help.
I have the following problem which, for lack of a better description, I'm referring to as the problem I've listed in the title.
Specifically I have a knapsack problem ...
- 111
1
vote
1
answer
184
views
Metaheuristic for NP-complete problem without exact algorithms other than brute-force
Computing Pure Nash Equilibria (PNE) is a Game Theory related problem.
Deciding if there exists PNE in a given game has been shown to be NP-Complete (Gottlob et al.).
I want to design a metaheuristic ...
- 1,314
1
vote
1
answer
309
views
Numerical Boardgame -- Help with with a pruning method (alpha-beta : minimax)
I'm developing a simple AI to play a boardgame which consists of N x N squares, each with a predefined value.
...
- 163
1
vote
1
answer
377
views
Local search: Problem with neighborhood definition
I have question on understanding the following neighborhood relation within a local-search approximation scheme.
Let $M$ be a legal matching on any bipartite graph.
Let $U_k$ be the neighborhood ...
- 13
1
vote
1
answer
5k
views
Why is Uniform cost search called "uniform" cost search?
By this possibly good attempt to explain this, the "uniformity" in the Uniform cost search is actually the uniformity of the heuristic function.
Is this explanation correct ? If yes, then don't all <...
- 113
1
vote
1
answer
49
views
What is a good heuristic for multi-point A* on a directed graph?
I am conducting a stateful search of a large graph in an effort to find some solutions of minimal cost. With an admissible heuristic for estimated time to completion from a given state (as in A*), I ...
- 11
1
vote
0
answers
139
views
Simplified Memory Bounded A*
I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
- 11
1
vote
1
answer
105
views
How to think about heuristics
I have a game about drone delivery company.
The game consists of a rectangular map, which contains tiles that cannot be passed. I can control a certain amount of drones, each one of them starts at a ...
- 131
1
vote
0
answers
87
views
minimising Longest-Path in DAG
Assume we have weighted DAG (directed-acycle-graph), source s and target t.
Define the number of edges as $E$.
Given $0<\alpha<1$:
Choose $\alpha*E$ edges to cut their weight by half so that the ...
- 11
1
vote
0
answers
232
views
Which non convex optimization algorithms guarantee a global optima?
Most non-convex optimization algorithms I have come across so far rely basically on random restart to find a better solution. e.g. Genetic Algorithm, Simulated Annealing, Metropolis Hastings Monte ...
- 289
1
vote
0
answers
19
views
Is there an heuristic for finding out the smallest height you can get when packing items in a tube?
It's sort of similar to bin packing, but instead of the minimum amount of bins,I was interested in just one infinite bin and finding out what's the smallest height you could get when you start packing ...
- 141
1
vote
0
answers
63
views
What is an example of meta-heuristic algorithm for solving Mario NP-hard problem?
Applying entertainment with computations is my main motivation in studying Computer Science, however, I'm still a neophyte to this field. While searching across the net, I came across this paper ...
1
vote
0
answers
39
views
Heuristic algorithm for the minimum weighted s-t cut with linear running time
To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $O(n^{2}\sqrt{m})$ time complexity. I'm interested in solving ...
- 253
1
vote
0
answers
241
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 ...
- 145
1
vote
0
answers
177
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 ...
- 1,113
1
vote
0
answers
365
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 ...
- 119
1
vote
1
answer
59
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 ...
- 13
1
vote
1
answer
1k
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 ...
- 153
1
vote
0
answers
90
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 ...
- 173
1
vote
0
answers
495
views
Prove that a convex combination of admissible heuristics is admissible
I got this question that's been troubling me for some time.
If $h_1$ and $h_2$ are admissible heuristic functions, prove that $h_3 = (c-1)\,h_1 + c\,h_2$, $0 < c < 1$, is also an admissible ...
- 111
1
vote
0
answers
102
views
Was the "cuckoo search" independently discovered before 2009? If so, what was the name given to it?
Background: I would like to experiment with evolutionary algorithms to generate the "optimal" poem, according to a fitness function to be determined later. However, I cannot think of a good way of ...
1
vote
0
answers
72
views
Difference between Memetic and Cultural algorithms
What is the difference between a memetic algorithm and a cultural algorithm? I mean they're both evolutionary algorithms where they select a subset of the population to apply some local search logic. ...
- 111
1
vote
1
answer
164
views
Is there any good way to judge whether the rectangle is inside the point cloud? [closed]
How to judge whether a rectangle in the figure is inside the given point cloud? For example, in this figure, the red rectangle is outside the point cloud and the green rectangle is outside the point ...
- 11
1
vote
0
answers
98
views
Neighbourhood design in Variable Neighbourhood Search
Variable Neighbourhood Search (VNS) is a metaheuristic for solving (combinatorial) optimization problems. It iteratively explores growing neighbourhoods to find better local optima in each iteration.
...
- 1,314
1
vote
0
answers
91
views
RINS: start - incumbent and relaxation solution have all different values
RINS: Relaxation induced neighborhood search, firstly introduced by Danna et.al in 2004 in "Exploring relaxation induced neighborhoods to improve MIP solutions"
I wanted to design an example how the ...
- 121
1
vote
0
answers
14
views
Symmetric Roles of the two problem solutions in RINS
Currently, I am reading the paper "Exploring relaxation induced neighborhood to improve MIP solutions" by Danna et.al. from 2004 and they are talking about a symmetric role of incumbent and the ...
- 121
1
vote
0
answers
128
views
Does the vehicle routing problem and variations have approximation ratios or a PTAS?
This is a somewhat big question since there are many variations on the VRP. The most studied seems to be the capacitated version, the CVRP, but variations considering time windows, backhaul/linehaul, ...
- 497
1
vote
0
answers
72
views
TSP heuristics for limited distance information [closed]
this is my first question on ComputerScience beta. :)
I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site.
Problem:
I'm looking for ...
- 111
1
vote
1
answer
115
views
Is there a way to predict rendering times? [closed]
In purpose of load balancing I need to approximatively predict rendering time my graphics software (in the specific case it's Autodesk Maya) needs to render a task given an input file (.ma/.mb) and ...
- 11
1
vote
0
answers
1k
views
Improving MSE as fitness function for a genetic algorithm
I am implementing an autoencoder neural network in matlab, the weights of which are being optimised by a genetic algorithm.
At the moment I am working on the first layer, trying to get an improved ...
- 657
1
vote
0
answers
57
views
0
votes
2
answers
4k
views
When does the nearest neighbor heuristic fail for the Traveling Salesperson?
Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem?
I was trying to construct a specific example of this for my friends and was failing.
- 11
0
votes
2
answers
245
views
Greedy Heuristic for the Traveling Salesperson Problem
We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any ...
- 463
0
votes
1
answer
2k
views
Longest Path A*, Admissible Heuristics, and Optimalness
Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path.
I have some ...
- 25
0
votes
1
answer
101
views
Hueristic Algorithm to find the maximum clique
Let the algorithm be defined as follows:
Consider the following heuristic algorithm for finding the maximum size clique
in a graph. (1). Delete from the graph a vertex that is not connected
to every ...
- 101
0
votes
1
answer
244
views
Heuristic function
Is there any way to prove that an admissible heuristic may not be consistent?
Most proof I came across are through examples .Is there a generalized proof?
- 103
0
votes
1
answer
47
views
Quickly pruning edges below average weight for a membership-based weighting
I have points represented as sparse high-dimensional binary vectors, or put another way, I have a list of groups that each point belongs to. For two points, the edge weight between them is $\sum_i 1/|...
- 1,721
0
votes
1
answer
82
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 ...
0
votes
1
answer
59
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 ...
- 251
0
votes
1
answer
122
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 ...
- 131
0
votes
1
answer
1k
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
0
votes
1
answer
498
views
Why to implement Open list in Heuristic search with priority queue
I don't understand why do we need to implement Open list using priority queue? There could be other data structure.
I understand the usage of priority queues from this example clearly. The newly ...
- 209
0
votes
3
answers
62
views
Heuristically determine a value f such that a probability d/f approaches 1/2
We have a set X of N elements. We want to get a new set X' having a size M < N.
...
- 221
0
votes
0
answers
10
views
A stagnation check for heuristics, especially simulated annealing?
I'm studying heuristics for a course in my Master's. Our professor has told us that in order to point to a higher grade in the exam, we should check if our algorithm hits a stagnation points and that ...
- 1
0
votes
0
answers
24
views
Manhattan distance always less node expansion than misplaced tiles heuristic?
I created a 8-puzzle search solver using BFS, A* with manhattan distance, and A* with misplaced tiles.
I generated data that said that for a particular random board, misplaced tiles did less node ...
