A comparison of multiobjective depth-first algorithms

被引：3
|
作者：
Coego, J. [1 ]
Mandow, L. [1 ]
Perez de la Cruz, J. L. [1 ]
机构：
[1] Univ Malaga, Dpto Lenguajes & Ciencias Comp, E-29071 Malaga, Spain
来源：
JOURNAL OF INTELLIGENT MANUFACTURING | 2013年 / 24卷 / 04期
关键词：
Multiobjective; Linear-space; Search; Iterative-deepening; Branch-and-bound; SHORTEST-PATH PROBLEMS; FRONTIER SEARCH;
D O I：
10.1007/s10845-012-0632-y
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Many real world problems involve several, usually conflicting, objectives. Multiobjective analysis deals with these problems locating trade-offs between different optimal solutions. Regarding graph search problems, several algorithms based on best-first and depth-first approaches have been proposed to return the set of all Pareto optimal solutions. This article presents a detailed comparison between two representatives of multiobjective depth-first algorithms, PIDMOA* and MO-DF-BnB. Both of them extend previous single-objective search algorithms with linear-space requirements to the multiobjective case. Experimental analyses on their time performance over tree-shaped search spaces are presented. The results clarify the fitness of both algorithms to parameters like the number or depth of goal nodes.
引用
收藏
页码：821 / 829
页数：9
相关论文
共 50 条
  • [31] Depth-First: Walking the Web of Chemical Information
    Mayer, Marina
    KEMIJA U INDUSTRIJI-JOURNAL OF CHEMISTS AND CHEMICAL ENGINEERS, 2008, 57 (02): : 70 - 71
  • [32] Depth-first method for attack graph generation
    Information Security Research Center, Harbin Engineering University, Harbin 150001, China
    不详
    Jilin Daxue Xuebao (Gongxueban), 2009, 2 (446-452):
  • [33] DEPTH-FIRST SEARCH AND KURATOWSKI SUBGRAPHS.
    Williamson, S.G.
    1600, (31):
  • [34] Anytime AND/OR depth-first search for combinatorial optimization
    Otten, Lars
    Dechter, Rina
    AI COMMUNICATIONS, 2012, 25 (03) : 211 - 227
  • [35] Comparative Study of Complexities of Breadth-First Search and Depth-First Search Algorithms using Software Complexity Measures
    Akanmu, T. A.
    Olabiyisi, S. O.
    Omidiora, E. O.
    Oyeleye, C. A.
    Mabayoje, M. A.
    Babatunde, A. O.
    WORLD CONGRESS ON ENGINEERING, WCE 2010, VOL I, 2010, : 203 - 208
  • [36] Depth-first search in directed planar graphs, revisited
    Allender, Eric
    Chauhan, Archit
    Datta, Samir
    ACTA INFORMATICA, 2022, 59 (04) : 289 - 319
  • [37] Improving the efficiency of depth-first search by cycle elimination
    Dillenburg, John F., 1600, (45):
  • [38] A depth-first algorithm to reduce graphs in linear time
    Bartha, Miklos
    Kresz, Miklos
    11TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND NUMERIC ALGORITHMS FOR SCIENTIFIC COMPUTING (SYNASC 2009), 2009, : 273 - 281
  • [39] Depth-first search for solving job scheduling problem
    Zhang, Xuanping
    Hang, Shengce
    Xi Tong Gong Cheng Yu Dian Zi Ji Shu/Systems Engineering & Electronics, 1998, 20 (08): : 19 - 22
  • [40] Duplicate Avoidance in Depth-First Search with Applications to Treewidth
    Dow, P. Alex
    Korf, Richard E.
    21ST INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI-09), PROCEEDINGS, 2009, : 480 - 485
12345