# Questions tagged [heuristics]

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

181 questions
Filter by
Sorted by
Tagged with
114 views

### Find a string that covers many sets of binary strings with don't-cares

Consider $N$ sets $S_1,S_2,....,S_{N}$ of binary strings with don't-cares ($X$) with $|S_i| = n$ and the length of all strings is $m$. In my application, $N=1000$, $n=100$ and $m=500$. I have to find ...
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 ...
135 views

### Early termination of A* with weak heuristic if solution is known

I have a large graph G and a pair of nodes s,t. I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent. Suppose I already know of a path ...
313 views

### Compute connect-four opening moves

my question is about how to compute a database with initial moves for Connect Four, where each board constellation is classified as leading to a win, draw or lose. John Tromp already has done this ...
46 views

### Branch and Bound - Transform a into b

I'm trying to design an algorithm which will accept two natural numbers: a and b. Its purpose is to get b from a by making the following operations: *3 and /2. For example, if a = 10 and b = 7, then: ...
185 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. ...
2k views

### When to use SAT vs Constraint Satisfaction?

If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it. Another standard approach is to express it as a constraint satisfaction problem, ...
513 views

### Mutation and crossover operations in discrete differential evolutionary operations?

I need to use discrete differential evolutionary algorithm for assigning discrete values from set size $L$ to vectors of size $D$ where $L$ could be smaller, equal or larger than $D$. Elements of ...
179 views

### Evolutionary algorithm in stochastic environment

Consider the following model problem: I want to use an evolutionary algorithm to optimize the starting point of particles for which it is apriori clear where they would start in state space, but not ...
105 views

### Path finding well know problems [closed]

Is there any pathfinding trivial problems like the TSP? I know that is possible to solve TSP using A*, Best-first and using spanning tree and other things as heuristic but, is there any problem well ...
608 views

### Global relabeling heuristic: Push-relabel maxflow

I have a correct, working implementation of the preflow-push-relabel maxflow algorithm . I am trying to implement the global relabeling update heuristic , but have run into some issues. I have ...
93 views

### Symmetry in Pattern Databases

I am trying to understand the use of symmetry in pattern databases (Heuristics, single agent search). This is too specialized of a topic to find common videos or explanations in general. I read the ...
52 views

### Why do admissible functions allow $A^*$ to retain correct shortest path computations?

I was reading about how to use $A^*$ and was told that: A heuristic is admissible if $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ function indicates that the shortest path from $u$ to $t$. I was ...
34 views

### What is the number of degrees of freedom of my problem in this Simulated Annealing context?

I'm trying to apply a Simulated Annealing technique to solve my (NP-complete) optimization problem. I'm using this book to help myself out. In the section on Simulated Annealing and more specifically ...
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 ...
126 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 ...
249 views

### Why to implement Open list in Heuristic search with priority queue

I don't understand why do we need to implement Open list using priority queue? There could be other data structure. I understand the usage of priority queues from this example clearly. The newly ...
86 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. ...
745 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, ...
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 ...
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 ...
8k views

### Heuristic for Finding Multiple Goals in Graph - e.g. using Kruskals Algorithm

I'm a none-computer-science-student and get some knowledge on AI by taking the CS188.1x Course (Artificial Intelligence) on www.edx.org . Currently, I am working on the "Search in Pacman" Project; ...
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-...
279 views

### Informed search with a lower-bound heuristic?

I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal state....
1k views

### A heuristic for finding a maximum disjoint set

Background I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares. This problem is NP-complete. Many papers suggest approximation ...
68 views

### Is there a name for algorithms which detect nearly-similar structures?

I'm interested in how you might detect similarities in tree structures. For example, in these three JSON documents; ...
718 views

### Difference between heuristic-based searching and optimal path searching

I'm currently studying for an AI computer-science course. One thing is difficult for me to grasp and somewhat vaguely explained in my course-material: I understand that with search-methods like e.g. ...
302 views

### Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their ...
4k views

### Algorithm A vs Algorithm A*: What's the difference?

I can find quite a bit of literature on A* but very little on A. What is the difference between the two search algorithms?
42 views

### Search problem when the effects of actions are not deterministic

The standard search problem studied in AI contains: An initial state $A$; A final (goal) state $Z$; A set of actions that can change the state; each action takes as input a certain state and returns ...
113 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, ...
169 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?
2k views

### Classification of job shop scheduling problems

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, ...
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 ...
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 ...
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 ...
172 views

### Heuristic for Tournament Scheduling

I am holding a bi-yearly tournament in my city, for which I want to write a program that gives me (nearly-)optimal pairings, and waiting time. The setup is as follows: ...
174 views

### What makes a metaheuristic meta?

According to Wikipedia: ...metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a lower-level procedure or heuristic (partial search algorithm) that may ...
360 views

### Quick union and heuristic by size

Studying Quick-Find and Quick-Union heuristic I've found clear that: with quick find trees and a union based on the size of the trees we can make a union in $T_{am}(n)=O(\log(n))$ with quick find ...
3k views

### How can I fill bookcases with shelves of books using the least number of bookcases?

Sorry for layman's term question, my background in computer science is weak. What I have is a list of shelves with books of varying height. Each shelf stores a value that describes how many shelves (...
5k views