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
0 answers
22 views

Manhattan distance always less node expansion than misplaced tiles heuristic?

I created a 8-puzzle search solver using BFS, A* with manhattan distance, and A* with misplaced tiles. I generated data that said that for a particular random board, misplaced tiles did less node ...
Dennis Gahm's user avatar
0 votes
0 answers
26 views

A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost

I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles. We know that: Dijkstra's algorithm uses ...
Math98's user avatar
  • 1
0 votes
0 answers
14 views

How to choose cells from a table to maximize their sum, with selection constraints?

I have a table of fixed positive integer values of anything up to several dozen. There are six columns and several hundred rows. I must choose exactly two values from each column, and zero or one ...
Atario's user avatar
  • 101
1 vote
1 answer
49 views

Greedy algorithms criterion/ intution

Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy ...
green_32's user avatar
  • 113
0 votes
0 answers
25 views

Designing Algorithm for MST problem for a optical fiber network bounded by costs

So I need to design an algorithm for the following problem: Suppose we need to build an optical fibre network for 20 cities. We are given a distance matrix of the cities which tells us which cities ...
muhammed gunes's user avatar
1 vote
1 answer
36 views

What is a good heuristic for multi-point A* on a directed graph?

I am conducting a stateful search of a large graph in an effort to find some solutions of minimal cost. With an admissible heuristic for estimated time to completion from a given state (as in A*), I ...
Zannick's user avatar
  • 11
0 votes
1 answer
48 views

Which combinatorial problem is reminiscent to mine?

I am trying to understand which combinatorial problem best fits the one I have. I am mostly asking from the perspective of being pointed towards relevant literature. I will explain the problem with an ...
csTheoryBeginner's user avatar
1 vote
0 answers
81 views

Simplified Memory Bounded A*

I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
Error 404's user avatar
0 votes
0 answers
11 views

Simple example where informed heuristic has larger state space?

So far, I understand that not all informed heuristics can guarantee small search spaces than uninformed, but I am not sure what's a simple example for this type of scenario?
abcxyz's user avatar
  • 1
1 vote
1 answer
47 views

What is a heuristic in human computer interaction?

I have found multiple definitions of what a heuristic is, and I have found multiple computer science-related definitions. In my university course, the lectures cite the Nielson Norman Group defining a ...
Eris's user avatar
  • 13
2 votes
0 answers
46 views

Modified DPLL for 3-SAT by reducing to 2-SAT

In Boolean Satisfiability of CNF formulae we have $k$-SAT where each clause has at most $k$ literals. It is well known that $k$-SAT is polynomial time reducible to $3$-SAT. It is also well known that $...
vvg's user avatar
  • 135
0 votes
1 answer
36 views

Is there an optimisation algorithm that does not require a good initial solution?

I was reading this question on CS stack exchange called How important is initial state for local search optimisation? I would like to extend it with the following example: I have been reading about ...
Ship's user avatar
  • 3
0 votes
0 answers
56 views

Is a metaheuristics a Markov Decision Process?

Is a metaheuristics optimization algorithm, such as simulated annealing, a Markov Decision Process? For example, considering the combinatorial optimization problem of finding the minimum of $f : \{0,1\...
incud's user avatar
  • 459
1 vote
1 answer
150 views

Kolmogorov complexity and data compression revisited

The question of the relationship between Kolmogorov complexity and data compression is rather difficult. However, at the heuristic level, the complexity of an object and the rate of its compression by ...
lesobrod's user avatar
  • 111
1 vote
1 answer
104 views

If the heuristic $h(n)$ is the estimated cost from node $n$ to the goal, then why would we want a heuristic that has a greater cost?

I am currently studying the concept of heuristics in search algorithms. I recently asked this question about the so-called "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\...
The Pointer's user avatar
0 votes
0 answers
75 views

How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?

I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following: Greedy search minimises estimated path-cost to goal. But it's ...
The Pointer's user avatar
1 vote
1 answer
42 views

Algorithm/heuristic for large tournament matchup pairings

I'm scheduling a large invitational tournament with the following conditions The event takes place over 8 weeks Teams arrive and depart on different dates/times, so each day of the event will have a ...
Ron M's user avatar
  • 113
1 vote
1 answer
122 views

search with inadmissible heuristics

I was told that search algorithm such as IDA* or Beam Search with any inadmissible heuristic is not guaranteed to find a solution. Can someone explain why that is the case? I was thinking sure the ...
Sam's user avatar
  • 163
-1 votes
1 answer
57 views

Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?

I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
Fernanda's user avatar
2 votes
1 answer
580 views

Difference between cost and the heuristic function in A* search

Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
Ewan Valentine's user avatar
0 votes
1 answer
191 views

How to analyze the amortized running time of indexed linked list operations using potential method?

I have implemented an indexed linked list that runs (under mild assumptions) all single-element operations in $\mathcal{O}(\sqrt{n})$ time. The description is here and Java implementation is here. It’...
coderodde's user avatar
0 votes
0 answers
36 views

Special case of single vehicle routing

I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
advocateofnone's user avatar
1 vote
1 answer
51 views

Partition data into two sets of the same size such that the sum of the average distances is maximized

Say I have a set of strings $S=\{s_1, s_2, ..., s_N\}$, and I want to partition $S$ into two sets $S_1$ and $S_2$ equally, i.e., $||S_1|-|S_2||\leq1$. Define the difference of a set as $$Diff(S_k)=\...
h_axlrose's user avatar
0 votes
0 answers
52 views

How to build a data-structure for a moving points

Problem:- I have moving points in a 2d space with a fixed obstacle(A polygon) and a fixed destination. I want to find at what time Source(which is moving) can get a path to destination and what is ...
Naruto's user avatar
  • 157
2 votes
1 answer
79 views

Why the choice of the adjacent vertex with the least degree is a good heuristic for the hamiltonian path problem?

Even if the hamiltonian path problem is NP-hard there exist heuristics which return a correct path for many instances in linear time. In particular one of the main rules is always choosing the ...
Tortar's user avatar
  • 167
4 votes
1 answer
180 views

Warnsdorff's rule: more errors with odd sized boards

I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
Tortar's user avatar
  • 167
1 vote
1 answer
95 views

How to think about heuristics

I have a game about drone delivery company. The game consists of a rectangular map, which contains tiles that cannot be passed. I can control a certain amount of drones, each one of them starts at a ...
Dani's user avatar
  • 131
2 votes
0 answers
197 views

Can A* with an inadmissible heuristic still be optimal?

It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...
Chemin's user avatar
  • 21
1 vote
1 answer
33 views

Heuristics for a variant of the traveling salesman problem

I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset. ...
Davis Yoshida's user avatar
8 votes
1 answer
163 views

What is the approximation ratio of this bin-backing algorithm?

Consider the following algorithm for bin packing: Initially, sort the items by their size. Put the largest item in a new bin. Fill the bin with small items in ascending order of size, up to the ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
84 views

minimising Longest-Path in DAG

Assume we have weighted DAG (directed-acycle-graph), source s and target t. Define the number of edges as $E$. Given $0<\alpha<1$: Choose $\alpha*E$ edges to cut their weight by half so that the ...
Amran Tomer's user avatar
1 vote
1 answer
53 views

CVRP and removing edges from a graph

I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances. I know that, in general, the complexity of ...
Michele Bolognini's user avatar
1 vote
1 answer
281 views

How do I solve a search problem on an infinite graph?

I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \...
sdasdadas's user avatar
  • 165
1 vote
1 answer
70 views

Grasshopper Optimization Algorithm

I am currently reading a paper on a meta-heuristic called 'Grasshopper Optimization Algorithm'. The main idea of the algorithm is to utilize the social behavior of grasshoppers in a swarm to solve ...
gython's user avatar
  • 111
-1 votes
1 answer
25 views

A very simple question about Admissible Heurisitcs

Given admissible heuristics f(s), g(s), h(s). It is true that max(f(s), g(s), h(s)) is still admissible.. but is it still admissible if its max(f(s), g(s) + h(s)). I believe it is not admissible but I ...
Mikey's user avatar
  • 11
6 votes
0 answers
95 views

Scheduling tasks on a graph with assistance

This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following: Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
user avatar
2 votes
1 answer
68 views

Optimization problem over bidirectional connected graph

A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators,...
dcfg's user avatar
  • 145
4 votes
1 answer
139 views

One-dimensional packing problem: Optimal decomposition of music structure

I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music. Problem Description Given a ...
Job Savelsberg's user avatar
2 votes
1 answer
67 views

Graph partition that maximize the number of triangles within its parts

Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal? This ...
JEK's user avatar
  • 128
1 vote
1 answer
53 views

How can I make the variance of a multiple sum of set of fixed number of variables minimum?

Here is the problem: There are $MN$ people, where there are $M>1$ seeds and $N>0$ people are in each seed. We have to make $N$ teams of $M$ people where everyone in the team have different seeds....
user5876164's user avatar
2 votes
0 answers
39 views

Messy Representation Encoding example

I am currently working through Metaheuristics by El-Ghazali Talbi where he discusses encodings of algorithms. "Messy representations: In linear representations of fixed length, the semantics of ...
chrisper's user avatar
1 vote
1 answer
54 views

Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points

I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a ...
Conor Henry's user avatar
2 votes
1 answer
93 views

How important is initial state for local search optimisation?

I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation. I'm wondering how important the ...
Mr Felix U's user avatar
0 votes
0 answers
111 views

Minimizing the length a Boolean Algebra Expression in disjunctive normal form

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
Fergus Kavanagh's user avatar
1 vote
0 answers
223 views

Which non convex optimization algorithms guarantee a global optima?

Most non-convex optimization algorithms I have come across so far rely basically on random restart to find a better solution. e.g. Genetic Algorithm, Simulated Annealing, Metropolis Hastings Monte ...
Souradeep Nanda's user avatar
1 vote
0 answers
19 views

Is there an heuristic for finding out the smallest height you can get when packing items in a tube?

It's sort of similar to bin packing, but instead of the minimum amount of bins,I was interested in just one infinite bin and finding out what's the smallest height you could get when you start packing ...
J. Dionisio's user avatar
1 vote
2 answers
71 views

Algorithm for optimal rule-based arrangements?

I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as ...
Sam's user avatar
  • 123
1 vote
1 answer
88 views

What solution to apply for finding the optimal parameters?

For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an ...
Cristian M's user avatar
0 votes
0 answers
90 views

Search algorithm for vehicles moving through a square grid

I started to learn AI and I'm trying to solve the following problem like a search problem and I'm wondering which search algorithm would be the best in this case. Please give me at least some tips, I ...
Ion's user avatar
  • 1
1 vote
0 answers
61 views

What is an example of meta-heuristic algorithm for solving Mario NP-hard problem?

Applying entertainment with computations is my main motivation in studying Computer Science, however, I'm still a neophyte to this field. While searching across the net, I came across this paper ...
Anonymous player's user avatar

1
2 3 4 5