Igor Korolev (korolev) wrote,
Igor Korolev
korolev

Ошибка в алгоритме

Такой диагноз я поставил сегодняшней ночью своей программе. uhryap в пятницу обнаружил, что она ищет явно не оптимальные пути. Причина оказалось в том, что я поставил запрет на бектрейкинг не в том месте, и в результате часть вариантов отпадала. Исправил, обрадовался. Но потом нашлись несколько филологических ошибок, из-за которых число рассматриваемых вариантов было меньше. Исправив это, я неожиданно обнаружил, что прога на большинстве маршрутов зависает. Долго бился, и вот пришёл к выводу, что в программе-то ошибке нет, а виноват алгоритм - эвристический поиск в глубину. Правда, при введении предметно-зависимой эвристики всё нормализуется, однако же тема у меня "Поиск оптимального маршрута в метро", а не "Поиск оптимального маршрута в московском метро". Так что придётся переделывать на эвристический поиск в ширину. И как это моё научное руководство этого не предвидело?
Subscribe

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments