Questions tagged [heuristics]

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

53 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
443 views

Heuristic Repair and N-Queens Problem

Problem: I am trying to solve the $N$-Queens problem using Constraint Satisfaction and Heuristic Repair (also known as Min-Conflicts). I wrote a program to do this for any given $N$ queens and $N * N$...
5
votes
0answers
417 views

How to apply ant colony optimization to the TSP but repeating nodes and edges

I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial ...
5
votes
0answers
440 views

Why are the conditions for optimality different for A* tree and graph search?

I am unclear as to why the conditions for optimality for A* search are different for graph search and tree search. When discussing conditions for optimality for A* search in Russell and Norvig's ...
4
votes
0answers
690 views

A good heuristic for 2D Rubik's cube

I am looking for a good heuristic function for solving a 2D $n\times n$ Rubik's cube using A* search. There is a game already in the play store. The rules of the game: Swiping LEFT means the ...
4
votes
0answers
55 views

Testing whether an analytic function vanishes identically

I have an application that basically reduces to testing whether a given function vanishes identically. The function is given symbolically, using unary and binary operators on complex numbers. For ...
3
votes
0answers
23 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 ...
3
votes
0answers
41 views

Defining preferred paths makes $A^*$ heuristic lose admissibility

In a geographical graph, where each edge's cost is equal to the physical distance between its nodes, one can be tempted to manipulate the cost of some of the edges, to make it a bit lower, in order to ...
3
votes
0answers
52 views

Heuristic for making set of indexes in an array/matrix with generating functions/patterns

I am trying to find a lead on how to solve or find a heuristic the following kind of problem: Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a ...
3
votes
0answers
376 views

Trying to understand the Gilmore-Lawler lower bound

For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the ...
3
votes
0answers
1k views

Time complexity 2-opt method

I'm doing a practice test for a course on routing problems. There's a question asking to infere the time complexity of the 2-opt method. I can see that the complexity per iteration is in $O(n^2)$ ...
3
votes
1answer
445 views

How to tell if a Heuristic is monotonic

I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,...
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, ...
2
votes
0answers
56 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
0answers
63 views

Are there many empirical results about which metaheuristics are well-suited for which problem domains?

One of the nice things about genetic algorithms is that they can easily be used for a diverse array of problem domains, whereas PSO for example seems best-suited for candidates of real-valued vectors (...
2
votes
0answers
468 views

Simulated Annealing for graph coloring

I am working on a simulated annealing algorithm for graph coloring. The model I follow is the following: http://riad.pk.edu.pl/~zk/pubs/PPAM07_2.pdf. I have troubles understanding the cooling schedule ...
2
votes
0answers
59 views

How to compare A* with DP approach in finding shortest Path?

Consider a hypercube defined over $n$ dimensions where the edges are associated to strictly positive weights, and nodes are marked with $n$ bit-strings, e.g. the source is marked as (0,0,0) in a 3-...
2
votes
0answers
174 views

Experimental Survey on Different Heuristics for Knapsack Problem

I am looking for a good survey/study of experimental results of heuristics for Knapsack problem (or implemented libraries in java/c++). Any help is appreciated!
2
votes
0answers
121 views

Heuristics for tree decomposition into k shortest paths

What kind of heuristics are useful in a tree decomposition of a graph to find the k shortest paths from a given source to a vertex? Moreover, the local shortest paths at each node in a tree are ...
1
vote
0answers
169 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
vote
0answers
149 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 ...
1
vote
0answers
83 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 ...
1
vote
0answers
200 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 ...
1
vote
0answers
93 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
0answers
63 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. ...
1
vote
0answers
90 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
vote
0answers
84 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 ...
1
vote
0answers
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 ...
1
vote
0answers
114 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, ...
1
vote
0answers
806 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 ...
1
vote
0answers
53 views

A heuristic for finding a disjoint set of representatives

This is my problem: ...
0
votes
0answers
15 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
29 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-...
0
votes
0answers
52 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
69 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 ...
0
votes
0answers
39 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 ...
0
votes
0answers
204 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
0answers
45 views

MAC-AC3 algorithm puts arcs in queue

I am studying Csp and I don't understand the line no 1.1 . Does queue contains all arcs or not?Explain with me 4-queens please. ...
0
votes
0answers
190 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? ...
0
votes
0answers
25 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 ...
0
votes
0answers
17 views

Can Heuristic repair algorithm be applied to TSP?

Can Heuristic repair algorithm (or it's modification) be applied to Traveling Sales Person problem ? My gut feeling is that it can. But I have no idea - what cost(s)/conflicts should be minimized. ...
0
votes
0answers
40 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
280 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
30 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
0
votes
0answers
262 views

What is the best heuristic function for evaluating the state in game of sprouts?

We are developing game of sprouts bot using min-max algorithm. We need a good heuristic function for evaluating the state of the game/player. Can someone please suggest?
0
votes
0answers
431 views

Creating admissible and consistent Heuristic function Help

I am trying to create a heuristic function for use in an A* algorithm. The problem to be solved is a single row tile puzzle with 3 total w tiles and 3 b tiles and one "_" tile as shown below WWW_BBB ...
0
votes
0answers
70 views

Table of incompatible turns in an intersection (steps to writing a program)

I just began reading Data Structures and Algorithms (Aho, Hopcraft, and Ullman). At the beginning, there is an example that discusses designing a traffic light for a complicated intersection of roads. ...
0
votes
0answers
102 views

A* heuristic for the game Blockage

There is a flash game that you can very easily find on Google called Blockage. Rules & Goal of the game : Get all coloured blocks from their initial position to a corresponding target spot ...
0
votes
0answers
52 views

Algorithms or specific approaches for maximum independent set problem in triangle free graphs

And obviously there will be no trivial vertex which has only 2 edges. I think triangle free graphs are (subjectively) easier than complicated graphs, i wonder if you know some heuristic approaches/...
0
votes
0answers
36 views

What is the best way to find similarity between two bodies?

Suppose we have two human bodies. We need to find some number that represents a similarity score between the two bodies. However in order to achieve that we need to find the similarity between the ...
0
votes
0answers
2k views

8 puzzle admissible heuristic that dominates Manhattan distance?

I have a modified 8 puzzle problem such that each transition's cost is associated with the number of the piece that is moved. So, for example, if piece "3" is moved, the move would cost 3 units. I ...