Functional programming and non-distributivity in pathfinding problems
Standard approaches for finding the cost and the path of problems in graphs are based on algorithms relying the fulfilment of certain algebraic properties such associativity and distributivity, for instance the multiplication of matrices. This thesis presents an investigation on the implementation o...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/35183/ |
| _version_ | 1848795022547222528 |
|---|---|
| author | Saenz Carrasco, Juan Carlos |
| author_facet | Saenz Carrasco, Juan Carlos |
| author_sort | Saenz Carrasco, Juan Carlos |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Standard approaches for finding the cost and the path of problems in graphs are based on algorithms relying the fulfilment of certain algebraic properties such associativity and distributivity, for instance the multiplication of matrices. This thesis presents an investigation on the implementation of functional paradigm approach to tackle the problem in the lack of the distributivity property for pathfinding problems in graphs.
The literature on the application, design and implementation, of this approach is scarce. The order in which a bicriteria optimization problem is selected affects the fulfilment of at least one of the properties in the calculation for pathfinding problems.
Two well-known algorithms, Dijkstra’s shortest path and Floyd-Roy-Warshall all-pairs, are adapted and tuned for their application to the problems investigated here, Maximum Capacity (or Bottleneck)-Shortest path and knapsack problem.
The performance of the functional approach is assessed and results are bench- marked by two evaluations methods, eager and lazy. Also the application of the derived functions into the existing algorithms are evaluated in both pure and imperative-functional versions. |
| first_indexed | 2025-11-14T19:25:29Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-35183 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T19:25:29Z |
| publishDate | 2016 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-351832025-02-28T13:31:15Z https://eprints.nottingham.ac.uk/35183/ Functional programming and non-distributivity in pathfinding problems Saenz Carrasco, Juan Carlos Standard approaches for finding the cost and the path of problems in graphs are based on algorithms relying the fulfilment of certain algebraic properties such associativity and distributivity, for instance the multiplication of matrices. This thesis presents an investigation on the implementation of functional paradigm approach to tackle the problem in the lack of the distributivity property for pathfinding problems in graphs. The literature on the application, design and implementation, of this approach is scarce. The order in which a bicriteria optimization problem is selected affects the fulfilment of at least one of the properties in the calculation for pathfinding problems. Two well-known algorithms, Dijkstra’s shortest path and Floyd-Roy-Warshall all-pairs, are adapted and tuned for their application to the problems investigated here, Maximum Capacity (or Bottleneck)-Shortest path and knapsack problem. The performance of the functional approach is assessed and results are bench- marked by two evaluations methods, eager and lazy. Also the application of the derived functions into the existing algorithms are evaluated in both pure and imperative-functional versions. 2016-12-14 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en arr https://eprints.nottingham.ac.uk/35183/1/4159723.pdf Saenz Carrasco, Juan Carlos (2016) Functional programming and non-distributivity in pathfinding problems. MPhil thesis, The University of Nottingham. Functional programming pathfinding problem solution |
| spellingShingle | Functional programming pathfinding problem solution Saenz Carrasco, Juan Carlos Functional programming and non-distributivity in pathfinding problems |
| title | Functional programming and non-distributivity in pathfinding problems |
| title_full | Functional programming and non-distributivity in pathfinding problems |
| title_fullStr | Functional programming and non-distributivity in pathfinding problems |
| title_full_unstemmed | Functional programming and non-distributivity in pathfinding problems |
| title_short | Functional programming and non-distributivity in pathfinding problems |
| title_sort | functional programming and non-distributivity in pathfinding problems |
| topic | Functional programming pathfinding problem solution |
| url | https://eprints.nottingham.ac.uk/35183/ |