Questions tagged [heuristics]
Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.
218
questions
0
votes
0answers
37 views
How to build a data-structure for a moving points
Problem:- I have moving points in a 2d space with a fixed obstacle(A polygon) and a fixed destination. I want to find at what time Source(which is moving) can get a path to destination and what is ...
2
votes
1answer
63 views
Why the choice of the adjacent vertex with the least degree is a good heuristic for the hamiltonian path problem?
Even if the hamiltonian path problem is NP-hard there exist heuristics which return a correct path for many instances in linear time. In particular one of the main rules is always choosing the ...
4
votes
1answer
75 views
Warnsdorff's rule: more errors with odd sized boards
I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
1
vote
1answer
39 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 ...
2
votes
0answers
45 views
Can A* with an inadmissible heuristic still be optimal?
It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...
1
vote
1answer
27 views
Heuristics for a variant of the traveling salesman problem
I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset.
...
7
votes
1answer
106 views
What is the approximation ratio of this bin-backing algorithm?
Consider the following algorithm for bin packing:
Initially, sort the items by their size.
Put the largest item in a new bin.
Fill the bin with small items in ascending order of size, up to the ...
0
votes
0answers
17 views
How to solve this grouping problem heuristically?
There are $S$ servers in the system.
There are also $M$ computers in the system.
Each computer shows different efficiencies when they are connected to different servers.
Lets say, for computer $m$, ...
1
vote
0answers
51 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 ...
1
vote
1answer
26 views
CVRP and removing edges from a graph
I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances.
I know that, in general, the complexity of ...
1
vote
1answer
81 views
How do I solve a search problem on an infinite graph?
I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \...
1
vote
1answer
60 views
Grasshopper Optimization Algorithm
I am currently reading a paper on a meta-heuristic called 'Grasshopper Optimization Algorithm'.
The main idea of the algorithm is to utilize the social behavior of grasshoppers in a swarm to solve ...
-1
votes
1answer
21 views
A very simple question about Admissible Heurisitcs
Given admissible heuristics f(s), g(s), h(s).
It is true that max(f(s), g(s), h(s)) is still admissible.. but is it still admissible if its max(f(s), g(s) + h(s)). I believe it is not admissible but I ...
6
votes
0answers
83 views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
2
votes
1answer
56 views
Optimization problem over bidirectional connected graph
A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators,...
4
votes
1answer
134 views
One-dimensional packing problem: Optimal decomposition of music structure
I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music.
Problem Description
Given a ...
2
votes
1answer
50 views
Graph partition that maximize the number of triangles within its parts
Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal?
This ...
1
vote
1answer
48 views
How can I make the variance of a multiple sum of set of fixed number of variables minimum?
Here is the problem:
There are $MN$ people, where there are $M>1$ seeds and $N>0$ people are in each seed.
We have to make $N$ teams of $M$ people where everyone in the team have different seeds....
2
votes
0answers
28 views
Messy Representation Encoding example
I am currently working through Metaheuristics by El-Ghazali Talbi where he discusses encodings of algorithms.
"Messy representations: In linear representations of fixed length, the semantics
of ...
1
vote
1answer
35 views
Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points
I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a ...
2
votes
1answer
49 views
How important is initial state for local search optimisation?
I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation.
I'm wondering how important the ...
0
votes
0answers
25 views
Minimizing the length a Boolean Algebra Expression in disjunctive normal form
I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
1
vote
0answers
166 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 ...
1
vote
0answers
15 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 ...
1
vote
2answers
63 views
Algorithm for optimal rule-based arrangements?
I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as ...
1
vote
1answer
40 views
What solution to apply for finding the optimal parameters?
For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an ...
0
votes
0answers
43 views
Search algorithm for vehicles moving through a square grid
I started to learn AI and I'm trying to solve the following problem like a search problem and I'm wondering which search algorithm would be the best in this case. Please give me at least some tips, I ...
1
vote
0answers
43 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 ...
0
votes
0answers
20 views
Use of Tabu search Algorithm for solving optimization problem
I am trying to solve a maximization problem using the Tabu search algorithm but there is no relevant code available on the internet. Any kind of sample code is highly appreciable.
My function is F(...
1
vote
1answer
121 views
Proving 2 heuristics are admissible
We have $h_1(n)$ and $h_2(n)$ which are both admissible heuristics. We know that $h_1(n) < h_2(n)$ for every state $n$ in a search problem.
Now we are given two heuristics $h_3(n)=\frac{h_1(n)}{1+...
1
vote
0answers
35 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 ...
1
vote
1answer
98 views
Partition the indices of 2d array to minimize sum of sub-matrices
Given an $n\times n$ Matrix $M$, and the indices $[{1,2,3,4,...,n}]$ are divided into several intervals : $[1,x_1],[x_1,x_2],...[x_k,n]$, which further extract several squared sub-matrices along the $...
8
votes
1answer
2k 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 ...
1
vote
1answer
28 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
59 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
69 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
31 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
48 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
211 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
57 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 ...
1
vote
1answer
229 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
38 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
62 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
907 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
90 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 (...
3
votes
2answers
1k 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 ...
3
votes
1answer
170 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
57 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
176 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
443 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?