An improved meet in the middle algorithm for graphs with unit costs

Edward C. Sewell, John A. Pavlik, Sheldon H. Jacobson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper proves several new properties of the Meet in the Middle (MMe) bidirectional heuristic search algorithm when applied to graphs with unit edge costs. Primarily, it is shown that the length of the first path discovered by MMe never exceeds the optimal length by more than one and that if the length of the first path found is odd, then it must be optimal. These properties suggest that the search strategy should emphasize finding a complete path as soon as possible. Computational experiments demonstrate that fully exploiting these new properties can decrease the number of nodes expanded by anywhere from twofold to over tenfold.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th International Symposium on Combinatorial Search, SoCS 2019
EditorsPavel Surynek, William Yeoh
PublisherAAAI Press
Pages145-149
Number of pages5
ISBN (Electronic)9781577358084
StatePublished - 2019
Event12th International Symposium on Combinatorial Search, SoCS 2019 - Napa, United States
Duration: Jul 16 2019Jul 17 2019

Publication series

NameProceedings of the 12th International Symposium on Combinatorial Search, SoCS 2019

Conference

Conference12th International Symposium on Combinatorial Search, SoCS 2019
CountryUnited States
CityNapa
Period7/16/197/17/19

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'An improved meet in the middle algorithm for graphs with unit costs'. Together they form a unique fingerprint.

Cite this