Relevant bibliographies by topics / Greedy search algorithm

Academic literature on the topic 'Greedy search algorithm'

Author: Grafiati
Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Greedy search algorithm.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Greedy search algorithm"

1

Stern, Roni, Rami Puzis, and Ariel Felner. "Potential Search: A New Greedy Anytime Heuristic Search." Proceedings of the International Symposium on Combinatorial Search 1, no. 1 (August 25, 2010): 119–20. http://dx.doi.org/10.1609/socs.v1i1.18177.

Full text
Abstract:
In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the "anytime aspect" of anytime algorithms - the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.
APA, Harvard, Vancouver, ISO, and other styles
2

Benabbou, Nawal, Cassandre Leroy, Thibaut Lust, and Patrice Perny. "Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 14 (May 18, 2021): 12233–40. http://dx.doi.org/10.1609/aaai.v35i14.17452.

Full text
Abstract:
We propose two incremental preference elicitation methods for interactive preference-based optimization on weighted matroid structures. More precisely, for linear objective (utility) functions, we propose an interactive greedy algorithm interleaving preference queries with the incremental construction of an independent set to obtain an optimal or near-optimal base of a matroid. We also propose an interactive local search algorithm based on sequences of possibly improving exchanges for the same problem. For both algorithms, we provide performance guarantees on the quality of the returned solutions and the number of queries. Our algorithms are tested on the uniform, graphical and scheduling matroids to solve three different problems (committee election, spanning tree, and scheduling problems) and evaluated in terms of computation times, number of queries, and empirical error.
APA, Harvard, Vancouver, ISO, and other styles
3

Dor, Avner. "The Greedy Search Algorithm on Binary Vectors." Journal of Algorithms 27, no. 1 (April 1998): 42–60. http://dx.doi.org/10.1006/jagm.1997.0893.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Prihozhy, A. A. "Exact and greedy algorithms of allocating experts to maximum set of programmer teams." «System analysis and applied information science», no. 1 (June 8, 2022): 40–46. http://dx.doi.org/10.21122/2309-4923-2022-1-40-46.

Full text
Abstract:
The allocation of experts to programmer teams, which meet constraints on professional competences related to programming technologies, languages and tools an IT project specifies is a hard combinatorial problem. This paper solves the problem of forming the maximum number of teams whose experts meet all the constraints within each team. It develops and compares two algorithms: a heuristic greedy and exact optimal. The greedy algorithm iteratively solves the set cover problem on a matrix of expert competences until can create the next workable team of remaining experts. The paper proves that the allocation greedy algorithm is not accurate even if the set cover algorithm is exact. We call the allocation algorithm as double greedy if the set cover algorithm is greedy. The exact algorithm we propose finds optimal solution in three steps: generating a set of all non-redundant teams, producing a graph of team’s independency, and searching for a maximum clique in the graph. The algorithm of generating the non-redundant teams traverses a search tree constructed in such a way as to guarantee the creation of all non-redundant teams and absorbing all redundant teams. The edges of the non-redundant team independency graph connect teams that have no common expert. The maximum clique search algorithm we propose accounts for the problem and graph features. Experimental results show that the exact algorithm is a reference one, and the double-greedy algorithm is very fast and can yield suboptimal solutions for large-size allocation problems.
APA, Harvard, Vancouver, ISO, and other styles
5

Heusner, Manuel, Thomas Keller, and Malte Helmert. "Understanding the Search Behaviour of Greedy Best-First Search." Proceedings of the International Symposium on Combinatorial Search 8, no. 1 (September 1, 2021): 47–55. http://dx.doi.org/10.1609/socs.v8i1.18425.

Full text
Abstract:
A classical result in optimal search shows that A* with an admissible and consistent heuristic expands every state whose f-value is below the optimal solution cost and no state whose f-value is above the optimal solution cost. For satisficing search algorithms, a similarly clear understanding is currently lacking. We examine the search behaviour of greedy best-first search (gbfs) in order to make progress towards such an understanding. We introduce the concept of high-water mark benches, which separate the search space into areas that are searched by a gbfs algorithm in sequence. High-water mark benches allow us to exactly determine the set of states that are not expanded under any gbfs tie-breaking strategy. For the remaining states, we show that some are expanded by all gbfs searches, while others are expanded only if certain conditions are met.
APA, Harvard, Vancouver, ISO, and other styles
6

Piacentini, Chiara, Sara Bernardini, and J. Christopher Beck. "Autonomous Target Search with Multiple Coordinated UAVs." Journal of Artificial Intelligence Research 65 (August 8, 2019): 519–68. http://dx.doi.org/10.1613/jair.1.11635.

Full text
Abstract:
Search and tracking is the problem of locating a moving target and following it to its destination. In this work, we consider a scenario in which the target moves across a large geographical area by following a road network and the search is performed by a team of unmanned aerial vehicles (UAVs). We formulate search and tracking as a combinatorial optimization problem and prove that the objective function is submodular. We exploit this property to devise a greedy algorithm. Although this algorithm does not offer strong theoretical guarantees because of the presence of temporal constraints that limit the feasibility of the solutions, it presents remarkably good performance, especially when several UAVs are available for the mission. As the greedy algorithm suffers when resources are scarce, we investigate two alternative optimization techniques: Constraint Programming (CP) and AI planning. Both approaches struggle to cope with large problems, and so we strengthen them by leveraging the greedy algorithm. We use the greedy solution to warm start the CP model and to devise a domain-dependent heuristic for planning. Our extensive experimental evaluation studies the scalability of the different techniques and identifies the conditions under which one approach becomes preferable to the others.
APA, Harvard, Vancouver, ISO, and other styles
7

Kazakovtsev, Lev, Dmitry Stashkov, Mikhail Gudyma, and Vladimir Kazakovtsev. "Algorithms with greedy heuristic procedures for mixture probability distribution separation." Yugoslav Journal of Operations Research 29, no. 1 (2019): 51–67. http://dx.doi.org/10.2298/yjor171107030k.

Full text
Abstract:
For clustering problems based on the model of mixture probability distribution separation, we propose new Variable Neighbourhood Search algorithms (VNS) and evolutionary genetic algorithms (GA) with greedy agglomerative heuristic procedures and compare them with known algorithms. New genetic algorithms implement a global search strategy with the use of a special crossover operator based on greedy agglomerative heuristic procedures in combination with the EM algorithm (Expectation Maximization). In our new VNS algorithms, this combination is used for forming randomized neighbourhoods to search for better solutions. The results of computational experiments made on classical data sets and the testings of production batches of semiconductor devices shipped for the space industry demonstrate that new algorithms allow us to obtain better results, higher values of the log likelihood objective function, in comparison with the EM algorithm and its modifications.
APA, Harvard, Vancouver, ISO, and other styles
8

Xiao, Zhuolei, Yerong Zhang, Kaixuan Zhang, Dongxu Zhao, and Guan Gui. "GARLM: Greedy Autocorrelation Retrieval Levenberg–Marquardt Algorithm for Improving Sparse Phase Retrieval." Applied Sciences 8, no. 10 (October 1, 2018): 1797. http://dx.doi.org/10.3390/app8101797.

Full text
Abstract:
The goal of phase retrieval is to recover an unknown signal from the random measurements consisting of the magnitude of its Fourier transform. Due to the loss of the phase information, phase retrieval is considered as an ill-posed problem. Conventional greedy algorithms, e.g., greedy spare phase retrieval (GESPAR), were developed to solve this problem by using prior knowledge of the unknown signal. However, due to the defect of the Gauss–Newton method in the local convergence problem, especially when the residual is large, it is very difficult to use this method in GESPAR to efficiently solve the non-convex optimization problem. In order to improve the performance of the greedy algorithm, we propose an improved phase retrieval algorithm, which is called the greedy autocorrelation retrieval Levenberg–Marquardt (GARLM) algorithm. Specifically, the proposed GARLM algorithm is a local search iterative algorithm to recover the sparse signal from its Fourier transform magnitude. The proposed algorithm is preferred to existing greedy methods of phase retrieval, since at each iteration the problem of minimizing the objective function over a given support is solved by using the improved Levenberg–Marquardt (ILM) method and matrix transform. A local search procedure such as the 2-opt method is then invoked to get the optimal estimation. Simulation results are given to show that the proposed algorithm performs better than the conventional GESPAR algorithm.
APA, Harvard, Vancouver, ISO, and other styles
9

Oktaviandi, Rizky Berlia, M. Sadid Tafsirul Hadi, Alanfansyah Ghozy Santoso, and Nova El Maidah. "Perbandingan Algoritma Genetika dengan Algoritma Greedy Untuk Pencarian Rute Terpendek." INFORMAL: Informatics Journal 3, no. 1 (February 25, 2019): 6. http://dx.doi.org/10.19184/isj.v3i1.9847.

Full text
Abstract:
In everyday life we ​​often travel from place to place. So that we need to consider the time and cost efficient. Therefore, accuracy is needed to determine the shortest path as a consideration in decision to show the path to be taken. The results obtained also require speed and accuracy with the help of a computer. Using or functioning a computer there must be a distributed program in it. The programs contained in the computer vary widely and each program must use an algorithm. Algorithm is a collection of commands to solve a problem gradually from start to finish. There are various algorithms that can be used to find the shortest route such as Breadth First Search algorithm, Depth First Search, A *, Hill Climbing and others. For that required comparison algorithm which is able to find the shortest route accurately and efficiently. In this journal, the algorithm to be compared is the genetic algorithm and greedy algorithm to find the shortest route on a map. Some aspects to be compared are aspects of the accuracy, speed, and complexity of genetic algorithms and greedy algorithms for the shortest route search.
APA, Harvard, Vancouver, ISO, and other styles
10

Wang, Chao, Deguang Wang, and Chun Jin. "A quick Heuristic and a general search algorithm for traveling salesman problem." E3S Web of Conferences 360 (2022): 01097. http://dx.doi.org/10.1051/e3sconf/202236001097.

Full text
Abstract:
This paper puts forward a constructive heuristic algorithm called the method of inserting the minimum neighbor edge from outside to the center (IMNEFOTC) that can be applied to solve large-scale and ultra-large-scale travelling salesman problems. Through it and the randomized greedy heuristic algorithm (RGH) which greedy heuristic algorithm is modified, a general meta-heuristic search algorithm framework is built. The general search algorithm (GSA) is based on a set of initial solutions, and continuous 2-opt operations are performed, so as to search for solutions in better quality. The data from the experiment reveals that the performance of IMNEFOTC is better than the traditional greedy algorithm, and the GSA can obtain a pretty satisfactory solution in a reasonable range of time.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Greedy search algorithm"

1

Neas, Charles Bennett. "A Greedy Search Algorithm for Maneuver-Based Motion Planning of Agile Vehicles." Thesis, Virginia Tech, 2010. http://hdl.handle.net/10919/36213.

Full text
Abstract:
This thesis presents a greedy search algorithm for maneuver-based motion planning of agile vehicles. In maneuver-based motion planning, vehicle maneuvers are solved offline and saved in a library to be used during motion planning. From this library, a tree of possible vehicle states can be generated through the search space. A depth-first, library-based algorithm called AD-Lib is developed and used to quickly provide feasible trajectories along the tree. AD-Lib combines greedy search techniques with hill climbing and effective backtracking to guide the search process rapidly towards the goal. Using simulations of a four-thruster hovercraft, AD-Lib is compared to existing suboptimal search algorithms in both known and unknown environments with static obstacles. AD-Lib is shown to be faster than existing techniques, at the expense of increased path cost. The motion planning strategy of AD-Lib along with a switching controller is also tested in an environment with dynamic obstacles.
Master of Science
APA, Harvard, Vancouver, ISO, and other styles
2

Sun, Qing. "Greedy Inference Algorithms for Structured and Neural Models." Diss., Virginia Tech, 2018. http://hdl.handle.net/10919/81860.

Full text
Abstract:
A number of problems in Computer Vision, Natural Language Processing, and Machine Learning produce structured outputs in high-dimensional space, which makes searching for the global optimal solution extremely expensive. Thus, greedy algorithms, making trade-offs between precision and efficiency, are widely used. %Unfortunately, they in general lack theoretical guarantees. In this thesis, we prove that greedy algorithms are effective and efficient to search for multiple top-scoring hypotheses from structured (neural) models: 1) Entropy estimation. We aim to find deterministic samples that are representative of Gibbs distribution via a greedy strategy. 2) Searching for a set of diverse and high-quality bounding boxes. We formulate this problem as the constrained maximization of a monotonic sub-modular function such that there exists a greedy algorithm having near-optimal guarantee. 3) Fill-in-the-blank. The goal is to generate missing words conditioned on context given an image. We extend Beam Search, a greedy algorithm applicable on unidirectional expansion, to bidirectional neural models when both past and future information have to be considered. We test our proposed approaches on a series of Computer Vision and Natural Language Processing benchmarks and show that they are effective and efficient.
Ph. D.
APA, Harvard, Vancouver, ISO, and other styles
3

Farooq, Farhan. "Optimal Path Searching through Specified Routes using different Algorithms." Thesis, Högskolan Dalarna, Datateknik, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:du-4530.

Full text
Abstract:
To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes.To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook
APA, Harvard, Vancouver, ISO, and other styles
4

Zakaria, Rabih. "Optimization of the car relocation operations in one-way carsharing systems." Thesis, Belfort-Montbéliard, 2015. http://www.theses.fr/2015BELF0281/document.

Full text
Abstract:
L'autopartage est un service de mobilité qui offre les mêmes avantages que les voitures particulières mais sansnotion de propriété. Les clients du système peuvent accéder aux véhicules sans ou avec réservation préalable. Laflotte de voitures est distribuée entre les stations et les clients peuvent prendre une voiture d'une station et ladéposer dans n'importe quelle autre station (one-way), chaque station disposant d'un nombre maximum de placesde stationnement. La demande pour la prise ou le retour des voitures dans chaque station est souvent asymétriqueentre les stations et varie au cours de la journée. Par conséquent, certaines stations accumulent des voitures etatteignent leur capacité maximale prévenant alors de nouvelles voitures de trouver une place de stationnement.Dans le même temps, des stations se vident et conduisent au rejet de la demande de retrait de clients. Notre travailporte sur l'optimisation des opérations de redéploiement de voitures afin de redistribuer efficacement les voitures surles stations suivant la demande qui varie en fonction du temps et de l'espace. Dans les systèmes d'autopartage àsens unique, le problème du redéploiement de voitures sur les stations est techniquement plus difficile que leproblème de la redistribution des vélos dans les systèmes de vélopartage. Dans ce dernier, on peut utiliser uncamion pour déplacer plusieurs vélos en même temps, alors que nous ne pouvons pas le faire dans le systèmeautopartage en raison de la taille des voitures et de la difficulté de chargement et de déchargement. Ces opérationsaugmentent le coût de fonctionnement du système d'autopartage sur l'opérateur. De ce fait, l'optimisation de cesopérations est essentielle afin de réduire leur coût. Dans cette thèse, nous développons un modèle deprogrammation linéaire en nombre entier pour ce problème. Ensuite, nous présentons trois politiques différentes deredéploiement de voitures que nous mettons en oeuvre dans des algorithmes de recherche gloutonne et nousmontrons que les opérations de redéploiement qui ne considèrent pas les futures demandes ne sont pas efficacesdans la réduction du nombre de demandes rejetées. Les solutions fournies par notre algorithme glouton sontperformantes en temps d'exécution (moins d'une seconde) et en qualité en comparaison avec les solutions fourniespar CPLEX. L'évaluation de la robustesse des deux approches présentées par l'ajout d'un bruit stochastique sur lesdonnées d'entrée montre qu'elles sont très dépendantes des données même avec l'adoption de valeur de seuil deredéploiement. En parallèle à ce travail algorithmique, l'analyse de variance (ANOVA) et des méthodes derégression multilinéaires ont été appliqués sur l'ensemble de données utilisées pour construire un modèle global afind'estimer le nombre de demandes rejetées. Enfin, nous avons développé et comparé deux algorithmesévolutionnaires multicritères pour prendre en compte l'indécision sur les objectifs de l'optimisation, NSGA-II et unalgorithme mémétique qui a montré une bonne performance pour résoudre ce problème
To buy it. Users can have access to vehicles on the go with or without reservation. Each station has a maximumnumber of parking places. In one-way carsharing system, users can pick up a car from a station and drop it in anyother station. The number of available cars in each station will vary based on the departure and the arrival of cars oneach station at each time of the day. The demand for taking or returning cars in each station is often asymmetric andis fluctuating during the day. Therefore, some stations will accumulate cars and will reach their maximum capacitypreventing new arriving cars from finding a parking place, while other stations will become empty which lead to therejection of new users demand to take a car. Users expect that cars are always available in stations when they needit, and they expect to find a free parking place at the destination station when they want to return the rented car aswell. However, maintaining this level of service is not an easy task. For this sake, carsharing operators recruitemployees to relocate cars between the stations in order to satisfy the users' demands.Our work concerns the optimization of the car relocation operations in order to efficiently redistribute the cars overthe stations with regard to user demands, which are time and space dependent. In one-way carsharing systems, therelocation problem is technically more difficult than the relocation problem in bikesharing systems. In the latter, wecan use trucks to move several bikes at the same time, while we cannot do this in carsharing system because of thesize of cars and the difficulty of loading and unloading cars. These operations increase the cost of operating thecarsharing system.As a result, optimizing these operations is crucial in order to reduce the cost of the operator. In this thesis, we modelthis problem as an Integer Linear Programming model. Then we present three different car relocation policies thatwe implement in a greedy search algorithm. The comparison between the three policies shows that car relocationoperations that do not consider future demands are not effective in reducing the number of rejected demands.Results prove that solutions provided by our greedy algorithm when using a good policy, are competitive withCPLEX solutions. Furthermore, adding stochastic modification on the input data proves that the robustness of thetwo presented approaches to solve the relocation problem is highly dependent on the input demand even afteradding threshold values constraints. After that, the analysis of variance (ANOVA) and the multi-linear regressionmethods were applied on the used dataset in order to build a global model to estimate the number of rejecteddemands. Finally, we developed and compared two multi-objectives evolutionary algorithms to deal with thedecisional aspect of the car relocation problem using NSGA-II and memetic algorithms
APA, Harvard, Vancouver, ISO, and other styles
5

Kopřiva, Jan. "Srovnání algoritmů při řešení problému obchodního cestujícího." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2009. http://www.nusl.cz/ntk/nusl-222126.

Full text
Abstract:
The Master Thesis deals with logistic module innovation of information system ERP. The principle of innovation is based on implementation of heuristic algorithms which solve Travel Salesman Problems (TSP). The software MATLAB is used for analysis and tests of these algorithms. The goal of Master Thesis is the comparison of selections algorithm, which are suitable for economic purposes (accuracy of solution, speed of calculation and memory demands).
APA, Harvard, Vancouver, ISO, and other styles
6

He, Jeannie. "Automatic Diagnosis of Parkinson’s Disease Using Machine Learning : A Comparative Study of Different Feature Selection Algorithms, Classifiers and Sampling Methods." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-301616.

Full text
Abstract:
Over the past few years, several studies have been published to propose algorithms for the automated diagnosis of Parkinson’s Disease using simple exams such as drawing and voice exams. However, at the same time as all classifiers appear to have been outperformed by another classifier in at least one study, there appear to lack a study on how well different classifiers work with a certain feature selection algorithm and sampling method. More importantly, there appear to lack a study that compares the proposed feature selection algorithm and/or sampling method with a baseline that does not involve any feature selection or oversampling. This leaves us with the question of which combination of feature selection algorithm, sampling method and classifier is the best as well as what impact feature selection and oversampling may have on the performance. Given the importance of providing a quick and accurate diagnosis of Parkinson’s disease, a comparison is made between different systems of classifier, feature selection and sampling method with a focus on the predictive performance. A system was chosen as the best system for the diagnosis of Parkinson’s disease based on its comparative predictive performance on two sets of data - one from drawing exams and one from voice exams.
Som en av världens mest vanligaste sjukdom med en tendens att leda till funktionshinder har Parkinsons sjukdom länge varit i centrum av forskning. För att se till att så många som möjligt får en behandling innan det blir för sent har flera studier publicerats för att föreslå algoritmer för automatisk diagnos av Parkinsons sjukdom. Samtidigt som alla klassificerare verkar ha överträffats av en annan klassificerare i minst en studie, verkar det saknas en studie om hur väl olika klassificerare fungerar med en viss kombination av urvalsalgoritm (feature selection algorithm på engelska) och provtagningsmetod. Därutöver verkar det saknas en studie där resultatet från den föreslagna urvalsalgoritmen och/eller samplingsmetoden jämförs med resultatet av att applicera klassificeraren direkt på datan utan någon urvalsalgoritm eller resampling. Detta lämnar oss en fråga om vilket system av klassificerare, urvalsalgoritm och samplingsmetod man bör välja och ifall det är värt att använda en urvalsalgoritm och överprovtagningsmetod. Med tanke på vikten av att snabbt och noggrant upptäcka Parkinsons sjukdom har en jämförelse gjorts för att hitta den bästa kombinationen av klassificerare, urvalsalgoritm och provtagningsalgoritm för den automatiska diagnosen av Parkinsons sjukdom.
APA, Harvard, Vancouver, ISO, and other styles
7

Jurčík, Lukáš. "Evoluční algoritmy při řešení problému obchodního cestujícího." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2014. http://www.nusl.cz/ntk/nusl-224447.

Full text
Abstract:
This diploma thesis deals with evolutionary algorithms used for travelling salesman problem (TSP). In the first section, there are theoretical foundations of a graph theory and computational complexity theory. Next section contains a description of chosen optimization algorithms. The aim of the diploma thesis is to implement an application that solve TSP using evolutionary algorithms.
APA, Harvard, Vancouver, ISO, and other styles
8

Kadri, Ahmed Abdelmoumene. "Simulation and optimization models for scheduling and balancing the public bicycle-sharing systems." Thesis, Université de Lorraine, 2015. http://www.theses.fr/2015LORR0268.

Full text
Abstract:
Les enjeux du développement durable, le réchauffement climatique, la pollution dans les grandes villes, la congestion et les nuisances sonores, l'augmentation des prix de carburants, sont parmi des nombreux facteurs qui incitent les pays développés à l'innovation dans les transports publics. Dans ce contexte, l'introduction des systèmes de vélos en libre-service, au cours de ces dernières années, est une des solutions adoptées par de nombreuses grandes villes. Malgré leur succès fulgurant dans le monde entier, il existe peu d'études fondamentales sur ce type transport urbain. Pourtant, leur exploitation et leur management par des opérateurs soulèvent de nombreuses questions notamment d'ordre opérationnel. Dans ce contexte, cette thèse s'adresse aux problèmes d'ordonnancement et de rééquilibrage des stations de vélos en libre-service. Ce sont des problèmes cruciaux pour la qualité de service et la viabilité économique de tels systèmes. Le rééquilibrage consiste à redistribuer le nombre de vélos entre les différentes stations afin de satisfaire au mieux les demandes des usagers. Cette régulation se fait souvent par le biais de véhicules spécifiques qui font des tournées autour des différentes stations. Ainsi, deux problèmes d'optimisation difficiles se posent : la recherche de la meilleure tournée du véhicule de régulation (ordonnancement de la tournée) et la détermination des nombres de véhicules à utiliser (rééquilibrage des stations). Dans cette optique, les travaux de cette thèse constituent une contribution à la modélisation et à l'optimisation de performances des systèmes de vélos en libre-service en vue de leur rééquilibrage et leur ordonnancement. Plusieurs méthodes d'optimisation et ont été développées et testées. De telles méthodes incorporent différentes approches de simulation ou d'optimisation comme les réseaux de Petri, les algorithmes génétiques, les algorithmes gloutons, les algorithmes de recherche par voisinage, la méthode arborescente de branch-and-bound, l'élaboration des bornes supérieures et inférieures, etc. Différentes facettes du problème ont été étudiées : le cas statique, le cas dynamique, l'ordonnancement et le rééquilibrage avec un seul (ou multiple) véhicule(s). Afin de montrer la pertinence de nos approches, la thèse comporte également plusieurs applications réelles et expérimentations
In our days, developed countries have to face many public transport problems, including traffic congestion, air pollution, global oil prices and global warming. In this context, Public Bike sharing systems are one of the solutions that have been recently implemented in many big cities around the world. Despite their apparent success, the exploitation and management of such transportation systems imply crucial operational challenges that confronting the operators while few scientific works are available to support such complex dynamical systems. In this context, this thesis addresses the scheduling and balancing in public bicycle-sharing systems. These problems are the most crucial questions for their operational efficiency and economic viability. Bike sharing systems are balanced by distributing bicycles from one station to another. This procedure is generally ensured by using specific redistribution vehicles. Therefore, two hard optimization problems can be considered: finding a best tour for the redistribution vehicles (scheduling) and the determination of the numbers of bicycles to be assigned and of the vehicles to be used (balancing of the stations). In this context, this thesis constitutes a contribution to modelling and optimizing the bicycle sharing systems' performances in order to ensure a coherent scheduling and balancing strategies. Several optimization methods have been proposed and tested. Such methods incorporate different approaches of simulation or optimization like the Petri nets, the genetic algorithms, the greedy search algorithms, the local search algorithms, the arborescent branch-and-bound algorithms, the elaboration of upper and lower bounds, ... Different variants of the problem have been studied: the static mode, the dynamic mode, the scheduling and the balancing by using a single or multiple vehicle(s). In order to demonstrate the coherence and the suitability of our approaches, the thesis contains several real applications and experimentations
APA, Harvard, Vancouver, ISO, and other styles
9

Marie, Benjamin. "Exploitation d’informations riches pour guider la traduction automatique statistique." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS066/document.

Full text
Abstract:
S'il est indéniable que de nos jours la traduction automatique (TA) facilite la communication entre langues, et plus encore depuis les récents progrès des systèmes de TA statistiques, ses résultats sont encore loin du niveau de qualité des traductions obtenues avec des traducteurs humains.Ce constat résulte en partie du mode de fonctionnement d'un système de TA statistique, très contraint sur la nature des modèles qu'il peut utiliser pour construire et évaluer de nombreuses hypothèses de traduction partielles avant de parvenir à une hypothèse de traduction complète. Il existe cependant des types de modèles, que nous qualifions de « complexes », qui sont appris à partir d'informations riches. Si un enjeu pour les développeurs de systèmes de TA consiste à les intégrer lors de la construction initiale des hypothèses de traduction, cela n'est pas toujours possible, car elles peuvent notamment nécessiter des hypothèses complètes ou impliquer un coût de calcul très important. En conséquence, de tels modèles complexes sont typiquement uniquement utilisés en TA pour effectuer le reclassement de listes de meilleures hypothèses complètes. Bien que ceci permette dans les faits de tirer profit d'une meilleure modélisation de certains aspects des traductions, cette approche reste par nature limitée : en effet, les listes d'hypothèses reclassées ne représentent qu'une infime partie de l'espace de recherche du décodeur, contiennent des hypothèses peu diversifiées, et ont été obtenues à l'aide de modèles dont la nature peut être très différente des modèles complexes utilisés en reclassement.Nous formulons donc l'hypothèse que de telles listes d'hypothèses de traduction sont mal adaptées afin de faire s'exprimer au mieux les modèles complexes utilisés. Les travaux que nous présentons dans cette thèse ont pour objectif de permettre une meilleure exploitation d'informations riches pour l'amélioration des traductions obtenues à l'aide de systèmes de TA statistique.Notre première contribution s'articule autour d'un système de réécriture guidé par des informations riches. Des réécritures successives, appliquées aux meilleures hypothèses de traduction obtenues avec un système de reclassement ayant accès aux mêmes informations riches, permettent à notre système d'améliorer la qualité de la traduction.L'originalité de notre seconde contribution consiste à faire une construction de listes d'hypothèses par passes multiples qui exploitent des informations dérivées de l'évaluation des hypothèses de traduction produites antérieurement à l'aide de notre ensemble d'informations riches. Notre système produit ainsi des listes d'hypothèses plus diversifiées et de meilleure qualité, qui s'avèrent donc plus intéressantes pour un reclassement fondé sur des informations riches. De surcroît, notre système de réécriture précédent permet d'améliorer les hypothèses produites par cette deuxième approche à passes multiples.Notre troisième contribution repose sur la simulation d'un type d'information idéalisé parfait qui permet de déterminer quelles parties d'une hypothèse de traduction sont correctes. Cette idéalisation nous permet d'apporter une indication de la meilleure performance atteignable avec les approches introduites précédemment si les informations riches disponibles décrivaient parfaitement ce qui constitue une bonne traduction. Cette approche est en outre présentée sous la forme d'une traduction interactive, baptisée « pré-post-édition », qui serait réduite à sa forme la plus simple : un système de TA statistique produit sa meilleure hypothèse de traduction, puis un humain apporte la connaissance des parties qui sont correctes, et cette information est exploitée au cours d'une nouvelle recherche pour identifier une meilleure traduction
Although communication between languages has without question been made easier thanks to Machine Translation (MT), especially given the recent advances in statistical MT systems, the quality of the translations produced by MT systems is still well below the translation quality that can be obtained through human translation. This gap is partly due to the way in which statistical MT systems operate; the types of models that can be used are limited because of the need to construct and evaluate a great number of partial hypotheses to produce a complete translation hypothesis. While more “complex” models learnt from richer information do exist, in practice, their integration into the system is not always possible, would necessitate a complete hypothesis to be computed or would be too computationally expensive. Such features are therefore typically used in a reranking step applied to the list of the best complete hypotheses produced by the MT system.Using these features in a reranking framework does often provide a better modelization of certain aspects of the translation. However, this approach is inherently limited: reranked hypothesis lists represent only a small portion of the decoder's search space, tend to contain hypotheses that vary little between each other and which were obtained with features that may be very different from the complex features to be used during reranking.In this work, we put forward the hypothesis that such translation hypothesis lists are poorly adapted for exploiting the full potential of complex features. The aim of this thesis is to establish new and better methods of exploiting such features to improve translations produced by statistical MT systems.Our first contribution is a rewriting system guided by complex features. Sequences of rewriting operations, applied to hypotheses obtained by a reranking framework that uses the same features, allow us to obtain a substantial improvement in translation quality.The originality of our second contribution lies in the construction of hypothesis lists with a multi-pass decoding that exploits information derived from the evaluation of previously translated hypotheses, using a set of complex features. Our system is therefore capable of producing more diverse hypothesis lists, which are globally of a better quality and which are better adapted to a reranking step with complex features. What is more, our forementioned rewriting system enables us to further improve the hypotheses produced with our multi-pass decoding approach.Our third contribution is based on the simulation of an ideal information type, designed to perfectly identify the correct fragments of a translation hypothesis. This perfect information gives us an indication of the best attainable performance with the systems described in our first two contributions, in the case where the complex features are able to modelize the translation perfectly. Through this approach, we also introduce a novel form of interactive translation, coined "pre-post-editing", under a very simplified form: a statistical MT system produces its best translation hypothesis, then a human indicates which fragments of the hypothesis are correct, and this new information is then used during a new decoding pass to find a new best translation
APA, Harvard, Vancouver, ISO, and other styles
10

Chang, Fu-Sheng, and 張福生. "Greedy-Search-based Multi-Objective Genetic Algorithm for Emergency Humanitarian Logistics Scheduling." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/wp7ygu.

Full text
Abstract:
博士
國立中山大學
資訊工程學系研究所
104
To enable the immediate and efficient dispatch of relief to victims of disaster, this thesis proposes a greedy-search-based multi-objective genetic algorithm (GSMOGA) that is capable of regulating the distribution of available resources and automatically generating a variety of feasible emergency logistics schedules for decision-makers. The proposed algorithm merges the features of local search ability of the greedy method and the diversity of multi-objective genetic algorithm to enhance local search speed and diversity explore ability. It uses the Google Map to draw up the available roads which connect the demand points and supply points and applies the Dijkstra algorithm to find the shortest path between each demand point and supply point. It also dynamically adjust distribution schedules from various supply points according to the requirements at demand points, and adopts the NSGAII method to perform rank & sort procedure to find the feasible solution schedules on non-dominated Pareto front in order to minimize the following: unsatisfied demand for resources, time to delivery, and transportation costs. The sequence of three objectives are also applied to be the priority sequence to generate and order routing schedules for the decision maker. The algorithm uses the case of the Chi-Chi earthquake in Taiwan to verify its performance. Simulation results demonstrate that with a limited and unlimited number of available vehicles, the proposed algorithm outperforms the multi-objective genetic algorithm (MOGA) and the standard greedy algorithms in ‘time to delivery’ by 56.16% and 64.11%, respectively under the 10,000 generations and average situation. The final routing figures show that the GSMOGA is more comprehensive in the emergency logistics scheduling problem. We study the effect of different crossover methods on the performance of GSMOGA. The results show that order based crossover performs the best. We verify the correctness of GSMOGA by comparing the result using the brute force approach.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Greedy search algorithm"

1

Rajpurohit, Jitendra, and Tarun K. Sharma. "A Greedy Jellyfish Search Optimization Algorithm." In Lecture Notes in Electrical Engineering, 769–78. Singapore: Springer Nature Singapore, 2022. http://dx.doi.org/10.1007/978-981-19-2828-4_69.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Yang, Weiming. "Non-Greedy Heuristic Web Spiders Search Algorithm." In Lecture Notes in Electrical Engineering, 1728–33. London: Springer London, 2012. http://dx.doi.org/10.1007/978-1-4471-2386-6_236.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Musiał, Kamil, Joanna Kotowska, Dagmara Górnicka, and Anna Burduk. "Tabu Search and Greedy Algorithm Adaptation to Logistic Task." In Computer Information Systems and Industrial Management, 39–49. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-59105-6_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Das, Shyama, and Sumam Mary Idicula. "KMeans Greedy Search Hybrid Algorithm for Biclustering Gene Expression Data." In Advances in Experimental Medicine and Biology, 181–88. New York, NY: Springer New York, 2010. http://dx.doi.org/10.1007/978-1-4419-5913-3_21.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Shi, Chenghao, Zhonghua Tang, Yongquan Zhou, and Qifang Luo. "Greedy Squirrel Search Algorithm for Large-Scale Traveling Salesman Problems." In Intelligent Computing Methodologies, 830–45. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-13832-4_67.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Alonso-Barba, Juan I., Luis de la Ossa, Jose A. Gámez, and Jose M. Puerta. "Scaling Up the Greedy Equivalence Search Algorithm by Constraining the Search Space of Equivalence Classes." In Lecture Notes in Computer Science, 194–205. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22152-1_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Mendoza, Martha, Carlos Cobos, Elizabeth León, Manuel Lozano, Francisco Rodríguez, and Enrique Herrera-Viedma. "A New Memetic Algorithm for Multi-document Summarization Based on CHC Algorithm and Greedy Search." In Lecture Notes in Computer Science, 125–38. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-13647-9_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Gu, Shuyang, Chuangen Gao, and Weili Wu. "A Binary Search Double Greedy Algorithm for Non-monotone DR-submodular Maximization." In Algorithmic Aspects in Information and Management, 3–14. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-16081-3_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Puerta, Jose M., Juan Ángel Aledo, José Antonio Gámez, and Jorge D. Laborda. "Structural Fusion/Aggregation of Bayesian Networks via Greedy Equivalence Search Learning Algorithm." In Lecture Notes in Computer Science, 432–43. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-29765-7_36.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Frühwirth, Rudolf, and Are Strandlie. "Vertex Finding." In Pattern Recognition, Tracking and Vertex Reconstruction in Particle Detectors, 131–41. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-65771-0_7.

Full text
Abstract:
AbstractVertex finding is the search for clusters of tracks that originate at the same point in space. The chapter discusses a variety of methods for finding primary vertices, first in one and then in three dimensions. Details are given on model-based clustering, the EM algorithm and clustering by deterministic annealing in 1D, and greedy clustering, iterated estimators, topological vertex finding, and a vertex finder based on medical imaging in 3D.
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Greedy search algorithm"

1

Heusner, Manuel, Thomas Keller, and Malte Helmert. "Search Progress and Potentially Expanded States in Greedy Best-First Search." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/735.

Full text
Abstract:
A classical result in optimal search shows that A* with an admissible and consistent heuristic expands every state whose f-value is below the optimal solution cost and no state whose f-value is above the optimal solution cost. For satisficing search algorithms, a similarly clear understanding is currently lacking. We examine the search behavior of greedy best-first search (GBFS) in order to make progress towards such an understanding. We introduce the concept of high-water mark benches, which separate the search space into areas that are searched by a GBFS algorithm in sequence. High-water mark benches allow us to exactly determine the set of states that are expanded by at least one GBFS tie-breaking strategy and give us a clearer understanding of search progress.
APA, Harvard, Vancouver, ISO, and other styles
2

Sundman, Dennis, Saikat Chatterjee, and Mikael Skoglund. "FROGS: A serial reversible greedy search algorithm." In 2012 Swedish Communication Technologies Workshop (Swe-CTW). IEEE, 2012. http://dx.doi.org/10.1109/swe-ctw.2012.6376286.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Shi, Chun, Ming Zhao, Chunyu Li, Chunlei Lin, and Zhengjie Deng. "Construct Optimal Binary Search Tree by Using Greedy Algorithm." In 2016 International Conference on Education, Management and Computer Science. Paris, France: Atlantis Press, 2016. http://dx.doi.org/10.2991/icemc-16.2016.205.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Liu, Feng, and Zebang Song. "A Probabilistic Greedy Search Value Iteration Algorithm for POMDP." In 2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE, 2016. http://dx.doi.org/10.1109/ictai.2016.0143.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Wan, Guihong, and Haim Schweitzer. "Heuristic Search for Approximating One Matrix in Terms of Another Matrix." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/221.

Full text
Abstract:
We study the approximation of a target matrix in terms of several selected columns of another matrix, sometimes called "a dictionary". This approximation problem arises in various domains, such as signal processing, computer vision, and machine learning. An optimal column selection algorithm for the special case where the target matrix has only one column is known since the 1970's, but most previously proposed column selection algorithms for the general case are greedy. We propose the first nontrivial optimal algorithm for the general case, using a heuristic search setting similar to the classical A* algorithm. We also propose practical sub-optimal algorithms in a setting similar to the classical Weighted A* algorithm. Experimental results show that our sub-optimal algorithms compare favorably with the current state-of-the-art greedy algorithms. They also provide bounds on how close their solutions are to the optimal solution.
APA, Harvard, Vancouver, ISO, and other styles
6

Liu, Wei, Rui Wang, Kang Yang, Xu Yang, and Tao Zhang. "A greedy strategy based iterative local search algorithm for orienteering problems." In 6th International Workshop on Advanced Algorithms and Control Engineering (IWAACE 2022), edited by Daowen Qiu, Xuexia Ye, and Ning Sun. SPIE, 2022. http://dx.doi.org/10.1117/12.2652866.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Wei, Yingzi, Yulan Hu, and Kanfeng Gu. "Parallel Search Strategies for TSPs Using a Greedy Genetic Algorithm." In Third International Conference on Natural Computation (ICNC 2007). IEEE, 2007. http://dx.doi.org/10.1109/icnc.2007.537.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Chen, Yeou-Jiunn, and Tzu-Meng Haung. "Planar-oriented ripple based greedy search algorithm for vector quantization." In 2012 Computing, Communications and Applications Conference (ComComAp). IEEE, 2012. http://dx.doi.org/10.1109/comcomap.2012.6154804.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Joslin, David, and Justin Collins. "Greedy transformation of evolutionary algorithm search spaces for scheduling problems." In 2007 IEEE Congress on Evolutionary Computation. IEEE, 2007. http://dx.doi.org/10.1109/cec.2007.4424500.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Asadi, Nima, Yin Wang, Ingrid Olson, and Zoran Obradovic. "A Greedy Best-First Search Algorithm for Accurate Functional Brain Mapping." In 2018 Conference on Cognitive Computational Neuroscience. Brentwood, Tennessee, USA: Cognitive Computational Neuroscience, 2018. http://dx.doi.org/10.32470/ccn.2018.1103-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Greedy search algorithm"

1

Kularatne, Dhanushka N., Subhrajit Bhattacharya, and M. Ani Hsieh. Computing Energy Optimal Paths in Time-Varying Flows. Drexel University, 2016. http://dx.doi.org/10.17918/d8b66v.

Full text
Abstract:
Autonomous marine vehicles (AMVs) are typically deployed for long periods of time in the ocean to monitor different physical, chemical, and biological processes. Given their limited energy budgets, it makes sense to consider motion plans that leverage the dynamics of the surrounding flow field so as to minimize energy usage for these vehicles. In this paper, we present two graph search based methods to compute energy optimal paths for AMVs in two-dimensional (2-D) time-varying flows. The novelty of the proposed algorithms lies in a unique discrete graph representation of the 3-D configuration space spanned by the spatio-temporal coordinates. This enables a more efficient traversal through the search space, as opposed to a full search of the spatio-temporal configuration space. Furthermore, the proposed strategy results in solutions that are closer to the global optimal when compared to greedy searches through the spatial coordinates alone. We demonstrate the proposed algorithms by computing optimal energy paths around the Channel Islands in the Santa Barbara bay using time-varying flow field forecasts generated by the Regional Ocean Model System. We verify the accuracy of the computed paths by comparing them with paths computed via an optimal control formulation.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Greedy search algorithm' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography