# Questions tagged [heuristics]

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

180 questions
Filter by
Sorted by
Tagged with
1answer
379 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 ...
1answer
90 views

### Search Heuristics Where the Search Space Has No Gradient

If I'm not mistaken, search heuristics rely on problems where the best answer is very close to pretty-good answers. For example, the traveling salesman problem. If there is a route which is the ...
1answer
701 views

### Monotone property of heuristic in $A^*$ algorithm

In the $A^*$ algorithm, the optimality of the path is guaranteed when the heuristic has the property of being admissible or monotone\consistent. I was able to understand the admissible property, ...
2answers
314 views

### Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

Why is it the lower the h(n) cost the more nodes need to be expanded in A*? As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html If h(n) is always lower than (or equal ...
1answer
900 views

### Can heuristic methods and machine learning approaches be considered alternate methods to solve NP-Complete problems?

I was watching the videos from Skiena's Computational Biology Lectures, which is also available at youtube. In those videos, the professor made a statement that, most of the problems posed to computer ...
1answer
451 views

### Algorithm to use for a TSP variant

What type of algorithm would you suggest me to use for this problem? I want to implement an algorithm that minimize the total distance in a graph (TSP) but for only X nodes. Also, we can go as many ...
1answer
22 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 ...
1answer
18 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 ...
1answer
94 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 ...
1answer
167 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 ...
1answer
72 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 <...
2answers
117 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 ...
1answer
64 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 ...
1answer
480 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 ...
1answer
964 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 ...
1answer
137 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 ...
1answer
124 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 ...
1answer
183 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. ...
1answer
320 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 ...
1answer
4k 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 <...
0answers
166 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 ...
1answer
46 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 ...
1answer
270 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 ...
1answer
244 views

### A* Search Algorithm Implementation with Priority Queue

I've got a question regarding the A* search algorithm's implementation. According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to ...
0answers
75 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 ...
0answers
184 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 ...
0answers
91 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 ...
0answers
61 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. ...
1answer
108 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 ...
0answers
85 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. ...
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 ...
0answers
13 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 ...
0answers
112 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, ...
0answers
65 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 ...
1answer
56 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 ...
0answers
762 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 ...
0answers
53 views

### A heuristic for finding a disjoint set of representatives

This is my problem: ...
1answer
11k views

### Given two heuristic values how do I tell which one is admissible?

I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes. Am I correct in thinking the way to see which one is admissible is add up all the values of ...
2answers
88 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 ...
1answer
1k 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 ...
1answer
53 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 ...
1answer
1k views

### Prove consistency of maximum of two consistent heuristic functions?

Suppose we have two heuristic functions $h_1$ and $h_2$ which are both consistent, that is, $$h_i(n) \leq c(n,a,n') + h_i(n')\qquad \ i\in\{1,2\}\,,$$ where $c(n,a,n')$ denotes cost of reaching the ...
1answer
165 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?
1answer
41 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/|...
1answer
32 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 ...
1answer
14 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 ...
1answer
17 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 ...
1answer
49 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 ...
1answer
548 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 ...
1answer
157 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 ...