Всем известна классическая задача на поиск кратчайшего пути в матрице. Скажем 0 обозначает свободную клетку, 1 - стена, S - старт, F - финиш. Решается поиском в ширину. Мне нужно решить похожую задачу: теперь на карте есть еще и предметы, нужно их все собрать и вернуться назад в точку S(точки F уже нет, ибо не нужна). Нужно найти кратчайший маршрут. Есть такая идея у меня: каждый раз находить ближайший предмет и забирать его. Но я не уверен, что к такому алгоритму нет контртестов, да и доказать корректность нормально не смогу. Кто-то может точно сказать правильный ли этот алгоритм? Или предложить 100% корректный алгоритм.
2 ответа
Легко показать, что предлагаемый жадный алгоритм не обязательно находит оптимальное решение. Контрпример на рисунке:
В данном случае алгоритм построит маршрут S-1-2-3-4-5-S, тогда как оптимальным будет другой маршрут: S-1-2-5-3-4-S.
Вообще, это у вас получается разновидность задачи коммивояжера, смотрите в эту сторону.
Достаточно понятно что это и есть оптимальный алгоритм, быстрее чем кратчайшим путём от каждого объекта вы его не заберёте. А так как на каждом шаге других препятствий нету, так как мы их устранили на предыдущем шаге, то ваш путь к каждому объекту и будет кратчайший. Но тут и волновой алгоритм не нужен, так как препятствия устраняются поэтапно и на каждом этапе по сути препятствий нет.
Это в случае если в задание надо каждый предмет возвращать по отдельности в точку F. Если все вместе, то не оптимальный, смотри пример Yaant-а.