Questions tagged [heuristics]

Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.

Filter by
Sorted by
Tagged with
0 votes
1 answer
181 views

How to analyze the amortized running time of indexed linked list operations using potential method?

I have implemented an indexed linked list that runs (under mild assumptions) all single-element operations in $\mathcal{O}(\sqrt{n})$ time. The description is here and Java implementation is here. It’...
1 vote
1 answer
29 views

Difference between cost and the heuristic function in A* search

Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
0 votes
0 answers
36 views

Special case of single vehicle routing

I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
1 vote
1 answer
50 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 ...
1 vote
1 answer
39 views

Partition data into two sets of the same size such that the sum of the average distances is maximized

Say I have a set of strings $S=\{s_1, s_2, ..., s_N\}$, and I want to partition $S$ into two sets $S_1$ and $S_2$ equally, i.e., $||S_1|-|S_2||\leq1$. Define the difference of a set as $$Diff(S_k)=\...
9 votes
3 answers
29k views

Why is the A* search heuristic optimal even if it underestimates costs?

A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus ...
0 votes
0 answers
41 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
1 answer
68 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
1 answer
109 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
1 answer
30 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. ...
2 votes
0 answers
74 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 ...
13 votes
1 answer
17k views

How does consistency imply that a heuristic is also admissible?

A heuristic function $h (n)$ is... Consistent if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the ...
8 votes
1 answer
114 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 ...
1 vote
0 answers
67 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
1 answer
28 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
1 answer
115 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
1 answer
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
1 answer
23 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 ...
9 votes
2 answers
270 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their stable, ...
3 votes
2 answers
514 views

Are most metaheuristic algorithms different metaphors for the same method?

Most times I encounter this random metaphors for metaheuristic optimization they seem like a modified genetic algorithm to me. What do you think? Is there a way to remove the analogies/metaphors to ...
6 votes
0 answers
85 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\}$. ...
22 votes
3 answers
38k views

How does an admissible heuristic ensure an optimal solution?

When using A* (or any other best path finding algorithm), we say that the heuristic used should be admissible, that is, it should never overestimate the actual solution path's length (or moves). How ...
10 votes
1 answer
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 ...
2 votes
1 answer
62 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
1 answer
136 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
1 answer
55 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
1 answer
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
0 answers
30 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
1 answer
39 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
1 answer
59 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
0 answers
45 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
0 answers
189 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
0 answers
16 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
2 answers
66 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
1 answer
43 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
0 answers
76 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
0 answers
46 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
0 answers
24 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
1 answer
175 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
0 answers
36 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 ...
2 votes
1 answer
4k views

Nilsson's sequence score for 8-puzzle problem in A* algorithm

I am learning the A* search algorithm on an 8-puzzle problem. I don't have questions about A*, but I have some for the heuristic score - Nilsson's sequence score. Justin Heyes-Jones web pages - A* ...
1 vote
1 answer
122 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 $...
3 votes
2 answers
1k views

the meaning of heuristics in artificial intelligence

I would like to know what 'heuristics' actually means in artificial intelligence. For example, I am reading a paper by Engelbrecht on the convergence analysis of the particles of the algorithm. The ...
1 vote
1 answer
33 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
0 answers
83 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 ...
4 votes
1 answer
4k 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
0 answers
82 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
0 answers
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
0 answers
49 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, ...
5 votes
2 answers
3k views

Why doesn't 2-opt return an optimal solution?

To find a solution for the Traveling Salesman Problem (TSP), one way to go is an algorithm called 2-opt, which is explained below. ...

1
2 3 4 5