China
Africa
Explore chapters and articles related to this topic
Heuristic and metaheuristic algorithms
Published in Dušan Teodorović, Miloš Nikolić, Quantitative Methods in Transportation, 2020
Dušan Teodorović, Miloš Nikolić
Engineers frequently use greedy heuristic algorithms to solve combinatorial optimization problems. The application of these algorithms is justified when, due to the dimensions of the problem under study, exact methods result in a very long computer time. Greedy heuristic algorithms are fast and generate solutions that are, generally, not optimal. The basic characteristic of the greedy algorithm is that, when trying to discover a global optimum, a greedy algorithm always takes the locally optimal choice at each stage. At each stage, a greedy algorithm looks for what is the best thing to do at that stage, without considering future stages. For example, the greedy heuristic for the Traveling Salesman Problem reads: always go to the nearest city that has not been visited.
Basic Algorithmic Techniques
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
Vishal Khandelwal, Ankur Srivastava
An algorithm is defined as a sequence of simple steps that solves a more complicated problem. At each step, the algorithm makes a decision from a set of choices. Greedy algorithms [1] have the property of making a choice that looks the best at that time. This may or may not guarantee the optimality of the final solution. The key advantage of greedy algorithms is simplicity. In this section, we will discuss the basic properties that a problem must have for greedy strategies to yield the optimal solution. If we can demonstrate the following properties in a problem, then greedy methods will yield the optimal solution: Problem can be modeled as a combination of a greedy choice and a smaller subproblem.There exists an optimal solution to the problem in which the greedy choice has been made.Combination of the optimal solution to the subproblem and the greedy choice results in the optimal solution to the overall problem.
Deployment and Scheduling of Wireless Sensor Networks for Monitoring Water Grids
Published in Panagiotis Tsakalides, Athanasia Panousopoulou, Grigorios Tsagkatakis, Luis Montestruque, Smart Water Grids, 2018
Fig. 1.4 (c) shows the deployment achieved by Algorithm 4 for MAX Cover Problem (1.6). We have known from Fig. 1.4 (a) that using only four nodes can cover the whole water grid. Thus, the deployment in Fig. 1.4 (a) is an optimal solution for the MAX Cover problem. We have mentioned before that the greedy algorithm may not give us the optimal solution. We can see here that the four nodes deployed in Fig. 1.4 (c) fail to cover the whole water grid. However, such a deployment covers 11 out of 12 junctions, which satisfies Proposition 5.
AGV dispatching algorithm based on deep Q-network in CNC machines environment
Published in International Journal of Computer Integrated Manufacturing, 2021
Kyuchang Chang, Seung Hwan Park, Jun-Geol Baek
In addition, the agent selects and executes an action based on an -greedy policy. The greedy algorithm can be defined as an algorithm for selecting the best currently available option without considering the long-term effects of that decision (which could be a suboptimal decision). The -greedy algorithm is defined as a greedy algorithm that adds randomness when deciding between options. Instead of always selecting the best available option, it is possible to randomly explore other options with a probability , or to select the best option with a probability . Therefore, it is possible to add randomness to the algorithm by increasing , which allows the algorithm to explore other options more frequently. The DQN algorithm gradually reduces the value. Thus, it is possible to reduce the dependence on untrained models at an early stage.
The effect of autonomous systems on the crew size of ships – a case study
Published in Maritime Policy & Management, 2021
Carmen Kooij, Robert Hekkenberg
In this paper, the assignment problem is solved by using a greedy algorithm. A greedy algorithm is a heuristic method that is used in operations research to quickly find a solution to a problem. As the algorithm is based on logical choices made in each step the implementation time is relatively short. (Sharma 2019). This also means that the runtime of the algorithm is very short. This logic-based decision process is also the downside of a greedy algorithm. It looks for local optima in the hope of finding the global optimum, which it does not achieve for every problem (Sharma 2019). To reduce the possibility of the algorithm ending up in a local optimum, the tasks are sorted from most expensive to cheapest. Additionally, the problem is small enough to perform a manual check on the results to identify possible local optima. The following sections explains the crew analysis algorithm (CAA) that utilises this greedy algorithm.
A Greedy Ant Colony System for Defensive Resource Assignment Problems
Published in Applied Artificial Intelligence, 2018
Mônica De Rezende, Beatriz S. L. P De Lima, Solange Guimarães
Greedy algorithms solve optimization problems by selecting at each iteration the choice that best fits the objective function at that instant, choosing a local optimal solution. We used the greedy approach of MMR algorithm (Kolitz 1988), denoted here as MMR2, for comparison purposes since it is well known that this MMR algorithm provide better results (Johansson and Falkman 2011) than the MMR of Den Broeder et al. (1959), named here MMR1. Both algorithms have as input parameters vector V of target values and matrix P of kill probabilities, and, as output, vector S. Differently from MMR1, the MMR2 solution is independent to list sequences, since it scans all target values and all resources, searching for the pair that currently maximizes reduction of threat values. Also, as in all such an algorithm, after the assignment of a resource to a target, the target value diminishes for the next iteration, reducing the threat level associated with this target. Both MMR algorithms provide solutions very quickly, even for large-scale scenarios. For non-complex input scenarios, MMR2 reaches the global optimum more frequently, being very effective. However, for complex situations, MMR1 and MMR2 solutions are frequently reduced to poor quality local optima.