Testing of Heuristic Methods: A Case Study of Greedy Algorithm - Software Engineering Techniques Access content directly
Conference Papers Year : 2011

Testing of Heuristic Methods: A Case Study of Greedy Algorithm

A. C. Barus
  • Function : Author
  • PersonId : 1014445
T. Y. Chen
  • Function : Author
  • PersonId : 1014446
D. Grant
  • Function : Author
  • PersonId : 1014447
F. -C. Kuo
  • Function : Author
  • PersonId : 1014448
M. F. Lau
  • Function : Author
  • PersonId : 1014449

Abstract

Algorithms which seek global optima are computationally expensive. Alternatively, heuristic methods have been proposed to find approximate solutions. Because heuristic algorithms do not always deliver exact solutions it is difficult to verify the computed solutions. Such a problem is known as the oracle problem. In this paper, we propose to apply Metamorphic Testing (MT) in such situations because MT is designed to alleviate the oracle problem and can be automated. We demonstrate the failure detection capability of MT on testing a heuristic method, called the Greedy Algorithm (GA), applied to solve the set covering problem (SCP). The experimental results show that MT is an effective method to test GA.
Fichier principal
Vignette du fichier
978-3-642-22386-0_19_Chapter.pdf (176.71 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01572541 , version 1 (07-08-2017)

Licence

Attribution

Identifiers

Cite

A. C. Barus, T. Y. Chen, D. Grant, F. -C. Kuo, M. F. Lau. Testing of Heuristic Methods: A Case Study of Greedy Algorithm. 3rd Central and East European Conference on Software Engineering Techniques (CEESET), Oct 2008, Brno, Czech Republic. pp.246-260, ⟨10.1007/978-3-642-22386-0_19⟩. ⟨hal-01572541⟩
59 View
463 Download

Altmetric

Share

Gmail Facebook X LinkedIn More