Questions tagged [heuristics]
Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.
-1
votes
0answers
11 views
Regarding Metaheuristic algorithm
I have a confusion regarding meta heuristic algorithms. I am currently looking at Sine Cosine Algorithm(SCA). I am trying to combine it with K means algorithm. Does metaheuristic algorithms calculate ...
0
votes
0answers
16 views
Define a heuristic function in Prolog Programming [on hold]
I'm working on writing a prolog programming to simulate the sliding-tile puzzle games through best first search algorithm with a heuristic function: the counts of the number of tiles out of place.
...
0
votes
0answers
7 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
16 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
-1
votes
1answer
8 views
How to prove if a heuristic function is admissible or not
Can somebody tell me how to solve this problem?
1
vote
1answer
41 views
Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?
I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first.
For example, should I start with one node; calculate ...
1
vote
1answer
35 views
A* Search Algorithm Implementation with Priority Queue
I've got a question regarding the A* search algorithm's implementation.
According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to ...
2
votes
1answer
32 views
Does domination rule apply for inadmissible heuristics?
Let's say $h_1(n) \geq h_2(n)$ so that dominance is established even if $h_1$ and $h_2$ are both inadmissible/non-optimal heuristics -in whichever given search space.
Is $h_1$ still faster/better ...
0
votes
0answers
13 views
Questions regarding Particle Swarm Optimization (for TSP) algorithm (paper)
I'm trying to re-implement an algorithm from a paper regarding the Particle Swarm Optimization metaheuristic for the Traveling Salesman Problem.
The paper is the following: Goldbarg et al. (2006): ...
3
votes
2answers
48 views
Optimization Problem when calculating fitness is expensive
I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...
0
votes
1answer
67 views
Aren’t most constraining variable and least constraining value the exact opposite?
So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on
remaining variables but LCV is opposite: it tries to rule out as least values for other variables ...
0
votes
0answers
93 views
Most constraining variable and least constraining value in N-queens problem
So I implemented a function for the n-queens problem in python and it was great only for up to n=25 but after that it was slow.
But I read that using Most constraining variable and least constraining ...
0
votes
1answer
26 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 ...
1
vote
1answer
25 views
What is the peak in fitness landscape
I have just started reading about fitness landscapes and I couldn't understand what the peak means. What does the peak mean?
2
votes
1answer
53 views
SAT Solving + Turing Machines
I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:
Randomness
Heuristics
Backtracking
SAT is just one example ...
1
vote
1answer
19 views
Justification behind this heuristic in SMA*+
I'm reading the paper Enhanced Simplified Memory-bounded A Star (SMA*+). In short, the authors propose a limited-memory version of A* where we cull nodes if we are out of memory, to re-expand them ...
0
votes
0answers
10 views
Techniques used in customizing Task Scheduling
I am just learning about Scheduling, in particular the Completely Fair Scheduler.
In thinking of specific cases of the types of things that would need to be "prioritized" against each other, there ...
0
votes
1answer
61 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 ...
1
vote
1answer
11 views
How to get initial flow for TSP with missing edges
I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing.
How do I generate a valid initial path effectively?
I would use a greedy ...
1
vote
0answers
48 views
Comparison of time-dependent traveling salesman heuristics
I'm looking into implementing a heuristic for the time-dependent traveling traveling salesman problem (TDTSP) that completes in a certain amount of time.
There are a wide range of possible ways to ...
1
vote
1answer
55 views
Improvement Heuristics for Asymmetric TSP
i have been solving the Time-Dependent Traveling Salesman Problem using
an Ant Colony Optimization.
Upon reading the ACO papers, there are several reminders which state
that ACO performs best with ...
0
votes
0answers
38 views
Algorithms to try for solving a variation of the TSP problem
I am trying to solve the TSP problem in its symmetric variation, where the triangle inequality does not hold, for around 400 cities. Do you know some algorithms that perform particularly well on this ...
0
votes
0answers
145 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?
1
vote
1answer
372 views
How does the nearest insertion heuristic for TSP work?
In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson ...
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 ...
0
votes
2answers
70 views
Greedy Heuristic for the Traveling Salesperson Problem
We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any ...
-2
votes
1answer
163 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
258 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
27 views
With admissible heuristic function; larger heuristic value implies expanding fewer nodes during the search?
My intuition comes from the contour graph that; with zero heuristic, the contour graph is a perfect circle; however, with the larger heuristic value (more close to true cost), the contour becomes more ...
3
votes
1answer
157 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
30 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
44 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 ...
1
vote
1answer
122 views
consistent heuristic - does it always exist?
I am studying for an artificial inteligence class, and i have to classify the following sentence
"For any search space, there is always an admissable and consistent A* heuristic".
Well, i know that ...
-4
votes
1answer
453 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), ...
0
votes
0answers
63 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
207 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
0answers
433 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 ...
4
votes
1answer
171 views
Comparing A* search to Simulated Annealing
Good Afternoon,
I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my ...
0
votes
0answers
877 views
Difference between Heuristic and Split Criteria on Decision Trees?
I am studying Decision Trees for the first time and I can’t really understand the difference between “Heuristics” and “Split Criteria” on Decision Trees.
Read about “maximally reduction of intra-...
1
vote
0answers
146 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 ...
2
votes
0answers
59 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
0answers
78 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 ...
1
vote
1answer
68 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
2answers
99 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 ...
4
votes
1answer
242 views
Does this A-Star heuristic already exist?
I've been thinking about the A* algorithm recently. For context, A* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's ...
1
vote
1answer
301 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 ...
0
votes
0answers
39 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/...
1
vote
1answer
60 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 ...
0
votes
1answer
201 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
34 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 ...
