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
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 ...
2
votes
0answers
478 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 ...
4
votes
1answer
137 views

Path cover with paths of bounded length, in the plane

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 ...
0
votes
0answers
135 views

Why max heuristic is inacurrate?

H_max() algorithms work by considering a state in the planning graph, and using all applicable actions to make every atom in that state true. The h_max() for a given state is the cost of the most ...
3
votes
1answer
488 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,*,...
5
votes
1answer
497 views

Heuristic algorithms for the dense assignment problem

Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or ...
1
vote
1answer
1k views

Implement multi-fragment heuristics for the traveling salesman problem

I would like to implement the multi-fragment heuristics algorithm for finding a solution to the traveling salesman problem. The algorithm is described here as follows: This seriation method re-...
0
votes
1answer
2k 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 ...
5
votes
0answers
513 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 ...
3
votes
1answer
4k views

Are depth-first/breadth-first considered special cases of best-first?

In literature in general, are DFS and BFS considered to be special cases of best-first search? Suppose the cost function is: $f(n) = g(n) + h(n)$ Is it correct to reason that if and $g(n) = depth(n)...
13
votes
1answer
13k views

How does consistency imply that a heuristic is also admissible?

A heuristic function $h (n)$ is... Consistent if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the ...
1
vote
1answer
111 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
1answer
176 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 ...
3
votes
2answers
121 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 ...
3
votes
0answers
53 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 ...
2
votes
1answer
987 views

AI: Heuristic function A* search

I have an assignment in my university where I have to implement Uniform Cost Search and A* Search. We have an input which includes a map and queries. The map is weighted, directed graph, represented ...
0
votes
0answers
377 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 ...
3
votes
1answer
163 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 ...
3
votes
1answer
47 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: ...
4
votes
1answer
221 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 ...
-1
votes
1answer
115 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 ...
3
votes
2answers
123 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 ...
2
votes
1answer
62 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 ...
2
votes
1answer
44 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 ...
1
vote
1answer
93 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 ...
0
votes
1answer
314 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 ...
1
vote
1answer
143 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
0answers
93 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. ...
2
votes
1answer
942 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
0answers
86 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 ...
2
votes
0answers
60 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
1answer
325 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....
2
votes
1answer
91 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; ...
2
votes
1answer
797 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. ...
2
votes
1answer
5k 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?
3
votes
1answer
43 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 ...
1
vote
0answers
119 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, ...
0
votes
1answer
185 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?
3
votes
2answers
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 ...
5
votes
0answers
58 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 ...
1
vote
0answers
66 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
237 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. ...
3
votes
1answer
184 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 ...
5
votes
1answer
375 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 ...
4
votes
3answers
13k views

Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'?

Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as: $h_1(n)$ = number of misplaced tiles $h_2(n)$ = total Manhatten distance Could anyone tell why $h_2$ is a better ...
3
votes
1answer
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 (...
3
votes
1answer
6k views

Heuristic for sokoban puzzle problem

I am trying to write IDA* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast. My heuristic is to consider $h(...
2
votes
1answer
18k 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 ...
2
votes
2answers
395 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 ...