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
1answer
42 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
55 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
21 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
19 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
66 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
279 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 ...
0
votes
1answer
351 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
1answer
286 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 ...
0
votes
3answers
58 views

Heuristically determine a value f such that a probability d/f approaches 1/2

We have a set X of N elements. We want to get a new set X' having a size M < N. ...
0
votes
0answers
16 views

What does the gradient mean in evolutionary algorithm?

I have been reading about evolutionary algorithms and I often find the concept of gradient that is used as "to follow a gradient"...
0
votes
0answers
30 views

A heuristic for finding an edge cycle cover

I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph. In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
0
votes
0answers
53 views

How do evaluation functions influence the optimal sequence of moves?

Assume you have a game tree and the features $(f_1, f_2, f_3,\ldots,f_n )$ that describe the state of the game at any node. Also assume that you are using depth-limited minimax and always expand up to ...
0
votes
0answers
104 views

What is the difference between nearest and cheapest insertion algorithms for a Traveling salesman problem?

I know that in the cheapest insertion algorithm we include the node which is not in the "base group" that has smaller cost given all possible combinations, and for the nearest we include the node with ...
0
votes
0answers
42 views

What kind of standard deviation must be used in optimization algorithms?

I would like to ask about the standard deviation of objective function value. There are two types of standard deviations: Population standard deviation Sample standard deviation In metaheuristic ...
0
votes
0answers
226 views

How can an A* algorithm visit all nodes?

Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
0
votes
1answer
29 views

Defining Local Search stopping criteria

When performing a local search, for example, a 2-node exchange in a metaheuristic (like GRASP), what is the usual stopping criteria for that procedure? Some bibliography says that the local search ...
0
votes
0answers
250 views

How MAC-3(maintaining arc consistency-3) algorithm works?

I am studying CSP problems in artificial intelligence. I don't understand the MAC-3 algorithm especially line number 10. Could you tell me with step by step? ...
0
votes
0answers
28 views

Relevance of the ZeroSum game to Heuristic search?

A question was posed to me as to the relevance of the ZeroSum game to Heuristic search algorithms. I know that the zero sun game is a theory in which one persons gain is exactly balanced to another ...
0
votes
0answers
44 views

can someone provide a good resource for understanding 2 opt heuristic?

I have looked into wikipedia and this MIT slide. A step by step iteration of the algorithm with a clear example would be appreciated.
0
votes
0answers
349 views

8 puzzle admissible heuristic where tiles are in correct position

For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once. But ...
0
votes
0answers
31 views

How many states are examined in the most wins heuristic for tic-tac-toe (9-grid)?

I'm new to AI, and have a hard time to understanding how to count the total states are examined in the most wins heuristic for tic-tac-toe two plys deeper(9-grid)? Need help
0
votes
1answer
54 views

Steps to create a heuristic for solving a problem

I am completely new to AI and doing self-learning to acquire this knowledge. I went through the different available search algorithm like BFS, DFS and A* but something that I can't understand is a ...
0
votes
0answers
267 views

What is the best heuristic function for evaluating the state in game of sprouts?

We are developing game of sprouts bot using min-max algorithm. We need a good heuristic function for evaluating the state of the game/player. Can someone please suggest?
0
votes
0answers
474 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 ...
0
votes
0answers
74 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
0answers
104 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 ...
0
votes
0answers
53 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/...
0
votes
0answers
37 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 ...
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 ...
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
0answers
356 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 ...
-1
votes
2answers
51 views

Can data be compressed through this hash function technique?

I'd like to know if this data compression scheme would work or not, and why: Suppose we have a file. If we treat the bits that make up the file as the binary representation of a number n, we have n (...
-1
votes
1answer
1k views

Where is the recursion, in the minimax-decision algorithm?

The below is from an article titled: Minimax: Recursive Implementation To be a recursive function, you need to call yourself. What part of this pseudo code is calling itself? How does depth-...
-1
votes
1answer
107 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 ...
-1
votes
1answer
149 views

How to prove if a heuristic function is admissible or not

Can somebody tell me how to solve this problem?
-2
votes
1answer
297 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.
-3
votes
1answer
2k 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), ...

1 2 3 4