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
3
votes
0answers
40 views

Defining preferred paths makes $A^*$ heuristic lose admissibility

In a geographical graph, where each edge's cost is equal to the physical distance between its nodes, one can be tempted to manipulate the cost of some of the edges, to make it a bit lower, in order to ...
-2
votes
1answer
269 views

If $h(s)$ is an admissible heuristic, is $\sqrt{h(s)}$ admissible?

I was thinking yes because $0 \leq \sqrt{h(s)} < h(s)$ but I'm not entirely sure.
0
votes
0answers
366 views

Creating admissible and consistent Heuristic function Help

I am trying to create a heuristic function for use in an A* algorithm. The problem to be solved is a single row tile puzzle with 3 total w tiles and 3 b tiles and one "_" tile as shown below WWW_BBB ...
2
votes
1answer
303 views

Are there practical methods for solving ILP?

Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms! Is solving an ...
0
votes
0answers
36 views

Table of incompatible turns in an intersection (steps to writing a program)

I just began reading Data Structures and Algorithms (Aho, Hopcraft, and Ullman). At the beginning, there is an example that discusses designing a traffic light for a complicated intersection of roads. ...
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 ...
2
votes
1answer
945 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 ...
-3
votes
1answer
1k views

Best heuristic for A*? [closed]

I'm trying to build a maze solver using A* algorithm. The maze is a grid with movement allowed in 4 directions (up, down, left, right). If there's a starting cell (x1, y1) and a destination (x2, y2), ...
7
votes
3answers
18k views

Why is the A* search heuristic optimal even if it underestimates costs?

A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus ...
0
votes
0answers
100 views

A* heuristic for the game Blockage

There is a flash game that you can very easily find on Google called Blockage. Rules & Goal of the game : Get all coloured blocks from their initial position to a corresponding target spot ...
1
vote
1answer
335 views

If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?

That is, if h(n) = h*(n), then A* only expands nodes that lie on an optimal path to the goal. But does this imply that A* will always take a linear time in the solution length to find an optimal ...
4
votes
3answers
10k 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 ...
4
votes
0answers
583 views

A good heuristic for 2D Rubik's cube

I am looking for a good heuristic function for solving a 2D $n\times n$ Rubik's cube using A* search. There is a game already in the play store. The rules of the game: Swiping LEFT means the ...
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
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 ...
2
votes
0answers
63 views

Are there many empirical results about which metaheuristics are well-suited for which problem domains?

One of the nice things about genetic algorithms is that they can easily be used for a diverse array of problem domains, whereas PSO for example seems best-suited for candidates of real-valued vectors (...
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
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
965 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 ...
0
votes
0answers
44 views

Algorithms or specific approaches for maximum independent set problem in triangle free graphs

And obviously there will be no trivial vertex which has only 2 edges. I think triangle free graphs are (subjectively) easier than complicated graphs, i wonder if you know some heuristic approaches/...
6
votes
2answers
6k views

Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?

I'm reading through the RMIT course notes on state space search. Consider a state space $S$, a set of nodes in which we look for an element having a certain property. A heuristic function $h:S\to\...
2
votes
1answer
611 views

Is a two-opt move guaranteed to produce a non-worse tour?

I have a little doubt with respect to the two-opt improvement heuristic for TSP. I understand how it works, from the Wikipedia article on 2-opt and "Heuristics for the Traveling Salesman Problem". ...
1
vote
1answer
691 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-...
4
votes
1answer
1k views

How to verify that a heuristic is consistent?

A heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the step cost of ...
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 ...
8
votes
3answers
7k views

Difference between heuristic and approximation algorithm?

i have a problem regarding the following situation. I have two arrays of numbers like this: ...
0
votes
1answer
308 views

Are most metaheuristic algorithms different metaphors for the same method?

Most times I encounter this random metaphors for metaheuristic optimization they seem like a modified genetic algorithm to me. What do you think? Is there a way to remove the analogies/metaphors to ...
0
votes
0answers
36 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
3k 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 ...
3
votes
1answer
2k views

Why doesn't 2-opt return an optimal solution?

To find a solution for the Traveling Salesman Problem (TSP), one way to go is an algorithm called 2-opt, which is explained below. ...
1
vote
1answer
481 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
1k 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
392 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
412 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
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. ...
5
votes
0answers
408 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
891 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
441 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
124 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
123 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
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 ...
5
votes
1answer
352 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 ...
7
votes
3answers
13k 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
396 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
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 ...
3
votes
1answer
2k 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)...
12
votes
1answer
9k 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
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 ...
3
votes
2answers
113 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 ...