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
1
vote
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 ...
1
vote
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 ...
1
vote
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, ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 <...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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. ...
1
vote
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 ...
1
vote
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 <...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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. ...
1
vote
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 ...
1
vote
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. ...
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
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 ...
1
vote
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, ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
0answers
53 views

A heuristic for finding a disjoint set of representatives

This is my problem: ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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?
0
votes
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/|...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...