# Questions tagged [heuristics]

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

199 questions
Filter by
Sorted by
Tagged with
216 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 ...
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, ...
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 ...
82 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 ...
42 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?
288 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 ...
24 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 ...
352 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 ...
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 ...
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 ...
175 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 ...
277 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?
4k views

### How does the nearest insertion heuristic for TSP work?

In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson ...
42 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 ...
101 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 ...
329 views

### If $h(s)$ is an admissible heuristic, is $\sqrt{h(s)}$ admissible?

I was thinking yes because $0 \leq \sqrt{h(s)} < h(s)$ but I'm not entirely sure.
508 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 ...
374 views

### Are there practical methods for solving ILP?

Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms! Is solving an ...
76 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. ...
65 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 ...
229 views

### consistent heuristic - does it always exist?

I am studying for an artificial inteligence class, and i have to classify the following sentence "For any search space, there is always an admissable and consistent A* heuristic". Well, i know that ...
2k views

### Best heuristic for A*? [closed]

I'm trying to build a maze solver using A* algorithm. The maze is a grid with movement allowed in 4 directions (up, down, left, right). If there's a starting cell (x1, y1) and a destination (x2, y2), ...
108 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 ...
627 views

### If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?

That is, if h(n) = h*(n), then A* only expands nodes that lie on an optimal path to the goal. But does this imply that A* will always take a linear time in the solution length to find an optimal ...
756 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 ...
363 views

### Comparing A* search to Simulated Annealing

Good Afternoon, I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my ...
220 views

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 ...
66 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 (...
98 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 ...
75 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 <...
149 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 ...
519 views

### Does this A-Star heuristic already exist?

I've been thinking about the A* algorithm recently. For context, A* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's ...
465 views

### How to proof a heuristic?

I am not very familiar with "heuristic", so please correct me if anything said by me is wrong. Per my understanding, Algorithm is an automatic steps which guarantee to give a correct solution ...
56 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/...
65 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 ...
373 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 ...
39 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 ...
2k 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. ...
830 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 ...
770 views

### Is a two-opt move guaranteed to produce a non-worse tour?

I have a little doubt with respect to the two-opt improvement heuristic for TSP. I understand how it works, from the Wikipedia article on 2-opt and "Heuristics for the Traveling Salesman Problem". ...
463 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$...
65 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. ...
1k views

### Sort array with minimum swaps

Given an array, I need to sort the array (if not already sorted) in either decreasing or increasing order so that number of swaps are minimized. I was thinking of first determining whether it is ...
2k views

### How to verify that a heuristic is consistent?

A heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the step cost of ...
435 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 ...
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 ...
1k views

### Heuristics for the $n$-puzzle

An admissible heuristic for an n-puzzle is the Manhattan distance. Now if the cost of a transition is equal to the number of the piece that is moved, is it true that the Manhattan distance is still an ...
475 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 ...
I have a weighted, undirected, Euclidean complete graph $G$, a special vertex $r$, and an upper bound $b$. I want to find a minimum-cost path cover that covers all vertices of $G$, subject to the ...