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
0
votes
0answers
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 ...
4
votes
2answers
4k views

Forward checking vs arc consistency on 3-SAT

If I were to let the variables be the propositions and, constraint be all clauses being satisfied, which technique would be more effective in solving 3-SAT? Forward checking or arc consistency? From ...
1
vote
1answer
842 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 ...
0
votes
0answers
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 ...
3
votes
1answer
484 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
0answers
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$...
1
vote
0answers
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. ...
5
votes
0answers
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 ...
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
477 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 ...
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
1answer
474 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 ...
8
votes
3answers
15k views

How does the 3-opt algorithm for TSP work?

I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers ...
5
votes
0answers
504 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 ...
1
vote
1answer
171 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
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
12k 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
110 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 ...
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 ...
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 ...
0
votes
0answers
376 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
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: ...
1
vote
1answer
235 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. ...
18
votes
1answer
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, ...
3
votes
1answer
566 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 ...
4
votes
1answer
212 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
113 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
1answer
670 views

Global relabeling heuristic: Push-relabel maxflow

I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues. I have ...
3
votes
2answers
122 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
61 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
41 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 ...
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 ...
0
votes
1answer
308 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
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
931 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
85 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
2answers
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; ...
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
323 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....
4
votes
2answers
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 ...
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
794 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. ...
5
votes
1answer
373 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 ...
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 ...